Motivasi

Suatu hari, saya bepergian keliling kota dengan transportasi umum dan saya membuat masalah grafik yang menarik yang memodelkan masalah menemukan koneksi terpendek antara dua tempat.

Kita semua tahu "masalah jalur terpendek" klasik: Diberikan grafik berarah dengan panjang dan dua simpul , temukan jalur terpendek antara dan (yaitu, jalur yang meminimalkan panjang total tepi). Dengan asumsi panjang sisi non-negatif, ada berbagai algoritma dan masalahnya mudah.w e ∈ R + 0$G=(V,E)$s , t ∈ V s $w_e\in\mathbb{R}_0^+,\,e\in E$$s,t\in V$$s$$t$

Ini adalah model yang bagus untuk case yang sedang kita jalani, misalnya. Verteks adalah persimpangan jalan di jaringan jalan kami dan setiap sisi memiliki panjang tetap - dalam meter, misalnya. Kemungkinan interpretasi lain dari bobot adalah waktu yang diperlukan untuk beralih dari satu simpul ke simpul lainnya. Inilah interpretasi yang menarik minat saya sekarang.$w_e$

Masalah

Saya sekarang ingin memodelkan situasi berikut. Saya ingin melakukan perjalanan dari titik A ke titik B di kota melalui transportasi umum dan meminimalkan waktu . Jaringan transportasi umum dapat dengan mudah dimodelkan sebagai grafik terarah seperti yang Anda harapkan. Bagian yang menarik adalah bobot tepi (waktu model itu) - angkutan umum (bus, misalnya) hanya menyisakan dalam interval tertentu, yang berbeda untuk setiap pemberhentian (titik dalam grafik). Dengan kata lain - bobot edge tidak konstan, mereka berubah tergantung pada waktu kita ingin menggunakan edge.

Bagaimana model situasi ini: Kami memiliki grafik diarahkan dan tepi-berat fungsi yang mengambil waktu sebagai argumennya dan mengembalikan waktu yang diperlukan untuk menggunakan tepi di jalur kita. Sebagai contoh, jika bus dari vertex ke vertex daun pada dan dibutuhkan waktu dan kami tiba di vertex pada , maka adalah bobot tepi. Jelas, .w : E × R + 0 → R + 0 v u t = 10 5 v t = 8 w ( v u , 8 ) = 7 w ( v u , 10 ) = $G=(V,E)$ $w\colon E\times \mathbb{R}_0^+\rightarrow\mathbb{R}_0^+$$v$$u$$t=10$$5$$v$$t=8$$w(vu,8)=7$$w(vu,10)=5$

Agak sulit untuk mendefinisikan bobot total lintasan, tetapi kita bisa melakukannya secara rekursif. Biarkan menjadi jalur yang diarahkan. Jika maka . Kalau tidak, , di mana adalah sub-path tanpa . Ini adalah definisi alami yang sesuai dengan situasi dunia nyata. k = 1 w ( P ) = 0 w ( P ) = w ( P ′ ) + w ( v k - 1 v k , w ( P ′ ) ) P ′ P v $P=v_1v_2\ldots v_{k-1} v_k$$k=1$$w(P)=0$$w(P)=w(P')+w(v_{k-1}v_k,w(P'))$$P'$$P$$v_k$

Kita sekarang dapat mempelajari masalah dengan berbagai asumsi pada fungsi . Asumsi alami adalah yang memodelkan "menunggu waktu ".w ( e , t ) ≤ w ( e , t + Δ ) + Δ  untuk semua  e ∈ E , Δ ≥ 0 , $w$

Jika fungsi "berperilaku baik" dimungkinkan untuk mengurangi masalah ini ke masalah jalur terpendek klasik. Tapi kita bisa bertanya apa yang terjadi ketika fungsi berat menjadi liar. Dan bagaimana jika kita menjatuhkan asumsi menunggu?

Pertanyaan

Pertanyaan saya adalah sebagai berikut.

• Apakah masalah ini pernah ditanyakan sebelumnya? Sepertinya agak alami.
• Apakah ada penelitian tentang itu? Tampak bagi saya bahwa ada berbagai sub-masalah yang harus ditanyakan dan dipelajari - terutama mengenai sifat-sifat fungsi berat.
• Bisakah kita mengurangi masalah ini (mungkin dengan beberapa asumsi) menjadi masalah jalur terpendek klasik?

Ini dikenal sebagai masalah "jalur terpendek bergantung pada waktu". Memang penelitian telah dilakukan untuk masalah ini; lihat misalnya kertas klasik karya Orda dan Rom, dan kertas SODA baru-baru ini yang membuktikan bahwa ketika fungsi bobot masing-masing sisi adalah ukuran polinomial-sejajar-linier, maka jalur terpendek antara dua titik tetap berubah kali.$n^{\Theta(\log n)}$

Algoritma Dijkstra memang dapat digunakan untuk masalah ini, ketika kebijakan menunggu diberlakukan, yaitu, menunggu di sebuah simpul jika itu mengurangi waktu tiba terakhir. Tanpa kebijakan penantian, situasinya jauh lebih liar: jalur terpendek mungkin tidak sederhana, jalan setapak dari jalur terpendek mungkin bukan jalan terpendek antara dua titik akhir dari jalur bawah tanah, jalur yang melintasi sejumlah tepi yang tak terbatas mungkin memiliki waktu tiba yang terbatas, dll. Lihat lagi kertas karya Orda dan Rom untuk diskusi lebih lanjut.

Apakah Anda mengetahui masalah "jalur nondecreasing terpendek"? Itu didefinisikan untuk memodelkan situasi seperti ini. Meskipun sedikit kurang ekspresif dibandingkan dengan formulasi Anda, ada beberapa opsi cepat untuk itu.

Jika Anda berasumsi bahwa waktunya adalah integral (yang masuk akal dalam kasus angkutan umum), Anda dapat membuat jaringan yang diperluas waktu, mirip dengan yang disarankan oleh Ford-Fulkerson untuk aliran maksimum dari waktu ke waktu (atau aliran tercepat) dan temukan jalur terpendek dalam grafik ini sebagai gantinya.