''IRZAN ADITIA N 4KA10": PENYELESAIAN MASALAH MELALUI PROSES PENCARIAN/SEARCHING

Agen Pemecah Permasalahan

Problem Solving Agent memutuskan apa yang akan dilakukan dengan mencari serangkaian aksi yang mengarah pada kondisi yang diharapkan. Intelligence agent seharusnya memaksimalkan ukuran kinerja mereka.

Contoh :

· Sebuah agent melakukan perjalanan ke Romania. Agent saat ini ada di Arad.

· Pesawat terbang besok dari Bucharest.

· Formulated Goal, didasarkan pada situasi saat ini dan ukuran kinerja agent, adalah langkah pertama dalam menyelesaikan masalah. Tugas agent adalah untuk menemukan rangkaian aksi yang mana yang membawa ke goal kondisi. Sebelum melakukan itu, perlu diputuskan aksi dan kondisi apa yang dipertimbangkan. Untuk agent pada contoh, Formulated Goal adalah :

o Ada di Bucharest

· Formulated Problem adalah proses memutuskan aksi dan kondisi apa yang dipertimbangkan, yang membawa ke goal. Agent pada contoh memiliki Formulated Problem sebagai berikut :

o Kondisi : bermacam-macam kota

o Aksi : berkendaraan antara kota

Agent sekarang memiliki goal untuk berkendaraan ke Bucharest dan mempertimbangkan akan kemana pergi dari Arad. Ada beberapa jalur alternatif menuju Arad. Tetapi agent tidak tahu jalan terbaik karena tidak cukup tahu tentang kondisi yang hasilnya dari pengambilan aksi. Jika agent tidak memiliki pengetahuan tambahan maka akan stuck. Cara terbaik adalah memilih secara acak.

Find Solution. Proses untuk mencari rangkaian penyelesaian disebut Search (pencarian). Suatu algoritma pencarian menganggap masalah sebagai input dan menghasilkan solusi dalam bentuk rangkaian aksi. Sekali solusi ditemukan, aksi yang menyarankan dikeluarkan. Hal ini disebut eksekusi.

Goal-based agent : Mempertimbangkan action-action yang akan datang dan hasil yang ingin dicapai.
Agent probleng solving : Menemukan rangkaian tindakan (sequence action) untuk mencapai tujuannya.
Algoritma Uniformed : Tidak ada informasi untuk problem, hanya deskripsi pada masalah tersebut.

Pencarian sebagai solusi pemecahan masalah

Pencarian adalah masalah yang paling penting dan paling sering ditemui dalam bidang kecerdasan buatan. Permasalahan ini dapat menjadi penentu keberhasilan sistem kecerdasan buatan.

Pada bagian akan dibahas 3 jenis metoda pencarian, yaitu :

Metoda pencarian sederhana yang hanya mencari penyelesaian, misalnya : depth- first search, breadth-first search, hill climbing, dan beam search.
Metoda pencarian yang mencari jarak atau jalur terpendek, misalnya British Museum Procedure, Branch and Bound, Dynamic Programming dan A*. metoda-metoda ini mencari kemungkinan optimal dari harga perjalanan.
Metoda yang digunakan untuk berhadapan dengan musuh, misalnya minimax search, alpha-betha prunning.

Strategi Pencarian yang tidak berbentuk / uniformed search strategi

Strategi Pencarian :

Terdapat empat kriteria dalam strategi pencarian, yaitu :

Completeness: Apakah strategi tersebut menjamin penemuan solusi jika solusinya memang ada?
Time complexity: Berapa lama waktu yang diperlakukan?
Space complexity: Berapa lama memori yang diperlukan?
Optimality : Apakah strategi tersebut menemukan solusi yang paling baik jika terdapat beberapa solusi berbeda pada permasalahan yang ada?

Breadth-First Search (BFS)

merupakan pencarian yang dilakukan dengan mengunjungi tiap tiap node secara sistematis pada setiap level hingga keadaan tujuan ditemukan. Penelususran yang dilakukan dengan mengunjungi node node pada level yang sama hingga ditemukan tujuan (goal state) nya. 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 simpul-simpul yang tadi dikunjungi, demikian seterusnya. algoritma BFS menggunakan graf sebagai media representasi persoalan, tidak sulit untuk mengaplikasikan algoritma ini dalam persoalan-persoalan teori graf.

Pengimplementasian Breath First Search dapat ditelusuri dengan menggunakan daftar list open dan closed, untuk menelusuri gerakan pencarian di dalam ruang keadaan. Pada algoritma BFS, simpul anak yang telah dikunjungi disimpan dalam suatu antrian. Antrian ini digunakan untuk mengacu simpul-simpul yan bertetangga dengannya yang akan dikunjungi kemudian sesuai urutan pengantrian.

Uniform-cost search (UCS)

Pencarian dengan Breadth First Search akan menjadi optimal ketika nilai pada semua path adalah sama. Dengan sedikit perluasan, dapat ditemukan sebuah algoritma yang optimal dengan melihat kepada nilai tiap path di antara node-node yang ada. Selain menjalankan fungsi algoritma BFS, Uniform Cost Search melakukan ekspansi node dengan nilai path yang paling kecil. Hal ini bisa dilakukan dengan membuat antrian pada successor yang ada berdasar kepada nilai path-nya (node disimpan dalam bentuk priority queue).

Depth First Search (DFS)

Teknik pencarian dengan Depth First Search adalah dengan melakukan ekspansi menuju node yang paling dalam pada tree. Node paling dalam dicirikan dengan tidak adanya successor dari node itu. Setelah node itu selesai diekspansi, maka node tersebut akan ditinggalkan, dan dilakukan ke node paling dalam lainnya yang masih memiliki successor yang belum diekspansi.

Depth Limited Search

Pencarian menggunakan DFS akan berlanjut terus sampai kedalaman paling terakhir dari tree. Permasalahan yang muncul pada DFS adalah ketika proses pencarian tersebut menemui infinite state space. Hal ini bisa diatasi dengan menginisiasikan batas depth pada level tertentu semenjak awal pencarian. Sehingga node pada level depth tersebut akan diperlakukan seolah-olah mereka tidak memiliki successor.

Iterative Deepening Depth First Search

Iterative deepening search merupakan sebuah strategi umum yang biasanya dikombinasikan dengan depth first tree search, yang akan menemukan berapa depth limit terbaik untuk digunakan. Hal ini dilakukan dengan secara menambah limit secara bertahap, mulai dari 0,1, 2, dan seterusnya sampai goal sudah ditemukan.

Bidirectional Search

Pencarian dengan metode bidirectional search adalah dengan menjalankan dua pencarian secara simultan, yang satu dikerjakan secara forward dari initial state menuju ke goal, sedangkan yang satu lagi dikerjakan secara backward mulai dari goal ke initial state. Yang kemudian diharapkan bahwa kedua pencarian itu akan bertemu di tengah-tengah.