Arama Algoritmaları
Arama Algoritmaları
Bu yazıda çeşitli Arama Algoritmalarının C kodlarına yer verim.
Yer Alan algoritmalar:
•Breadth First Search (BFS)
•Depth First Search (DFS)
•Depth limited Search (DLS)
•Iterative Deepening Search (IDS)
•Bidirectional Search (BS)
Yukarıda yer alan algoıritmalaları tek bir kaynak kodda toparladım.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
//////////////// our tree /////////////////
struct tree{
int index;
int board[9];
int depth;
int fringe_size;
struct tree *father;
struct tree *children[4];
struct tree *next;
struct tree *back;
};
typedef struct tree T;
//////////////// our Fringe ///////////////////////
typedef struct tree F;
typedef F *Fptr;
Fptr head=NULL,tail=NULL;
Fptr Ghead=NULL,Gtail=NULL;
//////////////// define our goal state ///////////////
int goal_state[9]={1 ,2, 3, 8, 0 , 4 , 7 , 6 , 5 };
int counter;
int limit=0;
int i , j , k;
int inx=1; // index of our state
T *root=NULL; // ROOT of our tree
int swap=0; // use in to solve Bidirectional Search
int check_BS=0; // use in to solve Bidirectional Search
//////////////// General Prototypes /////////////////
T *randomState();
void printstate(T *);
int checkGoal(T *);
int checkGoal_BS(T *B ,T *G);
int checkRepeated(T *node);
void startSolve_BFS(T *B);
void startSolve_DFS(T *B);
void startSolve_DL(T *B);
void startSolve_IDS(T *B);
void startSolve_BS(T *B ,T *G);
//////////////// Tree Prototypes ////////////////////
T *createNode();
void expand(T *old,int dir);
//////////////// Fringe Prototypes //////////////////
void printFringe(Fptr);
int emptyF(Fptr);
int popF(Fptr *,Fptr *);
void pushF(Fptr *, Fptr *, T *);
int Fringe_size(Fptr);
FILE *fp;
//////////////// File Prototypes //////////////////
void OpenFile();
void CloseFile();
void printToFile(T *);
/////////////// Open Fringe.dat //////////////////
void OpenFile()
{
fp = fopen("fringe.dat", "a+") ;
if(fp == NULL){
printf("\"fringe.dat\" dosyasi acilamadi!") ;
exit(0) ;
}
}
//////////////// Close File /////////////////////////
void CloseFile()
{
fclose(fp);
}
//////// Print Node's Board to file as a integer ////
void printToFile(T *B)
{
int n_board=0;
for(i=0;i<9;i++) n_board=n_board+((B->board[i])*(pow(10,i)));
fprintf(fp,"\n%d",n_board);
}
/////////// print our fringe on screen ////////////
void printFringe(Fptr currentPtr){
if(currentPtr==NULL)
printf("\nFringe is empty\n");
else{
while(currentPtr!=NULL){
printf(">%d",currentPtr->index);
currentPtr=currentPtr->next;
}
}
}
////////////// calculate fringe size /////////////
int Fringe_size(Fptr currentPtr){
counter=0;
if(currentPtr==NULL)
printf("\nFringe is empty\n");
else{
while(currentPtr!=NULL){
counter++;
currentPtr=currentPtr->next;
}
}
// printf("\nFRINGE SIZE = %d\n",counter);
return counter;
}
//////////// controls that fringe is empty /////////////
int emptyF(Fptr head){
return head==NULL;
}
//////// pop node our fringe - First In First Out /////////
Fptr popFIFO(Fptr *head,Fptr *tail){
Fptr f_temp;
f_temp=*head; // that we returns f_temp
*head=(*head)->next; // we shift head one step
if(*head==NULL)
*tail=NULL;
return f_temp;
}
////////// pop node our fringe - Last in First Out ////////////
Fptr popLIFO(Fptr *head,Fptr *tail){
Fptr f_temp;
f_temp=*tail; //that we returns f_temp
(*tail)=(*tail)->back; //we shift tail one step
if(*tail==NULL)
*head=NULL;
if((*tail==NULL) && (*head==NULL))
return NULL;
return f_temp;
}
/////////////////// push node our fringe ////////////////
void pushF(Fptr *head,Fptr *tail, T *node){
Fptr newptr;
newptr=malloc(sizeof(Fptr));
if(newptr != NULL) {
newptr=node;
newptr->next=NULL;
newptr->back=NULL;
if(emptyF(*head)) //if fringe is empty
*head=newptr;
else{
(*tail)->next=newptr;
newptr->back=(*tail);
}
*tail=newptr;
}
else
printf("\nInsert to Fringe is FAILED!!\n");
}
//////////////////// creates a new node ////////////////
T *createNode()
{
int i=0;
T *newNode;
newNode=(T*)malloc(sizeof(T));
if(!(newNode=(T*)malloc(sizeof(T)))) {
printf("Out of memory!\n");
exit(1);
}
inx=inx+1;
newNode->index=inx; // sets new Node's index
newNode->depth=0; // sets new Node's depth zero
newNode->fringe_size=0; // sets new Node's fringe size zero
for(i=0;i<9;i++) newNode->board[i]=0;
newNode->father = NULL;
newNode->children[0] = NULL;
newNode->children[1] = NULL;
newNode->children[2] = NULL;
newNode->children[3] = NULL;
newNode->next=NULL;
return newNode;
}
//////////////// expans node in Tree ////////////////
void expand(T *old,int dir)
{
int i=0;
int temp;
int n_board[9];
T *newNode;
for(i=0;i<9;i++) n_board[i]=old->board[i];
newNode=createNode();
//////// change state ///////////
if(dir==0){ // if direction is "zero",the blank sets left
for(i=0;i<9;i++){ if(n_board[i]==0){ temp=n_board[i-1]; n_board[i-1]=0; n_board[i]=temp; } } } if(dir==1){ // if direction is "1",the blank sets right for(i=8;i>=0;i--){
if(n_board[i]==0){
temp=n_board[i+1];
n_board[i+1]=0;
n_board[i]=temp;
}
}
}
if(dir==2){ // if direction is "2",the blank sets top
for(i=0;i<9;i++){ if(n_board[i]==0){ temp=n_board[i-3]; n_board[i-3]=0; n_board[i]=temp; } } } if(dir==3){ // if direction is "3",the blank sets bottom for(i=8;i>=0;i--){
if(n_board[i]==0){
temp=n_board[i+3];
n_board[i+3]=0;
n_board[i]=temp;
}
}
}
for(i=0;i<9;i++) newNode->board[i]=n_board[i];
newNode->father = old;
newNode->depth=(old->depth+1); // newnode's depth is father's +1
// if node is not repeated or it is Bidirectional Search
if((checkRepeated(newNode) == 0) || (check_BS==1)){
if((limit==0) || (limit>=newNode->depth)){
// this if statement is for depth limited search
// if limit equals zero it means there is not depth limit search
old->children[dir] = newNode; // newnode is old node's child
OpenFile();
printToFile(newNode);
CloseFile();
// push newnode in our fringe
if((swap%2)==0)
pushF(&head,&tail,newNode);
if((swap%2)==1)
pushF(&Ghead,&Gtail,newNode);
newNode->fringe_size= Fringe_size(head);
//calculate our fringe size
}
}
}
/////////// Checks for goal state ///////////
int checkGoal(T *B)
{
int c_board[9];
counter=0;
for(i=0;i<9;i++) c_board[i]=B->board[i];
for(i=0;i<9;i++){ if(c_board[i]==goal_state[i]) counter++; } //if counter is 9 it is goal state if(counter==9){ printf("\nALGORITHM FOUND THE GOAL STATE"); printstate(B); while(B->father!=NULL){
B=B->father;
printstate(B);
}
return 0; //it is goal state
}
else
return 1; //it is not goal state
}
/*
* Checks for goal state in Bidirectional Search
* 1 - it is not goal state
* 0 - it is goal state
*/
int checkGoal_BS(T *B , T *G)
{
T *GF;
counter=0;
GF=G->father;
for(i=0;i<9;i++){ if(B->board[i]==(G->board[i]))
counter++;
}
if(counter==9){
printf("\nALGORITHM FOUND THE GOAL STATE");
printstate(B);
while(B->father!=NULL){
B=B->father;
printstate(B);
}
return 0;
}
counter=0;
if(GF!=NULL){
for(i=0;i<9;i++){ if(B->board[i]==(GF->board[i]))
counter++;
}
if(counter==9){
printf("\nALGORITHM FOUND THE GOAL STATE");
printstate(B);
while(B->father!=NULL){
B=B->father;
printstate(B);
}
return 0;
}
}
if(GF!=NULL){
for(j=0;j<4;j++){ counter=0; if((GF->children[j])!=NULL){
for(i=0;i<9;i++){ if(B->board[i]==(GF->children[j]->board[i]))
counter++;
}
if(counter==9){
printf("\nALGORITHM FOUND THE GOAL STATE");
printstate(B);
while(B->father!=NULL){
B=B->father;
printstate(B);
}
return 0;
}
}
}
}
return 1;
}
//////////// Checks for repeated state //////////
int checkRepeated(T *node) {
int counter=0;
int board;
int n_board=0;
// convert board as integer
for(i=0;i<9;i++) n_board=n_board+((node->board[i])*(pow(10,i)));
OpenFile(); //open file
while(!feof(fp)){ // search file
fscanf(fp,"%d",&board);
if(board==n_board){
CloseFile();
return 1; // node is expanded before
}
}
CloseFile();
return 0; // node is not repeated
}
//////// solve Breadth First Search ////////////
void startSolve_BFS(T *B)
{
int c;
T *tmp;
T *f;
tmp=B;
c=checkGoal(tmp);//if it is "zero" end the program
if(c==0){
getch();
exit(1);
}
if(c!=0){ // if state is not repeated
for(i=0;i<9;i++){ if(tmp->board[i]==0){
if(i==0){
expand(tmp,1);
expand(tmp,3);
}
if(i==1){
expand(tmp,0);
expand(tmp,1);
expand(tmp,3);
}
if(i==2){
expand(tmp,0);
expand(tmp,3);
}
if(i==3){
expand(tmp,1);
expand(tmp,2);
expand(tmp,3);
}
if(i==4){
expand(tmp,0);
expand(tmp,1);
expand(tmp,2);
expand(tmp,3);
}
if(i==5){
expand(tmp,0);
expand(tmp,2);
expand(tmp,3);
}
if(i==6){
expand(tmp,1);
expand(tmp,2);
}
if(i==7){
expand(tmp,0);
expand(tmp,1);
expand(tmp,2);
}
if(i==8){
expand(tmp,0);
expand(tmp,2);
}
}
}
f=popFIFO(&head,&tail); //pop node in our fringe
startSolve_BFS(f);
}
}
//////// solve Depth First Search ////////////
void startSolve_DFS(T *B)
{
int c;
T *tmp;
T *f;
tmp=B;
c=checkGoal(tmp);//if it is "zero" end the program
if(c==0){
getch();
exit(1);
}
if(c!=0){ // if state is not repeated
for(i=0;i<9;i++){ if(tmp->board[i]==0){
if(i==0){
expand(tmp,1);
expand(tmp,3);
}
if(i==1){
expand(tmp,0);
expand(tmp,1);
expand(tmp,3);
}
if(i==2){
expand(tmp,0);
expand(tmp,3);
}
if(i==3){
expand(tmp,1);
expand(tmp,2);
expand(tmp,3);
}
if(i==4){
expand(tmp,0);
expand(tmp,1);
expand(tmp,2);
expand(tmp,3);
}
if(i==5){
expand(tmp,0);
expand(tmp,2);
expand(tmp,3);
}
if(i==6){
expand(tmp,1);
expand(tmp,2);
}
if(i==7){
expand(tmp,0);
expand(tmp,1);
expand(tmp,2);
}
if(i==8){
expand(tmp,0);
expand(tmp,2);
}
}
}
f=popLIFO(&head,&tail); //pop node from our fringe
if(f==NULL){
printf("\nCAN NOT SOLVE PROBLEM WITH DEPTH FIRST SEARCH!!!\n");
exit(1);
}
startSolve_DFS(f);
}
}
//////// solve Depth limited Search ////////////
void startSolve_DL(T *B){
int c;
T *tmp;
T *f;
tmp=B;
c=checkGoal(tmp);//if it is "zero" end the program
if(c==0){
getch();
exit(1);
}
if(c==1){ // if state is not repeated
for(i=0;i<9;i++){ if(tmp->board[i]==0){
if(i==0){
expand(tmp,1);
expand(tmp,3);
}
if(i==1){
expand(tmp,0);
expand(tmp,1);
expand(tmp,3);
}
if(i==2){
expand(tmp,0);
expand(tmp,3);
}
if(i==3){
expand(tmp,1);
expand(tmp,2);
expand(tmp,3);
}
if(i==4){
expand(tmp,0);
expand(tmp,1);
expand(tmp,2);
expand(tmp,3);
}
if(i==5){
expand(tmp,0);
expand(tmp,2);
expand(tmp,3);
}
if(i==6){
expand(tmp,1);
expand(tmp,2);
}
if(i==7){
expand(tmp,0);
expand(tmp,1);
expand(tmp,2);
}
if(i==8){
expand(tmp,0);
expand(tmp,2);
}
}
}
f=popLIFO(&head,&tail); //pop node from our fringe
if(f==NULL){
printf("\nCAN NOT SOLVE PROBLEM WITH %d LIMITED DEPTH!!!\n",limit);
exit(1);
}
startSolve_DL(f);
}
}
//////// solve Iterative Deeping Search ////////////
void startSolve_IDS(T *B){
int c;
T *tmp;
T *f;
tmp=B;
c=checkGoal(tmp);//if it is "zero" end the program
if(c==0){
getch();
exit(1);
}
if(c!=0){
for(i=0;i<9;i++){ if(tmp->board[i]==0){
if(i==0){
expand(tmp,1);
expand(tmp,3);
}
if(i==1){
expand(tmp,0);
expand(tmp,1);
expand(tmp,3);
}
if(i==2){
expand(tmp,0);
expand(tmp,3);
}
if(i==3){
expand(tmp,1);
expand(tmp,2);
expand(tmp,3);
}
if(i==4){
expand(tmp,0);
expand(tmp,1);
expand(tmp,2);
expand(tmp,3);
}
if(i==5){
expand(tmp,0);
expand(tmp,2);
expand(tmp,3);
}
if(i==6){
expand(tmp,1);
expand(tmp,2);
}
if(i==7){
expand(tmp,0);
expand(tmp,1);
expand(tmp,2);
}
if(i==8){
expand(tmp,0);
expand(tmp,2);
}
}
}
f=popLIFO(&head,&tail);
if(f==NULL){
printf("\nCAN NOT SOLVE PROBLEM WITH %d LIMITED DEPTH!!!\n",limit);
limit++; //increased the limit
pushF(&head,&tail,root); //push root to our fringe
f=popFIFO(&head,&tail);
// open and close to file for empty the file
fp = fopen("fringe.dat", "w+") ;
fclose(fp);
startSolve_IDS(f); // start to solve again with new limit
}
startSolve_IDS(f);
}
}
//////// solve Bidirectional Search ////////////
void startSolve_BS(T *B, T *G){
int c;
T *tmp;
T *f;
T *g;
tmp=B;
check_BS=1;
// We have 2 start node
// first is our random state, second is our goal state
c=checkGoal_BS(tmp,G);//if it is "zero" end the program
if(c==0){
getch();
exit(1);
}
if(c!=0){ // if state is not repeated
for(i=0;i<9;i++){ if(tmp->board[i]==0){
if(i==0){
expand(tmp,1);
expand(tmp,3);
}
if(i==1){
expand(tmp,0);
expand(tmp,1);
expand(tmp,3);
}
if(i==2){
expand(tmp,0);
expand(tmp,3);
}
if(i==3){
expand(tmp,1);
expand(tmp,2);
expand(tmp,3);
}
if(i==4){
expand(tmp,0);
expand(tmp,1);
expand(tmp,2);
expand(tmp,3);
}
if(i==5){
expand(tmp,0);
expand(tmp,2);
expand(tmp,3);
}
if(i==6){
expand(tmp,1);
expand(tmp,2);
}
if(i==7){
expand(tmp,0);
expand(tmp,1);
expand(tmp,2);
}
if(i==8){
expand(tmp,0);
expand(tmp,2);
}
}
}
// we have 2 fringe
swap++; //use integer swap to select fringe
if((swap%2)==0){
f=popFIFO(&head,&tail); //pop first node from first fringe
g=popLIFO(&Ghead,&Gtail); //pop second node to solve BS
pushF(&Ghead,&Gtail,g); //push it for use second step
startSolve_BS(f,g);
}
if((swap%2)==1){
g=popFIFO(&Ghead,&Gtail); //pop first node from second fringe
f=popLIFO(&head,&tail);
pushF(&head,&tail,f);
startSolve_BS(g,f);
}
}
}
/////////// prints state on screen ////////////
void printstate(T *B){
printf("\n*********************");
for(i=0;i<9;i++){ if(i%3==0) printf("\n"); printf("%d\t",B->board[i]);
}
printf("\n*********************\n");
printf("NODE's DEPTH : %d\n",B->depth);
printf("NODE's Fringe Size : %d\n",B->fringe_size);
}
/////// creates our first random state //////////
T *randomState()
{
int direction,temp,a;
int rand_state[9];
T *newNode;
T *GNode;
newNode = createNode();
GNode = createNode();
for(i=0;i<9;i++) //equal random state with goal state
rand_state[i]=goal_state[i];
k=rand()%10+10; // generate random move between 10 and 20
printf("Number of move to generate first state random is %d\n",k);
for(j=0;j<k;j++)
{
for(a=0;a<10;a++){
if(rand_state[a]==0) // find which element is zero in state
break;
}
if(a==0){ // if first element is zero
direction=rand()%2; // generate random direction
if(direction==0){
temp=rand_state[1];
rand_state[1]=rand_state[0];
rand_state[0]=temp;
}
if(direction==1){
temp=rand_state[3];
rand_state[3]=rand_state[0];
rand_state[0]=temp;
}
}
if(a==1){ // if second element is zero
direction=rand()%3;
if(direction==0){
temp=rand_state[1];
rand_state[1]=rand_state[0];
rand_state[0]=temp;
}
if(direction==1){
temp=rand_state[2];
rand_state[2]=rand_state[1];
rand_state[1]=temp;
}
if(direction==2){
temp=rand_state[1];
rand_state[1]=rand_state[4];
rand_state[4]=temp;
}
}
if(a==2){ // if third element is zero
direction=rand()%2;
if(direction==0){
temp=rand_state[2];
rand_state[2]=rand_state[1];
rand_state[1]=temp;
}
if(direction==1){
temp=rand_state[2];
rand_state[2]=rand_state[5];
rand_state[5]=temp;
}
}
if(a==3){ // if fourth element is zero
direction=rand()%3;
if(direction==0){
temp=rand_state[3];
rand_state[3]=rand_state[0];
rand_state[0]=temp;
}
if(direction==1){
temp=rand_state[3];
rand_state[3]=rand_state[4];
rand_state[4]=temp;
}
if(direction==2){
temp=rand_state[3];
rand_state[3]=rand_state[6];
rand_state[6]=temp;
}
}
if(a==4){ // if fifth element is zero
direction=rand()%4;
if(direction==0){
temp=rand_state[4];
rand_state[4]=rand_state[1];
rand_state[1]=temp;
}
if(direction==1){
temp=rand_state[3];
rand_state[3]=rand_state[4];
rand_state[4]=temp;
}
if(direction==2){
temp=rand_state[4];
rand_state[4]=rand_state[5];
rand_state[5]=temp;
}
if(direction==3){
temp=rand_state[4];
rand_state[4]=rand_state[7];
rand_state[7]=temp;
}
}
if(a==5){ // if sixth element is zero
direction=rand()%3;
if(direction==0){
temp=rand_state[5];
rand_state[5]=rand_state[2];
rand_state[2]=temp;
}
if(direction==1){
temp=rand_state[5];
rand_state[5]=rand_state[4];
rand_state[4]=temp;
}
if(direction==2){
temp=rand_state[5];
rand_state[5]=rand_state[8];
rand_state[8]=temp;
}
}
if(a==6){ // if seventh element is zero
direction=rand()%2;
if(direction==0){
temp=rand_state[6];
rand_state[6]=rand_state[3];
rand_state[3]=temp;
}
if(direction==1){
temp=rand_state[6];
rand_state[6]=rand_state[7];
rand_state[7]=temp;
}
}
if(a==7){ // if eightth element is zero
direction=rand()%3;
if(direction==0){
temp=rand_state[7];
rand_state[7]=rand_state[4];
rand_state[4]=temp;
}
if(direction==1){
temp=rand_state[7];
rand_state[7]=rand_state[6];
rand_state[6]=temp;
}
if(direction==2){
temp=rand_state[7];
rand_state[7]=rand_state[8];
rand_state[8]=temp;
}
}
if(a==8){ // if nineth element is zero
direction=rand()%2;
if(direction==0){
temp=rand_state[8];
rand_state[8]=rand_state[5];
rand_state[5]=temp;
}
if(direction==1){
temp=rand_state[8];
rand_state[8]=rand_state[7];
rand_state[7]=temp;
}
}
}
for(i=0;i<9;i++) newNode->board[i]=rand_state[i];
/*
newNode->board[0]=1;
newNode->board[1]=3;
newNode->board[2]=4;
newNode->board[3]=8;
newNode->board[4]=2;
newNode->board[5]=5;
newNode->board[6]=7;
newNode->board[7]=6;
newNode->board[8]=0;
*/
for(i=0;i<9;i++) GNode->board[i]=goal_state[i];
printf("\n---->FIRST STATE<----"); printstate(newNode); // print our random state root = newNode; pushF(&head,&tail,root); // push root our fringe pushF(&Ghead,&Gtail,GNode); return root; } int main() { int secim; T *s; T *g; fp = fopen("fringe.dat", "w+") ; fclose(fp); srand(time(NULL)); randomState(); s=popFIFO(&head,&tail); g=popFIFO(&Ghead,&Gtail); pushF(&Ghead,&Gtail,g); printf("\n>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>");
printf("\nSelect Algorithm to solve");
printf("\n[1] Breadth First Search");
printf("\n[2] Depth First Search");
printf("\n[3] Depth limited Search");
printf("\n[4] Iterative Deepening Search");
printf("\n[5] Bidirectional Search\n");
printf("Enter number of your choice : ");
scanf("%d",&secim);
switch(secim){
case 1:
startSolve_BFS(s);
Fringe_size(head);
break;
case 2:
startSolve_DFS(s);
Fringe_size(head);
break;
case 3:
printf("\nENTER THE DEPTH LIMIT:");
scanf("%d",&limit);
startSolve_DL(s);
break;
case 4:
limit=1;
startSolve_IDS(s);
break;
case 5:
startSolve_BS(s,g);
break;
default:
printf("\nWRONG CHOICE!!");
}
CloseFile();
}
Posted In
Yorumlar
Özgür Eralp
Yanıt Bırak