Depth-first
search (DFS)
==>Depth-first
search (DFS) adalah proses searching sistematis buta yang melakukan
ekpansi sebuah path (jalur) menuju penyelesaian masalah sebelum
melakukan ekplorasi terhadap path yang lain.
==>Proses
searching mengikuti sebuah path tunggal sampai menemukan goal atau dead
end. Apabila proses searching menemukan dead-end, DFS akan melakukan
penelusuran balik ke node terakhir untuk melihat apakah node tersebut
memiliki path cabang yang belum dieksplorasi
DFS dapat juga digunakan untuk mengumpulkan sampel dari node
grafik. Namun, DFS tidak lengkap, mirip dengan BFS tidak lengkap, bias terhadap
node dari tingkat tinggi.
pencarian depth-first mulai A, dengan asumsi bahwa tepi kiri
dalam grafik yang ditunjukkan dipilih sebelum bagian samping kanan, dan dengan
asumsi pencarian mengingat node dikunjungi sebelumnya dan tidak akan mengulangi
mereka (karena ini adalah grafik kecil), akan mengunjungi node dalam urutan
sebagai berikut: A, B, D, F, E, C, G. Tepi dilalui dalam bentuk pencarian pohon
Trémaux, struktur dengan aplikasi penting dalam teori graf.
Melakukan pencarian yang sama tanpa mengingat sebelumnya
mengunjungi hasil node pada kelenjar mengunjungi di urutan A, B, D, F, E, A, B,
D, F, E, dll selamanya, terperangkap dalam A, B, D, F , E siklus dan tidak
pernah mencapai C atau G.
Output Depth-first search (DFS)
Empat jenis tepi didefinisikan oleh pohon rentang
Penjelasan nyaman dari pencarian pertama kedalaman grafik
adalah dalam hal pohon rentang dari simpul dicapai selama pencarian.
Berdasarkan pohon rentang, tepi grafik asli dapat dibagi menjadi tiga kelas:
tepi ke depan, titik mana dari node dari pohon ke salah satu keturunannya, tepi
belakang, titik mana dari node ke salah satu nenek moyangnya, dan lintas tepi,
yang melakukan keduanya. Kadang-kadang pohon tepi, tepi yang termasuk ke dalam
spanning tree sendiri, diklasifikasikan secara terpisah dari tepi ke depan.
Jika grafik asli diarahkan maka semua ujungnya adalah pohon tepi atau tepi
kembali.
Hal ini juga memungkinkan untuk menggunakan pencarian
mendalam-pertama yang linear memesan simpul dari grafik asli (atau pohon). Ada
tiga cara yang umum untuk melakukan hal ini:
• preordering adalah daftar simpul dalam urutan bahwa mereka
pertama kali dikunjungi oleh algoritma pencarian mendalam-pertama. Ini adalah
cara yang kompak dan alami menggambarkan kemajuan pencarian, seperti yang
dilakukan sebelumnya dalam artikel ini. Sebuah preordering dari sebuah pohon
ekspresi adalah ekspresi dalam notasi Polandia.
• postordering adalah daftar simpul dalam urutan yang mereka
terakhir dikunjungi oleh algoritma. Sebuah postordering dari sebuah pohon
ekspresi adalah ekspresi dalam notasi Polandia terbalik.
• postordering adalah daftar simpul dalam urutan yang mereka
terakhir dikunjungi oleh algoritma. Sebuah postordering dari sebuah pohon
ekspresi adalah ekspresi dalam notasi Polandia terbalik....
mulai di simpul A, salah satu mengunjungi node secara
berurutan, untuk menghasilkan daftar baik ABDBACA, atau ACDCABA (tergantung
pada apakah algoritma memilih untuk mengunjungi B atau C pertama). Perhatikan
bahwa ulangi kunjungan dalam bentuk mundur ke node, untuk memeriksa apakah itu
masih belum dikunjungi tetangga, termasuk di sini (bahkan jika itu ditemukan
memiliki tidak ada). Jadi preorderings mungkin adalah ABDC dan ACDB (order by
kejadian paling kiri node dalam daftar di atas), sedangkan postorderings
sebaliknya kemungkinan yang ACBD dan ABCD (order by kejadian paling kanan node
dalam daftar di atas). Postordering terbalik menghasilkan penyortiran topologi
dari setiap grafik asiklik diarahkan. Urutan ini juga berguna dalam analisis
kontrol aliran seperti yang sering merupakan linearisasi alami dari aliran
kontrol. Grafik di atas mungkin mewakili aliran kontrol dalam sebuah fragmen
kode seperti
aplikasi
Mirip dengan kedalaman-pertama pencarian yang digunakan
dalam menghasilkan labirin Acak algoritma.
Algoritma yang menggunakan depth-first pencarian sebagai
sebuah blok bangunan meliputi:
Mencari komponen yang terhubung.
Sortasi topologi.
Mencari 2 - (edge atau vertex)-komponen terhubung.
Mencari 3 - (edge atau vertex)-komponen terhubung.
Menemukan jembatan grafik.
Membangkitkan kata dalam rangka untuk merencanakan Batas Set
Grup.
Mencari komponen terhubung kuat.
Planarity pengujian [4] [5]
Memecahkan teka-teki dengan hanya satu solusi, seperti
labirin. (DFS dapat disesuaikan untuk menemukan semua solusi untuk labirin
dengan hanya termasuk node di jalan saat di set dikunjungi.)
Generasi Maze dapat menggunakan pencarian depth-first acak.
Menemukan biconnectivity dalam grafik.
Depth-limited
saerch (DLS)
Di komputer mendalam terbatas pencarian sains adalah suatu
algoritma untuk mengeksplorasi simpul dari grafik. Ini merupakan modifikasi
dari depth-first search dan digunakan misalnya dalam algoritma iteratif
memperdalam kedalaman-pertama pencarian.
umum
Seperti pencarian depth-first normal, kedalaman terbatas
pencarian sebuah pencarian uninformed. Ia bekerja persis seperti depth-first
search, tapi menghindari kekurangan mengenai kelengkapan dengan memberlakukan
batas maksimum pada kedalaman pencarian. Bahkan jika pencarian masih bisa
memperluas simpul melampaui kedalaman itu, itu tidak akan melakukannya dan
dengan demikian tidak akan mengikuti jalan jauh dalam atau terjebak dalam
siklus. Oleh karena itu kedalaman terbatas pencari akan mencari solusi jika
dalam batas kedalaman, yang menjamin setidaknya kelengkapan pada semua grafik.
Algoritma (informal)
General
1. Menentukan titik mana harus memulai pencarian dan
menetapkan kedalaman maksimum pencarian
2. Periksa apakah titik saat ini adalah negara tujuan
• Jika tidak: Melakukan apa-apa
• Jika ya: kembali
3. Periksa apakah titik saat berada dalam kedalaman maksimum
pencarian
• Jika tidak: Melakukan apa-apa
• Jika ya:
1. Memperluas titik dan menyimpan semua penerusnya dalam tumpukan
2. Hubungi DLS rekursif untuk semua simpul dari stack dan
kembali ke Langkah 2
ruang kompleksitas
Karena kedalaman terbatas pencarian internal menggunakan
depth-first search, kompleksitas ruang adalah setara dengan normal
kedalaman-pertama pencarian.
waktu kompleksitas
Karena kedalaman terbatas pencarian internal menggunakan
depth-first-search, kompleksitas waktu adalah setara dengan normal
kedalaman-pertama pencarian, dan O () di mana singkatan jumlah simpul dan
jumlah tepi dalam grafik dieksplorasi. Perhatikan bahwa kedalaman terbatas
pencarian tidak mengeksplorasi seluruh grafik, tetapi hanya bagian yang
terletak dalam terikat ditentukan.
kelengkapan
Meskipun kedalaman terbatas pencarian tidak bisa mengikuti
jalan panjang tak terhingga, juga tidak dapat terjebak dalam siklus, secara
umum algoritma ini tidak lengkap karena tidak menemukan solusi yang terletak di
luar kedalaman pencarian tertentu. Tetapi jika kedalaman pencarian maksimum
dipilih untuk menjadi lebih besar dari kedalaman solusi algoritma menjadi
lengkap.
optimalitas
Kedalaman terbatas pencarian tidak optimal. Ia masih
memiliki masalah depth-first pencarian yang pertama kali mengeksplorasi salah
satu jalan sampai akhir, sehingga mungkin menemukan solusi yang lebih mahal
daripada beberapa solusi di jalan lain.
Depth-limited
saerch (DLS)
Di komputer mendalam terbatas pencarian sains adalah suatu
algoritma untuk mengeksplorasi simpul dari grafik. Ini merupakan modifikasi
dari depth-first search dan digunakan misalnya dalam algoritma iteratif
memperdalam kedalaman-pertama pencarian.
umum
Seperti pencarian depth-first normal, kedalaman terbatas
pencarian sebuah pencarian uninformed. Ia bekerja persis seperti depth-first
search, tapi menghindari kekurangan mengenai kelengkapan dengan memberlakukan
batas maksimum pada kedalaman pencarian. Bahkan jika pencarian masih bisa
memperluas simpul melampaui kedalaman itu, itu tidak akan melakukannya dan
dengan demikian tidak akan mengikuti jalan jauh dalam atau terjebak dalam
siklus. Oleh karena itu kedalaman terbatas pencari akan mencari solusi jika
dalam batas kedalaman, yang menjamin setidaknya kelengkapan pada semua grafik.
Algoritma (informal)
General
1. Menentukan titik mana harus memulai pencarian dan
menetapkan kedalaman maksimum pencarian
2. Periksa apakah titik saat ini adalah negara tujuan
• Jika tidak: Melakukan apa-apa
• Jika ya: kembali
3. Periksa apakah titik saat berada dalam kedalaman maksimum
pencarian
• Jika tidak: Melakukan apa-apa
• Jika ya:
1. Memperluas titik dan menyimpan semua penerusnya dalam tumpukan
2. Hubungi DLS rekursif untuk semua simpul dari stack dan
kembali ke Langkah 2
ruang kompleksitas
Karena kedalaman terbatas pencarian internal menggunakan
depth-first search, kompleksitas ruang adalah setara dengan normal
kedalaman-pertama pencarian.
waktu kompleksitas
Karena kedalaman terbatas pencarian internal menggunakan
depth-first-search, kompleksitas waktu adalah setara dengan normal
kedalaman-pertama pencarian, dan O () di mana singkatan jumlah simpul dan
jumlah tepi dalam grafik dieksplorasi. Perhatikan bahwa kedalaman terbatas
pencarian tidak mengeksplorasi seluruh grafik, tetapi hanya bagian yang
terletak dalam terikat ditentukan.
kelengkapan
Meskipun kedalaman terbatas pencarian tidak bisa mengikuti
jalan panjang tak terhingga, juga tidak dapat terjebak dalam siklus, secara
umum algoritma ini tidak lengkap karena tidak menemukan solusi yang terletak di
luar kedalaman pencarian tertentu. Tetapi jika kedalaman pencarian maksimum
dipilih untuk menjadi lebih besar dari kedalaman solusi algoritma menjadi
lengkap.
optimalitas
Kedalaman terbatas pencarian tidak optimal. Ia masih
memiliki masalah depth-first pencarian yang pertama kali mengeksplorasi salah
satu jalan sampai akhir, sehingga mungkin menemukan solusi yang lebih mahal
daripada beberapa solusi di jalan lain.
Tidak ada komentar:
Posting Komentar