Ai Lab File

Artificial Intelligence Lab file

Atishay Jain 10783017 4CO5

Index

S. No. 1 2 3 4 5 6 7

Topic Breadth First Search Depth First Search Depth First Search with Iterative Deepening Simple Hill Climbing Steepest Ascent Hill Climbing Best First Search Tower of Hanoi

Page No 3 3 5 6 10 14 18

Program 1&2 : BFS & DFS /*****************************

2

*Name: Atishay Jain *Course: BE Final Year *Group: 4CO5 *Subject: Artificial Intelligence *Prog: BFS & DFS *****************************/ #include<stdio.h> int main() { int n,i,j,x,s; int a[100][100]; int stack[100]={0}; int tos=0; int visited[100]={0}; int next=0,flag=0; int queue[100]; int front=0; int rear=0; int parent[100]={0}; do{ // Program for dfs and bfs printf("Please enter the number of nodes(<100):" ); scanf("%d",&n); }while(n>100); printf("Please enter the adjacency matrix:\n"); for(i=0;i",next+1); for(i=0;i
3

{ }

stack[tos++]=i; visited[i]=1;

}

} }while(tos!=0); if(flag!=1) { printf("\n It is not possible to reach the destination."); } printf("\nBFS traversal:\n"); queue[rear++]=x; visited[x]=-1; parent[x]=-1; flag=0; do{ next=queue[front++]; if(next==s) { printf("%d",next+1); printf("\nShortest Route:"); do{ printf("%d<-",next+1); next=parent[next]; }while(next!=x); printf("%d\n",x+1); flag=1; break; } printf("%d->",next+1); for(i=0;i
Program 3: DFS with Iterative Deepening /***************************** *Name: Atishay Jain

4

*Course: BE Final Year *Group: 4CO5 *Subject: Artificial Intelligence *Prog: DFS Iterative Deepening *****************************/ #include<stdio.h> #include int main() { int n,i,j,x,s; int a[100][100]; int stack[100]={0}; int stops[100]={0}; int tos=0;

do{

int int int int

next=0,flag=0; front=0; rear=0; parent[100]={0};

printf("Please enter the number of nodes(<100):" ); scanf("%d",&n); }while(n>100); printf("Please enter the adjacency matrix:\n"); for(i=0;i
5

if(lk==k)

{printf("%d->",next+1);} if(lk<=k) { for(i=0;i
Program 4: Simple Hill Climbing /***************************** *Name: Atishay Jain *Course: BE Final Year *Group: 4CO5 *Subject: Artificial Intelligence *Prog: Simple Hill Climbing for 8 Puzzle Problem *****************************/ #include #include #include using namespace std; int start[3][3],final[3][3]; //Finds the position of the tile no t int findpos(int a[][3],int t) { for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { if(a[i][j]==t) return (3*i+j+1); }

6

} } //Calculation of Heuristic: Distance from final state int heurestic(int a[][3]) { int h=0,posi,posg; for(int i=1;i<=9;i++) { posi=findpos(a,i); posg=findpos(final,i); h+=abs((float)posg-posi); } return h; } //Matrix Display void display(int a[][3]) {

}

for(int i=0;i<3;i++) { cout<<"\n"; for(int j=0;j<3;j++) { if(a[i][j] !=9 ) cout<
int main() { int next[3][3]; int i ,j,hi,hf,hn, posi,posj,lftflags=0,rtflags=0, upflags=0, dwnflags=0,lftflagp=0,rtflagt=0, upflagp=0,dwnflagp=0; cout<<"\nEnter starting state(Enter 9 for blank):\n"; for(i=0;i<3;i++) for(j=0;j<3;j++) cin rel="nofollow">>start[i][j]; cout<<"\nEnter Final state(9 for empty tile):\n"; for(i=0;i<3;i++) for(j=0;j<3;j++) cin>>final[i][j]; hi=heurestic(start); hf=heurestic(final); cout<<"Strating h:"<
7

{

next[i][j]=start[i][j];

}

} while(hi>hf) {

for(i=0;i<3;i++) { for(j=0;j<3;j++) { if(next[i][j]==9) { posi=i; posj=j; } }

}

if(posi-1>=0 && upflags==0) { next[posi][posj]=next[posi-1][posj]; next[posi-1][posj]=9; upflags=1;dwnflagp=1;

} else if(posi+1<=2 && dwnflags==0) {

next[posi][posj]=next[posi+1][posj]; next[posi+1][posj]=9; dwnflags=1;upflagp=1;

} else if(posj-1>=0 && lftflags==0) {

next[posi][posj]=next[posi][posj-1]; next[posi][posj-1]=9; lftflags=1;rtflagt=1;

} else if(posj+1<=2 && rtflags==0) {

} else {

next[posi][posj]=next[posi][posj+1]; next[posi][posj+1]=9; rtflags=1;lftflagp=1;

cout<<"\nThe search cannot reach to the destination";

8

break;

}

//Calculate the heuristic of next state hn=heurestic(next); if(hn>=hi) { //Next Heuristic for(i=0;i<3;i++) { for(j=0;j<3;j++) { next[i][j]=start[i][j]; } } rtflagt=0; lftflagp=0; upflagp=0; dwnflagp=0; } else { hi=hn; lftflags=lftflagp; rtflags=rtflagt; upflags=upflagp; dwnflags=dwnflagp; rtflagt=0; lftflagp=0; upflagp=0; dwnflagp=0; cout<<"\n\n"<<"heurestic="<
} getch(); return 0; }

Program 5: Steepest Ascent Hill Climbing 9

/***************************** *Name: Atishay Jain *Course: BE Final Year *Group: 4CO5 *Subject: Artificial Intelligence *Prog: Steepest Ascent Hill Climbing for 8 Puzzle Problem *****************************/ #include #include #include using namespace std; int start[3][3],final[3][3]; //Finds the position of the tile no t int findpos(int a[][3],int t) { for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { if(a[i][j]==t) return (3*i+j+1); } } } //Calculation of Heuristic: Distance from final state int heurestic(int a[][3]) { int h=0,posi,posg; for(int i=1;i<=9;i++) { posi=findpos(a,i); posg=findpos(final,i); h+=abs((float)posg-posi); } return h; } //Matrix Display void display(int a[][3]) { for(int i=0;i<3;i++) { cout<<"\n"; for(int j=0;j<3;j++) { if(a[i][j] !=9 ) cout<
10

}

}

} int main() { int next[3][3]; int i ,j,hi,hf,hn, posi,posj,lftflags=0,rtflags=0, upflags=0, dwnflags=0,lftflagp=0,rtflagp=0, upflagp=0,dwnflagp=0; cout<<"\nEnter starting state(Enter 9 for blank):\n"; for(i=0;i<3;i++) for(j=0;j<3;j++) cin rel="nofollow">>start[i][j]; cout<<"\nEnter Final state(9 for empty tile):\n"; for(i=0;i<3;i++) for(j=0;j<3;j++) cin>>final[i][j]; hi=heurestic(start); hf=heurestic(final); cout<<"Strating h:"<hf) { for(i=0;i<3;i++) { for(j=0;j<3;j++) { if(next[i][j]==9) { posi=i; posj=j; } }

} cout<<"\nOptions:\n"; int h1=999,h2=999,h3=999,h4=999; if(posi-1>=0 && upflags==0) { next[posi][posj]=next[posi-1][posj]; next[posi-1][posj]=9; h1=heurestic(next); cout<<"\nHeurestic:"<
11

} if(posi+1<=2 && dwnflags==0) { next[posi][posj]=next[posi+1][posj]; next[posi+1][posj]=9; h2=heurestic(next); cout<<"\nHeurestic:"<
} if(posj-1>=0 && lftflags==0) {

next[posi][posj]=next[posi][posj-1]; next[posi][posj-1]=9; h3=heurestic(next); cout<<"\nHeurestic:"<
} if(posj+1<=2 && rtflags==0) {

next[posi][posj]=next[posi][posj+1]; next[posi][posj+1]=9; h4=heurestic(next); cout<<"\nHeurestic:"<
} if(h1<=h2 && h1<=h3 && h1<=h4) { next[posi][posj]=next[posi-1][posj]; next[posi-1][posj]=9; upflags=1;dwnflagp=1; } else if(h2<=h1 && h2<=h3 && h2<=h4) { next[posi][posj]=next[posi+1][posj]; next[posi+1][posj]=9; dwnflags=1;upflagp=1; } else if(h3<=h1 && h3<=h2 && h3<=h4) { next[posi][posj]=next[posi][posj-1]; next[posi][posj-1]=9; lftflags=1;rtflagp=1;

12

} else if(h4<=h1 && h4<=h2 && h4<=h3) { next[posi][posj]=next[posi][posj+1]; next[posi][posj+1]=9; rtflags=1;lftflagp=1; }

//Calculate the heuristic of next state hn=heurestic(next); if(hn>hi) { cout<<"\nThe search cannot reach to the destination"; break; } else { hi=hn; lftflags=lftflagp; rtflags=rtflagp; upflags=upflagp; dwnflags=dwnflagp; rtflagp=0; lftflagp=0; upflagp=0; dwnflagp=0; cout<<"\nChosen:"; cout<<"\nHeurestic="<
} getch(); return 0; }

