Dalam melakukan pencarian, salah satu cara yang banyak digunakan untuk menggambarkan masalah adalah dengan mencantumkan atau menggambarkan semua kemungkinan keadaan yang ada. Memecahkan masalah berarti bergerak atau berpindah dari satu ruang (node) dari titik awal sampai titik yang dituju (ditentukan), untuk karenanya kita memerlukas satu set operator untuk bergerak dari satu node ke node lainnya.
Untuk memecahkan masalah kita perlu:
1. Formulasikan Tujuan (menentukan state goal (keadaan tujuan));
2. Formulasikan masalah (menentukan aksi/tindakan dan keadaan apa yang akan dipertimbangkan, sesuai dengan goal yang telh diberikan);
3. Melakukan pencarian untuk mencapai goal.
FORMULASI MASALAH:
• Inisialisasi keadaan awal
• Actions/Tindakan (umumnya mentransformasikan agent dari satu keadaan ke keadaan lainnya); biasanya, suatu suksesor fungsi memetakan kumpulan keadaan kedalam suatu set (action, successor-rate)
• Cost/Biaya (actions biasanya memiliki beberapa atau minimal satu positif)
• State Space/Ruang Keadaan :kumpulan dari seluruh state yang dapat dicapai dari keadaan awal; dapat dibuatkan sebuah graf : 1.)node adalah state, 2.)egdes adalah action.
• path/Jalur menuju state space: urutan actions.
• Objective : cost path minimum dimulai keadaaan awal sampai ke state goal (solusi optimal).
keterangan:
• State Space tidak sama dengan Search Tree; search tree digeneralisasi dari state space/successor fungsi selama dilakukan pencarian.
• State tidak sama seperti node; node berisikan suatu keadaan ditambah informasi lainnya (seperti pointer ke children atau parents )
ATRIBUT PENCARIAN:
• Optimalisasi: apakah algoritma dapat menemukan cost path terendah untuk mencapai goal?
• Kelengkapan: apakah algoritma akan menemukan jalur menuju goal/tujuan jika memang ada?
– digunakan untuk mendefinisikan “return failure otherwise”
– jika tidak ada solusi, dan algoritma tidak dapat mendeteksinya (mendeteksi state berulang-ulang(loop)), maka akan menjadi infinite search dan tidak akan ada hasil yang dikembalikan.
• Kompleksitas Waktu: waktu yang dibutuhkan untuk melakukan pencarian (contoh: jumlah nodes yang digeneraisasikan selama proses pencarian).
• Kompleksitas waktu: memori yang dibutuhkan.
Terdapat dua metode untuk melakukan pencarian yaitu dengan BLIND SEARCH dan HEURISTIC SEARCH.
1. METODE PENCARIAN BUTA (BLIND SEARCH)
A. DEFINISI
Blind Search atau Uninformed Search secara umum mengartikan bahwa saat proses pencarian kita tidak memiliki clue/hint apakah hasil yang ditemukan lebih baik daripada yang lainnya, sehingga kita tidak mengetahui apakah hasil dari eksplorasi tersebut bermanfaat secara maksimal atau tidak.
Search Space (ruang pencarian) dieksplorasi tanpa memanfaatkan apapuun informasi yang menyangkut pada masalah maka dari itu digunakan istilah blind search atau naive search, dan karena metode ini masih sangat umum maka hasil yang didapat secara instrinsik kurang efisien.
B. CONTOH BLIND SEARCH:
RANDOM SEARCH
Metode ini akan memilih secara acak keadaan baru dari keadaan yang sekarang, jika goal(tujuan) telah dicapai maka pencarian akan berhenti, namun jika tidak maka akan operator selanjutnya secara acak untuk pindah ke keadaan selanjutnya.
C. STRATEGI YANG TERDAPAT PADA BLIND SEARCH:
• Breadth-first search
• Uniform-cost search
• Depth-first search
Strategi pencarian didefinisikan berdasarkan ekspansi nodes.
D. BREADTH-FIRST SEARCH
Breadth-First Search (BFS) dimulai dari akar node (root) lalu mengeksplor ke seluruh cabang (branch) dalam level yang sama.
• BFS dikatakan komplit/selesai jika terdapat solusi dan BFS menemukannya.
• BFS dikatakan optimal jika solusi yang didapat dapat dipastikan menjadi jalur terpendek (shortest path).
• Algoritma dapat diimplementasikan dengan First In First Out (FIFO) stack.
D.1 CARA KERJA DAN ALGORITMA BREADTH-FIRST SEARCH
Eksplorasi node dimulai root (A) lalu bergerak ke kanan untuk mencari node pada level yang sama, jika sudah tidak ada, maka akan ke level selanjutnya dimulai dari kiri-kanan sampai menemukan goal (tujuan).
ALGORITMA:
List open, closed, successors={};
Node root_node, current_node;
insert-last(root_node,open)
while not-empty(open);
current_node=remove-first(open);
insert-last(current_node,closed);
if (goal(current_node)) return current_node;
else
successors=successorsOf(current_node);
for(x in successors)
if(not-in(x,closed)) insert-last(x,open);
endIf
endWhile
D.2 CONTOH BREADTH-FIRST SEARCH
• Initial State: S
• State Goal : F
HASIL: S-A-F
keterangan:
terdapat 3 buah node F namun, BFS akan mengembalikan node F yang pertama kali ditemukan yaitu dari parent node A. Karena ini merupakan BLIND SEARCH yang begrarti pencarian tidak mendapatkan clue/petunjuk sehingga hasil pencarian belum tentu mendapatkan hasil yang paling efisien.
E. DEPTH-FIRST SEARCH
Depth-First Search melakukan eksplorasi dimulai root node (akar) lalu ke cabang pertama (dimulai dari paling kiri) sampai ke kedalaman maksimum , setelah itu baru dilakukan eksplorasi ke cabang lainnya, dan terus dilakukan sampai menemukan state goal.
Jika telah mencapai node yang terdalam namun tidak juga ditemukan solusi, maka akan mundur sampai menemukan cabang yang belum dieksplorasi. Tree dilakukan pencarian dengan top-to-bottom, left-to-right.
Depth-First Search dikatakan tidak komplit:
• jika siklus yang disajikan dalam graf lalu DFS melakukan eksplorasi terhadap siklus berulang(tidak ada batas).
• jika tidak terdapat siklus, maka algoritma komplit.
• Efek siklus dapat dibatasi dengan memaksakan kedalaman pencarian yang maksimal(namun algoritma tetap tidak komplit).
Depth-First Search dikatakan tidak optimal:
• jika solusi pertama yang ditemukan bukan merupakan solusi dengan shortest path (jalur terpendek) menuju goal yang telah ditentukan.
Algoritma dapat diimplementasikan dengan menggunakan Last In First Out (LIFO) stack atau menggunakan Rekursif (recursion).
E.1 CARA KERJA DAN ALGORITMA DEPTH-FIRST SEARCH
Eksplorasi dimulai dari root node (S) lalu ke cabang pertamanya (B), setelah itu ke cabang (child) pertama node B yaitu E, karena node E tidak memiliki child maka ke cabang kedua node B yaitu F, dan dilakukan dengan cara seperti itu sampai menemukan state goal yang telah ditapkan.
ALGORITMA:
List open, closed, successors={};
Node root_node, current_node;
insert-first(root_node,open)
while not-empty(open);
current_node= remove-first(open);
insert-first (current_node,closed);
if (goal(current_node)) return current_node;
else
successors=successorsOf(current_node);
for(x in successors)
if(not-in(x,closed)) insert-first(x,open);
endIf
endWhile
E.2 CONTOH DEPTH-FIRST SEARCH
• INITIAL STATE: S
• STATE GOAL : F
HASIL: S-A-B-F
KETERANGAN:
Dimulai dari root node (S) selanjutnya berpindah ke cabang (child) pertamanya (paling kiri) yaitu node A, lalu berpindah ke cabang pertama yang dimiliki node yaitu node S. Karena node S tidak memilki child maka berpindah ke child selanjtnya dari node A yaitu B, lalu berpindah ke child pertama cabang B yaitu S, karena node S tidak memiliki child maka berpindah ke child kedua miilik node B yaitu A, dan karena node A juga tidak memiliki child maka berpindah ke node ketiga cabang milik B yaitu F, karena kita telah menemukan state goal yaitu node F, maka search berhenti dan mengembalikkan hasil S-A-B-F.
2. METODE PENCARIAN HEURISTIK
A. DEFINISI
Pencarian heuristik adalah teknik pencarian AI yang menggunakan heuristik untuk pergerakannya(berpindah). Heuristik sendiri merupakan aturan praktis yang mungkin mengarah pada solusi. Heuristik membantu mengurangi jumlah alternatif dari bilangan eksponensial menjadi bilangan polinomial. Secara umum, istilah heuristik digunakan untuk saran yang sering efektif, namun tidak dalam setiap kasus. Dalam pencarian heuristik setiap state diberi sebuah “heuristic value “(h-value) yang digunakan pencarian dalam memilih langkah terbaik selanjutnya.
