Masalah, Ruang Keadaan dan Pencarian

Bab II

Masalah, Ruang Keadaan dan Pencarian

Dalam materi ini kelompok kami membahas tentang bagaimana menganalisis suatu masalah,keadaan yang mungkin terjadi serta pencarian penyelesaian suatu masalah dalam membuat project yang berkaitan dengan kecerdasan buatan.

Masalah, Ruang Keadaan dan Pencarian
SISTEM AI
Input->Computer->output
Masalah->Computer->Jawaban
Pertanyaan->computer->Solusi

MASALAH
untuk membangun sistem yang mampu untuk menyelesaikan suatu masalah perlu mempertimbangkan 4 hal yaitu :
–Mendefinisikan masalah dengan tepat
• Spesifikasi yang tepat mengenai keadaan awal
• Solusi yang diharapkan
–Menganalisis masalah serta mencari beberapa teknik
penyelesaian masalah yang sesuai
–Merepresentasikan pengetahuan yang perlu untuk
menyelesaikan masalah
–Memilih teknik penyelesaian masalah yang terbaik

RUANG KEADAAN (State Space)
Suatu ruang yang berisi semua keadaan yang mungkin sehingga secara umum untuk mendeskripsikan masalah yang baik harus :
• Mendefinisikan suatu ruang keadaan
• Menetapkan satu atau lebih keadaan awal
• Menetapkan satu atau lebih tujuan
• Menetapkan kumpulan aturan

Ada beberapa cara untuk mempresentasikan Ruang keadan :
• Graph Keadaan
1. Terdiri dari node-node yang menunjukkan
keadaan yaitu keadaan awal dan keadaan baru
yang akan dicapai dengan menggunakan
operator
2. Node-node saling dihubungkan dengan
menggunakan arc (busur) yang diberi panah
untuk menunjukkan arah




Contoh lintasan dari M ke T
– M-A-B-C-E-T, M-A-B-C-E-H-T, M-D-C-E-T, M-D-C-E-H-T
Yang tidak sampai
– M-A-B-C-E-F-G, M-A-B-C-E-I-J, M-D-C-E-F-G, M-D-C-E-I-J, M-D-I-J


• Pohon Pelacakan


Keuntungan pohon pelacakan:
>> Tujuan tercapai
>> Tidak terjadi siklus
Kelemahan pohon pelacakan:
>> Proses pelacakan agak lama (perlu waktu lama)



METODE PENCARIAN dan PELACAKAN
Ada 2 teknik pencarian dan pelacakan, yakni:
1. Pencarian Buta (Blind Search)
a. Pencarian Melebar Pertama (Breadth-First Search)
b. Pencarian Mendalam Pertama (Depth-First Search)
2. Pencarian terbimbing (heuristic search)
a. Pembangkit & Pengujian (generate and test)
b. Pendakian Bukit (Hill climbing)
b.1 Simple Hill Climbing
b.2 Steepest-Ascent Hill Climbing
c. Pencarian Terbaik Pertama (Best First Search)
c.1 OR Graph
c.2 Algoritma A*
d. Simulated Annealing