Pencarian grafik: Lebar-pertama vs kedalaman-pertama

Saat mencari grafik, ada dua algoritma mudah: breadth-first dan depth-first (Biasanya dilakukan dengan menambahkan semua node grafik adjactent ke antrian (breadth-first) atau stack (depth-first)).

Sekarang, apakah ada kelebihan satu sama lain?

Yang bisa saya pikirkan:

• Jika Anda berharap data Anda berada cukup jauh di dalam grafik, kedalaman-pertama mungkin menemukannya lebih awal, karena Anda akan turun ke bagian yang lebih dalam dari grafik dengan sangat cepat.
• Sebaliknya, jika Anda mengharapkan data Anda cukup jauh di grafik, luas pertama mungkin memberikan hasil lebih awal.

Adakah sesuatu yang saya lewatkan atau sebagian besar karena pilihan pribadi?

Saya ingin mengutip jawaban dari Stack Overflow oleh hstoerr yang mencakup masalah dengan baik:

Itu sangat tergantung pada struktur pohon pencarian dan jumlah dan lokasi solusi .
Jika Anda tahu solusinya tidak jauh dari akar pohon, pencarian pertama luasnya (BFS) mungkin lebih baik. Jika pohon sangat dalam dan solusinya jarang, pencarian pertama kedalaman (DFS) mungkin berakar selamanya, tetapi BFS bisa lebih cepat. Jika pohonnya sangat lebar, BFS mungkin membutuhkan terlalu banyak memori, sehingga mungkin sama sekali tidak praktis. Jika solusinya sering tetapi terletak jauh di dalam pohon, BFS mungkin tidak praktis. Jika pohon pencarian sangat dalam, Anda harus membatasi kedalaman pencarian untuk pencarian pertama kedalaman (DFS), misalnya (misalnya dengan pendalaman berulang).

Tapi ini hanya aturan praktis; Anda mungkin perlu bereksperimen.

Rafał Dowgird juga berkomentar:

Beberapa algoritma bergantung pada properti DFS (atau BFS) tertentu untuk bekerja. Sebagai contoh algoritma Hopcroft dan Tarjan untuk menemukan komponen yang terhubung 2 mengambil keuntungan dari fakta bahwa setiap node yang sudah dikunjungi ditemui oleh DFS berada di jalur dari root ke node yang saat ini dieksplorasi.

Satu hal yang penting dalam dunia multicore kami: BFS jauh lebih mudah diparalelkan. Ini wajar secara intuitif (mengirimkan utas untuk setiap anak) dan dapat dibuktikan juga demikian. Jadi, jika Anda memiliki skenario di mana Anda dapat menggunakan paralelisme, maka BFS adalah cara untuk pergi.

(Saya menjadikan ini sebagai wiki komunitas. Silakan diedit.)

Jika

• $b$ adalah faktor percabangan
• $d$ adalah kedalaman di mana solusinya
• d ≤ $h$ adalah ketinggian pohon (jadi, )$d\le h$

Kemudian

