- Saat ini
- Dalam antrean
- Final
- Jalur
- Perkiraan garis lurus
Pencarian A*
Pencarian A* menemukan jalur terpendek dari awal ke tujuan, seperti algoritma Dijkstra, tetapi tahu kira-kira di mana tujuannya. Tiap simpul mendapat perkiraan sisa jarak, yaitu garis lurus ke tujuan, dan pencarian selalu berlanjut dari simpul dengan jarak sejauh ini ditambah perkiraan yang terkecil. Klik simpul untuk memulai darinya, pilih tujuan, lalu jalankan langkah demi langkah untuk melihat pencarian menuju tujuan dan membiarkan seluruh sudut graf tak tersentuh. Tekan Putar untuk melihat pencarian, atau Langkah dan Mundur untuk maju satu langkah demi satu langkah. Geser penggeser langkah untuk melompat ke mana saja. Klik simpul untuk menjadikannya awal; ubah klik ke Tujuan lalu klik simpul lain untuk menjadikannya tujuan. Angka di tiap sisi adalah panjangnya, angka di tiap simpul adalah jaraknya sejauh ini, dan garis putus-putus adalah perkiraan garis lurus untuk sisa jarak. Baris di bawah graf adalah antrean, skor terendah lebih dulu, beserta tiap skor: jarak sejauh ini ditambah perkiraan. Graf baru membuat graf lain; pilih berapa simpul dan sisinya. Saat papan dipilih, tombol panah melangkah, spasi memutar dan menjeda, serta Home dan End melompat ke awal dan akhir.
Cara kerjanya
- Klik simpul untuk menjadikannya awal. Ubah klik ke Tujuan lalu klik simpul lain untuk menjadikannya tujuan.
- Tekan Putar, atau pakai Langkah dan Mundur untuk bergerak satu langkah demi satu langkah. Geser penggeser langkah untuk melompat ke mana saja dalam pencarian.
- Perhatikan skor dalam antrean dan perkiraan garis lurus yang putus-putus. Di akhir, bandingkan simpul yang dibutuhkan A* dengan algoritma Dijkstra.
Cara kerja pencarian A*
Beri awal jarak 0 dan masukkan ke antrean. Tiap simpul dalam antrean punya skor: jaraknya sejauh ini ditambah perkiraan sisa jarak. Ulangi: ambil simpul dengan skor terendah, dan tandai jaraknya final. Jika itu tujuan, berhenti. Jika bukan, untuk tiap tetangga yang belum final, tambahkan panjang sisi ke jarak simpul itu; jika hasilnya lebih pendek dari jarak tetangga sejauh ini, turunkan jaraknya, ingat simpul itu sebagai jalan ke sana, dan masukkan tetangga ke antrean dengan skor barunya.
Mengapa perkiraan tidak boleh terlalu panjang
A* menemukan jalur terpendek selama perkiraan tidak pernah menyatakan tujuan lebih jauh dari kenyataannya: perkiraan yang admissible. Garis lurus adalah salah satunya, karena tidak ada jalan antara dua tempat yang lebih pendek dari garis lurus. Perkiraan yang terlalu panjang bisa membuat A* melewatkan rute terbaik; perkiraan 0 di mana-mana mengubah A* menjadi algoritma Dijkstra, yang aman tetapi mencari ke segala arah. Makin baik perkiraannya, makin sedikit simpul yang dibutuhkan A*. Di aplikasi ini, panjang tiap sisi sama dengan panjang gambarnya, dibulatkan ke atas, jadi garis lurus adalah perkiraan yang aman.
Pertanyaan yang sering diajukan
Apa itu pencarian A*?
Algoritma pencarian jalur yang menemukan jalur terpendek dari awal ke tujuan. Cara kerjanya seperti algoritma Dijkstra, tetapi antreannya diurutkan menurut jarak sejauh ini ditambah perkiraan sisa jarak, sehingga A* menuju tujuan alih-alih menyebar ke segala arah.
Apa itu heuristik admissible?
Perkiraan jarak ke tujuan yang tidak pernah lebih panjang dari jarak terpendek sebenarnya. Dengan perkiraan admissible, A* selalu menemukan jalur terpendek. Jarak garis lurus di peta adalah contoh klasiknya.
Apakah A* lebih cepat dari algoritma Dijkstra?
Biasanya ya, jika Anda butuh jalan ke satu tujuan dan punya perkiraan yang baik: A* memfinalkan lebih sedikit simpul, karena simpul yang jauh dari tujuan mendapat skor tinggi. Dengan perkiraan 0, A* bekerja persis seperti algoritma Dijkstra. Algoritma Dijkstra pilihan yang lebih baik jika Anda butuh jarak ke setiap simpul.
Di mana A* digunakan?
Di gim video untuk menggerakkan karakter mengitari rintangan, di perencana rute, di perencanaan gerak robot, dan di pemecah teka-teki seperti 15-puzzle, tempat perkiraan menghitung seberapa jauh ubin dari tempatnya.
Apakah graf saya dikirim ke mana pun?
Tidak. Graf dibuat dan dicari di browser Anda, dan pengaturan terakhir Anda disimpan di penyimpanan lokal browser ini.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Ke Editor