Menyelesaikan Masalah Melalui Pencarian

1.  Agent pemecah permasalahan

Dalam membangun sebuah sistem AI, perlu dipertimbangkan 4 hal, yaitu:

1)      Mendefinisikan masalah dengan tepat. Pendefinisian ini mencakup deskripsi masalah dengan baik

2)      Menganalisis masalah tersebut serta mencari beberapa teknik penyelesaian masalah yang sesuai

3)      Mempresentasikan pengetahuan yang perlu untuk menyelesaikan masalah tersebut

4)      Memilih teknik penyelesaian masalah terbaik.

Dalam menentukan teknik penyelesaian terbaik dalam AI memang tidak mudah, untuk itu ada beberapa teknik penyelesaian masalah yang perlu kita pahami, antara lain:

1. Searching

Teknik penyelesaian masalah yang mempresentasikan masalah kedalam ruang keadaan (state) dan secara sistematis melakukan pembangkitan dan pengujian state-state dari initial state sampai ditemukan suatu goal state.

2. Reasoning

Teknik penyelesaian masalah yang mempresentasikan masalah kedalam logic (Mathematical Tools yang digunakan untuk merepresentasikan dan memanipulasi fakta dan aturan)

3. Planning

Memecah masalah dalam sub-sub masalah yang lebih kecil, menyelesaikan sub-sub masalah satu demi satu, kemudian menggabungkan solusi-solusi dari sub masalah tersebut menjadi sebuah solusi lengkap.

4. Learning

Program komputer yang secara otomatis sanggup belajar dan meningkatkan performancenya  melalui pengalaman

2.  Pencarian sebagai solusi pemecahan masalah

Untuk membangun system yang mampu menyelesaikan masalah, perlu dipertimbangkan 4 hal :

1.  Mendefinisikan masalah dengan tepat

ü  Spesifikasi yang tepat mengenai keadaan awal

ü  Solusi yang diharapkan

2.  Menganalisis masalah serta mencari beberapa teknik penyelesaian masalah yang sesuai

3.  Merepresentasikan pengetahuan yang perlu untuk menyelesaikan masalah

4.  Memilih teknik penyelesaian masalah yang terbaik

Posisi Awal : Selalu sama

Aturan Legal :

Aturan – aturan sangat berguna untuk menentukan gerak suatu bidak

Untuk mempermudah,

Horisontal = Huruf (a,b,c,d,e,f,g,h)

Vertical = Angka (1,2,3,4,5,6,7,8)

3.  strategi pencarian yang tidak terbentuk

·         Breadth-first search 

Breadth-first search adalah algoritma yang melakukan pencarian secara melebar yang mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut terlebih dahulu. Selanjutnya, simpul yang belum dikunjungi dan bertetangga dengan simpulsimpul yang tadi dikunjungi , demikian seterusnya. Jika graf berbentuk pohon berakar, maka semua simpul pada aras d dikunjungi lebih dahulu sebelum simpul-simpul pad aras d+1.

Algoritma ini memerlukan sebuah antrian q untuk menyimpan simpul yang telah dikunjungi. Simpulsimpul ini diperlukan sebagai acuan untuk mengunjungi simpul-simpul yang bertetanggaan dengannya. Tiap simpul yang telah dikunjungu masuk ke dalam antrian hanya satu kali. Algoritma ini juga membutuhkan table Boolean untuk menyimpan simpul yang te lah dikunjungi sehingga tidak ada simpul yang dikunjungi lebih dari satu kali.

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

·         Depth First Search

Algoritma DFS (Depth First 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 mirip dengan Algoritma BFS (Breadth First Search) yang sudah dijelaskan sebelumnya. Jika Algoritma BFS (Breadth First Search) melakukan perhitungan secara terurut dari urutan pertama sampai urutan terakhir, maka algoritma ini melakukan kebalikannya, yaitu melakukan perhitungan secara terurut dari urutan terakhir. Setelah menghabiskan semua kemungkinan dari titik terakhir, barulah mundur ke titik-titik sebelumnya sampai pada titik pertama.

·         Depth Limited Search

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.

·         iterative deepening depth-first search

Dalam ilmu komputer , pencarian pendalaman iteratif atau lebih spesifik iterative deepening depth-first search(IDS atau IDDFS) adalah strategi pencarian ruang / grafik negara di mana versi kedalaman kedalaman pencarian kedalaman pertama dijalankan berulang kali dengan kedalaman yang meningkat. batas sampai tujuan ditemukan. IDDFS setara dengan pencarian pertama , tapi menggunakan lebih sedikit memori; Pada setiap iterasi, ia mengunjungi simpul -simpul di pohon pencarian dengan urutan yang sama seperti pencarian pertama-tama , namun urutan kumulatif dimana simpul pertama kali dikunjungi secara efektif adalah keluasan-pertama.

·         Bi-Directional Search

Pencarian dengan metode bidirectional search adalah dengan menjalankan dua pencarian, pencarian maju (dari start ke goal) dan pencarian mundur (dari goal ke start). Ketika dua arah pencarian telah membangkitkan simpul yang sama, maka solusi telah ditemukan, yaitu dengan cara menggabungkan kedua jalur yang bertemu.

Ada beberapa masalah sebelum memustuskan untuk menngunakan strategi Bi-directional Search, yaitu:

1.       Bagaimana kalau terdapat beberapa node tujuan yang berbeda? 

2.       Terdapat perhitungan yang tidak efisien untuk selalu mengecek apakah node baruyang dibangkitkan sudah pernah dibangkitkan oleh pencarian dari arah yang berlawanan.

3.       Bagaimana menentukan strategi pencarian untuk kedua arah tersebut? Misalnya dari arah sumber dan dari arah tujuan digunakan BFS.

sumber :

http://tiindonesia.blogspot.co.id/2013/02/teknik-pemecahan-masalah-dalam-ai.html

https://aiukswkelasekelompok4a.wordpress.com/2009/02/06/masalah-ruang-keadaan-dan-pencarian/

http://jakaseptiadi.blogspot.co.id/2015/09/bi-directional-search-bds-depth-limited.html