Search and Problem-Solving

Search and Problem-Solving - Hi Guys! Membuat artikel ini berawal dari referensi dosen kampus dan di rangkum sesuai pemahaman saya. Menjelaskan tentang algoritma pencarian dan keterampilan penting bagi pengembang AI.

    Baca juga: Filsafat dan Sejarah AI

Search and Problem-Solving

Banyak masalah dapat diutarakan sebagai masalah pencarian. Merumuskan ruang pencarian dan memilih algoritma pencarian yang tepat sering kali membutuhkan pemikiran yang cermat dan merupakan keterampilan penting bagi pengembang AI. Pohon dasar (basic tree) dan Algoritma traversal jaringan (network traversal algorithms) termasuk prasyarat kursus, dan harus sudah terbiasa dengan breadth-first search (BFS), depth-first search (DFS), dan best-first search (termasuk kasus khusus, algoritma A*).

1. Breadth-First dan Depth-First Search

Untuk mendiskusikan algoritma pencarian yang lebih maju, seperti A*, kita mulai dengan mendefinisikan template umum untuk algoritma pencarian.

• Dalam pseudocode di atas, node_list menyimpan node yang akan dikunjungi.
• Urutan pengambilan node dari daftar oleh node_list.first() menentukan perilaku pencarian: hasil antrian (first-in, first-out) dengan breadth-first search (BFS) dan hasil tumpukan (last-in, first-out) dengan depth-first search (DFS).
• Dalam kasus BFS, operasi menambahkan node ke daftar (queue) adalah enqueue dan operasi menghapus node yang ditambahkan terlebih dahulu adalah dequeue.
• Dalam kasus DFS, operasi penambahan node ke daftar (stack) adalah push, dan operasi menghapus node yang ditambahkan terakhir adalah pop.
• Test goal_node menguji apakah tujuan atau simpul target pencarian ditemukan.
• Kadang-kadang masalahnya hanya melintasi jaringan (tree) sepenuhnya dalam urutan tertentu, dan tidak ada goal_node. Dalam hal ini, node selalu mengembalikan False.
• Sangat sulit untuk melihat bahwa BFS akan selalu mengembalikan jalur dengan transisi paling sedikit ke goal_node:
• Jika node A lebih dekat ke simpul awal daripada node B, pencarian diperluas ke node A lebih awal daripada ke B.
• Anda dapat berpikir pencarian BFS sebagai batas node (frontier of nodes) yang secara bertahap berkembang keluar dari node awal (starting node), sehingga semua node pada sejumlah langkah diperluas sebelumbergerak satu langkah di depan.
• DFS tidak menjamin bahwa jalan terpendek ditemukan, tetapi dalam beberapa kasus itu tidak masalah.
• (Lihat contoh memecahkan teka-teki Sudoku menggunakan DFS).
• Bisakah Anda memikirkan alasan bahwa DFS adalah pilihan yang lebih baik dalam penyelesaian masalah dibanding BFS?
• Mensimulasikan BFS (di atas pensil dan kertas) pencarian pertama mulai dari node A ketika goal_node yaitu node H. Silahkan, lakukan hal yang sama dengan dengan menggunakan DFS. 
• Dalam setiap kasus, sajikan konten node list (queue atau stack) di setiap langkah pencarian.
• Untuk memastikan bahwa semua orang mendapatkan hasil yang sama, mari kita sepakat bahwa node ditambahkan ke daftar dalam urutan abjad.

 Contoh cara menyelesaikan dengan BFS dan DFS:

2. Informed Search dan A*

Sering kali, berbagai transisi dalam ruang keadaan (state space) dikaitkan dengan biaya yang berbeda. Misalnya, melakukan tugas bisa memakan waktu antara beberapa detik dan beberapa jam. Atau jarak antara dua perhentian trem bisa antara seratus meter dan setengah kilometer. Jadi, menghitung jumlah transisi saja tidak cukup.

Untuk dapat memperhitungkan biaya yang berbeda, kita dapat menerapkan pencarian terbaik-pertama (best-first search), di mana daftar simpul diurutkan berdasarkan kriteria yang diberikan.

• Sebagai contoh, kita dapat memilih untuk selalu memperluas jalur dengan penghitungan biaya total minimum yang dikeluarkan dari simpul awal.

Ini dikenal sebagai algoritma Dijkstra (Dijkstra's algorithm). Dalam kasus khusus di mana biaya semua transisi adalah konstan, algoritma Dijkstra setara dengan BFS.

Templat algoritme pencarian generik di atas masih berlaku, tetapi dalam pencarian best-first, struktur data yang menyimpan node pada daftar node adalah antrian prioritas (priority queue).

• Saat menambahkan node ke antrian prioritas pada baris 14, semua diberi biaya atau nilai yang kemudian digunakan untuk memesan node dalamantrian.
• Bergantung pada aplikasi dan apakah tujuannya adalah untuk meminimalkan atau memaksimalkan nilai, antrian dapat berupa antrian prioritas minimum(min-priority queue) atau antrian prioritas maksimum(max-priority queue).

Pencarian yang diinformasikan (informed search) bergantung pada akses ke heuristik yang terkait dengan setiap node perkiraan biaya yang tersisa dari node ke tujuan. Ini bisa berupa, misalnya, jarak antara simpul dan tujuan yang diukur secara langsung (mis., Jarak Euclidean atau geodesik - atau
dengan kata sederhana, jarak garis lurus). Menggunakan heuristik sebagai kriteria untuk memesan node dalam antrian prioritas (min-) akan selalu memperluas node yang tampaknya lebih dekat ke tujuan sesuai dengan heuristik.

• Namun, ini dapat menyebabkan pencarian tersesat karena biaya yang dikeluarkan jalur tidak diperhitungkan.
• Pencarian seimbang yang memperhitungkan biaya yang dikeluarkan serta perkiraan biaya yang tersisa diperhitungkan dengan memesan antrian prioritas (minimum) dengan f(node, cost) = cost + h(node), di mana biaya adalah nilai yang terkait dengan simpul ketika ditambahkan ke antrian prioritas, dan h(node) adalah nilai heuristik, yaitu, perkiraan biaya yang tersisa dari node ke tujuan. Ini adalah pencarian A*.
• Jika Anda mencobanya di PathFinding applet, Anda akan segera melihat bahwa itu pencarian lain, yaitu metode tidak diinformasikan (uninformed search methods).

Demikian penjelasan artikel tersebut. Harap saya Anda sudah mengerti tentang AI, DFS dan BFS. Bila belum paham jangan sungkan-sungkan untuk bertanya. Semoga bermanfaat.
Terimakasih.