Algoritma Bellman-Ford - Mengapa edge dapat di-update?

The algoritma Bellman-Ford menentukan jalur terpendek dari sumber untuk semua simpul lainnya. Awalnya jarak antara dan semua simpul lainnya diatur ke . Kemudian jalur terpendek dari ke setiap titik dihitung; ini berlaku untuk iterasi . Pertanyaan saya adalah: $s$ $s$ $\infty$ $s$ $|V|-1$

Mengapa harus ada iterasi? $|V|-1$
Apakah penting jika saya memeriksa tepinya dalam urutan yang berbeda?
Katakanlah, jika saya pertama memeriksa tepi 1,2,3, tetapi kemudian pada iterasi kedua saya periksa 2,3,1.

MIT Prof. Eric mengatakan urutannya tidak masalah, tetapi ini membingungkan saya: bukankah algoritme akan memperbarui node berdasarkan edge jika nilainya bergantung pada edge tetapi diperbarui setelah ? $x_2$ $x_1$ $x_1$ $x_2$

algorithms shortest-path pengguna1675999
sumber

Implementasi mana yang Anda pertimbangkan? Pemrograman yang dinamis tidak memiliki masalah dengan ketertiban, jelas; bagi yang lain mungkin tidak sepele.

Raphael

Jawaban:

Pertimbangkan jalur terpendek dari ke , . Jalur ini paling banyak terdiri dari tepi, karena pengulangan simpul pada jalur terpendek selalu merupakan ide yang buruk (atau setidaknya ada jalur terpendek yang tidak mengulangi simpul), jika kita tidak memiliki siklus bobot negatif . $s$ $t$ $s, v_1, v_2, \dots, v_k, t$ $|V|-1$

Di babak satu, kita tahu bahwa tepi akan rileks, sehingga perkiraan jarak untuk akan benar setelah putaran ini. Perhatikan bahwa kami tidak tahu apa pada saat ini, tetapi karena kami telah merilekskan semua sisi, kami juga harus merilekskan ini. Di babak dua, kita santai di beberapa titik. Kami masih tidak tahu apa itu atau , tetapi kami tahu perkiraan jarak mereka benar. $(s, v_1)$ $v_1$ $v_1$ $(v_1, v_2)$ $v_1$ $v_2$

Mengulangi ini, setelah beberapa putaran , kita santai , setelah itu estimasi jarak untuk benar. Kami tidak tahu apa sampai seluruh algoritma selesai, tetapi kami tahu bahwa itu akan terjadi di beberapa titik (dengan asumsi tidak ada siklus bobot negatif). $k+1$ $(v_k, t)$ $t$ $k$

Jadi, pengamatan penting adalah bahwa setelah putaran , simpul ke- dari jalur terpendek harus memiliki estimasi jarak yang ditetapkan ke nilai yang benar. Karena jalur paling banyak Panjang tepi, putaran cukup untuk menemukan jalur terpendek ini. Jika a $i$ $i$ $|V|-1$ $|V|-1$ Putaran ke-5 masih mengubah sesuatu, maka sesuatu yang aneh sedang terjadi: semua jalur harus sudah 'diselesaikan' ke nilai akhir mereka, jadi kita harus memiliki situasi di mana ada siklus bobot negatif. $|V|$

Alex ten Brink
sumber

Saya punya sedikit keraguan di sini. Saya percaya | v | -1 adalah jumlah kasus terburuk dari putaran setelah mana jalur terpendek dihitung dari s ke t. Asumsikan kita memiliki simpul s, v1, v2..vn, t.Jika tepi dipilih dalam urutan ini katakanlah (s, v1), (v1, v2) .. (vn, t), maka dalam satu iterasi itu sendiri kita akan memiliki jalur terpendek dari s ke t.Ini hanya untuk memahami dan istilah praktis kita tidak tahu urutan tepi dipilih dan karenanya | v | -1 ronde. Apakah saya benar?

whokares

@ whokares: ya, Anda mungkin beruntung dan menemukan jalur terpendek di babak pertama. Anda tidak tahu pasti sampai babak terakhir bahwa nilai yang Anda temukan benar-benar adalah jalur terpendek, tetapi mungkin saja itu. Algoritma Dijkstra pada dasarnya 'menyebabkan' hal ini terjadi: jika semua sisi memiliki bobot non-negatif, maka antrian prioritas yang digunakan dalam algoritma Dijkstra 'memprediksi' urutan di mana Anda harus bersantai tepi sehingga Anda menemukan semua jalur terpendek dalam putaran pertama relaksasi Anda.

Alex ten Brink

Terima kasih atas pembaruannya. Saya mengerti. Dalam salah satu materi, disebutkan sebagai <br> Slide 6: Pilihan relaksasi yang buruk dapat menyebabkan banyak relaksasi secara eksponensial: <br> Slide 8: “Smart” urutan relaksasi tepi <br>

whokares

Terlepas dari urutan tepi di setiap iterasi, jalur terpendek akan dihitung dalam | v | -1 iterasi kan? Mengapa dia mengatakan eksponensial. Maksudnya jika kita memilih urutan yang sama untuk semua iterasi yang biasanya kita lakukan, kode relaksasi akan dipanggil tetapi memperbarui label untuk titik mungkin terjadi hanya beberapa kali lebih sedikit karena urutan sehingga menghemat prosesor waktu

whokares

@ whokares: algoritma pertama yang mereka sajikan (yang dapat memiliki waktu berjalan eksponensial) tidak mengendurkan semua sisi dalam satu putaran, tetapi sebaliknya menemukan beberapa sisi yang operasi relaksasi akan mengubah sesuatu, dan mengendurkan tepi ini. Jika Anda terus melakukan ini dan tidak ada siklus berat negatif, maka akhirnya tidak ada ujung yang akan membantu Anda lagi dan Anda berhenti. Namun, karena Anda tidak memiliki putaran dan tidak mengatur pemesanan di tepi mana untuk bersantai berikutnya, Anda mungkin akhirnya melakukan jumlah relaksasi yang eksponensial. Algoritma ditingkatkan yang mereka sajikan adalah Bellman-Ford, yang memang memiliki putaran.

Alex ten Brink

Jalan terpanjang bisa tanpa siklus apa pun |V|. Kita mulai dengan sumber, jadi kita sudah memiliki jalur dengan panjang 1, jadi kita perlu |V| - 1lebih banyak simpul untuk mendapatkan jalur terpanjang.

Urutan tidak penting karena setiap pesanan akan mempertahankan yang invarian: setelah n iterasi, nilai untuk setiap node kurang dari atau sama dengan biaya jalur biaya minimum dari ske node yang mengandung paling banyak ntepi.

Jika, pada awal iterasi, biayanya tepat hingga nnode, maka pada akhir iterasinya benar hingga n+1node. Penataan ulang dapat menyebabkan beberapa node memiliki biaya yang lebih rendah sebelum mereka biasanya diperbarui, tetapi mereka akhirnya akan diperbarui pula.

fgb
sumber

Saya tidak tahu apakah itu hanya saya, atau saya tidak bisa memvisualisasikan fakta ini dengan mudah. Bagi saya, saya masih berpikir mungkin ada beberapa node yang belum memperbarui dalam iterasi V-1.

user1675999

Tidak, Anda memiliki | E | = | V | -1 tepi saat Anda memiliki | V | node terhubung oleh jalur sederhana tanpa siklus. Dan Anda memiliki | V | -1 iterasi, hapus respons Anda karena itu salah.

Sam

@ Sam Siapakah Anda dan apa yang Anda katakan ada hubungannya dengan jawabannya?

fgb