Penyelesaian Masalah Melalui Proses
Pencarian/Searching
Penyelesaian
atau pemecahan masalah adalah bagian dari proses berpikir. Seiring dianggap
merupakan proses paling kompleks diantara semua fungsi kecerdasan, pemecahan
masalah telah didefinesikan sebagai proses kognitif tingkat tinggi yang
memerlukan modulasi dan kontrol lebih dari keterampilan rutinn atau dasar.
2.1 Agen
pemecah permasalahan
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.
2.2 Pencarian sebagai solusi pemecahan masalah
Searching di dalam AI (Artificial Intelligence)
adalah salah satu metode penyelesaian masalah dengan pencarian solusi pada
suatu permasalahan yang dihadapi. Teknik searching terbagi menjadi dua, yaitu :
1. Blind Searching
2. Heuristic Searching
- Blind Searching
Blind searching adalah model pencarian buta atau
pencarian yang tidak memiliki informasi awal, model pencarian ini memiliki tiga
ciri-ciri utama yaitu :
1. Membangkitkan simpul
berdasarkan urutan
2. Jika ada solusi maka
solusi akan ditemukan
3. Hanya memiliki
informasi tentang node yang telah dibuka, (node selanjutnya tidak ddiketahui)
Ada beberapa algoritma pencarian buta diantaranya BFS
(Breadth First Search), DFS (Depth First Search), dan UCS (Uniform Cost
Search).
- Heuristic Searching
Heuristic searching merupakan metode pencarian yang
memperhatikan nilai heuristik (nilai perkiraan). Teknik pencarian heuristik
merupakan suatu strategi untuk melakukan proses pencarian ruang keadaan (state
space) suatu problema secara selektif, metode ini melakukan proses pencarian di
sepanjang jalur yang memiliki kemungkinan sukses paling besar dan
mengesampingkan usaha yang memiliki kemungkinan hasil minim dan memboroskan
waktu. Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses
pencarian, namun dengan kemungkinan mengorbankan kelengkapan (completeness).
Heuristic search memperkirakan jarak menuju goal (yang
disebut dengan fungsi heuristik). Fungsi heuristik ini digunakan untuk
mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh
hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.
Jenis-jenis heuristic searching :
1. Generate and Test
2. Hill Climbing
3. Best First Search
4. Alpha Beta Prunning
5. Means-End-Analysis
6. Constraint
Satisfaction
2.3 Strategi
Pencarian yang tidak berbentuk / uniformed search strategi
Algoritma ini
tidak memberikan informasi apapun tentang permasalah yang ada, tetapi hanya
berfokus memberikan informasi tentang algorima tersebut. Algoritma ini juga
disebut Blind Search. Istilah Blind Search berpedoman bahwa, teknik pencarian
ini tidak memiliki informasi tambahan lain selain dari yang disediakan.Yang
dilakukan oleh algorima ini adalah melakukan generate dari successor dan membedakan
goal state dari non-goal state. Pencarian ini dilakukan berdasarkan pada urutan
mana saja node yang hendak di-expand.
Macam-macam Uninformed Search
Algorithm:
a. Breadth First Search(BFS)
Pencarian dengan metode
ini menggunakan teknik dimana langkah pertama yang harus dilakukan adalah root
node di-ekspansi, setelah itu dilanjutkan semua successor dari root node juga
di-expand. Hal ini terus dilakukan berulang-ulang hingga leaf(node pada level
paling bawah yang sudah tidak memiliki successor lagi).
b. Uniform Cost Search(UCS)
Pencarian
dengan BFS 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).
c. Depth First Search(DFS)
Teknik pencarian
dengan metode ini adalah dengan melakukan ekspansi menuju node yang paling
dalam pada tree. Node paling dalam dicirikan dengan tidak adanya successor dari
node itu. Setelah node selesai di ekspansi, maka node tersebut akan
ditinggalkan dan dilakukan ke node paling dalam lainnya yang masih memiliki
successor yang belum di ekspansi.
d. Depth Limited Search
Pencarian
menggunakan DFS akan berlanjut sampai kedalam paling terakhir dari sebuah tree.
Misalkan yang muncul pada DFS adalah ketikda proses pencarian tersebut menemui
infinite state space. Hal ini bisa diatasi dengan mengisiasikan batas depth
pada level tertentu semenjak awal pencarian. Sehingga node pada level depth
tersebut akan diperlakukan seolah-olah mereka sudah tidak memiliki successor.
e. 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.
f. 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.
Sumber:
TUGAS PENGETAHUAN TEKNOLOGI SISTEM
CERDAS
MINGGU KE-2
HERI JULIYANTO
13115135
3KA12
UNIVERSITAS GUNADARMA
Tidak ada komentar:
Posting Komentar