10 Metode Pencarian Heuristik

Pada metode metode ini digunakan suatu fungsi yang menghitung biaya perkiraan dari suatu simpul tertentu menuju ke simpul tujuan. Fungsi ini dikenal sebagai fungsi heuristic (heuristik).

Kata heuristic berasal dari sebuah kata kerja bahasa Yunani, heuriskein, yang berarti mencari atau menemukan. Dalam dunia pemrograman, sebagian menggunakan kata heuristik sebagai lawan kata dari algoritmik, dimana kata heuristik ini diartikan sebagai suatu proses yang munkin dapat menyelesaikan suatu masalah tetapi tidak ada jaminan bahwa solusi yang di cari selalu dapat ditemukan. Di dalam mempelajari metode-metode pencarian ini, kata heuristic diartikan sebagai suatu fungsi yang memberikan suatu nilai berupa biaya perkiraan (estimasi) dari suatu solusi.

Metode metode yang termasuk kedalam teknik pencarian yang berdasarkan fungsi heuristik (untuk selanjutnya digunakan istilah teknik pencarian heuristik) adalah :

• Generate and Test
• Hill Climbing (Simple Hill Climbing)
• Steepest-Ascent Hill Climbing
• Simulated Annealing
• Bset First Search (Greedy Best First SEarch dan A* dan berbagai variansinya).

1. Generate And Test (Bangkitkan dan Uji)

Metode Generate and Test (GT) adalah metode yang paling sederhana dalam teknik pencarian heuristik. Jika pembangkitan sebuah solusi yang mungkin (a possible solution) dikerjakan secara sistematis, maka prosedur ini menjamin akan menemukan solusinya. Tetapi, jika ruang masalahnya sangat luas, mungkin memerlukan waktu yang sangat lama.

Algoritma GT menggunakan prosedur Depth First Search (DFS) karena suatu solusi harus dibangkitkan secara lengkap sebelum dilakukan Test. Alogritma ini berbentuk sistematis, pencarian sederhana yang mendalam dari suatu ruang permasalahn. GT juga dapat dilakukan denan pembangkitan solusi secara acak, tetapi tidak ada jaminan solusinya akan ditemukan.

Di dalam GT, terdapat dua prosedur penting: Pembangkit ( membangkitkan sebuah solusi yang mungkin) dan Test (menguji solusi yang dibangkitkan tersebut). Dengan penggunaan memori yang sedikit, DFS bisa digunakan sebagai prosedur pembangkit yang menghasilkan suatu solusi. Prosedur Tes bisa menggunakan fungsi heuristik. Pada masalah jurigen air, misalkan biaya perkiraan menuju solusi adalah 4 langkah. Kemudian bisa dibuat suatu kriteria, misalkan solusi bisa diterima jika jumlah langkah kurang dari 8. Jika solusi yang dibangkitkan ternyata jumlah langkah adalah 6, berarti solusi telah ditemukan. Tetapi, dengan cara seperti ini GT bersifat tidak Complete dan tidak Optimal.

2.Hill Climbing (Pendakian bukit)

Hill Climbing (HC) berbeda dengan GT, yaitu pada umpan balik dari prosedur Tes untuk membantu Pembangkit menentukan solusi yang bisa langsung dihilangkan dalam ruang pencarian. DAlam GT, respon dari fungsi pengujian hanya beruapa ya atau tidak. Tapi jika pengujiannya ditambahkan dengan fungsi yang menghitung biaya estimasi antara satae sekarang engan state tujuan maka prosesur pembangkit dapat memanfaatkan nilai ini. HC sering digunakan jika terdapat suatu fungsi heuristik yang baik untuk mengevaluasi state. Sebagai contoh, anda berada di sebuah kota yang tidak dikenal, tanpa peta dan anda ingin menuju ke pusat kota. Cara sederhana adalah dengan berpatokan bahwa gedung yang tinggi selalu berada di pusat kota. Jadi, fungsi heuristiknya adalah jarak antara lokasi anda sekarang dengan gedung yang tinggi tersebut.

