Algoritma untuk menentukan rute tercepat?

17

Katakanlah kita pergi dari 1 ke 5. Rute terpendek adalah 1-4-3-5 (total: 60 km).

Grafik

Kita dapat menggunakan algoritma Dijkstra untuk melakukan itu.

Sekarang masalahnya adalah, rute terpendek tidak selalu yang tercepat, karena kemacetan lalu lintas atau faktor lainnya.

Sebagai contoh:

  • 1-2 diketahui sering mengalami kemacetan, sehingga harus dihindari.
  • Tiba-tiba kecelakaan mobil terjadi sepanjang 4-3, sehingga harus dihindari juga.
  • Dll ...

Jadi mungkin kita bisa mempercepat pada rute 1-4-5, karena tidak ada kemacetan / kecelakaan, sehingga akan tiba di 5 lebih cepat.

Nah itu ide umum, dan saya belum memikirkan detail lebih lanjut.

Apakah ada algoritma untuk menyelesaikan masalah ini?

graph dijkstra anta40
sumber
3
Apakah ini pekerjaan rumah? Bukankah ini hanya en.wikipedia.org/wiki/Travelling_salesman_problem untuk melintasi grafik berbobot?
StuperUser
9
@StuperUser: Tidak, TSP adalah sirkuit dari semua node tanpa duplikat. Dalam contoh kasus, misalnya, tidak perlu mengenai simpul 2.
David Thornley
2
@ DavidThornley, begitu. Jadi Dijkstra adalah untuk rute terpendek pada grafik berbobot? Dan TSP adalah traversal mengunjungi setiap node?
StuperUser
1
@Stuper: Lintasan terpendek, ya
BlueRaja - Danny Pflughoeft
2
@StuperUser, hanya FYI, TSP adalah masalah NP-Complete yang kuat tanpa solusi yang dapat dijalankan dalam waktu polinomial. ... Jadi sekarang kamu tahu.
riwalk

Jawaban:

5

Karena Anda membawa kemacetan ke dalam gambar, berhati-hatilah agar Anda tidak ditangkap oleh Paradox Braess . Jika semua orang memilih jalur optimal, itu menghasilkan waktu perjalanan yang lebih buruk untuk semua orang.

Michael Brown
sumber
49

Ya: Dijkstra

Dijkstra bekerja dengan baik untuk situasi ini.
Anda hanya menggunakan waktu daripada jarak sebagai bobot masing-masing busur.

Martin York
sumber
9
Biasanya 'jarak' di Dijkstra akan ditimbang untuk semua hal, biaya / tol, preferensi jalan bebas hambatan, batas kecepatan - menggunakan jarak hanya merupakan pendekatan sederhana yang sederhana. Inilah yang membuat algoritme begitu pintar
Martin Beckett
6
Meskipun Dijsktra akan melakukannya, saya biasanya akan memilih A * untuk pekerjaan penelusuran jalan yang serius; heuristik akan banyak membantu.
Mircea Chirea
6
Tautan: Algoritma pencarian * . Ini merupakan perpanjangan dari metode Dijkstra.
mgkrebbs
Selama ada heuristik yang berlaku, A * akan lebih unggul dari Dijkstra (dalam hal kinerja).
bummzack
Heuristik yang dapat diterima akan agak sulit untuk ditemukan di sini mengingat kita mempertimbangkan banyak faktor (seperti kemacetan lalu lintas).
pwny
16

Iya. Algoritma Dijkstra akan menyelesaikan masalah ini.

Masalah dalam kasus Anda adalah bahwa Anda secara otomatis menganggap jalur terpendek sama dengan jarak yang ditempuh, padahal sebenarnya itu lebih tepat untuk BIAYA mengambil rute.

Jika satu jalur memiliki hambatan maka BIAYA harus lebih tinggi, dan algoritme masih berlaku.

maple_shaft
sumber
Ya maaf jika saya tidak menggunakan kata-kata yang tepat. Yang saya maksud adalah 'rute yang paling nyaman' (biaya minimum)
anta40
11

Anda seharusnya hanya bisa mengganti jarak Anda dengan waktu antara node dan menyelesaikannya dengan cara yang sama.

DKnight
sumber
10

Dijkstra

Seperti yang dikatakan sebelumnya, itu tidak hanya digunakan untuk jarak terdekat. Saya percaya animasi ini memberikan pemahaman yang baik tentang "kekuatan" (karena tidak ada kata yang lebih baik) dari Dijkstra:

Dijkstra

Dinamis
sumber