Solusi sains dan teknologi -- Salah satu kegunaan pertama yang diketahui dari algoritma jalur terpendek di bidang teknologi ada di telepon pada tahun 1950an.Masalahnya adalah dalam mencari alternatif routing jika rute terpendek menjadi terhambat.Dalam algoritma jalur terpendek di dunia saat ini digunakan dalam kebanyakan aplikasi.Anda dapat menemukannya saat menghitung arah mengemudi, perutean perjalanan penerbangan, komunikasi jaringan, linguistik, jejaring sosial - semuanya menggunakan grafik untuk mewakili hubungan antar objek.
Solusi sains dan teknologi -- Dalam posting khusus ini, saya ingin menerapkan struktur data grafik terarah.Karena sifatnya, berat digraf biasanya digunakan dalam pemetaan aplikasi.Saya akan menggunakan grafik ini bersamaan dengan algoritma Dijkstra yang terkenal untuk menemukan jalur terpendek antara dua titik pada peta.Untuk melakukan ini, saya akan memetakan titik persimpangan di bagian kecil peta kota, kemudian m enghitung jarak terpendek antara titik-titik tersebut dengan menggunakan algoritma kami.
Solusi sains dan teknologi -- Akhirnya, saya akan menggunakan petunjuk arah Google Maps pada titik yang samaset untuk memvalidasi percobaan kami.Mari kita mulai dengan refresh cepat pada grafik terarah dan algoritma Dijkstra.V - set simpul, E - set dari tepi Grafik diarahkan dengan berat juga disebut digraph ditimbang adalah grafik yang berisi sekumpulan simpul (atau simpul) yang dihubungkan oleh tepi, di mana tepi berisi informasi tentang arah koneksi dan bobot sambungan itu.Bagaimana algoritma Dijkstra bekerja.
Solusi sains dan teknologi -- Ada banyak artikel bagus dan video yang menjelaskan algoritma yang relatif sederhana ini.Saya pikir video di bawah ini melakukan pekerjaan yang sangat baik dalam menjelaskannya.Seperti yang bisa Anda lihat, algoritma Dijkstra cukup sederhana namun memiliki beberapa kesalahan.Untuk menemukan jalur terpendek antara dua simpul A dan B, algoritma harus mengunjungi semua sub-grafik grafik.
Solusi sains dan teknologi -- Dengan grafik yang besar, ini bisa sangat memakan waktu.Hal yang baik tentang algoritma Dijkstra adalah bahwa sekali seluruh grafik dipindai, kita akan memiliki informasi tentang jalur terpendek tidak hanya dari titik A ke titik B, tetapi juga pada simpul manapun di graph.Cukup membuang-buang waktu, ayo kita kerja.Berikut adalah peta yang saya buat berdasarkan bagian kecil Williamsburg di Brooklyn, NY.
Solusi sains dan teknologi -- Semua lingkaran mewakili simpul grafik dan garis hitam dengan panah diarahkan dengan bobot yang ditetapkan masing-masing.Lingkaran hijau akan menjadi titik tujuan kita.Berdasarkan peta itu, saya membuat sebuah file input yang akan mengisi grafik dengan tepi dan simpul.Kami akan menggunakan file ini sebagai data masukan untuk algoritma kami.
Solusi sains dan teknologi -- Contoh data: 1 4 5.0 4 3 10.0 3 2 5.0 2 3 5.0 2 1 10.0 4 5 2.0 6 5 10.0 6 3 2.5 ...Dari contoh di atas setiap baris memetakan ke metode tanda tangan addEdge (dari, ke, berat) Implementasi grafik akan menggunakan pendekatan adjacency-list untuk menyimpan informasi tentang tepi.Saya mencoba menyederhanakan kode sehingga mudah dibaca, karena ini bukan implementasi yang optimal dan pasti bisa diperbaiki.Kode Untuk percobaan ini, saya membuat file Java berikut yang di-host di akun GitHub saya.
Solusi sains dan teknologi -- WeighedDigraphEdge.java - representasidari tepi grafik WeighedDigraph.java - grafik.DijkstraFind.java - algoritma jalur terpendek termasuk kode uji untuk eksperimen kami.https:@ 2.0, 25 @ 2.0, 27 -> 23 @ 2.0, 25 @ 6.0, 26 @ 4.0, 26 -> 27 @ 4.0, 28 -> 27 @ 2.5, Pengujian: Uji 1menjadi fungsi jarak, batas kecepatan dan kondisi lalu lintas dll.Pengujian hasil google pada waktu yang berbeda bisa menghasilkan hasil yang sama atau bahkan lebih berbeda karena pola lalu lintas berubah sepanjang hari.
Solusi sains dan teknologi -- Artikel terkait Berikut adalah artikel menarik dari Microsoft yang membahas tentang penelitian yang dilakukan untuk memperbaiki algoritma jalur terpendek.Artikel bagus yang menjelaskan algoritma Dijkstra secara lebih rinci.
Tidak ada komentar:
Posting Komentar