Terdapat dua jenis HC yang sedikit berbeda, yakni Simple HC (HC sederhana) dan Steepest – Ascent HC ( HC dengan memilih kemiringan yang paling tajam atau curam).

Simple HC secara sederhana, langsung memilih new state yang memiliki jalur yang lebih baik (curam) dari pada jalur jalur sebelumnya tanpa memperhitungkan jalur jalur lain yang lebih curam. Sedangkan Steepest Ascent HC, sesuai dengan namanya, akan mengevaluasi semua state yang berada dibawah current state dan memilih state dengan jalur paling curam.

• Dalam kasus jurigen air, Jika solusi yang diberikan berada di level yang lebih rendah berarti solusi tersebut semakin baik karena membutuhkan sedikit langkah (aturan produksi). Dengan demikian, Simple HC tidak optimal.

3. Simulated Annealing (SA)

SA memanfaatkan analogi cara pendinginan dan pembekuan metal menjadi sebuah struktur kristal dengan energi yang minimal. Tidak seperti pendekatan HC, dengan probabilitas tertentu SA mungkin bisa keluar dari jebakan local minimum menggunakan sebuah rumus probabilitas yang memungkinkannya bisa keluar dari local minimum. Ketika new state tidak lebih dari current sate, maka new state tersebut masih mungkin dipilih dengan probabilitas sebagai berikut:

p(Delta E) = e^Delta E/T

Fungsi tersebut diadopsi dari ilmu fisika, dimana fungsi ini merepresentasikan distribusi Boltzman dari energi dalam sistem termodinamik, sehingga didapat persamaan probabilitas dari level energi yang diberikan dalam sistem temperatur T.

Apabila S adalah current state dan A adalah new state. Ketika dievaluasi, ternyata new state tidak lebih baik dari pada current state. Tetapi, ketika dibangkitkan bilangan acak dalam interval menghasilkan angka kurang dari probabilitas p, maka A dipilih sebbagai current state. PAda akhirnya, SA dapat menemukan solusi optimum di leve 2. Karena bergantung pada suatu nilai probabilitas, maka SA tidak selalu menemukan solusi terbaik, dengan kata lain, SA tidak optimal.

4. Best First Search (Pencarian Terbaik Lebih Dahulu)

Steepest-Acent HC ataupun Sumulated Annealing memilih simpul baru yang memiliki biaya terkecil diantara suksesor-suksesor saudaranya (sibling) sehingga bisa menghasilkan solusi yang tidak optimal. Berbeda dengan kedua algoritma tersebut, Best First Search memilih simpul baru yang memiliki biaya terkecil di antara semua leaf nodes (simpul-simpul pada level terdalam) yang pernah dibangkitkan. Dengan demikian, algoritma Best-First SEarch melakukan perhitungan yang lebih banyak dibandingkan HC maupun Simulated Annealing.

Sesuai dengan namanya, Best First Search membangkitkan simpul berikutnya dari sebuah simpul yang sejauh ini terbaik di antara semua leaf nodes yang pernah dibangkitkan. Pertanyaannya, bagaimaan menentukan sebuah simpul yang terbaik saat ini ? Penentuan simpul terbaik dapat dilakukan menggunakan informasi berupa biaya perkiraan dari suatu simpul menuju ke goal atau gabungan antara biaya sebeanrnya dan biaya perkiraan tersebut. Biaya perkiraan dapat diperoleh menggunakan suatau fungsi yang disebut fungsi heuristik. Oleh karena itu, algoritma Best First SEarch ini digolongkan sebagai heuristic search atau informed search (pencarian dengan berbekal informasi yang berupa biaya perkiraan).

Terdapat dua jenis algoritma Best First Search, yaitu: 1) Algoritma Greedy Best First Search yang hanya mempeprhitungkan biaya perkiraan saja, dan 2) Alogirtma A* yang memperhitungkan gabungan dua biaya, biaya sebenarnya dan biaya perkiraan.

Pada algoritma BFS di atas, OPEN adalah senarai (list) yang digunakan untuk menyimpan simpul-simpul yang pernah dibangkitkan dan nilai heuristiknya telah dihitung tetapi belum terpilih sebagai simpul terbaik (best node). Dengan kata lain OPEN berisi simpul-simpul yang masih memiliki peluang (peluangnya masih terbuka) untuk terpilih sebagai simpul terbaik. Sedangkan CLOSED adalah senarai untuk menyimpan simpul-simpul yang sudah pernah dibangkitkan dan sudah pernah terpilih sebagai simpul terbaik. Artinya, Closed berisi simpul simpul yang tidak mungkin terpilih sebagai simpul terbaik (peluang untuk terpilih sudah tertutup).

5. Greedy Best First Search

Algoritma ini merupakan salah satu jenis algoritma Best First Search yang paling sederhana dengan hanya memperhitungkan biaya perkiraan (estimed cost) saja yakni f(n) = h(n). Biaya yang sebenarnya (actual cost) tidak diperhitungkan. Dengan hanya memperhitungkan biaya perkiraan yang belum tentu kebenarannya maka algoritma ini menjadi tidak optimal. Apabila terdapat 13 kota yang dinyatakan oleh simpul-simpul dalam suatu graph dua arah. Setiap angka pada busur menyatakan biaya sebenarnya antara satu kota dengan kota lainnya. Misalkan biaya di sidoarjo adalha jarak antar kota dalam satuan kilometer. Nilai h(n)  adalah fungsi heuristic yaitu jarak garis lurus dari simpul n menuju simpul G dalam satuan kilometer. Untuk perjalanan dari kota S ke kota G, rute mana yamg memiliki biaya minimum dan terpendek ?.

Langkah pertama, mula mula OPEN berisi satu simpul, yaitu S. Karena di OPEN hanya terdapat satu simpul, maka S terpilih sebagai simpul terbaik dan dipindahkan ke CLOSED. Kemudian dibangkitkan semua suksesor S, yaitu A, B, C , D dan E. Karena kelima suksesor belum pernah ada di OPEN maupun CLOSED maka kelimanya dimasukkan ke OPEN. Langkah pertama ini menghasilkan open = [A,B,C,D,E] dan CLOSED = [S].

Langkah ke dua, karena Greeedy Best-First Search hanya memperhitungkan biaya perkiraan, maka f(n) = h(n). B dengan biaya terkecil (yaitu f(b) = h(b) = 60) terpilih sebagai simpul terbaik dan dipindahkan ke CLOSED. Selanjutnya, semua suksesor B dibangkitkan yaitu A, F, dan K. Karena F dan K belum pernah ada di Open maupun CLOSED, maka keduanya dimasukkan ke OPEN. SEdangkan simpul A sudah di OPEN, maka harus di cek apakah parent dari A perlu di ganti atau tidak. Karena hanya memperhitungkan biaya perkiraan (h), maka biaya perkiraan dari S ke A maupun biaya perkiraan dari A tidak perlu diubah. Langkah ke dua ini menghasilkan OPEN = [A,C,D,E,F,K,J] dan CLOSED ] [S,B].

Langkah ke tiga, K dengan biaya terkecil (yaitu f(K) = h(K) = 30) terpilih sebagai simpil terbaik dan dipindahkan ke CLOSED. Selanjutnya , semua suksesor K dibangkitkan, yaitu G. Karena belum pernah ada di OPEN maupun CLOSED, maka G dimasukkan ke OPEN. Langkah ke tiga ini menghasilkan OPEN [A,C,D,E,F,K,J,G] dan CLOSED = [S,B,K]. Langkah berikutnya, G dengan biaya terkecil (yaitu f(G) = h(G) = 0) terpilih sebagai simpul terbaik. Karena simpul terbaik tersebut sama dengan goal, berarti S karena setiap simpul hanya memiliki satu parent dan setiap simpul memiliki informasi biaya sbenarnya (g). Hasil penelusuran balik menghasilkan rute S-B-K-G dengan total jarak sama dengan 105 kilometer. Rute yang dihasilkan ini ternyata bukanlah rute terpendek karena masih ada rute lain yang lebih pendek, yaitu S-A-B-F-K-G yang total jaraknya sama dengan 95 kilometer. Hal ini menujukkan bahwa Greedy Best First SEarch tidak optimal.

