Apa perbedaan antara pencarian grafik dan pencarian pohon?

Jawaban:

178

Dilihat dari jawaban-jawaban yang ada, sepertinya ada banyak kebingungan tentang konsep ini.

Masalahnya Selalu Grafik

Perbedaan antara pencarian pohon dan pencarian grafik tidak didasarkan pada fakta apakah grafik masalah adalah grafik pohon atau grafik umum. Itu selalu diasumsikan Anda berurusan dengan grafik umum. Perbedaannya terletak pada pola traversal yang digunakan untuk menelusuri grafik, yang dapat berbentuk grafik atau pohon.

Jika Anda berurusan dengan masalah berbentuk pohon , kedua varian algoritme memberikan hasil yang setara. Jadi, Anda dapat memilih varian pencarian pohon yang lebih sederhana.

Perbedaan Antara Pencarian Grafik dan Pohon

Algoritme pencarian grafik dasar Anda terlihat seperti berikut ini. Dengan simpul awal start, tepi terarah sebagai successorsdan goalspesifikasi yang digunakan dalam kondisi loop. openmenyimpan node dalam memori, yang saat ini sedang dipertimbangkan, daftar terbuka . Perhatikan bahwa kode pseudo berikut tidak benar di setiap aspek (2).

Pencarian Pohon

open <- []
next <- start

while next is not goal {
    add all successors of next to open
    next <- select one node from open
    remove next from open
}

return next

Bergantung pada cara Anda menerapkan select from open, Anda mendapatkan varian algoritme penelusuran yang berbeda, seperti penelusuran mendalam-pertama (DFS) (pilih elemen terbaru), penelusuran luas pertama (BFS) (pilih elemen terlama) atau penelusuran biaya seragam (pilih elemen dengan biaya jalur terendah ), penelusuran bintang-A yang populer dengan memilih simpul dengan biaya terendah plus nilai heuristik , dan seterusnya.

Algoritma yang disebutkan di atas sebenarnya disebut pencarian pohon . Ini akan mengunjungi keadaan grafik masalah yang mendasarinya beberapa kali, jika ada beberapa jalur yang diarahkan untuk itu rooting di keadaan awal. Bahkan dimungkinkan untuk mengunjungi suatu keadaan dalam jumlah tak terbatas jika berada pada loop terarah. Tetapi setiap kunjungan sesuai dengan simpul berbeda di pohon yang dihasilkan oleh algoritme penelusuran kami. Inefisiensi yang tampak ini kadang-kadang diinginkan, seperti yang dijelaskan kemudian.

Pencarian Grafik

Seperti yang kita lihat, penelusuran pohon dapat mengunjungi suatu keadaan beberapa kali. Dan karena itu ia akan menjelajahi "sub pohon" yang ditemukan setelah keadaan ini beberapa kali, yang bisa mahal. Pencarian grafik memperbaiki ini dengan melacak semua status yang dikunjungi dalam daftar tertutup . Jika penerus yang baru ditemukan nextsudah diketahui, itu tidak akan dimasukkan ke dalam daftar terbuka:

open <- []
closed <- []
next <- start

while next is not goal {
    add next to closed
    add all successors of next to open, which are not in closed 
    remove next from open
    next <- select from open
}

return next

Perbandingan

Kami melihat bahwa pencarian grafik membutuhkan lebih banyak memori, karena melacak semua status yang dikunjungi. Ini dapat dikompensasikan dengan daftar terbuka yang lebih kecil, yang menghasilkan peningkatan efisiensi pencarian.

Solusi optimal

Beberapa metode penerapan selectdapat menjamin untuk menghasilkan solusi yang optimal - yaitu jalur terpendek atau jalur dengan biaya minimal (untuk grafik dengan biaya yang melekat pada tepinya). Ini pada dasarnya berlaku setiap kali node diperluas untuk meningkatkan biaya, atau ketika biaya adalah konstanta positif bukan nol. Algoritme umum yang mengimplementasikan jenis pemilihan ini adalah pencarian biaya seragam , atau jika biaya langkah identik, BFS atau IDDFS . IDDFS menghindari konsumsi memori agresif BFS dan umumnya direkomendasikan untuk pencarian tanpa informasi (alias brute force) ketika ukuran langkah konstan.

