1. Heuristic
/ Informed Search (Best First Search)
APLIKASI GAME
BATTLE PUZZLE DENGAN METODE BESTFIRST SEARCH
Aqil
Muhammad Arviansyah Christnatalis
A. pengertian
Best Firs Search (BFS)
merupakan metode yang membangkitkan simpul berikutnya dari sebuah simpul terbaik diantara semua leaf
nodes (simpul - simpul pada level
terdalam) yang pernah dibangkitkan. Best - First Search (BFS)
merupakan kombinasi dari kelebihan metode Depth-First dan Breath-First Search. Pada
setiap langkah proses
BFS, dipilih simpul-simpul dengan menerapkan fungsi
heuristik yang memadai pada setiap
simpul yang dipilih
dengan menggunakan aturan-aturan tertentu untuk menghasilkan
penggantinya
B. Langkah
- langkah yang dilakukan
metode best first search dalam
menyelesaikan masalah adalah :
1.Buat
sebuah stack kemudian inisialisasikan node akar sebagai node pertama.
2.Bila
node pertama ≠ GOAL, node diganti dan dihapus dengan anak- anaknya.
3.Kemudian,keseluruhan
node pada stack diurutkan secara ascending
berdasarkan fungsi heuristic yang digunakan.
4.
Bila node pertama ≠ GOAL, ulangi langkah 2. Bila node pertama
= GOAL, cari
solusi dengan menelusuri jalur
dari GOAL ke node akar.\
Dari hasil tampilan pengujian bahwa user
harus bermain dengan
cepat agar bisa menang melawan komputer, dimana user
sendirilah yang akan memilih gambar
yang akan disusun dan
memilih potongan gambar yang tersedia (2x2, 3x3, 4x4). Algoritma Best
First Search berperan sebagai pergerakan komputer dalam menyusun potongan
gambar
C. Implementasi
meliputi
penggunaan aplikasi untuk menguji metode
best first search dalam mencari jalan terceoat pada game puzzle dan memperoleh
informasi berupa tingkat
akurasi metode saat digunakan.
Secara konsep
cara bermain Game Battle
Puzzle ini yaitu pemain harus menyusun potongan gambar
yang diacak berdasarkan gambar dan option yang telah dipilih sambil
melawan komputer. Metode Best first search telah diuji dalam
menyusun potongan gambar
dan berhasil tersusun berdasarkan
gambar asalnya
2. BLIND/UN-INF ORMED SEARCH (Bidirectional Search)
PENERAPAN BIDIRECTIONAL SEARCH DAN HELD-KARP PADA
PENENTUAN RUTE PENGIRIMAN PRODUK
I
Gede Surya Rahayuda,Ni Putu Linda Santiar,Norsa Yudhi Arso http://jtiik.ub.ac.id/index.php/jtiik/article/view/881/pdf
A. Pengertian
Bidirectional Search atau
pencarian dwi arah merupakan salah
satu metode pencarian
jalur yang menggunakan dua
alur logika pencarian,
yaitupencarianfront to back dan back to front. Pencarian dilakukan melalui
dua arah, pencarian
dari batas awal graph
sampai akhir dan pencarian
dari akhir graph menuju
ke awal, pencarian
akan berakhir ketika
kedua pencarian tersebut
bertemua ditengah graph (Chen et al.,
2017) (Holte et
al., 2017). Ira Pohl merupakan
ilmuwan pertama yang
mendesain dan mengembangkan
metode tersebut pada
tahun 1971, Bidirectional
Heuristic Search merupakan
versi pertama dari
metode tersebut. Kemudian pada pengembangan selanjutnya
Andrew Goldberg dan ilmuwan lainnya
menjelaskan kondisi pengakhiran yang benar untuk versi metode Bidirectional
Search pada algoritma Dijkstra (Sun, Lee and Batra, 2017)
.
B. Implementasi
Program dikembangkan
menggunakan bahasa pemrograman visual basic. Setelah kedua
program tersebut selesai, selanjutnya dilakukan ujicoba program tersebut
terhadap beberapa data tes Terdapat 20 paket pengiriman, masing-
masing paket terdiri dari5 titik atau lokasi. Tiap titik tersebut akan diinputkan kedalam
program, dan program
akan memproses untuk mencari
jalur terbaik dan menyusun rute
pengiriman dan setiap
hasil
percobaan akan dicatat
dan disimpan. Seperti terlihat pada gambar
4 dan 5. Terdapat
5 buah combobox pada program,
dimana nantinya admin akan memilih kode
toko langganan yang melakukan
pemesanan disesuaikan dengan paket
pengiriman pada data tes, selanjutnya jika
button jarak minimum
ditekan, maka program akan
memproses dan menampilkan hasil berupa: graph matrix,
jarak, waktu biaya minumum dan
rute tempuh terbaik
yang diperoleh.Metode Bidirectional
Search melakukan proses pencarian jalur
terdekat dengan dua proses pencarian. Proses
1 dimulai dari level awal dari graph matrix kemudian dilanjutkan ke level kedua dan seterusnya.
Disaat yang sama
juga dilakukan proses
2, pencarian
dimulai dari levelgraph matrix terakhir dan
dilanjutkan ke level yang lebih
kecil. Sehingga nantinya akan
didapatkan rute awal
dan rute akhir, rute
awal dan rute
akhir kemudian disatukan menjadi
rute gabungan. Karena
pada penelitian ini pengiriman harus kembali ke rute awal basis datalistokolis
rute kirim program menggunakan metode bidirectional search dan held-karphasil perbandingan
hasil data set dan data tes , maka rute hasil ditambahkan dengan jarak titik akhir ke titik awal
.
rapihkan kembali
BalasHapus