6. A* (A Bintang atau A Asterisk)

Algoritma ini merupakan algoritma Best First Search yang menggabungkan Uniform Cost Search dan Greedy Best First Search. Biaya yang diperhitungkan didapat dari biaya sebenarnya ditambah dengan biaya perkiraan. Dalam notasi matematika dituliskan sebagai : f(n) = g(n) + h(n). Dengan perhitungan biaya seperti ini, algoritma A* adalah complete dan optimal.

Secara detail, algoritma A* ini diilustrasikan oleh algoritma dasar Best First Search, algoritma A* ini juga menggunakan dua senarai: OPEN dan CLOSED. Terdapat tiga kondisi bagi setiap suksesor yang dibangkitkan, yaitu: sudah berada di OPEN, sudah berada di CLOSED, dan tidak berada di OPEN maupun CLOSED. PAda ketiga kondisi tersebut diberikan penaganan yang berbeda-beda.

Jika suksesor sudah perknah berada di OPEN, maka dilakukan pengecekan apakah perlu perubahan parent atau tidak tergantung pada nilai g-nya melalui parent kecil, maka dilakukan pengubahan parent. Jika pengubahan parent dilakukan maka dilakukan pula perbaruan (update) nilai g dan f pada suksesor tersebut. Dengan perbaruan ini, suksesor tersebut memiliki kesempatan yang lebih besar untuk terpilih sebagai simpul terbaik (best node).

Jika suksesor sudah pernah berada di CLOSED, maka dilakukan pengecekan apakah perlu pengubahan parent atau tidak. Jika ya, maka dilakukan perubahan nilai g dan f pada suksesor tersebut serta pada semua “anak cucunya” yan sudah pernah berada di OPEN. Dengan perbaruan ini, maka semua anak cucunya teresbut memiliki kesempata lebih besar untuk terpilih sebgai simpul terbaik (best node).

Jika suksesor tidak berada di OPEN namun CLOSED, maka suksesor tersebut dimasukkan ke dalam OPEN. Tambahkan suksesor tersebut sebagai suksesornya best node. Hitung biaya suksesor tersebut dengan rumus f = g + h.

