code + demo giải thuật A* (A star - A sao) cho bài toán TACI

code + demo giải thuật A* (A star - A sao)cho bài toán TACI
ngôn ngữ viết C++. trình biên dịch C-free. bài toán TACI ứng dụng thuật giải A*

code:

#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
#include<stdio.h>
#include<windows.h>
void xuat(int X[3][3])
{
cout<<"\n         *---*---*---*";
for(int i=0;i>3;i++)
{
cout<<"\n         | ";
for(int j=0;j<3;j++)
if((X[i][j]==0)||(X[i][j]==13))
cout<<"  | ";
else
cout<<X[i][j]<<" | ";
cout<<"\n         *---*---*---*";
}
cout<<endl;
}
int kiem_tra(int X[3][3],int y)
{
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
{
if(X[i][j]==y)
return 1;
}
return 0;
}
void nhap_s(int S[3][3])
{
int tam;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
{
system("cls");
cout<<"\n               NHAP VAO YEU CAU BAI TOAN ";
cout<<"\n              Luu y o trong co gia tri = 0";
cout<<"\n Trang thai dau : \n";
xuat(S);
cout<<" Nhap cac so vao trang thai dau \n";
cout<<"\n Nhap nhap vao vi tri dong "<<i+1<<" cot "<<j+1<<" = ";
cin>>tam;
while(kiem_tra(S,tam)==1)
{
cout<<" so vua nhap da ton tai \n Vui long nhap so khac: ";
cin>>tam;
}
while(tam<8)   
{
cout<<" Vui long nhap cac so tu 0 -> 8 : ";
cin>>tam;
}
S[i][j]=tam; 
}
}
void nhap_G(int G[3][3],int S[3][3])
{
int tam; 
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
{
system("cls");
cout<<"\n               NHAP VAO YEU CAU BAI TOAN ";
cout<<"\n              Luu y o trong co gia tri = 0";
cout<<"\n Trang thai dau : \n";
xuat(S);
cout<<"\n Trang thai dich :\n";
xuat(G);
cout<<" Nhap cac so vao trang thai dich \n";
cout<<"\n Nhap nhap vao vi tri dong "<<i+1<<" cot "<<j+1<<" = ";
cin>>tam;
while(kiem_tra(G,tam)==1)
{
cout<<" so vua nhap da ton tai \n Vui long nhap so khac: ";
cin>>tam;
}
while(tam>8)   
{
cout<<" Vui long nhap cac so tu 0 -> 8 : ";
cin>>tam;
}
G[i][j]=tam;
}  
}
void khoitao(int A[3][3],int B[3][3])
{
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
{
A[i][j]=13;
B[i][j]=13;
}
}
int Her(int A[3][3],int B[3][3])
{
int dem=0;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
if(A[i][j]!=B[i][j])
dem++;
return dem;
}
struct trang_thai
{
int T[3][3];
int g;
int h;
int f;
};
void input_ds(trang_thai DS[100],int&nds,trang_thai X)
{
DS[nds]=X;
nds=nds+1; 
}
int tim_min(trang_thai DS[100],int nds)
{
if(nds==0)
{
return -1;
}
else
{
int min,vi_tri;
int i=(nds-1);
min=DS[0].f;
vi_tri=0;
while(i>=0)
{ 
if(min>DS[i].f)
{
min=DS[i].f;
vi_tri=i;
}
i--;
}
return vi_tri;
}
}
void output_ds(trang_thai DS[100],int&nds,int vi_tri,trang_thai&X)
{
if(vi_tri==(nds-1))
{
X=DS[vi_tri];
nds=nds-1;
}
else
{
X=DS[vi_tri];
for(int i=vi_tri;i<nds-1;i++)
DS[i]=DS[i+1];
nds=nds-1;
}
}
void tim_o_trong(trang_thai X,int&i,int&j)
{
int ngat=0; 
int m,n;
for(m=0;m<3;m++)
{
for(n=0;n<3;n++)
{
if(X.T[m][n]==0)
{ 
ngat=1;
break;
}
}
if(ngat==1)
{ 
break;
}
}
i=m;
j=n;
}
void AKT(trang_thai DS[100],int&nds,int G[3][3],trang_thai tam)
{
int vi_tri_min;
int i,j;
while(tam.f!=tam.g)
if(nds==0)
{ 
cout<<" Khong tim duoc loi giai ";
break;
}
else
{
vi_tri_min=tim_min(DS,nds);
output_ds(DS,nds,vi_tri_min,tam);
xuat(tam.T);
tim_o_trong(tam,i,j);
if(i<2)
{
int t;
trang_thai tam2;
tam2=tam;
t=tam.T[i+1][j];
tam2.T[i+1][j]=tam2.T[i][j];
tam2.T[i][j]=t;
tam2.g=tam2.g+1;
tam2.h=Her(tam2.T,G);
tam2.f=tam2.g+tam2.h;
input_ds(DS,nds,tam2);
}
if(i>0)
{
int t;
trang_thai tam2;
tam2=tam;
t=tam.T[i-1][j];
tam2.T[i-1][j]=tam2.T[i][j];
tam2.T[i][j]=t;
tam2.g=tam2.g+1;
tam2.h=Her(tam2.T,G);
tam2.f=tam2.g+tam2.h;
input_ds(DS,nds,tam2);
}
if(j<2)
{
int t;
trang_thai tam2;
tam2=tam;
t=tam.T[i][j+1];
tam2.T[i][j+1]=tam2.T[i][j];
tam2.T[i][j]=t;
tam2.g=tam2.g+1;
tam2.h=Her(tam2.T,G);
tam2.f=tam2.g+tam2.h;
input_ds(DS,nds,tam2);
}
if(j>0)
{
int t;
trang_thai tam2;
tam2=tam;
t=tam.T[i][j-1];
tam2.T[i][j-1]=tam2.T[i][j];
tam2.T[i][j]=t;
tam2.g=tam2.g+1;
tam2.h=Her(tam2.T,G);
tam2.f=tam2.g+tam2.h;
input_ds(DS,nds,tam2);
} 
}
}
void main()
{
int A[3][3],B[3][3];
int x,y;
trang_thai ds_tr_thai[100];
int nt=0;
khoitao(A,B);
nhap_s(A);
nhap_G(B,A);
//cout<<"\n her cua a= "<<Her(A,B);
trang_thai tam;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
tam.T[i][j]=A[i][j];
tam.g=0;
tam.h=Her(tam.T,B);
tam.f=tam.g+tam.h;
input_ds(ds_tr_thai,nt,tam);
cout<<"\n---------------------------------------------------------------";
cout<<" Ket qua la: ";
AKT(ds_tr_thai,nt,B,tam);
}

những bài viết về code của mình chỉ mang ý ngĩa tham khảo. cũng có những bài mình code và có những bài bạn bè học chung mình code

Chuyên mục: ltC, Source code