Tugas 1 "Kecerdasan Buatan"
Nama : Zakia Nurul Aini
Teknik Informatika B
Semester 5
Heuristic/Informed Search
Pengertian Best First Search
Greedy
Best First Seacrh salah satu algoritma yang termasuk dalam kategori informed
search adalah greedy best firsh 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.
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 Fisrt Search fungsi evaluasi tidak bergantung pada cost
sebenarnya, tetapi hanya tergantung pada fungsi heuristic itu sendiri. Pada
jika pada algoritma A star pencarian yang dilakukan bergantung pada cost
sebenarnya dari sebuah dari sebuah simpul, pada Greedy Best Firsh Seacrh fungsi
evaluasi hanya bergantung pada fungsi heuristic yang mengestimasikan arah yang
benar, sehingga pencarian jalur dapat berlangsung dengan sangat cepat.
ð
Langkah-langkah Algoritma Best First Search:
Langkah-langkah dalam pencarian menggunakan metode Best Firsh
Search kita ambil contoh dari kasus mencari jalur angkot terpendek dari
Pancoran ke Manggarai. Sebagai contoh, berikut adalah rincian jarak tempuh dan
terif angkot. Rincian berikut ini adalah pengeluaran dari Pancoran ke Manggarai
yang dapat ditempuh dengan jarak sekitar ± 10 km yang akan membuat masalah harus
dipecahkan kembali yaitu “tarif angkot” yang harganya selalu relative (harga
jauh atau dekat bisa berbeda-beda) berdasarkan jalur dan tarif angkotnya
masing-masing.
Keterangan:
S => Pancoran
A
=> Kuningan
B
=> Palbatu
C
=> Cawang
D
=> Casablanca
E
=> Tebet
F
=> Bukit Duri
G=>
Manggarai
S
=> A => B =>
C => D => E =>
F => G => H
H(n) 1rb
1,5rb 3rb
1rb 1.5rb
2.5rb 0 2rb
Berikut
adalah langkah-langkahnya dalam menyelesaikan masalah jalur angkot:
Langkah
1: Langkah pertama
OPEN berisi satu simpul yaitu S, maka S jadi simpul terbaik dan dipindahkan ke
CLOSED. Kemudian dibangkitkan semua suksesor S, yaitu A,B,C karena ketiga
suksesor belum ada di OPEN. Langkah pertama menghasilkan OPEN= [A,B,C] &
CLOSED = [S].
Langkah
2: A dengan biaya
terkecil (yaitu f(A) = h(A) = 1rb) terpilih sebagai simpul terbaik & dipindahkan
ke CLOSED. Selanjutnya, semua suksesor A dibangkitkan, yaitu H&D karena
keduanya belum ada di OPEN & CLOSED maka keduanya dimasukan ke OPEN.
Langkah kedua menghasilkan OPEN= [B,C,D,H] & CLOSED = [S,A].
Langkah
3: D dengan biaya
terkecil (yaituf(D) = h(D) = 1rb) terpilih sebagai simpul terbaik &
dipindahkan ke CLOSED. Selanjutnya, semua suksesor D dibangkitkan, yaitu
B&F. karena F belum ada di OPEN & CLOSED maka F dimasukan ke OPEN.
Karena hanya menghitung biaya perkiraan (h), maka biaya perkiraan dari S ke B atau biaya perkiraan dari S ke B
melalui A & D berbeda yaitu (h(B)= 1,5rb) maka parent dari B perlu diubah
yaitu D. Langkah ketiga menghasilkan OPEN = [B,C,H,F] & CLOSED = [S,A,D].
Langkah
4: B dengan biaya
terkecil (yaitu f(B) = h(B) = 1,5rb) terpilih sebagai simpul terbaik &
dipindahkan ke CLOSED. Selanjutnya, semua susesor B dibangkitkan, yaitu E
karena E belum ada di OPEN dan CLOSED maka E dimasukan ke OPEN. Langkah ini
menghasilkan OPEN = [C,E,F,H] & CLOSED = [S,A,B,D].
Langkah
5: E dengan
biaya terkecil (yaitu f(E) = h(E) = 1,5rb) terpilih sebagai simpul terbaik
& dipindahkan ke CLOSED. Selanjutnya, semua susesor E dibangkitkan, yaitu C
& F.Kedua suksesor ini sudah ada di OPEN. Karena hanya menghitung biaya
perkiraan (h), maka biaya perkiraan dari S ke C atau biaya perkiraan dari S ke
C melalui E adalah sama (yaituh(C)=3rb) oleh karena itu, parent dari C tidak
perlu diubah lagi. Langkah ini menghasilkan OPEN = [C,F,H] dan CLOSED =
[S,B,D,E]
Langkah
6: E
dengan biaya terkecil (yaitu f(E) = h(E) = 1,5rb) terpilih sebagai simpul
terbaik dan dipindahkan ke CLOSED. Selanjutnya, semua suksesor ini sudah ada di
OPEN. Karena biaya perkiraan dari S ke C atau biaya perkiraan dari S ke C
melalui E adalah sama (yaituh(C)=3rb) oleh karena itu, parent dari C tidak
perlu diubah lagi. Sedangkan biaya perkiraan dari D ke F atau biaya perkiraan
dari E ke F berbeda (yaituh(B) = 1,5rb) maka parent dari F perlu diubah yaitu
E. Langkah ini menghasilkan OPEN = [C,H,G] & CLOSED = [S,A,B,D,E,F].
Langkah berikutnya G dengan biaya terkecil
terpilih sebagai simpul terbaik. Karena simpul terbaik tersebut adalah goal.
Berarti solusi telah ditemukan. Hasil penelusuran menghasilkan
rute
S-A-B-D-E-F-G dengan total jarak 14 km. Rute yang dihasilkan ini bukanlah rute
terpendek karena masih ada rute yang lain yang lebih pendek, yaitu S-C-G dengan
total jaraknya 4,5 km. Hal ini menunjukan bahwa Greedy Best Fisrt Search “tidak
optimal”.
ð
Implementasi dari Algoritma Best First Seacrh
Best fisrt search merupakan sebuah metode pencarian heuristic
dengan cara memilih nilai terbaik dari beberapa data. Pencarian best first
search dilakukan dengan membuka semua data serta menerapkan fungsi heuristic
pada setiap pencarian untuk menghasilkan pengganti data yang telah dibuka.
Metode best firt search diimplementasikan pada aplikasi
pembelajaran perkalian matematika berbasis multimedia interaktif. Pada aplikasi
ini best first search digunakan sebagai pengukur nilai waktu terkecil pada data
hasil pengujian dengan membandingkan tiga cara perhitungan perkalian. Untuk
mendapatkan nilai waktu terkecil dari masing-masing cara dibutuhkan data hasil
pengujian pada anak tunarungu. Dari data yang didapatkan best first search
melakukan pencarian dengan membuka semua data dan memilih data yang memiliki
nilai waktu terkecil. Kemudian best first search membandingkan nilai waktu pada
tiga cara tersebut, lalu memutuskan dari pencarian tersebut data dari cara
manakah yang memiliki nilai waktu terpendek.
Aplikasi pembelajaran
perkalian matematika dapat dimanfaatkan oleh anak tunarungu sebagai media
pembelajaran alternative. Karena pada dasarnya anak tunarungu kecenderungan
memiliki permasalahan dalam belajar yang disebabkan oleh kurangnya kemampuan
untuk memahami ujaran orang, kondisi ini, sering disebabkan oleh ketidak
mampuan dalam penguasaaan pendengaran , sehingga akhirnya mereka menghindari
aktivitas berbahasa karena pendengarannya terganggu.
Sehingga dapat disimpulkan bahwa dengan pembelajaran
perkalian matematika diharapkan dapat mengoptimalkan kemampuan belajar
perkalian matematika anak tunarungu.
Blind/Un-Informes search
Pengertian Dept Limited Search
Algoritma
DLS (Dept Limited Search) adalah salah satu algoritma yang digunakan untuk
pencarian jalur. Contoh yang dibahas
kali ini adalah mengenai pencarian jalur yang melalui semua titik. Algoritma
ini merupakan variasi dari Algoritma DFS (Dept First Search), jika algoritma
DFS (Dept First Search) melakukan perhitungan (yang dimulai dengan titik
terakhir)dengan cara menghabiskan semua tingkatan/kedalaman dari sebuah titik,
maka algoritma ini memiliki batasan dimana perhitungan pada sebuah titik hanya
dihitung sampai pada kedalaman tertentu, setelah semua kemungkinan, pada
kedalaman itu sudah habis, kemudian akan dilanjutkan pada titik berikutnya.
Langkah-langkah Algoritma Dept
Limited Search:
Algoritma Dept Limited Search memberikan batas kedalaman pada
algoritma Dept First Search (Russel & Norvig , 1995). Dengan algoritma Dept
Limited Search, penelusuran Dept First Search data dibatasi sehingga tidak
melakukan penelusuran terlalu dalam. Algoritma Dept Limited Search sebaga
berikut:
ð Tetapkan node awal dengan
kedalaman = 0 dan tentukan batas kedalaman.
ð Cek apakah node adalah
node tujuan, jika benar maka proses berhenti. Jika tidak maka lanjut ke langkah
C.
ð Cek apakah kedalaman node
sama, dengan batas kedalaman yang ditentukan. Jika benar, maka lanjutkan proses
dengan menelusur hanya node-node yang berada dalam batas kedalaman yang telah
ditentukan dan belum dikunjungi dengan kembali ke langkah B. Jika tidak maka
lanjutkan ke langkah D.
ð Perluas node dan kembali
ke langkah B.
Gambaran kerja algoritma Dept Limited Search dapat
digambarkan dalam bentuk Tree. Tree merupakan sebuah graf tidak berarah dan
merupakan jaringan bersambung yang tidak memiliki untai (loop) sehingga dengan
demikian dapat disimpulkan bahwa sebuah tree dapat dibentuk dari graf sederhana
karena graf sederhana tidak memiliki self loop ataupun edge parallel. Tree
terdiri dari sekumpulan elemen. Elemen tree adalah akar atau root dan simpul.
Derajat atau degree sebuah simpul menunjukan
jumlah anak pada simpul tersebut.
Implementasi Algoritma Dept Limited Search
Penerapan algoritma dept
limited search pada hint permainan Peg Soltaire di papan permainan versi
inggris ukuran 3x3 dan triangular berukuran 4x4, 5x5, serta 7x7 , mampu menemukan
solusi yaitu sisa satu kelereng serta
mampu mengani apabila tidak menemukan solusi. Penerapan algoritma Dept Limited
Search pun mampu menampilkan semua perpindahan langkah hingga ditemukan sisa 1
kelereng. Hal ini dibuktikan dengan cara menguji 10 soal pada system. Dari
hasil pengujian 10 soal pada system, 9 soal berhasil diselesaikan dan 1 soal
gagal diselesaikan karena tidak menemukan solusi berupa 1 sisa kelereng.
Permainan peg solitaire versi
inggris dengan ukuran 3x3 dengan menggunakan penelusuran pohon Dept Limited
Search. Contoh penerapan ini menggunakan jenis soal cross atau salib yang
terdiri dari 6 kelereng yang membentuk salib.
Sistem yang telah dibangun
berdasarkan hasil penelitian ini memiliki kelebihan antara lain system mampu
menyediakan bank soal yang terdiri dari
soal-soal berekstensi txt dan dapat degenerate ke papan permainan saat soal
tersebut dipilih , system mampu menyediakan soal random dimana jumlah lubang
kosong dapat dimasukan oleh pemain, system mampu menemukan solusi dengan
menerapkan algoritma dept limited search baik pada fasilitas hint ataupun saat
menggenerate pohon solusi dan system permainan peg solitaire memiliki tiga
versi papan yaitu papan versi inggris, eropa dan triangular. Selain itu, system
ini juga memilki beberapa kelemahan yaitu system hanya mampu menyelesaikan
papan versi inggris berukuran 3x3 dan papan versi triangular dengan ukuran 4 x
4, 5 x 5, dan 7 x 7, penggunaan algoritma dept limited search murni dan metode
iterative menyebabkan system butuh waktu yang lama untuk menemukan solusi untuk
papan berukuran besar yaitu papan versi inggris ukuran 5 x 5 dan 7 x 7 serta
papan versi eropa dengan ukuran 3 x 3, 4 x 4, dan 7 x 7, serta fasilitas hint
membutuhkan waktu yang cukup dalam menampilkan solusi apabila soal memiliki
kesulitan yang cukup tinggi.
Sumber Referensi:
rapihkan kembali
BalasHapus