Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /* puzzle 8 by hanhan */
- /* belum beres :D */
- #include <iostream>
- #include <cstdlib>
- //#include "random_state.h"
- using std::cout;
- using std::endl;
- #define atas -3
- #define bawah 3
- #define kanan 1
- #define kiri -1
- //int pAwal[9] = {7,2,4,5,0,6,1,8,3};
- //int pAwal[9] = {4,2,1,3,5,6,0,7,8};
- //int pAwal[9] = {2,8,3,1,6,4,7,0,5}; //bisa
- //int pAwal[9] = {2,8,1,4,6,3,0,7,5};
- //int pAwal[9] = {1,2,3,8,0,4,6,5,7}; //gagal
- //int pAwal[9] = {1,3,4,8,6,2,7,0,5}; //berhasil
- //int pAwal[9] = {1,3,4,8,0,2,7,6,5}; //berhasil
- int pAwal[9] = {1,2,3,8,0,4,6,5,7}; //gagal
- int pAkhir[9] = {1,2,3,8,0,4,7,6,5};
- clock_t start, finish;
- double waktu;
- struct PuzzleNode {
- int node[9];
- int g;
- int h;
- int f;
- int langkah;
- PuzzleNode *parent;
- int plangkah; //langkah parent
- PuzzleNode *next;
- };
- PuzzleNode neighbors[4];
- PuzzleNode *first = NULL; //first list open
- PuzzleNode *last = NULL; //last list open
- PuzzleNode *akhir = NULL; //awal list closed
- PuzzleNode *awal = NULL; //akhir list closed
- void cp(int a[], int b[]) //salin posisi
- {
- for(int i=0;i<9;i++)
- {
- a[i]=b[i];
- }
- }
- int abs(int x) //fungsi absolut (kenapa ga bisa pakai yang sudah jadi ya?
- {
- if(x<0) return (x*-1);
- return x;
- }
- int compare(int pState[], int pGoal[]) //bandingkan dua posisi
- {
- int sama =0;
- for(int i=0;i<9;i++)
- {
- if(pState[i]!=pGoal[i])
- {
- sama=0;
- break;
- }
- else
- sama=1;
- }
- return sama;
- }
- int manhattanHeuristic(int pState[]) //pakai manhattan distance
- {
- int distance=0;
- int row, col,r,c;
- for(r=0;r<9;r++)
- {
- for(c=0;c<9;c++)
- {
- if(pState[r]!=0)
- {
- if(pState[r]==pAkhir[c])
- {
- row = r%3;
- col = r/3;
- distance += abs(row-(c%3)) + abs(col-(c/3));
- }
- }
- }
- }
- return distance;
- }
- void cetakPuzzle(int pState[]) //cetak puzzle
- {
- for(int i=0;i<9;i++)
- {
- if(i%3==0)
- cout<<endl;
- cout<<pState[i]<<" ";
- }
- cout<<endl;
- }
- int cariNol(int pState[]) //cari posisi Nol
- {
- int posisi;
- for(int i=0;i<9;i++)
- {
- if(pState[i]==0)
- posisi = i;
- }
- return posisi;
- }
- void gerak(int pState[], int arah, int p[])
- {
- int pNol,temp2;
- //int p[9];
- cp(p,pState); //salin state[] ke temp
- pNol=cariNol(p); //cari posisi nol ada di mana
- //gerak berdasarkan posisi nol
- temp2= p[pNol]; //tukar-tukar
- p[pNol] = p[pNol+arah];
- p[pNol+arah] = temp2;
- }
- void cekNeighbors(PuzzleNode *pState)
- {
- int posNol = cariNol(pState->node);
- switch(posNol)
- {
- case 0:
- gerak(pState->node,kanan,neighbors[0].node);
- gerak(pState->node,bawah,neighbors[1].node);
- neighbors[0].langkah = kanan;
- neighbors[1].langkah = bawah;
- break;
- case 1:
- gerak(pState->node,kiri,neighbors[0].node);
- gerak(pState->node,kanan,neighbors[1].node);
- gerak(pState->node,bawah,neighbors[2].node);
- neighbors[0].langkah = kiri;
- neighbors[1].langkah = kanan;
- neighbors[2].langkah = bawah;
- break;
- case 2:
- gerak(pState->node,kiri,neighbors[0].node);
- gerak(pState->node,bawah,neighbors[1].node);
- neighbors[0].langkah = kiri;
- neighbors[1].langkah = bawah;
- break;
- case 3:
- gerak(pState->node,atas,neighbors[0].node);
- gerak(pState->node,kanan,neighbors[1].node);
- gerak(pState->node,bawah,neighbors[2].node);
- neighbors[0].langkah = atas;
- neighbors[1].langkah = kanan;
- neighbors[2].langkah = bawah;
- break;
- case 4:
- gerak(pState->node,kiri,neighbors[0].node);
- gerak(pState->node,atas,neighbors[1].node);
- gerak(pState->node,kanan,neighbors[2].node);
- gerak(pState->node,bawah,neighbors[3].node);
- neighbors[0].langkah = kiri;
- neighbors[1].langkah = atas;
- neighbors[2].langkah = kanan;
- neighbors[3].langkah = bawah;
- break;
- case 5:
- gerak(pState->node,kiri,neighbors[0].node);
- gerak(pState->node,atas,neighbors[1].node);
- gerak(pState->node,bawah,neighbors[2].node);
- neighbors[0].langkah = kiri;
- neighbors[1].langkah = atas;
- neighbors[2].langkah = bawah;
- break;
- case 6:
- gerak(pState->node,atas,neighbors[0].node);
- gerak(pState->node,kanan,neighbors[1].node);
- neighbors[0].langkah = atas;
- neighbors[1].langkah = kanan;
- break;
- case 7:
- gerak(pState->node,kiri,neighbors[0].node);
- gerak(pState->node,atas,neighbors[1].node);
- gerak(pState->node,kanan,neighbors[2].node);
- neighbors[0].langkah = kiri;
- neighbors[1].langkah = atas;
- neighbors[2].langkah = kanan;
- break;
- case 8:
- gerak(pState->node,kiri,neighbors[0].node);
- gerak(pState->node,atas,neighbors[1].node);
- neighbors[0].langkah = kiri;
- neighbors[1].langkah = atas;
- break;
- }
- }
- //samentawis
- void cetakOpen()
- {
- cout<<"=======Isi open==========="<<endl;
- PuzzleNode *current = first;
- while(current)
- {
- cetakPuzzle(current->node);
- cout<<"F: "<<current->f<<"| G: "<<current->g<<" | H: "<<current->h<<endl;
- current = current->next;
- }
- cout<<"=======sampai sini==========="<<endl;
- }
- void cetakClose()
- {
- cout<<"=======Isi close==========="<<endl;
- PuzzleNode *current = awal;
- while(current->next)
- {
- cetakPuzzle(current->node);
- cout<<"F: "<<current->f<<"| G: "<<current->g<<" | H: "<<current->h<<endl;
- current = current->next;
- }
- cout<<"=======sampai sini==========="<<endl;
- }
- void bestNode(PuzzleNode *temp)
- {
- PuzzleNode *lOpen = first;
- //PuzzleNode *temp = new PuzzleNode;
- int min = lOpen->f;
- cp(temp->node,lOpen->node);
- temp->f = lOpen->f;
- temp->g = lOpen->g;
- temp->h = lOpen->h;
- temp->langkah = lOpen->langkah;
- //cp(temp->parent,lOpen->parent);
- temp->parent=lOpen->parent;
- //bandingkan f terkecil
- while(lOpen)
- {
- // cout<<"nilai Min= "<<min<<endl;
- if(lOpen->f<min)
- {
- min = lOpen->f;
- temp->f = lOpen->f;
- cp(temp->node,lOpen->node);
- temp->f = lOpen->f;
- temp->g = lOpen->g;
- temp->h = lOpen->h;
- temp->langkah = lOpen->langkah;
- //cp(temp->parent,lOpen->parent);
- //temp->parent=lOpen->parent;
- }
- lOpen= lOpen->next;
- }
- //
- //cout<<"node terbaik dengan F: "<<temp->f<<endl;
- // cetakPuzzle(temp->node);
- }
- void inputList(PuzzleNode *pState)
- {
- //cout<<"input list open"<<endl;
- PuzzleNode *lOpen = new PuzzleNode;
- cp(lOpen->node,pState->node);
- lOpen->f = pState->f;
- lOpen->g = pState->g;
- lOpen->h = pState->h;
- lOpen->langkah = pState->langkah;
- lOpen->plangkah = pState->plangkah;
- //cp(lOpen->parent,pState->parent);
- lOpen->parent=pState->parent;
- if(!first)
- {
- first = lOpen;
- last = lOpen;
- } else
- {
- last->next = lOpen;
- last = lOpen;
- }
- }
- void delNode(PuzzleNode *pState)
- {
- PuzzleNode *current = first;
- while(current)
- {
- if(compare(current->node,pState->node)==1)
- {
- if(current==first)
- {
- //if(current->next){
- first = current->next;
- //}
- delete current;
- }else if(current==last)
- {
- PuzzleNode *pos;
- pos = first;
- while(pos->next != last)
- pos = pos->next;
- pos->next = NULL;
- last = pos;
- delete current;
- }
- else {
- PuzzleNode *pos;
- pos = first;
- while(pos->next != current)
- pos = pos->next;
- pos->next = current->next;
- delete current;
- }
- break;
- }
- current=current->next;
- }
- }
- void inputClose(PuzzleNode *pState)
- {
- // cout<<"input close akan dimasukkan F: "<<pState->f<<" G: "<<pState->g<<" H: "<<pState->h<<endl;
- PuzzleNode *temp = new PuzzleNode;
- cp(temp->node,pState->node);
- temp->f = pState->f;
- temp->g = pState->g;
- temp->h = pState->h;
- temp->langkah = pState->langkah;
- temp->plangkah = pState->plangkah;
- //cp(temp->parent,pState->parent);
- temp->parent=pState->parent;
- if(!awal)
- {
- awal = temp;
- akhir = temp;
- } else
- {
- akhir->next = temp;
- akhir = temp;
- }
- }
- int cekInClosed(int pState[])
- {
- int sama =0;
- PuzzleNode *lClosed = awal;
- while(lClosed)
- {
- if(compare(lClosed->node,pState)==1)
- {
- sama =1;
- break;
- }
- lClosed = lClosed->next;
- }
- return sama;
- }
- void rekonstruksi(PuzzleNode *pNode)
- {
- //belum beresss
- cout<<"langkah:"<<endl;
- //int s= compare(pNode->node,pAwal);
- cout<<pNode->langkah<<endl;
- while(compare(pNode->node,pAwal)!=1)
- {
- cout<<pNode->langkah<<endl;
- pNode= pNode->parent;
- }
- // while(pNode->langkah==0)
- // {
- // cout<<pNode->langkah<<endl;
- // pNode->langkah = pNode->plangkah;
- // }
- }
- void AStar()
- {
- start = clock();
- PuzzleNode *pState = new PuzzleNode;
- PuzzleNode *x = new PuzzleNode;
- PuzzleNode *y = new PuzzleNode;
- int g=0;
- //int j=0;
- bool lanjut=true;
- cp(pState->node,pAwal);
- pState->h = manhattanHeuristic(pState->node);
- pState->f = pState->h;
- pState->g = 0;
- pState->langkah = 0;
- //cp(pState->parent,pAwal);
- pState->parent = NULL;
- //1. masukkan state awal ke openList
- inputList(pState);
- //car node terbaik
- //selama ada isinya di open
- PuzzleNode *open = first;
- while(lanjut){
- //cout<<"iterasi: "<<g<<endl;
- g++;
- //cetakOpen();
- bestNode(x);
- //delete di open
- delNode(x);
- //masukkan x ke close;
- //cetakPuzzle(x->node);
- inputClose(x);
- if(compare(x->node,pAkhir)==1)
- {
- cout<<"\n\nHoreee...ketemu"<<endl;
- cout<<"Posisi awal"<<endl;
- cetakPuzzle(pAwal);
- cout<<"\nPosisi Akhir"<<endl;
- cetakPuzzle(x->node);
- cout<<"Waktu iterasi: "<<g<<endl;
- //rekonstruksi(x);
- break;
- }
- cekNeighbors(x);
- for(int i=0;i<4;i++)
- {
- if((neighbors[i].langkah!=0) )
- {
- //cek apakah ada di closed
- if(cekInClosed(neighbors[i].node)!=1)
- {
- //cp(y->parent,x->node);
- y->parent=x;
- y->plangkah = x->langkah;
- y->langkah = neighbors[i].langkah;
- //cout<<"nilai plangkah: "<<x->langkah<<endl;
- y->g = x->g + 1 ;
- y->h = manhattanHeuristic(neighbors[i].node);
- y->f = y->g + y->h;
- cp(y->node,neighbors[i].node);
- //masukkan ke openlist
- inputList(y);
- }
- }
- }
- //cetakClose();
- if(open)
- lanjut = true;
- else
- break;
- }
- finish = clock();
- waktu = (double(finish)-double(start))/CLOCKS_PER_SEC;
- cout<<"waktu : "<<waktu<<" detik"<<endl;
- }
- void menu()
- {
- int pilih;
- cout<<"\n\t1. {1,3,4,8,6,2,7,0,5}"<<endl;
- cout<<"\t2. {2,8,1,0,4,3,7,6,5}"<<endl; //katanya hard
- cout<<"\t3. {2,8,1,4,6,3,0,7,5}"<<endl;
- cout<<"\t4. {5,6,7,4,0,8,3,2,1}"<<endl;
- //cout<<"\t5. Random"<<endl;
- cout<<"\n\tPilih State Awal: ";
- //std::cin>>pilih;
- pilih =5;
- int p[9];
- int xrand=0;
- switch(pilih)
- {
- case 1:
- p= {1,3,4,8,6,2,7,0,5};
- cp(pAwal,p);
- AStar();
- break;
- case 2:
- p= {2,8,1,0,4,3,7,6,5};
- cp(pAwal,p);
- AStar();
- break;
- case 3:
- p= {2,8,1,4,6,3,0,7,5};
- cp(pAwal,p);
- AStar();
- break;
- case 4:
- p= {5,6,7,4,0,8,3,2,1};
- cp(pAwal,p);
- AStar();
- break;
- default:
- p= {2,8,3,1,6,4,7,0,5};
- cp(pAwal,p);
- AStar();
- break;
- }
- }
- int main()
- {
- menu();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement