Solusi sains dan teknologi -- Aplikasi seperti Google Maps atau sistem navigasi menghitung jalur terpendek atau jalur tercepat sepanjang waktu.Ada algoritma yang sangat efisien untuk menyelesaikan tugas ini sejak tahun 50an.Jalur yang paling andal dapat ditemukan melalui metode yang sama - menggunakan sedikit trik.Beberapa algoritma ditemukan pada tahun 50an dan 60an untuk memecahkan masalah jalur terpendek.
Solusi sains dan teknologi -- Di antaranya adalah algoritma Dijkstra, algoritma Bellman-Ford dan beberapa tahun kemudian algoritma pencarian A *.Meskipun algoritma ini dioptimalkan untuk aplikasi yang sedikit berbeda, pokoknya semuanya memecahkan masalah yang sama: mereka secara efisien menghitung jalur terpendek di jaringan jalan, atau (terlihat dari sudut pandang ilmuwan komputer) dalam grafik dengan simpul dan ujungnya.Distorsi Reality yang Bermanfaat Jalur tercepat dapat dihitung dengan menggunakan algoritma jalur terpendek.Untuk mela kukan ini, bukan panjang (misalnya dalam kilometer) seseorang hanya menggunakan waktu (misalnya dalam jam dan menit) yang mungkin dibutuhkan untuk setiap jalan (tepi).
Solusi sains dan teknologi -- Jadi, satu simply harus membagi panjang (s) dengan kecepatan yang diharapkan (v) untuk setiap tepi pada grafik.Gambar 1 menunjukkan contoh grafik transformasi dimana waktu yang dibutuhkan untuk setiap jalan diperhitungkan.Kami berasumsi bahwa Anda bisa menyetir 100 kmply harus membagi panjang (s) dengan kecepatan yang diharapkan (v) untuk setiap tepi pada grafik.Gambar 1 menunjukkan contoh grafik transformasi dimana waktu yang dibutuhkan untuk setiap jalan diperhitungkan.
Solusi sains dan teknologi -- Kami berasumsi bahwa Anda bisa menyetir 100 kmply harus membagi panjang (s) dengan kecepatan yang diharapkan (v) untuk setiap tepi pada grafik.Gambar 1 menunjukkan contoh grafik transformasi dimana waktu yang dibutuhkan untuk setiap jalan diperhit ungkan.Kami berasumsi bahwa Anda bisa menyetir 100 kmMasalah jalan yang andal untuk masalah jalur terpendek bekerja.Cukup keren, ey.
Solusi sains dan teknologi -- Saya tidak datang dengan trik ini sendiri.Telah dikenal sejak setidaknya 1975 (lihat [1] dan [2]).Meskipun, pada masa itu, ilustrasi mungkin tidak sebaik.🙂 Mengapa Bekerja Untuk menunjukkan mengapa mengubah grafik dengan logaritma negatif memiliki efek yang berguna yang dijelaskan di atas, kita harus mempertimbangkan masalah kita secara matematis.
Solusi sains dan teknologi -- Berikut ini adalah rumusan matematis dari jalur yang paling andal dan konversi selangkah demi selangkah, dengan setiap langkahnya dijelaskan: (1) (1) Istilah pertama mengatakan bahwa kita mencari jalan yang untuk produk probabilitasnya pi memiliki nilai maksimum.Fungsi argmax menyatakan bahwa kita tidak tertarik pada nilai keandalan maksimum (dalam hal ini kita akan menggunakan max saja), namun pada jalur p dimana dikatakan reliabilitas maksimal tercapai.Perbedaan yang halus namun penting.(2) (2) Karena logaritma adalah fungsi monoton yang meningkat, kita dapat aHal itu tanpa mengubah solusi dari masalah maksimalisasi.
Solusi sains dan teknologi -- (3) (3) Logaritma produk sama dengan jumlah logaritma.Ini adalah properti logaritma yang sangat praktis.Tetap bertahan.Kita hampir sampai.
Solusi sains dan teknologi -- (4) (4) Alih-alih mencari jumlah maksimum, kita bisa memberi tanda minus sebelum jumlah dan mencari minimum mulai sekarang.(5) (5) Alih-alih meniadakan keseluruhan jumlah, kita bisa saja meniadakan semua summands.Apa istilah yang dihasilkannya diungkapkan.Kita sekarang mencari jalan yang jumlah semua panjang tepi (masing-masing dengan -log pi) minimal, yang sekali lagi merupakan masalah jalur terpendek.
Solusi sains dan teknologi -- Kesimpulan Masalah menemukan jalur yang paling andal dapat diatasi dengan menggunakan algoritma jalur terpendek.Seseorang hanya harus menerapkan logaritma negatif terhadap probabilitas masing-masing tepi pada grafik dan menggunakan hasilnya sebagai panjang untuk algoritma jalur terpendek.Referensi CHRISTOFIDES, Nikos.Teori Grafik - Pendekatan Algoritma.
Solusi sains dan teknologi -- New York: Academic PressInc, 1975.ROOSTA, Mohammad.Routing melalui jaringan dengan keandalan maksimal.Jurnal Analisis dan Aplikasi Matematika, 1982, 88.
Solusi sains dan teknologi -- Jg., Nr.2, S.341-347.M Roosta, J.Math.Anal.Appl., 88 (1982), hal 341-347 Related Posts Juggling with Trees - Cara Meletakkan Informasi Hirarkis dengan Tepat Melacak di Pembibitan - Cara Memecahkan "Legespiel" .
Solusi sains dan teknologi --
Tidak ada komentar:
Posting Komentar