SEBUAH*

Juga algoritma pencarian A * tree (sangat populer) memberikan solusi optimal bila digunakan dengan heuristik yang dapat diterima . Algoritme pencarian grafik A * , bagaimanapun, hanya membuat jaminan ini ketika digunakan dengan heuristik yang konsisten (atau "monotonik") (kondisi yang lebih kuat daripada penerimaan).

(2) Cacat pseudo-code

Untuk mempermudah, kode yang disajikan tidak:

  • menangani pencarian yang gagal, yaitu hanya bekerja jika solusi dapat ditemukan
ziggystar
sumber
1
Jawaban yang bagus! Bisakah Anda menjelaskan apa yang Anda maksud dengan masalah berbentuk pohon ? Selain itu, bagaimana Anda mengusulkan penyimpanan jalur yang ditempuh oleh algoritme untuk mencapai tujuan dibandingkan dengan traversal lengkap?
Brian
1
@ Masalah berbentuk pohon Brian berarti grafik yang Anda cari adalah pohon. Dan untuk pertanyaan kedua Anda: ini tergantung pada masalahnya. Salah satu kemungkinan hanyalah menyimpan jalur ke sebuah node bersama dengan setiap node yang diperluas, jika memungkinkan.
ziggystar
5
Lebih formal untuk mengatakan bahwa 'status tunggal' dapat dikunjungi beberapa kali oleh pencarian pohon, dan BUKAN sebuah node. Karena setiap node di pohon pencarian sesuai dengan satu jalur di sepanjang grafik ruang negara dan dikunjungi paling banyak sekali oleh pencarian pohon. (Meskipun ini tidak berlaku untuk Pencarian Mendalam Iteratif yang melintasi pohon dengan batas kedalaman yang meningkat, tetapi dalam kasus itu juga dalam setiap iterasi setiap node dikunjungi hanya sekali)
Nader Ghanbari
1
@NaderhadjiGhanbari Apakah lebih memadai stateatau nodelebih untuk simpul dari grafik masalah yang mendasarinya , berbeda dengan grafik traversal, bergantung pada konteksnya. Tetapi menggunakan stateuntuk simpul grafik masalah dan nodeuntuk grafik traversal pasti dapat meningkatkan kejelasan jawabannya. Saya akan mencoba menulis ulang segera. Terima kasih.
ziggystar
TL; DR: pencarian grafik menggunakan struktur data tertutup sedangkan pencarian pohon tidak.
shinzou
7

Pohon adalah kasus khusus dari grafik, jadi apa pun yang berfungsi untuk grafik umum dapat digunakan untuk pohon. Pohon adalah grafik di mana terdapat tepat satu jalur di antara setiap pasangan node. Ini menyiratkan bahwa ia tidak berisi siklus apa pun, seperti yang dinyatakan dalam jawaban sebelumnya, tetapi grafik berarah tanpa siklus (DAG, grafik asiklik terarah) belum tentu berupa pohon.

Namun, jika Anda mengetahui bahwa grafik Anda memiliki beberapa batasan, misalnya grafik itu adalah pohon atau DAG, Anda biasanya dapat menemukan beberapa algoritma pencarian yang lebih efisien daripada grafik yang tidak dibatasi. Misalnya, mungkin tidak masuk akal untuk menggunakan A *, atau padanan non-heuristiknya "Algoritma Dijkstra", pada pohon (di mana hanya ada satu jalur untuk dipilih, yang dapat Anda temukan dengan DFS atau BFS) atau pada DAG (di mana jalur optimal dapat ditemukan dengan mempertimbangkan simpul dalam urutan yang diperoleh dengan penyortiran topologis).

Adapun graf terarah vs tak terarah merupakan kasus khusus graf berarah, yaitu kasus yang mengikuti aturan “jika ada sisi (tautan, transisi) dari u ke v ada juga sisi dari v ke u .

