Menyelesaikan Malasalah Melalui Proses Pencarian

 

Terdapat banyak metode yang telah diusulkan. Semua metode yang ada dapat dibedakan ke dalam 2 jenis : 

• Pencarian buta / tanpa informasi (blind / un-informed search) 
• Pencarian heuristik / dengan informasi (heuristic atau informed search) setiap metode mempunyai karakteristik yang berbeda-beda dengan kelebihan dan kekurangan masing-masing. 

 

Untuk mengukur performansi metode pencarian, terdapat 4 kriteria yang digunakan : 

1. Completeness : Apakah metode tersebut menjamin penemuan solusi jika solusinya memang ada? 

2. Time complexity : Berapa lama waktu yang diperlukan ? 

3. Space complexity : berapa banyak memori yang diperlukan ? 

4. Optimality : Apakah metode tersebut menjamin menemukan solusi yang terbaik jika terdapat beberapa solusi yang berbeda ?

 

Heuristic Searching Sebagai Dasar dari Kecerdasan Buatan 

• Para peneliti awal kecerdasan buatan menitik beratkan pada penyelesaianmasalah yang tidak menggunakan metoda komputasi konvensional. 
• Hal ini disebabkan metoda pemecahan masalah konvensional tidak dapat lagi digunakan.

 

INTELLIGENT AGENT 

 Menurut Okamoto & Takaoka (1997): 

Agent dapat dipandang sebagai sebuah objek yang mempunyai tujuan dan bersifat autonomous (memberdayakan resourcenya sendiri) untuk memecahkan suatu permasalahan melalui interaksi seperti kolaborasi, kompetisi, negosiasi, dsb 

• Agent = sesuatu yang seolah-olah merasakan sesuatu dari lingkungannya melalui sensor dan memberikan aksi balasan kepada lingkungan tersebut melalui effector. Multi agent = kumpulan dari beberapa agent yang berada pada lingkungan yang sama 
• Human agent = agent yang dibuat menyerupai manusia memiliki mata, telinga dan organ lain sebagai sensor, serta tangan, kaki, mulut, dan bagian tubuh lain sebagai effector.
• Sebuah agent robot menggunakan kamera dan sinar infrared dalam range tertentu sebagai sensor dan berbagai motor (mesin) sebagai effector • Berikut diagram interaksi agent dengan lingkungan melalui sensor dan effector 

Breadth-first Search 

• Breadth-first search (BFS) melakukan proses searching pada semua node yang berada pada level atau hirarki yang sama terlebih dahulu sebelum melanjutkan proses searching pada node di level berikutnya. 

Urutan proses searching BFS ditunjukkan dalam Gambar 1.6 adalah: A,B,C,D,E,F,

Depth-first Search 

• Depth-first search (DFS) adalah proses searching sistematis buta yang melakukan ekpansi sebuah path (jalur) menuju penyelesaian masalah sebelum melakukan ekplorasi terhadap path yang lain. 
• Proses searching mengikuti sebuah path tunggal sampai menemukan goal atau dead end. 
• Apabila proses searching menemukan dead-end, DFS akan melakukan penelusuran balik ke node terakhir untuk melihat apakah node tersebut memiliki path cabang yang belum dieksplorasi. 

Kelebihan DFS adalah: 

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

 

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.

Diasumsikan ada 5 titik yang harus dilalui semuanya, yaitu A,B,C,D,E

semua titik tidak terhubung secara langsung dengan titik-titik lainnya, melainkan hanya melalui jalur tertentu saja

setiap jalur juga memiliki biaya sendiri-sendiri

maka tentukan jalur yang harus diambil untuk mengelilingi semua titik yang ada

Diasumsikan data jalur yang tersedia adalah sebagai berikut

 

Uniform Cost Search

Uniform Cost Search adalah algoritma Seach Tree (graph) yang digunakan untuk menyelesaikan beberapa persoalan . Algoritma ini memulai pencarian dari root node, kemudian dilanjutkan ke node-node selanjutnya. Dimana node tersebut dipilih yang memilki harga (cost) terkecil dari root node. Algoritma ini merupakan modifikasi dari Bread First Search (BFS).

Sumber : 

lintang.staff.gunadarma.ac.id/Downloads/files/44491/MetodePencarian_BFSDFS.pdf