Metode Pencarian dalam Kecerdasan Buatan – Berbagai algoritma untuk pencarian (search algorithm) yang ada berbeda satu dengan yang lain dalam hal pengembangan kumpulan node untuk mencapai goal state. Perbedaan ini terutama dalam hal cara dan urutan pengembangan node, dan sangat berpengaruh pada kinerja masing-masing algoritma.
Menurut Mahafi dan Hemawan (2013:20), terdapat empat kriteria yang menjadi ukuran algoritma pencarian, yaitu: (1) completeness – apakah algoritma pasti dapat menemukan solusi, (2) time complexity – berapa lama waktu yang dibutuhkan untuk menemukan sebuah solusi, (3) space complexity – berapa memori atau resource yang diperlukan untuk melakukan pencarian, dan (4) optimality – apakah algoritma tersebut dapat menemukan solusi yang terbaik jika terdapat beberapa solusi yang berbeda.
Terdapat banyak metode pencarian yang telah diusulkan. Semua metode yang ada dapat dibedakan ke dalam dua jenis pencarian (Suyanto, 2011:15) yaitu: (1) pencarian buta/tanpa informasi (blind atau uninformed search), dan (2) pencarian heuristik/dengan informasi (heuristic atau informed search). Setiap metode mempunyai karakteristik yang berbeda-beda dengan kelebihan dan kekurangannya masing-masing.
Konsep Bidirectional Search
Bidirectional search merupakan pencarian dua arah dengan algoritma pencarian grafik yang menemukan jalur terpendek dari node sumber ke node tujuan dalam grafik diarahkan.
Menurut Sugaya dan Visu (2014:4) bidirectional search akan mencari jalur terpendek dari kedua arah, satu ke depan dari state awal dan satu mundur dari akhir serta akan berhenti ketika dua pencarian ini bertemu di tengah. Hal ini pula yang diungkapkan oleh Russel dan Norvig (2003:79-80) bahwa bidirectional search adalah pencarian dua arah dengan menjalankan dua simultan pencarian yaitu satu kedepan dari keadaan awal dan yang lain mundur dari tujuan serta berhenti ketika dua pencarian bertemu di tengah.
Bidirectional search bekerja lebih cepat dalam banyak kasus dan menemukan jalan terpendek. Contoh, dalam model yang disederhanakan dari kompleksitas masalah pencarian dimana kedua pencarian tersebut memperluas tree dengan percabangan faktor b dan jarak dari sumber tujuan adalah d. Kompleksitas dari dua pencarian ini direpresentasikan sebagai O(bd/2) (in Big O notation) dan jumlah waktu yang dibutuhkan untuk mencari dua node ini kurang dari O(bd) kompleksitas yang dihasilkan dari satu pencarian dari awal ke tujuan.
Dalam bidirectional search terdapat tiga buah arah pencarian yaitu: (1) forward (maju), (2) backward (mundur), dan (3) bidirectional (dua arah). Bagi pencarian dua arah ini terdapat beberapa langkah dalam penerapannya yaitu: (1) pada pencarian dua arah, node-node di perluas dari status awal ke tujuan secara bersamaan (simultan), (2) pada setiap tahap dicek apakah node-node yang dijumpai sudah dibangkitkan oleh yang lain, (3) jika iya, maka gabungan jalur adalah solusinya, (4) dua pencarian dapat bekerja paralel: satu dari asal ke tujuan, satu dari tujuan ke awal, dan (5) saat keduanya bertemu, diperoleh jalur yang baik.
Cara Kerja Bidirectional Search
Motivasi dalam bidirectional search ialah bd/2 + bd/2 lebih kecil daripada bd, atau pada Gambar 3. area dengan dua lingkaran kecil lebih kecil daripada area satu lingkaran besar yang berpusat di awal hingga mencapai tujuan.
Pencarian dua arah diimplementasikan dengan memiliki salah satu atau kedua dari pengecekan pencarian setiap node sebelum diperluas untuk melihat apakah itu adalah pinggiran pencarian tree, jika iya maka solusi telah ditemukan. Kebutuhan ruang merupakan salah satu kelemahan signifikan yang dimiliki oleh bidirectional search. Algoritma yang komplit dan optimal (untuk biaya yang sama), jika pencarian keduanya adalah perluasan pertama (breadth first), kombinasi-kombinasi yang lain mungkin mengorbankan kelengkapan, optimalitas ataupun keduanya.
Pengurangan dalam kompleksitas waktu membuat pencarian dua arah menarik, akan tetapi bagaimana dengan pencarian mundur? Membiarkan predeccessors dari state x, Pred (x) semuanya mempunya x sebagai successor. Bidirectional search membutuhkan Pred (x) dengan efisiensi yang dihitung. Kasus yang mudah adalah ketika seluruh aksi di ruang state dapat dibalik, jadi Pred (x) = Succ (x).
Pada kasus yang lain mungkin membutuhkan kecerdasan yang mendasar. Kasus yang paling sulit dari bidirectionalsearch adalah ketika pengujian goal hanya memberika deskripsi yang implisit dari beberapa kemungkinan yang lebih luas untuk mencapai tujuan yang telah ditetapkan.
Metode Pencarian Bidirectional Search
Pencarian dengan metode bidirectional search adalah dengan menjalankan dua pencarian secara simultan, yang satu dikerjakan secara forward dari initial state menuju ke goal, sedangkan yang satu lagi dikerjakan secara backward mulai dari goal ke initial state, yang kemudian diharapkan bahwa kedua pencarian itu akan bertemu di tengah-tengah (Suhartono, 2013).
Pada setiap iterasi, pencarian dilakukan dari dua arah yaitu pencarian maju (dari start ke goal) dan pencarianmundur (dari goal ke start).Ketika dua arah pencarian telah membangkitkan simpul yang sama, maka solusi telah ditemukan, yaitu dengan cara menghubungkan kedua jalur yang bertemu.
Jika pencarian maju menggunakan Breatdh First Search (BFS) dan pencarian mundur juga menggunakan BFS, maka jumlah langkah yang diperlukan adalah sebanyak O(2bd/2) ≈ O(bd/2). Dimana b adalah faktor percabangan dan d adalah kedalaman solusi. Contoh: misalkan, untuk b = 10 dan d = 6, maka BFS akan membangkitkan 1 + 10 + 102 + 103 + 104 +105 + 106 = 1.111.111 simpul. Sebaliknya, Bidirectonal Search (BDS) hanya membangkitkan 2 x (1 + 10 + 102 + 103) = 2.222 simpul. Hal ini jika kita bandingkan, jauh lebih sedikit dibanding jumlah simpul yang dibangkitkan BFS. Dalam kasus ini BDS memerlukan memori yang menyimpan hanya 2.222 simpul.
Sekian ulasan singkat tentang Metode Pencarian dalam Kecerdasan Buatan semoga dapat menjadi referensi bagi anda dan bermanfaat bagi anda, jika artikel ini dirasa berguna bagi anda silahkan bagikan/share artikel ini.Terima kasih telah berkunjung
Thank you for nice information
Please visit our website uhamka[.]ac[.]id