Pembaruan : Perhatikan bahwa jika yang Anda pedulikan adalah pola traversal pencarian daripada struktur grafik itu sendiri, ini bukanlah jawabannya. Lihat, misalnya, jawaban @ ziggystar.

njlarsson.dll
sumber
Hm, konteks pertanyaannya tidak sepenuhnya jelas bagi saya, tetapi melihatnya lagi setelah melihat jawaban Anda, @ziggystar, saya merasa bahwa penyebutan A * dan AI menunjukkan bahwa Anda mungkin benar, dan jawaban saya diluar konteks. Saya mengartikan "pencarian pohon" sebagai "mencari pohon". Bukan "mencari grafik umum menggunakan pola traversal berbentuk pohon", seperti yang tersirat dalam jawaban Anda.
njlarsson
@njlarsson Saya telah menyertakan pengungkapan ulang Anda dalam jawaban saya. Ini bagus untuk klarifikasi.
ziggystar
Menambahkan catatan ini dalam jawaban. Saya curiga bahwa jawaban saya adalah jawaban yang tepat untuk banyak orang yang menemukan jalan mereka ke sini melalui Google, dll., Meskipun mungkin di luar konteks yang dicari oleh Rayhanur Rahman.
njlarsson
Saya telah melihat banyak siswa mengalami kesulitan dalam mempelajari algoritme penelusuran dan jawaban Anda menyesatkan mereka.
Nader Ghanbari
1
Jawabannya adalah tentang algoritma pencarian juga, tetapi memang benar bahwa bukan itu yang ditanyakan oleh poster. Lihat "Pembaruan" pada jawaban - Saya menyadari pada Maret 2014 bahwa saya salah memahami pertanyaan tersebut. Alasan saya tidak menghapus jawabannya adalah karena mungkin masih berguna bagi seseorang yang datang ke sini melalui penelusuran.
njlarsson
3

Satu-satunya perbedaan antara grafik dan pohon adalah siklus . Grafik mungkin berisi siklus, pohon tidak bisa. Jadi, saat Anda akan menerapkan algoritme penelusuran di pohon, Anda tidak perlu mempertimbangkan keberadaan siklus, tetapi saat bekerja dengan grafik arbitrer, Anda harus mempertimbangkannya. Jika Anda tidak menangani siklusnya, algoritme pada akhirnya dapat jatuh dalam loop tak terbatas atau rekursi tak berujung.

Hal lain yang perlu dipikirkan adalah properti arah dari grafik yang Anda hadapi. Dalam kebanyakan kasus kita berurusan dengan pohon yang merepresentasikan hubungan induk-anak di setiap sisi. Sebuah DAG (grafik asiklik terarah) juga menunjukkan karakteristik yang serupa. Tetapi grafik dua arah berbeda. Setiap tepi dalam grafik dua arah mewakili dua tetangga. Jadi pendekatan algoritmik harus sedikit berbeda untuk kedua jenis grafik ini.

0605002
sumber
3
Untuk menambahkan ini, jika Anda benar-benar memiliki pohon, Anda tidak perlu melakukan deteksi duplikat di A *. Anda masih memerlukan cara untuk mengekstrak jalur terakhir, jadi Anda mungkin masih memiliki daftar tertutup.
Nathan S.
Dalam istilah normal, pohon adalah graf berarah dengan paling banyak satu jalur di antara dua simpul mana pun. Artinya, ada dua perbedaan antara grafik dan pohon: Berarah, dan keunikan jalur. Algoritme yang bekerja pada DAG tidak perlu memeriksa siklus, dan algoritme yang bekerja pada pohon tidak perlu memeriksa duplikat.
besok
1
Terminologi bervariasi, tetapi pohon tidak selalu dianggap terarah. Untuk pohon berakar , yaitu ketika satu simpul ditetapkan sebagai akar, terdapat arah tersirat, tetapi pohon tidak harus berakar. Juga, grafik umum dapat diarahkan atau tidak diarahkan. Selain itu, jika Anda hanya menuntut paling banyak satu jalur antara dua simpul, Anda juga menyertakan hutan . Sebuah pohon biasanya didefinisikan sebagai grafik yang terhubung, yaitu harus terdapat tepat satu jalur.
njlarsson
Jawaban ini mendapatkan lebih banyak perbedaan antara pohon dan grafik dalam teori grafik, tetapi tidak benar-benar dengan jenis algoritma pencarian yang berbeda.
mlibby
1

GRAFIK VS POHON

  • Grafik memiliki siklus
  • Pohon tidak memiliki siklus "Misalnya bayangkan pohon apa pun di kepala Anda, cabang tidak memiliki koneksi langsung ke akar, tetapi cabang memiliki koneksi ke cabang lain, ke atas"

Namun dalam kasus AI Graph-search vs Tree-search

Pencarian grafik memiliki properti yang baik setiap kali algoritme menjelajahi node baru dan menandainya sebagai telah dikunjungi, "Terlepas dari algoritme yang digunakan", algoritme biasanya menjelajahi semua node lain yang dapat dijangkau dari node saat ini.

Sebagai contoh perhatikan graf berikut dengan 3 simpul AB dan C, dan perhatikan tepi-tepi berikut

AB, BC, dan CA, Ada siklus dari C ke A,

Dan ketika melakukan DFS mulai dari A, A akan menghasilkan status baru B, B akan menghasilkan status baru C, tetapi ketika C dieksplorasi, algoritme akan mencoba menghasilkan status baru A tetapi A sudah dikunjungi sehingga akan diabaikan. Keren!

Tapi bagaimana dengan pohon? Algoritma pohon baik tidak menandai node yang dikunjungi sebagai telah dikunjungi, tetapi pohon tidak memiliki siklus, bagaimana itu akan masuk dalam loop tak terbatas?

Pertimbangkan Pohon ini dengan 3 simpul dan pertimbangkan tepi berikut

A - B - C berakar di A, ke bawah. Dan anggap saja kita menggunakan algoritma DFS

A akan menghasilkan status baru B, B akan menghasilkan dua status A & C, karena Pohon tidak memiliki "Tandai node yang dikunjungi jika dieksplorasi" sehingga mungkin algoritme DFS akan menjelajahi A lagi, sehingga menghasilkan status baru B, sehingga kita berada dalam lingkaran tak terbatas.

Tapi pernahkah Anda memperhatikan sesuatu, kami sedang mengerjakan edge yang tidak diarahkan, yaitu ada hubungan antara AB dan BA. tentu saja ini bukan sebuah siklus, karena siklus tersebut mengimplikasikan bahwa simpul harus> = 3 dan semua simpul berbeda kecuali simpul pertama dan simpul terakhir.

ST A-> B-> A-> B-> A ini bukan siklus karena melanggar properti bersepeda> = 3. Tapi memang A-> B-> C-> A adalah siklus> = 3 node berbeda Dicentang, node pertama dan terakhir sama Dicentang.

Sekali lagi pertimbangkan tepi pohon, A-> B-> C-> B-> A, tentu saja ini bukan siklus, karena ada dua B, yang berarti tidak semua node berbeda.

Terakhir, Anda dapat menerapkan algoritme penelusuran pohon, untuk mencegah menjelajahi node yang sama dua kali. Tapi itu memiliki konsekuensi.

Mohamed Horani
sumber
Jawaban ini membingungkan karena tampaknya mencampurkan situasi di mana masalah berupa pohon atau grafik dengan apakah algoritme penelusuran itu sendiri menggunakan pohon atau grafik selama penelusuran.
mlibby
1

Dengan kata sederhana, pohon tidak mengandung siklus dan dimana grafik dapat. Jadi, saat melakukan penelusuran, kita harus menghindari siklus dalam grafik agar tidak mengalami loop tak terbatas.

Aspek lain adalah pohon biasanya memiliki semacam pengurutan topologis atau properti seperti pohon pencarian biner yang membuat pencarian jadi lebih cepat dan mudah dibandingkan dengan grafik.

Madhi
sumber