Nama: BILIT ALATAS

 

Nama: BILIT ALATAS

Kelas: INF A 2018

NIM: 18.01.013.031

Pemateri: Anditya Arifianto

Materi: Blind search (Metode Pencarian Buta)

                 Dalam melakukan pencarian, salah satu cara yang banyak digunakan untuk menggambarkan masalah adalah dengan mencantumkan atau menggambarkan semua kemungkinan keadaan yang ada. Memecahkan masalah berarti bergerak atau berpindah dari satu ruang (node) dari titik awal sampai titik yang dituju (ditentukan), untuk karenanya kita memerlukan satu set operator untuk bergerak dari satu node ke node lainnya. Atribut pencarian:

• Optimalisasi: apakah algoritma dapat menemukan cost path terendah untuk mencapai goal?
• Kelengkapan: apakah algoritma akan menemukan jalur menuju goal/tujuan jika memang ada?

– digunakan untuk mendefinisikan “return failure otherwise”

– jika tidak ada solusi, dan algoritma tidak dapat mendeteksinya (mendeteksi state berulang-ulang(loop)), maka akan menjadi infinite search dan tidak akan ada hasil yang dikembalikan.

• Kompleksitas waktu: waktu yang dibutuhkan untuk melakukan pencarian (contoh: jumlah nodes yang digeneraisasikan selama proses pencarian).
• Kompleksitas waktu: memori yang dibutuhkan.

A.    Definisi

Blind Search atau Uninformed Search secara umum mengartikan bahwa saat proses pencarian kita tidak memiliki clue/hint apakah hasil yang ditemukan lebih baik daripada yang lainnya, sehingga kita tidak mengetahui apakah hasil dari eksplorasi tersebut bermanfaat secara maksimal atau tidak.

Search Space (ruang pencarian) dieksplorasi tanpa memanfaatkan apapuun informasi yang menyangkut pada masalah maka dari itu digunakan istilah blind search atau naive search, dan karena metode ini masih sangat umum maka hasil yang didapat secara instrinsik kurang efisien.

B.     Jenis-jenis Blind (Un-informed) Search

     1.     Breadth First Search (BFS)

          Breadth dapat diartikan dengan luas / lebar, sedangkan first adalah pertama. Penamaan metode ini disesuaikan dengan konsep algoritma secara garis besar yaitu melakukan proses pencarian pada semua node yang berada pada level atau hirarki yang sama terlebih dahulu sebelum melanjutkan proses pencarian pada node di level berikutnya. BFS akan mencari satu per satu node secara melebar dari kiri ke kanan secara berurutan berdasarkan tingkat level nodenya. Jika pada satu level belum ditemukan solusi yang diinginkan, maka pencarian dilanjutkan hingga level berikutnya. Demikian seterusnya hingga ditemukan solusi. Maka, dengan cara seperti ini, BFS menjamin ditemukannya solusi apabila solusinya memang ada. 

Algoritma:

List open, closed, successors={};

Node root_node, current_node;

insert-last(root_node,open)

while not-empty(open);

current_node=remove-first(open);

       insert-last(current_node,closed);

if (goal(current_node)) return current_node;

else

successors=successorsOf(current_node);

for(x in successors)

if(not-in(x,closed)) insert-last(x,open);

endIf

endWhile

  2.   Depth-First Search (DFS)        

        Depth-First Search melakukan eksplorasi dimulai root node (akar) lalu ke cabang pertama (dimulai dari paling kiri) sampai ke kedalaman maksimum , setelah itu baru dilakukan eksplorasi ke cabang lainnya, dan terus dilakukan sampai menemukan state goal.Jika telah mencapai node yang terdalam namun tidak juga ditemukan solusi, maka akan mundur sampai menemukan cabang yang belum dieksplorasi. Tree dilakukan pencarian dengan top-to-bottom, left-to-right.

Depth-First Search dikatakan tidak komplit:

• jika siklus yang disajikan dalam graf lalu DFS melakukan eksplorasi terhadap siklus berulang(tidak ada batas).
• jika tidak terdapat siklus, maka algoritma komplit.
• Efek siklus dapat dibatasi dengan memaksakan kedalaman pencarian yang maksimal(namun algoritma tetap tidak komplit).

    Depth-First Search dikatakan tidak optimal:

• jika solusi pertama yang ditemukan bukan merupakan solusi dengan shortest path (jalur terpendek) menuju goal yang telah ditentukan.

Algoritma dapat diimplementasikan  dengan menggunakan Last In First Out (LIFO) stack atau menggunakan Rekursif (recursion).

Algoritma:

List open, closed, successors={};

Node root_node, current_node;

insert-first(root_node,open)

while not-empty(open);

current_node= remove-first(open);

insert-first (current_node,closed);

if (goal(current_node)) return current_node;

else

successors=successorsOf(current_node);

for(x in successors)

if(not-in(x,closed)) insert-first(x,open);

endIf

endWhile

        3.   Depth Limited Search (DLS)

               Algoritma DLS (Depth Limited Search) adalah salah satu algoritma yang digunakan untuk pencarian jalur. Algoritma ini merupakan variasi dari algoritma DFS (Depth First Search) yang sudah dijelaskan sebelumnya. Jika Algoritma DFS (Depth First Search) melakukan perhitungan (yang dimulai dengan titik terakhir) dengan cara menghabiskan semua tingkatan / kedalaman dari sebuah titik, maka algoritma ini memiliki batasan dimana perhitungan pada sebuah titik hanya dihitung sampai pada kedalaman tertentu. Setelah semua kemungkinan pada kedalaman itu sudah habis, kemudian akan dilanjutkan pada titik berikutnya.

Algoritma:

Function DLS (node,depth)

          if depth = 0 and node is a goal

                        return node

            if depth > 0

                        foreach child of node

                                    found  DLS (child, depth - 1)

                                    if found ≠ null

                                                return found

            return null

        4.    Iterative – Deepening Search (IDS)

  BFS: complete and optimal

•    DFS: low space complexity
•    DLS: the question of “how deep?”
•    IDS: combine BFS with DFS/DLS
•    IDS: complete, optimal, low space complexity
•    Downside: the time complexity is escalated

          5.     Uniform Cost Search (UCS)

                Jika seluruh edges pada graph pencarian tidak memiliki cost / biaya yang sama, maka BFS                     dapat digeneralisasikan menjadi uniform cost search

                Bila pada BFS, pencarian dilakukan dengan melakukan ekspansi node berdasarkan urutan                      kedalaman dari root, maka pada uniform cost search, ekspansi dilakukan berdasarkan cost /                    biaya dari root.

                Pada setiap langkah, ekspansi berikutnya ditentukan berdasarkan cost terendah atau disebut                    sebagai fungsi g(n) dimana g(n) merupakan jumlah biaya edge dari root menuju node n.                          Node-node tsb disimpan menggunakan priority queue.

              6.    Bi- Directional Search (BDS)

Bidirectional Search atau Algoritma pencarian dua arah adalah algoritma pencarian grafik yang menemukan sumber bentuk jalur terkecil ke titik tujuan. Ini menjalankan dua pencarian simultan yaitu :

1. Forward search / titik awal menuju titik tujuan

2. Backward search / target titik ke arah titik sumber