Penyelesaian Masalah Melalui Proses Pencarian/ Searching

AGEN PEMECAHAN MASALAH
a. Graf Keadaan

b. Pohon Pelacakan

c. Pohon AND/OR

a. Graf Keadaan

Graf Keadaan

Pada graf keadaan dengan arah di atas:

>> Ada 4 lintasan yang mencapai tujuan, yakni :

1. M-A-B-C-E-T

2. M-A-B-C-E-H-T

3. M-D-C-E-T

4. M-D-C-E-H-T

>> Ada 5 lintasan yang tidak mencapai tujuan yakni :

1. M-A-B-C-E-F-G

2. M-A-B-C-E-I-J

3. M-D-C-E-F-G

4. M-D-C-E-I-J

5. M-D-I-J

•Graf Keadaan

Kelemahan graf berarah:

>> Memungkinkan terjadi siklus (perulangan) seandainya graf tidak memiliki arah.

>> Sulit mencapai tujuan

b. Pohon Pelacakan

Untuk menghindari kemungkinan adanya proses pelacakan suatu node secara berulang, maka digunakan struktur pohon

à Keuntungan pohon pelacakan:

>> Tujuan tercapai

>> Tidak terjadi siklus

à Kelemahan pohon pelacakan:

>> Proses pelacakan agak lama (perlu waktu

lama)

c. Pohon AND/OR

Kelemahan pada teknik pohon pelacakan dapat diselesaikan dengan teknik pelacakan menggunakan pohon AND/OR.

Metode Pencarian dan Pelacakan

Pencarian sebagai solusi masalah

Hal penting dalam menentukan keberhasilan sistem cerdasadalah kesuksesan dalam pencarian. Pencarian = suatu proses mencari solusi dari suatu permasalahan melalui sekumpulan kemungkinan ruang keadaan (state space). Ruang keadaan = merupakan suatu ruang yang berisi semua keadaan yang mungkin.

• Untuk mengukur perfomansi metode pencarian, terdapat empat kriteria yang dapat digunakan :

- Completeness : apakah metode tsb menjamin penemuan solusi jika solusinya memang ada?

- Time complexity : berapa lama waktu yang diperlukan?

- Space complexity : berapa banyak memori yg diperlukan

- Optimality : apakah metode tsb menjamin menemukan

solusi yg terbaik jika terdapat beberapa solusi berbeda?

. Best First Search

• Metode best first search merupakan kombinasi dari metode depth first search & breadth first search dengan mengambil kelebihan dari kedua metode tersebut. Hill climbing tidak diperbolehkan untuk kembali ke node yang lebih rendah meskipun node tersebut memiliki nilai heuristik lebih baik. Pada best first search, pencarian diperbolehkan mengunjungi node yang lebih rendah, jika ternyata node di level lebih tinggi memiliki nilai heuristik lebih buruk. Untuk mengimplementasikan metode ini, dibutuhkan 2 antrian yang berisi node-node, yaitu :

• OPEN : berisi node-node yang sudah dibangkitkan, sudah memiliki fungsi heuristik namun belum diuji. Umumnya berupa antrian berprioritas yang berisi elemen-elemen dengan nilai heuristik tertinggi.

• CLOSED : berisi node-node yang sudah diuji.

.UCS (Uniform Cost Search)
UCS (Uniform Sost Search) adalah perpaduan antara BFS dan DFS. Pada UCS, teknik pencariannya memperhatikan cost/jarak antara 1 node ke node lain.
Berikut ini adalah ilustrasinya :

Pada permasalahan diatas telah ditentukan jarak antara node. Maka pada model UCS, teknik yang akan dilakukan adalah membuka node yang memiliki nilai/cost antar node yang terendah.

pada gambar diatas jika kita buka :

c = 10

b = 20

a = 10

Karena nilai c dan a sama maka teserah mau membuka yang mana lebih dahulu.

Seandainya kita membuka c maka kita teruskan pencariannya, lalu kita buka :

d = 10+5 =15

DFS (Depth-first Search)
DFS (Depth-first Search) sering disebut juga pencarian mendalam. Sesuai dengan namanya “pencarian mendalam”, DFS tidak mencari solusi per level, namun mencari pada kedalaman sebelah kiri terlebih dahulu, kemudian bila belum ditemuakn “goal”nya dilanjutkan ke sisi sebelah kanan dan seterusnya sampai ditemukan target/goal.
Dengan menggunakan permasalahan yang sama dengan penjelasan di awal tadi, maka pada model DFS akan di dapatkan solusi seperti gambar di bawah ini.
 Jadi, solusi node yang di lalui pada DFS adalah a,b,e,h.
DFS memiliki beberapa keuntungan,yaitu memori yang di gunakan tidak terlalu banyak karena tidak membuka semua node.

e = 10+40 = 50 (mencapai goal, namun nilai cost nya dirasa masih terlalu besar)

Maka kita buka node d, lalu akan diperoleh hasil :

e = 10+5+30 = 45 (nilai pada pencarian ini pun terasa masih terlau besar) maka dari itu kita buka node yang kecil di awal tadi yaitu node a.

Setelah kita buka node a, maka akan di dapat hasil :

e = 10 + 20 = 30 (di dapatkan goal dengan solusi terbaik)

Dari kasus diatas, dapat kita lihat bahwa ada banyak cara unuk mendapatkan solusi. Namun dari berbagai macam penyelesaian kasus, kita dapat mencari solusi yang paling optimal dan ini lah ke unggulan dari model UCS.

Algoritma DLS (Depth 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 (Depth First Search) yang sudah dijelaskan sebelumnya. Jika Algoritma DFS (Depth 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.

Sumber :
http://xninexozar.blogspot.co.id/
http://aditya291296.blogspot.co.id/2017/09/pencarian-berbentuk-dan-eksplorasi.html