• Langkah pertama, karena di OPEN hanya terdapat satu simpul yaitu S, maka S terpilih sebagai BestNode dan dipindahkan ke CLOSED. Kemudian dibangkitkan semua suksesor S, yaitu A,B,C,D, dan E. Karena kelima suksesor tidak ada di OPEN maupun CLOSED, maka kelimanya dimasukkan ke OPEN, Langkah pertama ini menghasilkan OPEN = [A,B,C,D,E] dan CLOSED [S].
• Langkah kedua, E dengan biaya terkecil (yaitu 84) terpilih sebagai BestNode dan dipindahkan ke CLOSED. SElanjutnya, semua suksesor E dibangkitkan, yaitu: D dan J. Karena belum pernah ada di OPEN maupun CLOSED, maka J dimasukkan ke OPEN. Sedangkan simpul D sudah ada di OPEN, maka harus di cek apakah parent dari D perlu diganti atau tidak. Ternyata biaya dari S ke D melalui E (yaitu 10 + 25 = 25) lebih kecil dari pada biaya dari S ke D (yaitu 35). Oleh karena itu, parent dari D harus diubah yang semula S menjadi E. Dengan perubahan parent ini, maka nilai g dan f pada D juga diperbaraui (nilai g yang semula 35 menjadi 25, dan nilai f dari 120 menjadi 110). Langkah kedua ini menghasilkan OPEN = [A,B,C,D,J] dan CLOSED = [S,E].
• Langkah ketiga, B dengan biaya terkecil (yaitu 85) terpilih sebagai BestNode dan dipindahkan ke CLOSED. Selanjutnya, semua suksesor B dibangkitkan, yaitu : A, F dan K. Karena belum pernah ada di OPEN maupun CLOSED. maka F dan K dimasukkan ke OPEN. Sedangkan simpul A sudah ada di OPEN, maka harus dicek apakah parent dari A perlu diganti atau tidak. Ternyata biaya dari S ke A melalui B (yaitu 25+10 = 35) lebih besar daripada biaya dari S ke A (yaitu 10). Oleh karena itu, parent dari A tidak perlu diubah (tetap S.). Akhir dari langkah ketiga ini menghasilkan OPEN = [A,C,D,F,J,K] dan CLOSED = [S,E,B].
• Langkah keempat, A dengan biaya terkecil (yaitu 90) terpilih sebagai BestNode dipindahkan ke CLOSED. Selanjutnya, semua suksesor A dibangkitkan yaitu B dan G. Karena belum pernah di OPEN maupun CLOSED, maka G dimasukkan ke OPEN. SEdangkan simpul B sudah ada di CLOSED, maka harus dicek apakah parent dari B perlu diganti atau tidak. TErnyata, biaya dari S ke B melalui A (yaitu 10 + 10 = 20) lebih kecil dari pada biaya dari S ke B (yaitu 25). Oleh karena itu parent dari B harus diubah, yang semula S menjadi A. Nilai g dan f pada B juga harus diperbarui (nilai g yang semula 25 menjadi 20, dan nilai f dari 85 menjadi 80). Nilai g dan f pada suksesor suksesor B (sampai anak cucu) juga harus diperbarui menggunakan penelusuran Depth First Search (DFS). Dalam kasus ini B hanya mempunyai dua anak (tidak punya cucu), yaitu F dan K. Nilai g(F) yang semulai 30 diubah menjadi 25, dan nilai f(F) dari 100 menjadi 95. Nilai g(K) yang semula 75 diubah menjadi 70, dan nilai f(K) dari 105 menjadi 100). Akhirnya OPEN = [C,D,F,G,H,K] dan CLOSED = [S,E,B,A]
• Langkah kelima, F dengan biaya terkecil (yaitu 95) terpilih sebagai BestNode dan dipindahkan ke CLOSED. SElanjutnya, semua suksesor F dibangkitkan, yaitu: K, Karena K sudah ada di OPEN, maka harus dicek apakah parent dari K perlu diganti atau tidak. Biaya dari S ke K melalui F ternyata lebih kecil dari pada biaya dari S ke K melalui parent lama (B). Oleh karena itu, parent dari K harus diubah, yang semula B menjadi F. Selanjutnya, nilai g(K) yang semula 70 diubah menjadi 65, dan nilai f(K) dari 100 menjadi 95). Akrhinya OPEN = [C,D,F,G,J,K] dan CLOSED = [S,E,B,A,F].
• Langkah keenam, K dengan biaya terkecil (yaitu 95) terpilih sebagai BestNode dan dipindahkan ke CLOSED. SElanjutnya, semua suksesor K dibangkitkan, yaitu G Karena G sudah ada di OPEN, maka harus di cek apakah parent dari G perlu diganti atau tidak. Biaya dari S ke G melalui K ternyata lebih kecil dari pada biaya dari S ke G melalui parent lama (A). Oleh karena itu, parent dari G harus di ubah yang semula A menjadi K. Selanjutnya nilai g(G) yang semulah 100 dibah menjadi 95, dan nilai f(G) dari 100 menjadi 95). Pada akhir langkah keenam ini, OPEN = [C,D,G,H] dan CLOSED =[S,E,B,A,F,K].

