Depth-First Search (DFS)

Pencarian dilakukan pada satu node dalam setiap level dari yang paling kiri. Jika pada
level yang paling dalam, solusi belum ditemukan, maka pencarian dilanjutkan pada node
sebelah kanan. Node yang kiri dapat dihapus dari memori. Jika pada level yang paling
dalam tidak ditemukan solusi, maka pencarian dilanjutkan pada level sebelumnya.
Demikian seterusnya sampai ditemukan solusi. Jika solusi ditemukan maka tidak
diperlukan proses backtracking (penelusuran balik untuk mendapatkan jalur yang
dinginkan).

Kelebihan DFS adalah:
• Pemakain memori hanya sedikit, berbeda jauh dengan BFS yang harus
menyimpan semua node yang pernah dibangkitkan.
• Jika solusi yang dicari berada pada level yang dalam dan paling kiri, maka DFS
akan menemukannya secara cepat.

Kelemahan DFS adalah:
• Jika pohon yang dibangkitkan mempunyai level yang dalam (tak terhingga), maka
tidak ada jaminan untuk menemukan solusi (Tidak Complete).
• Jika terdapat lebih dari satu solusi yang sama tetapi berada pada level yang
berbeda, maka pada DFS tidak ada jaminan untuk menemukan solusi yang paling
baik (Tidak Optimal).

Strategi Pencarian

Terdapat empat kriteria dalam strategi pencarian, yaitu:

• Completeness: Apakah strategi tersebut menjamin penemuan solusi jika
solusinya memang ada?
• Time complexity: Berapa lama waktu yang diperlukan?
• Space complexity: Berapa banyak memori yang diperlukan?
• Optimality: Apakah strategi tersebut menemukan solusi yang paling baik jika
terdapat beberapa solusi berbeda pada permasalahan yang ada?

Strategi Kontrol

Syarat-syarat strategi kontrol:
• cause motion. Perhatikan kembali water jug problem. Jika kita
mengimplementasikan strategi kontrol sederhana dengan selalu memilih aturan
pertama pada daftar 12 aturan yang telah dibuat, maka kita tidak akan pernah
memecahkan masalah. Strategi kontrol yang tidak menyebabkan motion tidak
akan pernah mencapai solusi.
• Systematic. Strategi kontrol sederhana yang lain untuk water jug problem: pada
setiap siklus, pilih secara random aturan-aturan yang dapat diaplikasikan. Strategi
ini lebih baik dari yang pertama, karena menyebabkan motion. Pada akhirnya
strategi tersebut akan mencapai solusi. Tetapi mungkin kita akan mengunjungi
beberapa state yang sama selama proses tersebut dan mungkin menggunakan
lebih banyak langkah dari jumlah langkah yang diperlukan. Hal ini disebabkan
strategi kontrol tersebut tidak sistematik. Beberapa strategi kontrol yang
sistematik telah diusulkan, yang biasa disebut sebagai metoda-metoda dalam
teknik searching. Di bab ini, akan dibahas enam metoda, yaitu Breadth First
Search, Uniform Cost Search, Depth First Search, Depth-Limited Search,
Iterative-Deepening Depth-First Search, dan Bi-directional search. Masingmasing
metoda tersebut mempunyai karakteristik yang berbeda.

Sistem Produksi

Sistem produksi terdiri dari:

• Himpunan aturan, masing-masing terdiri dari sisi kiri (pola) yang menentukan
kemampuan aplikasi dari aturan tersebut dan sisi kanan yang menggambarkan
operasi yang dilalukan jika aturan dilaksanakan.
• Satu atau lebih pengetahuan atau basis data yang berisi informasi apapun untuk
tugas tertentu. Beberapa bagian basis data bisa permanen, dan bagian yang lain
bisa hanya merupakan solusi untuk masalah saat ini. Informasi dalam basis data
ini disusun secara tepat.
• Strategi kontrol yang menspesifikasikan urutan dimana aturan akan
dibandingkan dengan basis data dan menspesifikasikan cara pemecahan masalah
yang timbul ketika beberapa aturan sesuai sekaligus pada waktu yang sama.
• A rule applier (pengaplikasi aturan).

Karakteristik Masalah Dalam AI

• Apakah masalahnya dapat didekomposisi menjadi himpunan sub masalah yang (hampir) independen lebih kecil atau lebih mudah ?
• Dapatkah langkah penyelesaian diacuhkan paling tidak dibatalkan ketika dapat
dibuktikan hal tersebut tidak bijaksana ?
• Apakah universe masalahnya dapat diprediksi ?
• Apakah solusi yang baik dari masalah tertentu jelas tanpa membandingkan
dengan seluruh solusi lain yang mungkin ?
• Apakah solusi yang diinginkan sebuah keadaaan dari dunia atau sebuah jalur dari
keadaan ?
• Apa peran dari pengetahuan ?
• Apakah pekerjaan memerlukan interakasi dengan manusia ?

Penyelesaian Masalah berdasarkan teknik AI

Empat hal untuk membangun sistem atau memecahkan masalah tertentu :
1. Definisikan masalah dengan jelas
2. Analisis masalah
3. Kumpulkan dan representasikan knowledge
4. Pilih teknik pemecah masalah terbaik dan gunakan untuk masalah tertentu

Mendefinisikan Masalah sebagai “State Space Search” (SSS)
Misalnya permainan catur , maka SSS nya adalah :
Menspesifikasikan posisi awal dari papan catur
Peraturan (rules) yang mendefinisikan langkah-langkah yang legal
Posisi papan yang merepresentasikan pemenang dari satu sisi atau sisi lainnya.
Tujuan (Goal) dari permainan adalah : memenangkan permainan.

Penyelesaian Masalah berdasarkan teknik AI

Empat hal untuk membangun sistem atau memecahkan masalah tertentu :
1. Definisikan masalah dengan jelas
2. Analisis masalah
3. Kumpulkan dan representasikan knowledge
4. Pilih teknik pemecah masalah terbaik dan gunakan untuk masalah tertentu

Mendefinisikan Masalah sebagai “State Space Search” (SSS)
Misalnya permainan catur , maka SSS nya adalah :
Menspesifikasikan posisi awal dari papan catur
Peraturan (rules) yang mendefinisikan langkah-langkah yang legal
Posisi papan yang merepresentasikan pemenang dari satu sisi atau sisi lainnya.
Tujuan (Goal) dari permainan adalah : memenangkan permainan.