ARTIFICIAL INTELLIGENCE

 MASALAH DAN RUANG MASALAH

1. Bentuk solusi yang mungkin. Untuk beberapa masalah, ini berarti membentuk poin terpisah dari area permasalahan. Pada masalah lain, ini berarti membentuk jalur dari stata awal. 

2. Lakukan test untuk melihat apakah poin yang ditemui adalah solusi dengan membandingkan poin yang dipilih atau poin terakhir dari jalur yang dipilih dengan kumpulan stata tujuan 
3. Jika solusi sudah ditemukan, quit. Jika belum kembali ke langkah 1.

Contoh kasus TSP 

Sebuah rute yng harus dilewati seorang sales dimana sales tersebut harus merlewati setiap kota tepat sekali. Terdapat 4 kota, dengan jarak masing-masing kota AB=2, AC=4, AD=1, BC=5, BD=3, CD=3.

Tujuannya adalah mencari jarak terpendek bagi sales untuk mengunjungi semua kota sekali. Penyelesaian menggunakan generate-test adalah dengan membangkitkan solusisolusi yang mungkin ada sesuai permasalahan yang dihadapi oleh sales tersebut. Kombinasi abjad sebagai solusi yang mungkin adalah n! = 4! = 24. Tujuannya adalah mencari solusi dengan panjang terpendek. 

KONSEP PENCARIAN

Pencarian atau pelacakan merupakan salah satu teknik untuk menyelesaikan permasalahan dalam bidang kecerdasan buatan. Teknik dasar pencarian masalah memberikan suatu kunci bagi banyak sejarah penyelesaian yang penting dalam bidang kecerdasan buatan. Contoh beberapa aplikasi yang menggunakan teknik pencarian yaitu : 

•Masalah routing (travelling salesman problem) 

•Parsing bahasa dan interprestasinya 

•Permainan 

•logika pemrograman (pencarian fakta dan implikasinya) 

•Pengenalan pola 

•Sistem pakar berbasis kaidah (rule based expert system)

METODE HEURISTIK

Pencarian heuristic adalah metode yang sangat umum yang dapat diterapkan dalam begitu banyak masalah, meliputi begitu banyak variasi teknik yang spesifik, dimana masing-masing efektif untuk penyelesaian masalah tertentu yang lebih spesifik. Untuk memilih metode mana (atau kombinasi metode mana) yang akan digunakan untuk menyelesaikan masalah, penting untuk menganalisa masalah pada beberapa dimensi kunci atau karakteristik,

A.  Generate-and-Test

Teknik Generate-and-Test adalah teknik yang paling mudah dibandingkan teknik search yang lain, namun relatif lebih lama dalam mendapatkan solusi.

Kebaikan dan Keburukan Generate-and-Test 

Jika penurunan solusi yang mungkin dilakukan secara sistematis, maka procedure diatas akan dapat menemukan solusi suatu saat, jika memang ada. Tapi sayangnya jika ruang permasalahan sangat luas maka saat ditemukannya solusi akan menjadi sangat lama. Cara terbaik menerapkan generate-and-test yang sistematis adalah pada tree dari depth-first search dengan backtracking, yaitu kembali ke stata sebelumnya bila ditemui stata yg sudah pernah di test atau memodifikasi prosedurnya untuk menelusuri stata pada bentuk graph.

b. Hill Climbing 

Teknik Hill Climbing adalah pengembangan dari teknik Generate-and-Test, dengan penambahan adanya umpan balik dari prosedur test yang sudah digunakan untuk membantu memilih arah mana yang harus ditelusuri pada setiap area search.

Pada prosedur Generate-and-Test yang murni, fungsi test hanya ditanggapi dengan Ya atau Tidak. Tetapi pada HillClimbing fungsi test ditambahkan dengan fungsi heuristic atau fungsi objectif yang memungkinkan perkiraan seberapa dekat simpul yang ditelusuri terhadap goal state.

C. Best-First-Search Teknik 

Best-First-Search adalah teknik search yang menggabungkan kebaikan yang ada dari teknik DepthFirst-Search dan Breadth-First-Search. 

Tujuan menggabungkan dua teknik search ini adalah untuk menelusuri satu jalur saja pada satu saat, tapi dapat berpindah ketika jalur lain terlihat lebih menjanjikan dari jalur yang sedang ditelusuri. Untuk mendapatkan jalur yang menjanjikan adalah dengan memberikan skala prioritas pada setiap stata saat dihasilkan dengan fungsi heuristic.