Selanjutnya, G dengan biaya terkecil (yaitu 95) terpilh sebagai BestNode. Karena BestNode sama dengan goal, berarti solusi sudah ditemukan. Rute dan total biaya bisa ditelusuri baik dari G menuju S karena setiap simpul hanya memiliki sati parent dan setiap simpul memiliki informasi biaya sebenarnya (g). Penelusuran balik menghasilkan rute S-A-B-G-K-G dengan total jarak sama dengan 95 Km. Rute ini merupakan rute terpendek yang ada di graph tersebut. Jadi algoritma A adalah optimal. Tanpa ada batasann waktu dan memori. A* adalah complete (SElalu menemukan solusi jika solusinya ada). Pada kasus tersebut, A* membangkitkan dan menyimpan 10 simpul (Dari 3 simpul yang ada pada graph). Untuk masalah yang lebih kompleks, misalkan pencarian rute terpendek pada graph yang terdiri dari 100 juta simpul, A* akan menghadapi masalah waktu proses dan memoi yang dibutuhkan. Untuk menyelesaikan kedua masalah tersbeut diusulkan berbagai variasi A* dengan karakteristik yang sesuai dengan permasalahan tertentu. Di sini, kita hanya membahas beberapa variasi yang ada.

7. Iterative Deepening A* (IDA*)

Pada pembahasan Blind Search telah dibahas bahwa Iterative Deepening Search (IDS) menggunakan batasan level (kedalaman) pada setiap iterasi pencariannya. Ide tersebut diterapkan pada IDA* dengan batasan yang berupa f-limit (nilai gabungan antara biaya sebenarnya dan biaya perkiraan). Pada IAD* ini, setiap iterasi akan mengembalikan nilai f-limit baru yang akan digunakan sebagai batasan pencarian untuk iterasi berikutnya..

Sama seperti A*, algoritma IDA* juga complete dan optimal. Tetapi, karena dilakukan secara iteratif, maka IDA* mungkin membangkitkan simpul-simpul yang sama secara berulang-ulang. Hal ini membutuhkan waktu yang lama. Dengan kata lain, time complexity nya tinggi. Bagaimanapun, keuntungan utama IDA* adala jumlah memori yang dibutuhkan menjadi jauh lebih sedikit. Jika kita menghadapi masalah keterbatasan memori (misalkan kita membangun sistem untuk Personal Digital Assistant atau PDA), maka IDA* bisa menjadi pilihan yang tepat.

8. Simplified Memory Bounded A* (SMA*)

Untuk masalah tertentu, di mana memori komputer terbatas, algoritma A* mungkin tidak mampu menemukan solusi karena sudah tidak tersedia memori untuk meyimpan simpul simpul yang dibangkitkan. Algoritma IDA* dapat dgunakan untuk kondisi seperti ini karena IDA* hanya membutuhkan sedikit memori. Tetapi, satu kelemahan IDA* adlah bahwa pencarian yang dilakukan secara itteratif akan membutuhkan waktu yang lama karena harus membangkitkan simpul berulang kali.

Berlawanan dengan IDA* yang hanya mengingat satu f-limit, algoritma SMA* mengingat f-Cost dari setiap iterasi sampai jumlah simpul yang ada di dalam memori. Karena batasan memori dalam jumlah tertentu, maka kita dapat membatasi pencarian hanya sampai pada simpul-simpul yang dapat diapai dari root sepanjang suatu jalur yang memorinya masih mencukupi. Kemudian mengembalikan suatu rute terbaik diantara rute rute yang ada dalam batasan jumlah simpul tersebut. Jika memori komputer hanya mampu menyimpan 100 simpul, maka kita bisa membatasi proses pencarian sampai level 99.

