Pathfinding: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
Miko Cleova (bicara | kontrib) Dibuat dengan menerjemahkan halaman "Pathfinding" Tag: sangat pendek [ * ] Terjemahan Konten Terjemahan Konten v2 |
Miko Cleova (bicara | kontrib) Tidak ada ringkasan suntingan Tag: kemungkinan perlu pemeriksaan terjemahan VisualEditor |
||
Baris 1:
[[Berkas:Pathfinding_2D_Illustration.svg|ka|jmpl|250x250px| Jalur yang setara antara A dan B dalam lingkungan 2D]]'''Pathfinding''' atau '''pathing''' adalah merencanakan, dengan aplikasi komputer, dari rute terpendek antara dua titik. Ini adalah varian yang lebih praktis dalam [[Algoritma pemecahan labirin|memecahkan labirin]] . Bidang penelitian ini sangat didasarkan pada [[algoritma Dijkstra]] untuk menemukan jalur terpendek pada [[Glosarium teori graf|graf berbobot]] .
Pathfinding erat kaitannya dengan [[Masalah lintasan terpendek|masalah jalur terpendek]], dalam [[teori graf]], yang mengkaji bagaimana mengidentifikasi jalur yang paling memenuhi beberapa kriteria (terpendek, termurah, tercepat, dll) antara dua titik dalam jaringan besar.
== Algoritma ==
Pada intinya, metode pathfinding mencari [[Grafik (struktur data)|graf]] dengan memulai dari satu [[Titik (teori graf)|simpul]] dan menjelajahi simpul yang berdekatan sampai [[Node (Komputer Ilmiah)|simpul]] tujuan tercapai, umumnya dengan maksud untuk menemukan rute termurah. Meskipun metode pencarian grafik seperti pencarian [[Pencarian luas-pertama|luas pertama]] akan menemukan rute jika diberi waktu yang cukup, metode lain, yang "menjelajahi" grafik, akan cenderung mencapai tujuan lebih cepat. Analoginya adalah seseorang berjalan melintasi ruangan; daripada memeriksa setiap kemungkinan rute terlebih dahulu, orang tersebut umumnya akan berjalan ke arah tujuan dan hanya menyimpang dari jalur untuk menghindari halangan, dan membuat penyimpangan sekecil mungkin.
Dua masalah utama pencarian jalur adalah (1) menemukan jalur antara dua node dalam [[Grafik (struktur data)|graf]] ; dan (2) [[Masalah lintasan terpendek|masalah jalur terpendek]] —untuk menemukan [[Masalah lintasan terpendek|jalur terpendek yang optimal]] . Algoritme dasar seperti pencarian [[Pencarian luas-pertama|pertama]] dan [[Pencarian kedalaman pertama|mendalam]] mengatasi masalah pertama dengan [[Pencarian dengan kekerasan|menghabiskan]] semua kemungkinan; mulai dari node yang diberikan, mereka mengulangi semua jalur potensial hingga mencapai node tujuan. Algoritma ini berjalan masuk <math>O(|V|+|E|)</math>, atau waktu linier, di mana V adalah jumlah simpul, dan E adalah jumlah [[Tepi (teori grafik)|sisi]] di antara simpul.
== Referensi ==
| |||