1/2/2007
ANALISA SEARCHING ALGORITHM BREADTH-FIRST, DEPTH-FIRST DAN BEST-FIRST SEARCH PADA PENYELESAIAN PROBLEM KOTAK-8
Permasalahan p problem solving gy yang g dihadapi p di dunia nyata dapat dilakukan melalui pendekatan secara intelligence atau “cerdas”. Paradigma yang digunakan : { { { {
DESI RAMAYANTI (23206006) ARWIN (23206008) HENDRA (23206017)
AI mempunyai e pu ya bebe beberapa apa metode etode u untuk tu menyelesaikannya. Salah satu dari metode tersebut adalah Metode Searching Hal yang sangat menarik adalah bagaimana searching algorithm yang diterapkan berusaha mencari solusi, yang diistilahkan dengan goal state (GS), (GS) paling optimal dan lengkap dengan berbagai kompleksitas waktu dan ruang yang dihadapinya dari kondisi awal atau initial state (IS) yang diberikan.
Artificial Intelligence Computational Intelligence (Artificial Neural Networks -ANN) Fuzzy y Logic g Evolutionary Computation
Dalam konteks permasalahan problem solving, paradigma yang banyak digunakan adalah Artificial Intelligence (AI) atau Kecerdasan Tiruan
Paradigma AI banyak digunakan dalam berbagai aplikasi dan salah satu diantaranya adalah game, diantaranya aplikasi 8 8-puzzle p le atau ata Kotak-8 Kotak 8
Karakteristik menarik dari game ini adalah pada representasi data yang akan diolah oleh searching algorithm yang diaplikasikan kepadanya.
Untuk mengetahui lebih detil, di dalam naskah akan disampaikan analisa pembangkitan generasi penerus (successor) simpul induk (parent) hingga didapatkan anak (node) terbaik ditinjau dari mekanisme searching algorithm { { {
Breadth-First Search (BFS) Depth-First Search (DFS) Best-First Searh (BsFS)
1
1/2/2007
AI adalah suatu disiplin ilmu yang mempelajari bagaimana atau untuk membuat komputer agar mampu mendekati kecerdasan sebagaimana makhluk hidup
Wikipedia mendefinisikan AI sebagai a branch of computer science that deals with intelligent behavior, learning and adaptation in machines.
Di dalam penyelesaian suatu permasalahan, AI dianggap sebagai suatu Sistem Produksi yang berlandaskan pada 3 (tiga) komponen yakni :
Naskah ini disusun dengan tata urut { {
{
{
{
Bagian I berisi latar belakang penulisan naskah Bagian II akan disampaikan konsep AI dan searching algorithm yang akan dipresentasikan Bagian III implementasi software searching algorithm yang digunakan untuk problem solving Kotak-8. Bagian IV akan disampaikan analisa problem solving pada Kotak-8 Bagian V kesimpulan hasil analisa dari aplikasi searching algorithm pada permasalahan Kotak-8 ini.
{ {
{
Karakteristik menarik AI dalam menyelesaikan suatu masalah adalah adanya karakteristik heuristik yang melekat padanya.
Heuristik adalah {
{
{ {
Prinsip atau informasi atau knowledge (bersifat problem-specific) yang dapat digunakan sebagai panduan (guidance) dalam penelusuran untuk mencapai goal states dengan cara yang efektif. Estimasi seberapa dekat current state dengan goal state dan ia yang membedakan penelusuran yang bersifat “intelligence” dengan yang tidak. Ia tidak unik dan merupakan gabungan dari beberapa prinsip atau informasi namun tidak menjamin (secara penuh) dicapainya goal states. Salah satu metode dari informed search Dapat dianggap sebagai pruning (memotong pohon) dengan mempertimbangkan node yang promising (menjanjikan atau lebih pasti menuju GS).
Oleh karena itu, seyogyanya fungsi heuristik tidak terlalu rumit (sederhana dan mudah untuk dihitung) karena akan diaplikasikan ke setiap node.
Fakta Æ menyatakan deskripsi tentang obyek yang menjadi perhatian Kaidah (rule) Æ aturan yang bila diterapkan pada suatu keadaan (state) (dari fakta) akan menghasilkan keadaan (state) baru Prakondisi (antecedent) Æ persyaratan agar suatu kaidah tertentu dapat diterapkan pada suatu state Aksi (consequence) Æ hasil yang diperoleh bila kaidah yang bersangkutan dieksekusi.
Inferensi (penalaran) Æ adalah untaian (chain) dari kaidah untuk bergerak dari keadaan awal (initial state) menuju keadaan sasaran (goal state)
Dalam proses pencarian solusi terbaik, AI melakukan tindakan penelusuran (searching) menggunakan suatu algoritma tertentu. Searching pada dasarnya adalah penelusuran untuk mendapatkan l langkah k h terdekat t d k t ((minimal) i i l) menuju j GS dari d i IS dengan d menggunakan k kaidah (rule). Arah searching ditujukan kepada jumlah GS terbesar.
Searching ditentukan oleh 3 (tiga) faktor : { branching factor yang menyatakan jumlah rata-rata simpul yang dapat dicapai oleh simpul induk secara langsung, jumlah rata-rata kaidah untuk mencapai state berikutnya dan seberapa luas state space tree diagram searching { Jumlah GS { Model penalaran manusia.
Searching dapat dilakukan melalui salah satu dari 2 (dua) arah { forward searching yang mengikuti model penalaran manusia dan backward searching. Metode forward searching dilakukan dengan mencocokkanya dengan Prakondisi dan dilakukan bila branching factor kecil { backward searching dilakukan dengan cara mencocokkannya dengan Aksi atau mencari simpul induk.
2
1/2/2007
Proses penelusuran adalah sebagai berikut :
{ {
{
Diberikan keadaan awal atau IS. Aplikasikan prosedur atau kaidah dengan persyaratan Prakondisi dan Aksi yang telah ditetapkan untuk mendapatkan GS. Terapkan control strategy dengan memilih satu dari active rule y yang g ada untuk diterapkan. p Control strategy akan menentukan kesuksesan proses penelusuran. Kesalahan pemilihan control strategy akan berdampak pada tidak didapatkannya solusi seperti yang diharapkan.
Konsep dasar Æ penelusuran dengan cara mengekplorasi simpul anak k yang pertama t k li ia kali i buka. b k Bila Bil GS tidak tid k ditemukan dit k pada d simpul yang dibuka, ia akan bergerak mundur untuk membuka simpul anak berikutnya { { { { { {
{
Berikan simpul awal pada daftar “open”. Loop : if open = kosong then exit(fail). n := first(open) if goal(n) then exit(success) Remove(n, open) dan Add(n, closed) Ekspansikan n. Berikan pada kepala “open” semua simpul anak yang belum muncul pada “open” atau “closed” dan bubuhkan pointer pada n. Kembali ke Loop.
S
A
C
[S] [AB ] [CDB] [DB] [B] [EF] [HGF] [GF]
IS
B
D
E
F
Urutan pelacakan : S, A, C, D, B, E, F, H, G H
G GS
Tree Diagram
Fungsi pointer untuk solution path Urutan Searching
3
1/2/2007
[S] [AB ] [BCD] [CDEF] [DEF] [EF] [FHG] [HG] [G]
Konsep dasar Æ BFS akan melakukan penelusuran pada semua cabang yang dibuka dari simpul induknya. induknya Pencarian dilakukan dalam arah horisontal sehingga semua cabang yang dibuka dijamin akan mendapatkan giliran yang adil. Bila pada kedalaman (depth) yang sama GS belum ditemukan, maka dilakukan pembukaan cabang baru lagi sesuai dengan urutan pembukaan cabang sebelumnya Berikan simpul awal pada daftar “open”. Loop : if open = kosong then exit(fail). { n := first(open) ( p ) { if goal(n) then exit(success) { Remove(n, open) dan Add(n, closed) { Ekspansikan n, berikan semua simpul anak pada ekor “open” dan bubuhkan pointer dari simpul anak ke-n. { Kembali ke Loop. { {
Urutan pelacakan : S, A, B, C, D, E, F, H, G Fungsi pointer untuk solution path Tree Diagram
Urutan Searching
Konsep dasar Æ metode BsFS menggunakan nilai nilai heuristik tiap simpul yang dibuka. dibuka Simpul dengan nilai heuristik terkecil akan dibuka terlebih dulu. Bila GS belum ditemukan, akan dilakukan pemeriksaan pada simpul berikutnya dengan nilai heuristik terkecil pada kedalaman yang sama { { { { { {
{
Berikan simpul awal pada daftar “open” Loop : if open = kosong then exit(fail). n := first(open) if goal(n) then exit(success) Remove(n, open) dan Add(n, closed) Ekspansikan n, hitung h(n) untuk semua simpul anak ni dan bubuhkan pointer dari ni ke-n. Berikan semua simpul anak pada “open” dan urutkan mulai dari biaya terendahnya. Kembali ke Loop
h
4
1/2/2007
Time Complexity yang menyatakan waktu yang diperlukan untuk mencapai sasaran. Ini sangat berkaitan erat dengan cp cpu time dan branching factor. factor Space Complexity yang mengukur jumlah memory yang dibutuhkan untuk implementasi search dan diukur dalam bentuk besar byte.
Completeness yang mengukur jaminan bahwa GS dicapai oleh search berdasarkan pada searching algorithm yang dipakai. dipakai
Optimality yang memberikan ukuran jaminan bahwa solution path adalah paling minimum.
Penekanan utama : { {
{
Representasi struktur data. Proses pembangkitan generasi penerus (successor) atau simpul anak ( (child node). ) Solution path.
Shortest path to GS (solution path)
Compiler /Intepreter JDK versi 1.5.0.9 dengan Editor JCreator LE versi 4.0
Representasi Data Æ Struktur data direpresentasikan dalam bentuk vektor matriks dengan dimensi 1 x 9, sebagai contoh adalah [ 7 1 4 2 3 5 8 0 6 ] dimana “0” mewakili lokasi yang tid k terisi tidak t i i pada d susunan tile til Kotak-8 K t k8
Implementasi BFS, DFS, BestFS dan Solution Path.
5
1/2/2007
State -order : int[] -parent : State -size : int -level : int -cost : int -stateNum : int -path : String -pathBuffer : StringBuffer -heuristic : int
MyPuzzle.class
MyShufflePuzzle.class
M T S MyTreeSearch.class h l
State.class
+State(in initState : State, in order : int[]) +init() : void +getLevel() : int +getHeuristic() : int +getStateNum() : int +getCost() : int +getPath() : int +getParent() : State +setPath(in path : String) : void +setParent(in parent : State) : void +setLevel(in level : int) : void +calculateHeuristic(in goal : int[]) : void +isRoot() : boolean +getOrder() : int[] +isGoal(in goalState : State) : boolean +moveUp() : State +moveDown() : State +moveRight() : State +moveLeft() : State +shuffle() : State +getSuccessors() : ArrayList -getZeroposition(in order : int[]) : int -copyOrder() : int[] -compareTo(in o : Object) : int -toString() : String
Berikan simpul awal pada daftar “open”
MyTreeSearch
n
1
-initState : State -goalState : State -depth : int -numofState : int -open : LinkedList -close : ArrayList -goalFound : Boolean = false -printSolution : Boolean
+MyTreeSearch(in initState : State, in goalState : State, in depth : in, in printSolution : boolean) +depthFirstSearch() : void +breadthFirstSearch() : void +bestFirstSearch() : void +printSolutionPath(in theState : State) : void
public void breadthFirstSearch() { State currentState = null; open.addFirst(initState);
Loop : if open = kosong then exit(fail) n := first(open)
Mo de
Pa k
ai
System.out.println("Pencarian dengan Breadth First Search..."); while (!open.isEmpty()) { currentState = (State) open.getFirst(); System.out.println(currentState.toString() + "\n"); if ( currentState.isGoal(goalState)) { goalFound = true; System out println("Goal ditemukan.."); System.out.println("Goal ditemukan "); if goal(n) then exit(success)
Remove(n, open) Add(n, closed)
if(printSolution) printSolutionPath(currentState); break; } open.removeFirst(); close.add(currentState.toString());
6
1/2/2007
if (currentState.getLevel() < depth) {
Berikan simpul awal pada daftar “open”
public void depthFirstSearch() { State currentState = null; open.addFirst(initState);
ArrayList list = currentState.getSuccessors(); Iterator e = list.iterator(); while (e.hasNext()) { State successor = (State) e.next(); Ekspansikan n. Berikan pada ekor “open” semua simpul anak yang belum muncul pada “open” atau “closed” dan bubuhkan pointer pada n.
S t System.out.println("Pencarian t i tl ("P i dengan d Depth First Search..."); Loop : if open = kosong then exit(fail) n := first(open)
//untuk Solution Path if(printSolution) successor.setParent(currentState);
System.out.println(currentState.toString() + "\n"); if ( currentState.isGoal(goalState)) {
if (!close.contains(successor.toString())) { open.addLast(successor); numOfState++; } }
while (!open.isEmpty()) { currentState = (State) open.getFirst();
System.out.println("Goal ditemukan..."); goalFound = true;
if goal(n) then exit(success)
}
if(printSolution) printSolutionPath(currentState); break;
}
Kembali ke Loop
if (!goalFound) System.out.println("Goal tidak ditemukan...");
} Remove(n, open) Add(n, closed)
}
open.removeFirst(); close.add(currentState.toString()); System.out.println(currentState.getLevel());
if (currentState.getLevel() < depth) { ArrayList list = currentState.getSuccessors(); System.out.println("Jumlah suksesor : " + list.size());
Berikan simpul awal pada daftar “open”
System.out.println("Pencarian dengan Best First Search...");
Iterator e = list.iterator(); while (e.hasNext()) { State successor = (State) e.next();
Ekspansikan n. Berikan pada kepala “open” semua simpul anak yang belum muncul pada “open” atau “closed” dan bubuhkan pointer pada n.
Loop : if open = kosong then exit(fail) n := first(open)
//untuk Solution Path if(printSolution) successor.setParent(currentState); if ((!close.contains(successor.toString())) ( g())) { open.addFirst(successor); numOfState++; } }
if goal(n) then exit(success)
}
if ( currentState.isGoal(goalState)) { goalFound = true; System.out.println("Goal ditemukan..."); if(printSolution) printSolutionPath(currentState); break;
}
if (!goalFound) System.out.println("Goal tidak ditemukan...");
while (!open.isEmpty()) { currentState = (State) open.getFirst(); System.out.println(currentState.toString() + " nilai heuristik = " + currentState.getHeuristic() + "\n");
}
Kembali ke Loop
public void bestFirstSearch() { State currentState = null; open = new LinkedList(); ArrayList close = new ArrayList(); open.addFirst(initState);
Remove(n, open) Add(n, closed)
} open.removeFirst(); close.add(currentState.toString());
7
1/2/2007
ArrayList list = currentState.getSuccessors(); Iterator e = list.iterator();
Ekspansikan n, hitung h(n) untuk semua simpul anak ni dan bubuhkan pointer dari ni ke-n ke n.
public void printSolutionPath(State theState) { State curState = null; Stack stack = new Stack(); System.out.println("Solution pathnya adalah .. \n\n");
while ((e.hasNext()) ()) { State successor = (State) e.next(); //ditambahkan untuk menunjuk ke parent if(printSolution) successor.setParent(currentState);
//lakukan backtrack untuk menentukan solution pathnya... while(theState != null) { stack.push(theState); theState = theState.getParent(); }
if (!close.contains(successor.toString())) { Berikan semua simpul anak pada “open” dan urutkan mulai dari biaya terendahnya.
successor.calculateHeuristic(goalState.getOr der()); // calculate heuristic open.addFirst(successor); numOfState++; }
while(true) { try { curState = (State)stack.pop(); (State)stack pop(); } catch(EmptyStackException e) { break; }
} //sort open list in order of heuristic value Collections.sort(open); }
Kembali ke Loop
System.out.println(curState.toString() + "\n");
if (!goalFound) System.out.println("Goal tidak ditemukan");
} }
}
Test Input Vector
Digunakan 4 (empat) vektor input untuk membandingkan keefektifan algoritma dan solution path paling efisien
Algoritma
BFS DFS
{ { {
[103456278] [143026578] [743126508] [253160478]
15
BestFS BFS DFS
{
Depth
20
BestFS BFS DFS
20
BestFS BFS DFS BestFS
25
Completeness
Optimality
Panjang Solution Path (Cost)
Simpul dibuka
Ya
Ya
11
2.237
Ya
Tidak
21
7.425
Ya
Tidak
47
205
17 GS tidak ditemukan 109
29.288
Ya
Ya
Tidak
Tidak
Ya
Ya
Ya
Ya
Tidak
Tidak
Ya
Tidak
13 GS tidak ditemukan 91
5.431 495 4.741 2.220 996
Ya
Ya
7
268
Ya
Tidak
25
3.830
Ya
Ya
7
15
8
1/2/2007
IS
Test Input Vector
Algoritma
Depth
BFS DFS
15
BestFS
Completeness
Optimality
Panjang Solution Path (Cost)
Simpul dibuka
Ya
Ya
11
2.237
Ya
Tidak
21
7.425
Ya
Tidak
47
Depth - 0
Depth - 1
205
1
3
0
4
5
6
2
7
8
Rule Ka
Rule Ba
DFS
25
BestFS BFS DFS
30
BestFS BFS DFS BestFS
25
Ya
Ya
17
29.288
Ya
Tidak
25
5.098
Ya
Tidak
109
495
Ya
Ya
13
4.741
Ya
Tidak
29
15.670
Ya
Tidak
91
996
Ya
Ya
7
268
Ya
Tidak
25
3.830
Ya
Ya
7
15
Depth - 2
0
3
4
5
6
2
7
8
1
5
3
0
1
3
4
0
6
4
5
6
2
7
8
2
7
8
Rule Ki
Rule Ba
Rule Ka
BFS
1
Rule Ba
Rule Ki
Rule Ba
Rule At
Rule Ka
1
3
6
1
0
3
1
5
3
1
5
3
1
5
3
1
0
3
4
1
3
1
0
3
4
5
0
4
5
6
4
6
0
4
7
6
0
4
6
4
5
6
0
5
6
4
5
6
2
7
8
2
7
8
2
7
8
2
0
8
2
7
8
2
7
8
2
7
8
2
7
8
Pruning
Pruning
Pruning
Solution Path
1
2
3
4
5
6
7
0
8
1
2
3
4
5
6
7
8
0
GS
IS
Heuristik = 0
Rule Ki
1
0
3
4
5
6
2
7
8 Rule Ba
0
1
3
1
5
3
4
5
6
4
0
6
2
7
8
2
7
8
Heuristik = 4
Rule Ba
Heuristik = 3
Rule Ba
1
0
3
4
2
5
7
8
6
Rule Ka
Heuristik = 1
Heuristik = 0
1
2
3
1
3
0
4
0
5
4
2
5
7
8
6
7
8
6
Rule Ki
2
3
1
2
3
1
2
3
4
5
0
0
4
5
4
8
5
7
8
6
7
8
6
7
0
6
1
2
3
5
6
8
0
7
3
7
6
2
0
8
Heuristik = 4
Rule Ka
1
5
3
1
5
3
4
7
6
4
7
6
0
2
8
2
8
0
Rule Ba
1
4
5
4
Rule Ki
Heuristik = 4
Rule Ka
Solution Path Heuristik = 2
1
GS
9
1/2/2007
BFS menampilkan p keunggulan gg ditinjau j dari Completeness p
dan Optimality (Solution Path, Cost) BestFS mampu menampilkan Completeness dan namun
tidak Optimality karena Cost yang digunakan cukup besar DFS menampilkan performa terendah di antara ketiga
algoritma dan dalam beberapa problem tidak mampu mencapai Completeness dan Optimality Algoritma BFS adalah yang paling tepat digunakan untuk
menyelesaikan Problem Kotak-8 pada contoh kasus vektor input yang digunakan pada naskah ini
10