• DFS mengambil waktu dan ruangO ( h $O(b^h)$$O(h)$
• BFS mengambil waktu dan ruangO ( b d$O(b^d)$$O(b^d)$
• IDDFS membutuhkan waktu dan ruangO ( d $O(b^d)$$O(d)$

Alasan memilih

• DFS
  • tetap harus melihat seluruh pohon
  • Anda tahu , tingkat jawabannya$d$
  • tidak peduli apakah jawabannya paling dekat dengan root
• BFS
  • jawabannya dekat dengan root
  • Anda menginginkan jawaban yang paling dekat dengan root
  • memiliki beberapa core / prosesor
• IDDFS
  • Anda ingin BFS, tidak memiliki cukup memori, tetapi agak lambat dapat diterima

IDDFS = pencarian mendalam untuk pencarian mendalam-pertama

Satu skenario (selain menemukan jalur terpendek, yang telah disebutkan) di mana Anda mungkin harus memilih satu dari yang lain untuk mendapatkan program yang benar adalah grafik tak terbatas:

Jika kita mempertimbangkan misalnya pohon di mana setiap simpul memiliki jumlah anak yang terbatas, tetapi ketinggian pohon itu tidak terbatas, DFS mungkin tidak akan pernah menemukan simpul yang Anda cari - itu hanya akan terus mengunjungi anak pertama dari setiap simpul itu melihat, jadi jika yang Anda cari bukan anak pertama dari orang tuanya, ia tidak akan pernah sampai di sana. Namun BFS dijamin menemukannya dalam waktu yang terbatas.

Demikian pula jika kita mempertimbangkan pohon di mana setiap simpul memiliki jumlah anak yang tak terbatas, tetapi pohon memiliki ketinggian yang terbatas, BFS mungkin tidak berakhir. Itu hanya akan mengunjungi anak-anak dari simpul root dan jika simpul yang Anda cari adalah anak dari beberapa simpul lain, itu tidak akan tercapai. Dalam hal ini DFS dijamin menemukannya dalam waktu yang terbatas.

Breadth-first dan depth-first tentu memiliki perilaku kasus terburuk yang sama (simpul yang diinginkan adalah yang terakhir ditemukan). Saya menduga ini juga berlaku untuk case-averave jika Anda tidak memiliki informasi tentang grafik Anda.

Satu bonus bagus dari pencarian pertama-lebarnya adalah bahwa ia menemukan jalur terpendek (dalam arti tepi paling sedikit) yang mungkin atau mungkin tidak menarik.

Jika peringkat simpul rata-rata Anda (jumlah tetangga) tinggi relatif terhadap jumlah node (yaitu grafik padat), lebar-pertama akan memiliki antrian besar sedangkan kedalaman-pertama akan memiliki tumpukan kecil. Dalam grafik yang jarang, situasinya terbalik. Oleh karena itu, jika memori merupakan faktor pembatas, bentuk grafik yang ada mungkin harus menginformasikan pilihan strategi pencarian Anda.

Semua hal di atas benar, tetapi perlu dicatat bahwa BFS dan DFS membuat pohon mereka sendiri, berdasarkan urutan yang mereka gunakan untuk melintasi pohon. Masing-masing pohon memiliki properti sendiri yang dapat berguna dalam beberapa masalah.

Misalnya, semua tepi dalam grafik asli yang tidak ada di pohon BFS adalah tepi silang; tepi yang berada di antara dua cabang pohon BFS. Semua tepi dalam grafik asli yang tidak ada di pohon DFS adalah tepi belakang; tepi yang menghubungkan dua simpul di cabang pohon DFS. Properti seperti itu dapat berguna untuk masalah seperti pewarnaan khusus, dll.

Pohon DFS dan BFS keduanya memiliki sifat uniknya sendiri yang dapat memberi Anda informasi lebih berguna tentang grafik. Misalnya dengan DFS tunggal Anda dapat melakukan hal berikut:

• Temukan jembatan dan titik artikulasi (untuk grafik tidak berarah)
• Deteksi siklus
• Temukan komponen yang sangat terhubung (Algoritma Tarjan)

Dengan BFS, Anda dapat menemukan jalur terpendek antara simpul sumber dan simpul lainnya dalam grafik.

Bab Algoritma Grafik di CLRS meringkas properti ini dari DFS dan BFS dengan sangat baik.

Saya pikir akan menarik untuk menulis keduanya dengan cara yang hanya dengan mengganti beberapa baris kode akan memberikan Anda satu algoritma atau yang lain, sehingga Anda akan melihat bahwa dillema Anda tidak begitu kuat seperti pada awalnya. .

Saya pribadi menyukai interpretasi BFS sebagai membanjiri lanskap: daerah dataran rendah akan dibanjiri terlebih dahulu, dan baru kemudian daerah dataran tinggi akan mengikuti. Jika Anda membayangkan ketinggian lanskap sebagai isoline seperti yang kita lihat dalam buku-buku geografi, mudah untuk melihat bahwa BFS mengisi semua area di bawah isoline yang sama pada saat yang sama, seperti halnya dengan fisika. Dengan demikian, menafsirkan ketinggian sebagai jarak atau biaya skala memberikan ide algoritma yang cukup intuitif.

Dengan pemikiran ini, Anda dapat dengan mudah menyesuaikan ide di balik pencarian pertama yang luas untuk menemukan pohon rentang minimum dengan mudah, jalur terpendek, dan juga banyak algoritma minimisasi lainnya.

Saya belum melihat interpretasi intuitif dari DFS (hanya yang standar tentang labirin, tetapi tidak sekuat BFS dan banjir), jadi bagi saya tampaknya BFS tampaknya berkorelasi lebih baik dengan fenomena fisik seperti dijelaskan di atas, sementara DFS berkorelasi lebih baik dengan pilihan dillema pada sistem rasional (yaitu orang atau komputer yang memutuskan untuk melakukan permainan catur atau keluar dari labirin).

Jadi, bagi saya perbedaan antara kebohongan di mana fenomena alam paling cocok dengan model propagasi mereka (transversing) dalam kehidupan nyata.