Penyelesaian Masalah : Melalui Proses Pencarian
Penyelesaian Masalah
Penyelesaian atau pemecahan masalah adalah bagian dari proses
berpikir. Sering dianggap merupakan proses paling kompleks di antara semua
fungsi kecerdasan, pemecahan masalah telah didefinisikan sebagai proses
kognitif tingkat tinggi yang memerlukan modulasi dan kontrol lebih dari keterampilan-keterampilan
rutin atau dasar. Proses ini terjadi jika suatu organisme atau sistem
kecerdasan buatan tidak mengetahui bagaimana untuk bergerak dari suatu kondisi
awal menuju kondisi yang dituju.
Agen Pemecah Permasalahan
Dalam membangun sebuah sistem AI, perlu dipertimbangkan 4
hal, yaitu:
- Mendefinisikan masalah dengan tepat. Pendefinisian ini mencakup deskripsi masalah dengan baik
- Menganalisis masalah tersebut serta mencari beberapa teknik penyelesaian masalah yang sesuai
- Mempresentasikan pengetahuan yang perlu untuk menyelesaikan masalah tersebut
- 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
Pencarian sebagai solusi pemecahan masalah
Searching adalah mekanisme pemecahan masalah yang paling umum
di dalam kecerdasan buatan. Di dalam permasalahan-permasalahan kecerdasan
buatan, urutan langkah-langkah yang dibutuhkan untuk memperoleh solusi
merupakan suatu isu yang penting untuk diformulasikan. Hal ini harus dilakukan
dengan mengidentifikasikan proses try and error secara sistematis pada
eksplorasi setiap alternatif jalur yang ada.
METODE
PELACAKAN/PENCARIAN
- Hal penting dalam menentukan keberhasilan sistem cerdas adalah kesuksesan dalam pencarian. Pencarian = suatu proses mencari solusi dari suatu permasalahan melalui sekumpulan kemungkinan ruang keadaan (state space). Ruang keadaan = merupakan suatu ruang yang berisi semua keadaan yang mungkin.
- Untuk mengukur perfomansi metode pencarian, terdapat empat kriteria yang dapat digunakan :
- Time comp y lexit : berapa lama waktu yg diperlukan?
- Space complexity : berapa banyak memori yg diperlukan
- Optimality : apakah metode tsb menjamin menemukan solusi yg terbaik terbaik jika terdapat terdapat beberapa
beberapa solusi berbeda berbeda?
Strategi Pencarian yang Tidak Berbentuk/Uniformed Search Strategy
Masalah menentukan grafik dan sasaran, tapi bukan jalur mana
yang harus dipilih dari perbatasan. Ini adalah tugas dari strategi pencarian. Strategi
pencarian menentukan jalur mana yang dipilih dari perbatasan. Strategi yang
berbeda diperoleh dengan memodifikasi bagaimana pemilihan jalur di perbatasan
diterapkan.
- Depth-First Search
Algoritma Depth First Search (DFS) adalah salah satu
algoritma pencarian solusi yang digunakan di dalam kecerdasan buatan. Algoritma
ini termasuk salah satu jenis uninformed algorithm yaitu algoritma yang
melakukan pencarian dalam urutan tertentu tetapi tidak memiliki informasi
apa-apa sebagai dasar pencarian kecuali hanya mengikuti pola yang diberikan.
Di dalam DFS, pencarian dilakukan pada suatu struktur pohon
yaitu kumpulan semua kondisi yang mungkin yang diimplementasikan dalam sebuah
struktur pohon. Paling atas adalah akar (root) yang berisi kondisi awal
pencarian (initial state) dan di bawahnya adalah kondisi-kondisi berikutnya
sampai kepada kondisi tujuan (goal state).
Untuk melakukan pencarian, DFS menggunakan cara sebagai
berikut :
1. Masukkan Initial State pada Tumpukan.
2. Periksa apakah ada data di tumpukan.
3. Jika tidak, maka solusi tidak ditemukan, dan proses
berhenti.
4. Jika ya, Ambil state pada tumpukan paling atas.
5. Bandingkan State tersebut apakah sama dengan Goal State
6. Jika sama, maka solusi ditemukan dan proses berakhir.
7. Jika tidak, ekspansikan state tersebut.
6. Masukkan seluruh state hasil ekspansi ke dalam tumpukan.
7. Kembali ke langkah 2.
Pada prinsipnya, DFS ini menggunakan tumpukan untuk menyimpan
seluruh state yang ditemukan atau bisa dikatakan bahwa DFS menggunakan metode
LIFO (Last In First Out).
- Breadth-First Search
BREADTH-FIRST SEARCH (BFS) sebuah algoritma pencarian graf
yang dimulai dari node pangkal dan menjelajahi semua node yang berdekatan.dan
untuk setiap node yang berdekatan, bfs menjelajahi node-node yang tidak
terlihat sebelumnya (unexplored) dan seterusnya
BFS adalah sebuah metode pencarian yang bertujuan untuk
memperluas dan memeriksa semua node dari sebuah graf atau kombinasi dari urutan
dengan menggunakan semua solusi secara sistematis. dengan kata lain, bfs
mencari ke seluruh graf atau urutan secara mendalam tanpa mempertimbangkan
tujuannya (goal) sampai tujuan itu tercapai. bfs tidak menggunakan algoritma
heuristis.
Kelebihan BFS
- Tidak akan menemui jalan buntu.
- Menjamin ditemukannya solusi (jika solusinya memang ada)
dan solusi yang ditemukan pasti yang paling baik.
- Jika ada satu solusi maka bread-first search akan
menemukannya
Kekurangan BFS
Dan kekurangan dari metode BFS ini yaitu:
- Membutuhkan memori yang cukup banyak.
- Membutuhkan waktu yang cukup lama.
- 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 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.
Comments
Post a Comment