Program 6: Best First Search 13

/***************************** *Name: Atishay Jain *Course: BE Final Year *Group: 4CO5 *Subject: Artificial Intelligence *Prog: Best First Search of r8 Puzzle Problem *****************************/ #include #include #include<math.h> #include<process.h> struct node { int arr[3][3]; int h; int flag,r,l,u,d; }*ptr=NULL,*prevptr=NULL; node *a[50]; static int k=0; //Using specific Case for testing purposes… int initial[3][3]={2,8,3,1,6,4,7,9,5},final[3][3]={1,2,3,8,9,4,7,6,5}; int findpos(int arr[][3],int n) { for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { if(arr[i][j]==n) return (3*i+j+1); } } return 1; } int heurestic(int arr[][3]) { int h=0,posi,posg; for(int i=1;i<=9;i++) { posi=findpos(arr,i); posg=findpos(final,i); h+=abs(posg-posi); } return h; } void display(int arr[][3]) { for(int i=0;i<3;i++) { cout<<"\n"; for(int j=0;j<3;j++) { cout<<arr[i][j]<<"\t";

14

}

}

} void insert(node *n) { int t; if(k==0) { a[k]=n; k++; } else { t=n->h; int j; for(j=k;j>=0 && a[j]->h>t;j--) { a[j+1]=a[j]; } a[j+1]=n; k++; } } int main() { int next[3][3],temp[3][3]; int i,j,hi,hg,hn,posi,posj; cout<<"\nEnter start state(enter 9 for blank):"; for(i=0;i<3;i++) for(j=0;j<3;j++) cin>>initial[i][j]; cout<<"\nEnter goal state(enter 9 for blank):"; for(i=0;i<3;i++) for(j=0;j<3;j++) cin>>final[i][j]; ptr=new node; for(i=0;i<3;i++) for(j=0;j<3;j++) ptr->arr[i][j]=initial[i][j]; ptr->h=heurestic(ptr->arr); ptr->flag=0; ptr->l=0; ptr->r=0; ptr->u=0; ptr->d=0; hi=heurestic(initial); hg=heurestic(final); cout<<"Heurestic"<
15

while(hi>hg) { cout<<"\nSelected:"<<prevptr->h; for(i=0;i<3;i++) { for(j=0;j<3;j++) { next[i][j]=prevptr->arr[i][j]; temp[i][j]=next[i][j]; } } for(i=0;i<3;i++) { for(j=0;j<3;j++) { if(next[i][j]==9) { posi=i; posj=j; } } } if(posi-1>=0 && prevptr->u==0) { temp[posi][posj]=next[posi-1][posj]; temp[posi-1][posj]=9; ptr=new node; for(i=0;i<3;i++) for(j=0;j<3;j++) ptr->arr[i][j]=temp[i][j]; ptr->h=heurestic(ptr->arr); ptr->flag=0; ptr->d=1; ptr->u=0; ptr->l=0; ptr->r=0; insert(ptr); for(i=0;i<3;i++) for(j=0;j<3;j++) temp[i][j]=next[i][j]; } if(posi+1<=2 && prevptr->d==0) { temp[posi][posj]=next[posi+1][posj]; temp[posi+1][posj]=9; ptr=new node; for(i=0;i<3;i++) for(j=0;j<3;j++) ptr->arr[i][j]=temp[i][j]; ptr->h=heurestic(ptr->arr); ptr->flag=0; ptr->u=1; ptr->d=0;

16

ptr->l=0; ptr->r=0; insert(ptr); for(i=0;i<3;i++) for(j=0;j<3;j++) temp[i][j]=next[i][j]; } if(posj-1>=0 && prevptr->l==0) { temp[posi][posj]=next[posi][posj-1]; temp[posi][posj-1]=9; ptr=new node; for(i=0;i<3;i++) for(j=0;j<3;j++) ptr->arr[i][j]=temp[i][j]; ptr->h=heurestic(ptr->arr); ptr->flag=0; ptr->r=1; ptr->l=0; ptr->u=0; ptr->d=0; insert(ptr); for(i=0;i<3;i++) for(j=0;j<3;j++) temp[i][j]=next[i][j]; } if(posj+1<=2 && prevptr->r==0) { temp[posi][posj]=next[posi][posj+1]; temp[posi][posj+1]=9; ptr=new node; for(i=0;i<3;i++) for(j=0;j<3;j++) ptr->arr[i][j]=temp[i][j]; ptr->h=heurestic(ptr->arr); ptr->flag=0; ptr->l=1; ptr->r=0; ptr->u=0; ptr->d=0; insert(ptr); for(i=0;i<3;i++) for(j=0;j<3;j++) temp[i][j]=next[i][j]; } for(i=0;ih; if(a[i]->flag==0) { ptr=a[i]; a[i]->flag=1; break; }

17

} hn=heurestic(ptr->arr); cout<<"\nHeurestic="<arr); cout<<"selected:"<h; prevptr=ptr; if(hn==hg) cout<<"SUCCESS";

} getch(); return 0; }

Program 7: Tower of Hanoi /***************************** *Name: Atishay Jain *Course: BE Final Year *Group: 4CO5 *Subject: Artificial Intelligence *Prog: Tower of Hanoi *****************************/ #include<stdio.h> #include using namespace std; void move(char start,char end,char other,int n) { if(n==1) { cout<<"\nMove block no 1 from "<<start<<" to "<<end<<"."; return; } else { move(start,other,end,n-1); cout<<"\nMove block no "<>n; move('A','B','C',n); }

18