NEW BIDIRECTIONAL A* SEBAGAI MODIFIKASI BIDIRECTIONAL A*

NEW BIDIRECTIONAL A* SEBAGAI MODIFIKASI BIDIRECTIONAL A*

NEW BIDIRECTIONAL A* SEBAGAI MODIFIKASI BIDIRECTIONAL A*

Modified Bidirectional A* (MBDA) adalah algoritma Bidirectional A* yang telah dimodifikasi sehingga memiliki algoritma yang agak berbeda dengan algoritma Bidirectional A* yang asli. New Bidirectional A* (NBA*) adalah salah satu modifikasi dari algoritma Bidirectional A*.

New Bidirectional A* (NBA*) adalah algoritma pencarian heuristik yang berdasarkan pada A*. NBA* hanya memfokuskan satu masalah pada fungsi heuristik: konsistensi.

Layaknya A*, NBA* menggunakan sebuah struktur yang menjaga agar perluasan node tetap terkendali. Dengan menggunakan notasi asli, M berisi node yang berada di “tengah”, contohnya sebuah node diantara dua pencarian. Pada awalnya, semua node berada didalam M. Node-node yang berada didalam batas pencarian merupakan node milik M yang telah diberi label. Sebuah node X telah diberi label apabila G1(X) atau G2(X) memiliki nilai yang terbatas serta node tersebut belum diperluas. Selain M, L juga merupakan variabel yang dibaca dan ditulis oleh kedua proses pencarian. L berisi nilai dari solusi terbaik sementara yang ditemukan oleh algoritma dan awalnya bernilai tak hingga. L digunakan dalam kriteria pemangkasan bersama dengan FP, yang merupakan nilai fP terkecil dalam batas pencarian dari proses p.

Operasi yang dieksekusi oleh setiap proses sekarang akan lebih terperinci. Pada walnya, nilai G1 dari semua graf diset menjadi tak hingga. Kemudian, algoritma akan membuat G1(S1) = 0 dan F1 = f1(s1). Pada setiap iterasi, node X elemen dari M dengan nilai f1 terkecil akan dipilih untuk perluasan. Nilai f1 akan disingkirkan dari M dan dipangkas (tidak diperluas) apabila f1(X) >= (L^1) atau G1(X) + F2 – h2(x) >= L. Jika tidakm maka semua turunan Y akan dihasilkan. Untuk setiap Y, G1(Y) dan L akan masing-masing diperbaharui, oleh nilai pernyataan berikut: min(G1(y),G1(X) + D1(x,y)) dan min(L,G1(Y) + G2(y)). Pada akhir iterasi, nilai F1 akan diperbaharui oleh nilai f1 terkecil didalam batas pencarian. Eksekusi akan dihentikan saat tidak ada lagi kandidat node uang bisa diperluas pada setiap sisi pencarian. Pada saat ini, L memiliki nilai solusi optimal atau nilai tak hingga bila tidak ada solusi yang ditemukan.

Sumber:

Rios, Luis H.O. dan Chaimowicz, L.().” PNBA*: A Parallel Bidirectional Heuristic Search Algorithm”. Departamento de Ciˆencia da Computac¸ ˜ao, http://homepages.dcc.ufmg.br/~chaimo/public/ENIA11.pdf.