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 ihwal algoritma pencarian dan keterampilan penting bagi pengembang AI.

Search and Problem-Solving

Banyak dilema sanggup diutarakan sebagai dilema pencarian. Merumuskan ruang pencarian dan menentukan algoritma pencarian yang sempurna sering kali membutuhkan aliran 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 masalah khusus, algoritma A*).

1. Breadth-First dan Depth-First Search

Untuk mendiskusikan algoritma pencarian yang lebih maju, ibarat 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 sikap 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 masalah BFS, operasi menambahkan node ke daftar (queue) ialah enqueue dan operasi menghapus node yang ditambahkan terlebih dahulu ialah dequeue.
Dalam masalah DFS, operasi penambahan node ke daftar (stack) ialah push, dan operasi menghapus node yang ditambahkan terakhir ialah pop.
Test goal_node menguji apakah tujuan atau simpul sasaran 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 bersahabat ke simpul awal daripada node B, pencarian diperluas ke node A lebih awal daripada ke B.
Anda sanggup berpikir pencarian BFS sebagai batas node (frontier of nodes) yang secara sedikit demi sedikit 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 masalah itu tidak masalah.

(Lihat tumpuan memecahkan teka-teki Sudoku memakai DFS).

Bisakah Anda memikirkan alasan bahwa DFS ialah pilihan yang lebih baik dalam penyelesaian dilema dibanding BFS?
Mensimulasikan BFS (di atas pensil dan kertas) pencarian pertama mulai dari node A saat goal_node yaitu node H. Silahkan, lakukan hal yang sama dengan dengan memakai DFS.
Dalam setiap kasus, sajikan konten node list (queue atau stack) di setiap langkah pencarian.
Untuk memastikan bahwa semua orang mendapat hasil yang sama, mari kita setuju bahwa node ditambahkan ke daftar dalam urutan abjad.

Contoh cara menuntaskan dengan BFS dan DFS:

2. Informed Search dan A*

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

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

Sebagai contoh, kita sanggup menentukan untuk selalu memperluas jalur dengan penghitungan biaya total minimum yang dikeluarkan dari simpul awal.

Ini dikenal sebagai algoritma Dijkstra (Dijkstra's algorithm). Dalam masalah khusus di mana biaya semua transisi ialah 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 ialah antrian prioritas (priority queue).

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

Pencarian yang diinformasikan (informed search) bergantung pada terusan ke heuristik yang terkait dengan setiap node asumsi biaya yang tersisa dari node ke tujuan. Ini sanggup berupa, misalnya, jarak antara simpul dan tujuan yang diukur secara eksklusif (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 sepertinya lebih bersahabat ke tujuan sesuai dengan heuristik.

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

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

Search And Problem-Solving