Penyelesaian Masalah melalui proses Pencarian / Searching

Nama : Dimas Bayu Gumelar

NPM : 11115924

Kelas: 3KA10

Dosen : ESSY MALAYS SARI SAKTI

Pendefinisian Masalah Sebagai Pencarian Ruang Keadaan 

Masalah utama dalam membangun sistem berbasis AI adalah bagaimana

mengkonversikan situasi yang diberikan ke dalam situasi lain yang diinginkan

menggunakan sekumpulan operasi tertentu.

A Water Jug Problem 

Anda diberi dua buah gelas, yang satu ukuran 4 galon dan yang lain 3 galon. Kedua gelas

tidak memiliki skala ukuran. Terdapat pompa yang dapat digunakan untuk mengisi gelas

dengan air. Bagaimana anda mendapatkan tepat 2 galon air di dalam gelas 4 ukuran

galon?

Ruang masalah untuk masalah di atas dapat digambarkan sebagai himpunan pasangan

bilangan bulat (x,y) yang terurut, sedemikian hingga x = 0, 1, 2, 3, atau 4  dan y = 0, 1, 2,

atau 3; x menyatakan jumlah air dalam gelas ukuran 4 galon, dan y menyatakan jumlah

air dalam gelas ukuran 3 galon. Keadaan mula-mula adalah (0,0). State tujuan adalah

(2,n) untuk setiap nilai n. Operator-opeartor (aturan produksi) yang digunakan untuk memecahkan masalah terlihat pada gambar 2.1.

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).

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. Masing-masing metoda tersebut mempunyai karakteristik

yang berbeda. 

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? 

   

1. Breadth-First Search (BFS)

Pencarian dilakukan pada semua node dalam setiap level secara berurutan dari kiri ke

kanan. Jika pada satu level belum ditemukan solusi, maka pencarian dilanjutkan pada

level berikutnya. Demikian seterusnya sampai ditemukan solusi. Dengan strategi ini,

maka dapat dijamin bahwa solusi yang ditemukan adalah yang paling baik (Optimal).

Tetapi BFS harus menyimpan semua node yang pernah dibangkitkan. Hal ini harus

dilakukan untuk penelusuran balik jika solusi sudah ditemukan. Gambar 2.4

mengilustrasikan pembangkitan pohon BFS untuk masalah Water Jug. Pembangkitan

suksesor dari suatu node bergantung pada urutan dari Aturan Produksi yang dibuat

(lihat gambar 2.2). Jika urutan dari aturan 4 ditukar dengan aturan 5, maka pohon

BFS yang dibangkitkan juga akan berubah.

2. Uniform Cost Search (UCS)

Konsepnya hampir sama dengan BFS, bedanya adalah bahwa BFS menggunakan

urutan level dari yang paling rendah sampai yang paling tinggi. Sedangkan UCS

menggunakan harga terendah yang dihitung berdasarkan harga dari node asal menuju

ke node tersebut atau biasa dilambangkan sebagai g(n). BFS adalah juga UCS jika

harga g(n) = DEPTH(n). 

Syarat yang harus dipenuhi oleh pohon UCS: g(SUCCESSOR(n)) >= g(n) untuk

setiap node n. Jika syarat ini tidak dipenuhi maka UCS tidak bisa dipakai.

Depth-First Search (DFS)

3. 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).

4. Depth-Limited Search (DLS) 

Mengatasi kelemahan DFS (tidak complete) dengan membatasi kedalaman

maksimum dari suatu jalur solusi. Tetapi harus diketahui atau ada batasan dari sistem

tentang level maksimum. Jika batasan kedalaman terlalu kecil, DLS tidak complete. 

5. Iterative-Deepening Depth-First Search (IDS) 

Gambar 2.5 Penelusuran Depth First Search untuk Water Jug Problem. 

Merupakan metode yang berusaha menggabungkan keuntungan BFS (Complete dan

Optimal) dengan keuntungan DFS (Space Complexity yang rendah). Tetapi

konsekuensinya adalah Time Complexity-nya menjadi tinggi.

6. Bi-Directional Search

Pada setiap iterasi, pencarian dilakukan dari dua arah: dari node asal (start) dan dari

node tujuan (goal). Ketika dua arah pencarian membangkitkan node yang sama, maka

solusi telah ditemukan, dengan cara menggabungkan kedua jalur yang bertemu. Ada

beberapa masalah sebelum memustuskan untuk menngunakan strategi Bi-directional

Search, yaitu:  

• Bagaimana kalau terdapat beberapa node tujuan yang berbeda?

• Terdapat perhitungan yang tidak efisien untuk selalu mengecek apakah node baru 

yang dibangkitkan sudah pernah dibangkitkan oleh pencarian dari arah yang

berlawanan.  

• Bagaimana menentukan strategi pencarian untuk kedua arah tersebut? Misalnya

dari arah sumber dan dari arah tujuan digunakan BFS.

Daftar Pustaka

• Suyanto, ST.2008.Intelijensia Buatan.Bandung