Kamis, 11 April 2013

METODE PENCARIAN (ARTIFICIAL INTELEJENCE) DEPTH FIRST SEARCH (DFS)

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:

Poskan Komentar