Yessi Nurul Fadziah
1300024
C1 2013
Bi-directional Search
Metode pencarian ini dilakukan dari dua arah pada setiap
iterasi: dari titik asal (start) dan dari titik tujuan. Ketika dua arah
pencarian membangkitkan titik yang sama, maka solusi telah ditemukan, dengan
cara menggabungkan kedua jalur yang bertemu. Ada beberapa masalah sebelum
memustuskan untuk menngunakan strategi Bi-directional Search, yaitu:
- Bagaimana kalau terdapat beberapa titik tujuan yang berbeda?
- Terdapat perhitungan yang tidak efisien untuk selalu mengecek apakah titik baru yang dibangkitkan sudah pernah dibangkitkan oleh pencarian dari arah yang berlawanan.
- Bagaimana menentukan strategi pencarian untuk kedua arah tersebut? Misalnya dari arah sumber dan dari arah tujuan digunakan BFS
Keuntungan :
- Kecepatan. Jumlah waktu yang dibutuhkan oleh dua pencarian (maju dan mundur) jauh lebih kecil dari O (bd) kompleksitas
- Membutuhkan sedikit memori.
- Implementation dari algoritma pencarian bidirectional sulit karena logika tambahan harus disertakan untuk memutuskan mana pencarian pohon untuk memperpanjang pada setiap langkah.
- Salah satunya seharusnya mengetahui tujuan di awal.
- Algoritma terlalu efisien untuk menemukan persimpangan dua pohon pencarian
- Tidak selalu mungkin untuk mencari mundur untuk mengetahui wilayah yang berkemungkinan
Kekurangan
Depth Limited Search
Pencarian menggunakan DFS akan berlanjut terus sampai kedalaman paling
terakhir dari tree. Permasalahan yang muncul pada DFS adalah ketika proses
pencarian tersebut menemui infinite state space. Hal ini bisa diatasi dengan
menginisiasikan batas depth pada level tertentu semenjak awal pencarian.
Sehingga node pada level depth tersebut akan diperlakukan seolah-olah mereka
tidak memiliki successor.
Mengatasi kelemahan DFS (tidak complete) dengan membatasi
kedalaman maksimum dari suatu jalur solusi. Tetapi harus diketahui atau ada
batasan dari sistem tentang level maksimum. Jika batasan kedalaman terlalu
kecil, DLS tidak complete.
Perbandingan Strategi Pencarian BDS dan DLS
Keterangan:
b
: faktor pencabangan (the branching
factor)
d
: kedalaman solusi (the depth of
solution)
l
: batasan kedalaman (the depth limit)
