Apa perbedaan antara pencarian grafik dan versi pencarian pohon terkait dengan pencarian DFS, A * dalam kecerdasan buatan ?
sumber
Apa perbedaan antara pencarian grafik dan versi pencarian pohon terkait dengan pencarian DFS, A * dalam kecerdasan buatan ?
Dilihat dari jawaban-jawaban yang ada, sepertinya ada banyak kebingungan tentang konsep ini.
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.
Algoritme pencarian grafik dasar Anda terlihat seperti berikut ini. Dengan simpul awal start
, tepi terarah sebagai successors
dan goal
spesifikasi yang digunakan dalam kondisi loop. open
menyimpan node dalam memori, yang saat ini sedang dipertimbangkan, daftar terbuka . Perhatikan bahwa kode pseudo berikut tidak benar di setiap aspek (2).
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.
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 next
sudah 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
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.
Beberapa metode penerapan select
dapat 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.
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).
Untuk mempermudah, kode yang disajikan tidak:
state
ataunode
lebih untuk simpul dari grafik masalah yang mendasarinya , berbeda dengan grafik traversal, bergantung pada konteksnya. Tetapi menggunakanstate
untuk simpul grafik masalah dannode
untuk grafik traversal pasti dapat meningkatkan kejelasan jawabannya. Saya akan mencoba menulis ulang segera. Terima kasih.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.
sumber
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.
sumber
GRAFIK VS POHON
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.
sumber
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.
sumber