ALGORITMA A* / ALGORITMA A-Star
A. PENGERTIAN ALGORITMA A*
Algoritma A Star
merupakan salah satu algoritma yang menggunakan fungsi biaya. Atau algoritma pencarian
graf/pohon yang mencari jalur dari satu titik awal ke sebuah titik akhir yang
telah ditentukan.
Perbedaan algoritma A
Star dan algoritma Greedy terletak pada rumus yang digunakan oleh kedua
algoritma, algoritma greedy hanya menggunakan rumus perkiraan atau estimasi
saja tetapi algoritma A Star selain menggunakan rumus perkiraan atau estimasi,
juga menghitung cost yang diperlukan untuk mengembalikan puzzle ke posisi
berurut. Inilah yang membuat algoritma A Star lebih baik daripada algoritma
Greedy. Tetapi dengan lebih banyaknya rumus yang dihitung, hal ini menyebabkan
algoritma A Star bekerja dengan lambat sehingga waktu yang diperlukan untuk
menemukan solusi akan semakin besar pula karena selain menghitung biaya yang
diperlukan untuk berjalan dari simpul satu ke simpul lainnya, Algoritma A Star
juga menggunakan fungsi untuk memprioritaskan pemeriksaan simpul-simpul arah
yang benar
Heuristic
Kata heuristic berasal dari sebuah kata kerja
bahasa Yunani, heuriskein, yang berarti mencari atau memasukkan. Dalam dunia
pemograman, sebagian orang menggunakan kata heuristic sebagai lawan kata dari
algoritmik, dimana kata heuristic ini diartikan sebagai suatu proses yang
mungkin dapat menyelesaikan suatu masalah tetapi tidak menjamin bahwa selalu
solusi yang dicari selalu dapat ditemukan. Didalam mempelajari metode-metode
pencarian ini, kata heuristic diartikan sebagai suatu fungsi yang memberikan
suatu nilai berupa biaya perkiraan (estimasi) dari suatu solusi. Heuristic
adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian. Untuk
dapat menerapkan heuristic tersebut dengan baik dalam suatu domain tertentu,
diperlukan suatu Fungsi Heuristic. Fungsi heuristic ini digunakan untuk
mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh
hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan. Teknik pencarian heuristic (heuristic
searching) merupakan suatu strategi untuk melakukan proses pencarian ruang
keadaan (state space) suatu problema secara selektif, yang memandu proses
pencarian yang kita lakukan di sepanjang jalur yang memiliki kemungkinan sukses
paling besar.
A.
URAIAN LANGKA-LANGKAH ALGORITMA
Algoritma
A Star merupakan salah satu algoritma yang menggunakan fungsi biaya. Algoritma
A Star memeriksa kelayakan biaya yang diperlukan untuk mencapai suatu simpul
dari sebuah simpul lain. Dalam kasus puzzle 8 ini, algoritma A Star
membandingkan 2 posisi puzzle yaitu posisi puzzle awal (state awal) dengan
posisi puzzle yang terurut dengan benar (state akhir). Rumus yang digunakan
oleh algoritma A Star yaitu : f(n) = g(n)+h(n)
dengan:
g(n) = total keseluran
biaya untuk mencapai posisi benar
h(n) = total keseluruhan
biaya grid yang ada di posisi salah
Program ini akan
menghitung nilai g(n) yaitu
keseluruhan biaya untuk mencapai posisi benar dan h(n) yaitu dengan memeriksa
jumlah kotak yang berada di posisi yang salah. Lakukan langkah-langkah diatas sampai
ditemukan semua jalur atau langkah untuk mengembalikan Puzzle 8 ke posisi yang
berurut.
Perbedaan
algoritma A Star dan algoritma Greedy terletak pada rumus yang digunakan oleh
kedua algoritma, algoritma greedy hanya menggunakan rumus perkiraan atau
estimasi saja tetapi algoritma A Star selain menggunakan rumus perkiraan atau
estimasi, juga menghitung cost yang diperlukan untuk mengembalikan puzzle ke
posisi berurut. Inilah yang membuat algoritma A Star lebih baik daripada
algoritma Greedy. Tetapi dengan lebih banyaknya rumus yang dihitung, hal ini
menyebabkan algoritma A Star bekerja dengan lambat sehingga waktu yang
diperlukan untuk menemukan solusi akan semakin besar pula karena selain
menghitung biaya yang diperlukan untuk berjalan dari simpul satu ke simpul
lainnya, Algoritma A Star juga menggunakan fungsi untuk memprioritaskan
pemeriksaan simpul-simpul arah yang benar
·
Perancangan
Use
Case Diagram
Gambar
1 Use Case Diagram
Dari gambar 1
dapat dilihat bahwa user dapat menginputkan angka pada puzzle dengan inputan
manual atau inputan otomatis yang dilakukan oleh sistem. Setelah melakukan
inputan otomatis atau manual, maka dapat dilakukan pemilihan algoritma dalam
penyelesaian soal yaitu algoritma A Star atau algoritma Greedy.
Diagram Alir
Flowchart digunakan untuk menggambarkan alur suatu program menjadi lebih sederhana sehingga program tersebut dapat lebih mudah dimengerti.
Gambar 2 Flowchart Sistem
A.
URAIAN IMPLEMENTASI ALGORITMA DALAM STUDI KASUS
Puzzle
8 adalah representasi permainan teka-teki yang dapat diselesaikan dengan
mengurutkan atau menyusun komponen-komponen pembentuknya sesuai dengan kondisi
yang berurut. Komponen pada Puzzle 8 adalah berupa kotak-kotak bernomor atau
bergambar yang dapat diacak sedemikian hingga menjadi suatu pola random yang
dapat dicari jalan penyelesaiannya. Sesuai namanya, Puzzle 8 terdiri atas 8 kotak
dan 1 tempat kosong yang dapat digerakkan dengan aturan tertentu. Aturan
pergerakannya hanya berupa empat arah pergerakan, yaitu atas, bawah, kanan, dan
kiri. Pada Puzzle 8, batasannya adalah ukuran 3×3. Sehingga, 8 kotak yang
dimiliki hanya dapat bergerak dalam lingkup ukuran tersebut
Aplikasi
ini merupakan aplikasi pemecahan puzzle dimana terdapat form untuk user agar dapat
memasukkan angka dan kemudian dapat memilih algoritma apa yang digunakan dalam
pemecahan puzzle tersebut. Didalam form terdapat dua buah algoritma yang dapat
dipilih, yaitu Algoritma A Star dan Algoritma Greedy. Setelah user memilih
algoritma yang digunakan, maka masing-masing algoritma dapat menampilkan jalur
yang ditemukan, sehingga dari jawaban tersebut dapat dilihat bahwa algoritma
mana yang lebih baik.
Salah satu algoritma yang termasuk kedalam
kategori informed search adalah Greedy Best first search yang dikenal juga
dengan Greedy Search. Prinsip greedy adalah mengambil keputusan yang dianggap
terbaik hanya untuk saat itu saja yang diharapkan dapat memberikan solusi
terbaik secara keseluruhan. Oleh karena itu, pada setiap langkah harus dibuat
keputusan yang terbaik dalam menentukan pilihan. Keputusan yang telah diambil
pada suatu langkah tidak dapat diubah lagi pada langkah selanjutnya. Greedy
Best first search seperti halnya algoritma yang menggunakan strategi Best first
search lainnya mempunyai sebuah fungsi yang menjadi acuan kelayakan sebuah
simpul yaitu fungsi evaluasi . Pada Greedy Best first search fungsi evaluasi
tidak bergantung pada cost sebenarnya, tetapi hanya tergantung pada fungsi
heuristic itu sendiri. Jika pada algoritma A Star pencarian yang dilakukan
bergantung pada cost sebenarnya dari sebuah simpul yaitu , pada Greedy Best
first search fungsi evaluasi hanya bergantung pada fungsi heuristic yang
mengestimasikan arah yang benar, sehingga pencarian jalur dapat berlangsung
dengan sangat cepat. Secara matematis fungsi evaluasi pada greedy search diberikan
oleh = f(n) = h(n)
dengan:
= h(n) total keseluruhan biaya
grid yang ada di posisi salah.
Program
ini akan menghitung nilai h(n) dengan memeriksa
jumlah kotak yang berada di posisi yang salah. Semakin banyak jumlah kotak yang
berada di posisi yang salah, maka mungkin saja masih banyak langkah yang harus
ditempuh. Semakin sedikit jumlah kotak yang berada di posisi yang salah, maka
mungkin saja puzzle sudah hampir
mendekati penyelesaian. Rumus heuristic
ini diterapkan pada kotak yang mungkin untuk digerakkan. Kemudian dipilih
heuristic yang paling optimal diantara semua kemungkinan tadi. Kotak yang
terpilih, akan digerakkan ke kotak yang kosong, lalu akan dibangkitkan lagi
anak pohon dari status yang sekarang. Dan memulai lagi proses penentuan heuristic untuk kemungkinan kotak yang
baru.
Gambar 1 Splash
screen aplikasi
Gambar 6. Tampilan
utama aplikasi
Pada halaman gambar 6 user dapat
memilih dua cara untuk memasukkan angka yang ingin diselesaikan dari posisi
acak hingga posisi berurut. Cara yang dapat digunakan untuk memasukkan nomor
adalah cara manual, yaitu user itu sendiri yang menginputkan angka ke dalam
aplikasi atau dengan cara otomatis, yaitu aplikasi itu sendiri yang memasukkan
angka dengan acak Jika inputan telah benar, maka user dapat memilih untuk
mengerjakan soal tersebut menggunakan Algoritma A star atau Algoritma Greedy.
User juga dapat memilih untuk mengarjakan soal tersebut dengan dua buah
algoritma sekaligus, sehingga user dapat membandingkan hasil jalur yang
ditemukan oleh kedua algoritma tersebut
Gambar 7 Hasil
A. REFERENSI
DEPTH FIRST SEARCH
A. PENGERTIAN DEPTH FIRST SEARCH
DFS (Depth First Search) adalah
salah satu algoritma penelusuran struktur graf/pohon berdasarkan kedalaman. Simpul
ditelusuri dari root kemudian ke salah satu simpul anaknya (misalkan prioritas
penelusuran berdasarkan anak pertama [simpul sebelah kiri]), maka penelusuran
terus melalui simpul anak pertama dari simpul anak pertama level sebelumnya
hingga mencapai level terdalam.
Algoritma DFS adalah algoritma
recursion yang memanfaatkan backtracking. Algoritma ini melakukan pencarian
secara mendalam pada semua node dengan terus melakukan pencarian ke bawah
selama memungkinkan. Jika tidak memungkinkan, algoritma ini akan beralih
menggunakan backtracking.
B. URAIAN
LANGKA-LANGKAH ALGORITMA
Cara
kerja algoritma Depth First Search dalam membangkitkan labirin pada permainan
dijelaskan seperti pada Gambar 1. Pertama-tama tentukan ukuran labirin
berdasarkan tingkatan level permainan. Untuk menghindari ukuran labirin yang
terlalu kecil pada setiap level Penulis menggunakan rumus 15 + 2 x level saat ini.
Kemudian piiih sel bertetangga yang belum pernah dikunjungi secara acak, Jika
ada maka tambahkan pada stack lalu tandai bahwa sudah dikunjungi. Jika tidak
ada sel maka lakukan runut balik dari sel teratas yang ada pada stack. Lakukan
sampai stack kosong dan tidak ada lagi sel yang dapat dikunjungi.
Gambar
1 Kotak (Grid) Awal pada Labirin 9x9
Berikut ini adalah penjelasan cara pembuatan labirin
yang digunakan, secara konsep untuk membangkitkan labirin dimulai dengan kotak
(grid) yang merepresentasikan sel dan dinding-dindingnya. Dalam contoh kasus
ini diasumsikan bahwa ukuran kotak labirin adalah 9x9 yang dimulai dari indeks
0 sampai 8 seperti pada Gambar 1
Gambar 2 Kotak (Grid) Awal pada Labirin 9x9
Untuk memudahkan
penomoran pada kotak yang akan dijadikan labirin, maka dilakukan pemberian
indeks pada setiap kotak dimulai pada indeks [0,0] hingga indeks [8,8] yang
diisi dengan nilai 0 sampai 80 seperti pada Gambar 2.
Gambar 3 Pemberian Nomor pada
Setiap Kotak
Setiap satu sel
mempunyai 4 dinding yaitu atas, kanan, bawah, dan kiri. Sehingga kotak yang
memungkinkan untuk dijadikan sel pada kotak 9x9 ditunjukan pada Gambar 3.
Gambar
4 Sel-sel pada Kotak 9x9
Setiap kotak merupakan peubah yang dapat menampung
nilai. Nilai 0 untuk mewakilkan sebagai jalur dan nilai 1 untuk mewakilkan
dinding pada labirin. Pada awal inisialisasi peubah, setiap peubah diberi nilai
1 terlebih dahulu seperti pada Gambar 4.
Gambar 5 Nilai Awal pada Setiap Kotak
Dalam algoritma
Depth-First Search, langkah awal adalah menentukan titik awal. Diasumsikan
kotak awal yang dipilih pada kotak [1,1] Sehingga nilai pada kotak [1,1] diubah
menjadi 0 yang menandakan bahwa kotak [1,1] telah menjadi jalur dalam labirin.
Kemudian simpan penomoran kotak [1,1] ke dalam stack sesuai dengan penomoran
yang telah dibuat sebelumnya. Setelah menentukan titik awal maka langkah
selanjutnya adalah mengecek sel yang bertetangga dengan sel saat ini yang
mungkin untuk dijadikan sel. Terdapat 2 kemungkinan sel yang dapat dibentuk,
kemungkinan pertama yaitu ke atas pada kotak [3,1] atau ke kanan pada kotak
[1,3]. Pengacakan dilakukan untuk menentukan arah yang akan dituju, dalam kasus
ini Penulis melakukan pengacakan arah dengan bantuan algoritma Fisher-Yates.
Diasumsikan hasil dari arah yang diacak adalah ke kanan sehingga pembuatan
jalur di antara kotak saat ini dan kotak selanjutnya dilakukan dengan merubah
kotak [1,3] dan kotak diantara sel saat ini dan sel yang akan dijadikan juga
menjadi 0 seperti pada Gambar 5.
Gambar 6 Pembuatan Sel pada Kotak
[1,3]
Kotak-kotak yang telah
terubah menjadi 0 kemudian direpresentasikan menjadi pohon seperti Gambar 5
dengan pemberian nama pada simpul sesuai penomoran pada Gambar 2.
Gambar 7 Pengubahan dari Kotak ke
Dalam Bentuk Pohon
Ketika tahapan ini
menemui kondisi dimana tidak ada lagi sel tetangga yang dapat dijadikan jalur
labirin seperti pada Gambar 7. Algoritma Depth-First Search akan mulai merunut
balik (backtracking) dengan cara mengambil sel teratas dari stack.
Gambar 8 Kondisi Saat Backtracking
Proses ini dilakukan
terus menerus hingga tidak ada lagi kotak yang bisa dijadikan sel seperti pada
Gambar 8 dan dihasilkan struktur pohon seperti pada Gambar 9.
Gambar
9 Pengubahan dari Seluruh Kotak ke Dalam Bentuk Pohon
Gambar
10 Hasil Struktur Pohon
· Perancangan cepat prototype yaitu
merancang prototype dengan membuat desain sementara yang berfokus pada
penerapan algoritma Depth-First Search sebagai maze generator dan penyesuaian
cerita game yang akan dibuat.
· Membangun Prototype, pada tahap ini
prototype yang sudah dirancang sementara ataupun sudah jadi dievaluasi apakah
game sudah sesuai kebutuhan user. Apabila sudah desain sebelumnya dibangun
kembali.
· Selanjutnya setelah sistem sudah menjadi
suatu perangkat lunak yang siap pakai, harus diuji dahulu sebelum digunakan.
·
Perubahan desain dan prototype, pada
tahap ini dilakukan evaluasi terhadap rancangan game. Apakah rancangan
prototype game dan skenario yang dibuat sudah sesuai dengan yang diharapkan.
Jika tidak, maka prototype direvisi dengan mengulang langkah sebelumnya.
·
Impelementasi Sistem, yaitu menerapkan
game kepada pengguna untuk sarana pembelajaran bagi anak-anak khususnya kelas
IV. Pada tahap ini permainan labirin telah sesuai dengan kebutuhan yang telah
melalui proses pengujian yang telah dianggap berhasil. Kemudian permainan
labirin akan di Build ke PC sehingga permainan bisa diaplikasikan pada komputer
supaya bisa dimainkan untuk anak-anak.
A.
URAIAN IMPLEMENTASI ALGORITMA DALAM STUDI KASUS
Penerapan
pada permainan labirin metamorfosis terletak pada pembuatan jalur labirin.
Setiap kali dimulai permainan akan melakukan pembuatan jalur labirin dengan
menggunakan algoritma Depth-First Search. Contoh penerapan algoritma
Depth-First Search bisa dilihat ketika permainan mengacak labirin untuk level
1. pada level 1 ukuran kotak (grid) adalah 17x17 seperti pada Gambar 10.
Gambar 11 Penomoran pada Kotak (grid) 17x17
Pada
Unity ketika permainan berada pada level 1 dan dijalankan, bentuk labirin dapat
dilihat kotak (grid) secara keseluruhan dari scene view seperti pada Gambar 11.
Gambar 12 Contoh
Tampilan Labirin Level 1 pada Scene View
Format nama yang diberikan pada
dinding labirin yaitu <huruf_d><posisiX><posisiZ>_<penomoran_grid>,
sehingga pada kotak[0,0]. diberi nama d0,0_0. Sedangkan pada jalur labirin
diberikan format nama yaitu <huruf_EP>,<penomoran_grid> ,
sehingga pada kotak[1,1] diberi nama EP,18.
Hasil
Pengujian
Setelah
algoritma Depth-First Search berhasil diimplementasikan pada Unity untuk
membuat arena labirin, dilakukan pengujian yang bertujuan untuk menguji
kriteria labirin sempurna pada setiap level permainan labirin metamorfosis.
Level permainan labirin metamorfosis terdiri dari 12 level, masing-masing level
dilakukan pengujian sebanyak lima kali sehingga didapatkan 60 data sampel
seperti pada Tabel 1.
Dari Tabel 1 pada kolom loop dan sel
terisolasi menampilkan jumlah kondisi yang ) berarti solusi antar satu sel ke
sel lainnya mepunyai tepatüditemukan
sedangkan tanda ( satu jalur yang benar.
Setelah didapatkan 60 data sampel
seperti pada Tabel 1, dilakukan analisa untuk mengetahui hasil level labirin
telah memenuhi kriteria labirin sempurna. Pada Tabel 1 diperoleh semua jumlah
loop pada labirin yang telah diciptakan oleh permainan berjumlah nol, semua sel
terisolasi berjumlah nol, dan semua labirin mempunya tepat satu jalur yang
benar.
A.
REFERENSI
rapihkan kembali
BalasHapus