POKOK BAHASAN:
./Macam-macamAlgoritmaPencarian
./ Mendefinisikan Permasalahan sebagai Ruang Keadaan
./ Pencarian Buta (Depth First, Breadth First, Hill Climbing, Beam, Best First)
./ Pencarian Optimal (British Musium, Branch and Bound, Dynamic Programming, A*)
./ Game 2 pemain (Minimax, Alpha Beta Prunning)
TUJUAN BELAJAR:
Setelah mempelajari bab ini, mahasiswa diharapkan mampu:
./ Menjelaskan permasalahan kombinatorial, representasinya dan konsekuensinya.
./ Memilih algoritma
pencarian buta yang tepat untuk
sebuah permasalahan, mengimplementasikan dan karakteristiknya pada kompleksitas waktu dan ruang.
./ Memilih Algoritma Pencarian Heuristic yang tepat dan mengimplementasikan untuk sebuah permasalahan.
./ Menjelaskan kondisi
apa yang dijamin oleh sebuah algoritma heuristic sebagai solusi optimal.
./ Mengimplementasikan pencarian
minimax dan
alpha-beta pruning untuk beberapa game 2 pemain.
4.1 MACAM-MACAM ALGORITMA PENCARIAN
Permasalahan pencarian adalah merupakan yang sering dijumpai oleh peneliti
di bidang Kecerdasan Buatan. Permasalahan ini merupakan hal penting dalam menentukan keberhasilan system kecerdasan buatan. Dalam bab ini akan dipelajari 3 bagian dalam metode pencarian, yang pertama adalah metode yang sederhana yang hanya berusaha mencari kemungkinan penyelesaian. Metode yang termasuk pada bagian ini adalah dept-first search, hill climbing, breadth-first search, beam search dan best-first search.
Yang kedua, kita akan mempelajari metode yang lebih kompleks yang akan mencari jarak terpendek. Metode ini adalah British Museum Procedure, Branch and Bound, Dynamic Programming dan A*. Metode-metode ini digunakan pada saat harga perjalanan untuk mencari kemungkinan menjadi perhitungan
Yang ketiga, kita akan mempelajari beberapa prosedur/metode yang kita terapkan saat kita berhadapan dengan musuh.
Prosedur ini adalah minimax search, alpha-beta prunning. Metode ini banyak digunakan pada program-program permainan seperti catur
dsb.
Dalam gambar 4.1 terdapat bagan untuk
Metode Searching.
 | |||||||||||||||||||||||||||||||||||||||||||
Metode pencarian dikatakan penting untuk menyelesaikan permasalahan karena setiap state(keadaan) menggambarkan langkah-langkah untuk menyelesaikan permasalahan.
Metode pencarian dikatakan penting untuk perencanaan karena dalam sebuah permainan akan menentukan apa yang harus dilakukan, dimana setiap state menggambarkan kemungkinan posisi pada suatu saat.
Metode pencarian adalah bagian dari kesimpulan, dimana setiap state menggambarkan hipotesis dalam sebuah rangkaian deduktif.
4.1 MENDEFINISIKAN MASALAH SEBAGAI SUATU RUANG KEADAAN
Secara umum, untuk mendeskripsikan suatu permasalahan dengan baik harus:
1
Mendefinisikan suatu ruang keadaan.
2
Menerapkan satu atau lebih keadaan awal.
3
Menetapkan satu atau lebih tujuan.
4
Menetapkan kumpulan aturan.
Contoh 4.2.1
: petani, serigala, angsa dan padi
Contoh ini kita ambil dari bab 4. Permasalahan petani, serigala, angsa dan padi. Seorang petani ingin memindah dirinya
sendiri,
seekor serigala,
seekor
angsa
gemuk, dan seikat padi yang berisi menyeberangi sungai. Sayangnya, perahunya sangat terbatas; dia hanya dapat membawa satu objek
dalam
satu penyeberangan. Dan lagi,
dia
tidak
bisa meninggalkan serigala dan angsa dalam satu
tempat,
karena
serigala akan memangsa angsa. Demikian pula dia tidak bisa meninggalkan angsa dengan padi dalam satu tempat.
Dari permasalahan di atas untuk mendefinisikan masalah sebagai ruang keadaan kita tentukan langkah-langkah sebagai berikut:
A.
Tdentifikasi ruang keadaan.
Permasalahan ini dapat dilambangkan dengan (JumlahSerigala, JumlahAngsa, JumlahPadi, JumlahPetani). Sebagai contoh Daerah asal (0,1,1,1) berarti pada daerah asal tidak ada serigala, ada angsa, ada padi dan ada petani
tani.
A. Keadaan awal dan tujuan.
•
Keadaan awal, pada kedua seberang sungai:
o
Daerah asal: (1,1,1,1)
o
Daerah seberang: (0,0,0,0)
•
Tujuan, pada kedua seberang sungai:
o
Daerah asal: (0,0,0,0)
o
Daerah seberang: (1,1,1,1)
B. Aturan-aturan
Aturan-aturan dapat digambarkan seperti pada tabel 4.1.
Tabel 4.1 Aturan-aturan masalah Petani dan Barang Bawaannya
Salah satu solusi yang bisa ditemukan dapat dilihat pada tabel 4.2.
Tabel 4.2 Contoh
Solusi Masalah Petani, Serigala, Angsa, dan Padi
Contoh 4.2.2: Masalah teko air
Ada 2 buah teko masing-masing berkapasitas 4 galon (teko A) dan 3 galon (teko B). Tidak ada tanda yang menunjukkan batas ukuran pada
kedua teko tersebut. Permasalahannya : Bagaimanakah kita dapat mengisikan tepat 2 galon air ke dalam teko yang berkapasitas 4 galon?
Dari permasalahan di atas untuk mendefinisikan masalah sebagai ruang keadaan kita tentukan langkah-langkah sebagai berikut:
A. Tdentifikasi ruang keadaan.
Permasalahan ini dapat dilambangkan dengan (x,y). Dimana:
o
x = air yang diisikan pada teko A
o
y = air yang diisikan pada teko B
B. Keadaan awal dan tujuan.
•
Keadaan awal, kedua teko dalam keadaan kosong: (0,0).
•
Tujuan, keadaan dimana pada teko 4 galon berisi tepat 2 galon air: (2,n) untuk sembarang n.
C. Aturan-aturan
Aturan-aturan dapat digambarkan seperti pada tabel 4.2.
|
0 komentar:
Posting Komentar