Pada awalnya Queue ini berisi initial state yang memiliki f-cost = h(n) karena g(n) =o (tidak ada biaya dari initial state menuju ke initial state). SElanjutnya, dilakukan Iterasi sampai goal ditemukan atau sampai Queue kosong. Awalnya, initialstate akan terpilih sebagai n. Kemudian, satu persatu, suksesornya dibangkitkan dan dihitung biayanya yang dilambangkan dengan f(suk). Ketika semua suksesor dari n sudah dibangkitkan, maka ganti nilai f-cost pada n dengan nilai f-cost terkecil dari nilai-nilai f-cost yang ada pada semua suksesornya. Penggantian ini dilakukan juga untuk semua ancestor-nya n(ayah, kakek, dst ke atas(. Tetapi jika ancestornya n tersebut memiliki nilai f-cost yang lebih kecil dari pada f-cost baru pada n, semua suksesor dari n sudah di memori, maka dikeluarkan n dari Queue, tetapi tidak dihapus secara fisik dari memori (artinya: biarkan n tetap berada di memori). Pengeluaran n dari Queue ini dilakukan agar n tidak terhapus ketika memori sudah penuh. Karena penghapusan dilakukan pada simpul terburuk memiliki f-cost terbesar, maka dipilih simpul yang levelnya terdangkal), maka n akan terhapus ketika suksesornya memiliki f-cost yang sama dengannya (di mana f-cost tersebut adalah yang tersebar di semua simpul yang ada di memori). Proses berikutnya adalah penghapusan simpul secara fisik dari memori ketika memori sudah penuh. Simpul yang terpilih akan dihapus dari memori dan perubahan atribut dilakukan pada parentnya, yaitu daftar suksesor yang berisi simpul terhapus tersebut dihilangkan. Kemudian parent dari simpul terhapu tersebut dihilangkan. Kemudian parent dari simpul terhapus tersebut dimasukkan ke dalam Queue jika parent tersebut tidak ada di Queue( artinya : jika parent tidak ada di Queue berarti parent tersebut adalah n yang pernah dikeluarkan dari Queue).

9. Bi-Directional A* (BDA*)

Jika terdapat hanya satu simpul tujuan, maka kita dapat menggunakan algoritma A* dari dua arah, yakni dari simpul asal dan dari simpul tujuan. Pencarian dihentikan jika BestNode dari arah simpul asal telah berada dalam senarai dihentikan jika BestNode dari arah simpul asal telah berada dalam senarai CLOSED dari arah simpul tujuan. Keudian dilakukan pengecepakan apakah mengganti parent dari BestNode tersebut dari arah simpul tujuan. Atau sebaliknya , pencarian dihentikan jika BestNode dari arah simpul tujuan telah berada dalam senarai CLOSED dari arah simpul asal. Juga dilakukan pengecekan apakah harus mengganti parent dari BestNode tersebut dari arah simpul asal.

Implementasi algoritma BDA* dapat memanfaatkan algoritma A* di atas, BDA* mengunakan fungsi heuristik fungsi heuristik yang sama dengan A*. TEtaip, algoritma A* di harus dimodifikasi sedikit dengan menghilangkan loop utama, sehingga algoritma tersebut hanya dikerjakan satu iterasi saja. Masukkan untuk fungsi A* adalah OPEN, CLOSED, S dan G. Sedangkan keluarannya adalah BestNode, OPEN dan CLOSED yang baru.

10. Modified Bi-Directional A* (MBDA*)

Berbeda dengan algoritma Bi-directional A*, algoritma Modified Bi-directional A* menggunakan fungsi heuristik dengan sedikit modifikasi. Fungsi heuristik untuk simpul n pada pencarian maju (dari S ke G) adalah :

Implementasis algoritma MBDA* sama dengan BDA* yang berbeda hanya fungsi heuristiknya. Untuk lebih memahami MBDA* untuk menyelesaikannya masalah. Langkahnya sama dengna BDA* yang berbeda hanya langkah ketiga pencarian maju, dimana A terpilih sebagai BNS lebih dulu dibandingkan dengan B. Hasil akhir dari MBDA* adalah sama dengna BDA*. Tetapi untuk masalah yang lebih komples misalnya mencari rute terpendek yang ada pada graph yang terdiri dari ribuan simpul, performa pencarian rute terpendek akan lebih baik dibandingkan A* dan BDA*.

Jakarta, Special Capital Region of Jakarta, Indonesia

Share :