PDA

View Full Version : [Q] Giúp sửa lỗi chương trình AI giải bài toán TACI



phoenix
01-11-2002, 10:35
mọi người sửa lỗi chương trình này dùm phoenix với, nó chạy ko ổn định, lúc đúng lúc sai


#include <conio.h>
#include <stdio.h>
#define N 3
/*typedef struct Taci
{ int g,h,f;
int TC[N][N];
};*/
typedef Taci[N][N];

Taci Start,Goal,Tam,Nho,Tam1,Nho1,Trung;
void Nhap_Start()
{ for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
{ printf("Nhap Start[%d][%d]=",i,j);
scanf("%d",&Start[i][j]);
}
}
void Gt_Goal()
{ for(int i=0;i<N;i++)
Goal[0][i]=i+1;
int j=7;
for(i=0;i<N;i++)
Goal[2][i]=j--;
Goal[1][0]=8;
Goal[1][1]=0;
Goal[1][2]=4;
}
void Xuat(Taci A)
{ for(int i=0;i<N;i++)
{ for(int j=0;j<N;j++)
printf("%3d",A[i][j]);
printf("\n");
}
printf("\n");
}
int Tinh_H1(Taci Tam)
{ int h=0;
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
if(Tam[i][j]!=Goal[i][j])
h++;
return h;
}
void Swap(int x,int y)
{ int tam;
tam=x; x=y; y=tam;
}
void Tim_o_trong(Taci A,int &i,int &j)
{ for(i=0;i<N;i++)
for(j=0;j<N;j++)
if(A[i][j]==0)
return;
}
void Copy(Taci from,Taci to)
{ for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
to[i][j]=from[i][j];
}
int BiTrung(Taci A,Taci B)
{ for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
if(A[i][j]!=B[i][j])
return 0;
return 1;
}
int Chuyen_MT(Taci A,Taci &B,int i)
{ int d,c;
if(i==0) //trai sang phai
{ Tim_o_trong(A,d,c);
if(c==0) return 0;
Copy(A,B);
B[d][c]=B[d][c-1];
B[d][c-1]=0;
}
if(i==1) //Tren xuong duoi
{ Tim_o_trong(A,d,c);
if(d==0) return 0;
Copy(A,B);
B[d][c]=B[d-1][c];
B[d-1][c]=0;
}
if(i==2) //phai sang trai
{ Tim_o_trong(A,d,c);
if(c==N-1) return 0;
Copy(A,B);
B[d][c]=B[d][c+1];
B[d][c+1]=0;
}
if(i==3) //duoi len tren
{ Tim_o_trong(A,d,c);
if(d==N-1) return 0;
Copy(A,B);
B[d][c]=B[d+1][c];
B[d+1][c]=0;
}
return 1;
}



void main()
{ clrscr();
Nhap_Start();
Gt_Goal();
Xuat(Start);
int Thoat=1;
Copy(Start,Trung);
while(Thoat)
{
int min=500;
for(int i=0;i<4;i++)
if (Chuyen_MT(Start,Tam,i))
if (!BiTrung(Tam,Trung))
{
int h_Tam=Tinh_H1(Tam);
if(h_Tam==min)
{
int minNho=500;
for(int k=0;k<4;k++)
if (Chuyen_MT(Nho,Nho1,k))
if(!BiTrung(Nho1,Start))
{
int h_Nho1=Tinh_H1(Nho1);
if(h_Nho1<minNho)
minNho=h_Nho1;
}
int min_Tam=500;
for(k=0;k<4;k++)
if (Chuyen_MT(Tam,Tam1,k))
if (!BiTrung(Tam1,Start))
{
int h_Tam1=Tinh_H1(Tam1);
if(h_Tam1<min_Tam)
min_Tam=h_Tam1;
}
if(min_Tam<minNho)
Copy(Tam,Nho);
}
else
if(h_Tam<min)
{
min=h_Tam;
Copy(Tam,Nho);
}
}
Copy(Start,Trung);
Copy(Nho,Start);
Xuat(Start);
if (Tinh_H1(Start)==0)
Thoat=0;
}
// Xuat(Start);
getch();
}

Old Shark
03-11-2002, 00:26
Bạn Phoenix viết rắc rối quá, mà lại không có comment, nên tôi không hiểu hết. Tôi mạn phép bạn viết lại chương trình Taci dựa trên một số hàm bạn đã viết. Bạn thử chạy xem, xin lỗi tôi chưa thử được vì tôi đang ở nhà người khác, dùng máy tính của người khác, không có chương trình C, nên không thử được (Nhưng tôi nghĩ nó không có lỗi gì nghiêm trọng).
Bạn nên nhớ đây là cách giải theo Heuristic, có nghĩa là không đảm bảo sẽ luôn luôn thành công (Thực tế nếu bạn cho trạng thái Start quá xấu, rất nhiều khả năng chương trình sẽ thất bại do không tìm được giá trị hàm H1 tốt hơn).



#include <conio.h>
#include <stdio.h>

#define N 3 // Test với 3

typedef Taci[N][N]; // Ma trận 3x3

Taci Start, Goal, Test; /* Start : trạng thái đầu (user nhập vào)
Goal : trạng thái đích
Test : trạng thái đang được test */

// Cho user nhập trạng thái đầu

void Nhap_Start() {
for( int i = 0; i < N; i++ )
for( int j = 0; j < N; j++ ) {
printf( "Nhap Start[%d][%d]=", i, j );
scanf( "%d", &Start[i][j] );
}
}

// Thiết lập trạng thái đích : 1 2 3
// 8 0 4
// 7 6 5

void Init_Goal() {
for( int i = 0; i < N; i++ )
Goal[0][i] = i + 1;

int j = 7;

for( int i = 0; i < N; i++ )
Goal[2][i]=j--;

Goal[1][0] = 8;
Goal[1][1] = 0;
Goal[1][2] = 4;
}

// Hàm in ma trận ra màn hình

void Xuat( Taci A ) {
for ( int i = 0; i < N; i++ ) {
for ( int j = 0 ; j < N ; j++ )
printf( "%3d", A[i][j] );
printf( "\n" );
}
printf( "\n" );
}

// Hàm tính giá trị của hàm số Heuristic H1 = số vị trí khác nhau giữa trạng thái đang xét
// và trạng thái đích

int H1( Taci A ) {
int h = 0;
for ( int i = 0; i < N; i++ )
for ( int j = 0; j < N; j++ )
if ( A[i][j] != Goal[i][j]) // đếm số vị trí khác nhau
h++;

return h;
}

// Hàm tìm ô trống (trả về i, j là tọa độ của ô trống)

void Tim_o_trong ( Taci A, int &i, int &j ) {
for ( i = 0; i < N; i++ )
for ( j = 0; j < N; j++ )
if ( A[i][j] == 0 )
return;
}

// Hàm copy ma trận

void Copy ( Taci source, Taci dest ) {
for ( int i = 0; i < N; i++ )
for ( int j = 0; j < N; j++ )
dest[i][j] = source[i][j];
}


// Hàm Move di chuyển một ô vào ô trống, từ trạng thái A -> trạng thái B. Hàm trả về các
// giá trị sau:
// 0 : Không làm gì cả (không còn trường hợp nào)
// 1 : Di chuyển từ trái qua phải
// 2 : Di chuyển từ trên xuống dưới
// 3 : Di chuyển từ dưới lên trên
// 4 : Di chuyển từ phải sang trái
// (Hàm này xét từng khả năng di chuyển theo thứ tự ưu tiên nói trên)

int Move ( Taci A, Taci &B ) {
int x, y; // Toạ độ ô trống
Tim_o_trong( A, x, y ); // Tìm toạ độ ô trống

Copy ( A, B );

// Nếu y khác 0 : ô trống không nằm ở biên trái;
// lastMove != 4 : lần di chuyển trước đó không phải từ bên phải qua
// tested < 1 : chưa thử khả năng này
// thì di chuyển từ trái qua phải

if (( y ) && ( lastMove != 4 ) && ( tested < 1 )) {
B[x][y] = B[x][y - 1];
B[x][y - 1] = 0;
return 1;
}

// Nếu x khác 0 : ô trống không nằm ở biên trên;
// lastMove != 3 : lần di chuyển trước đó không phải từ dưới lên
// tested < 1 : chưa thử khả năng này
// thì di chuyển từ trên xuống dưới

if (( x ) && ( lastMove != 3 ) && ( tested < 2 )) {
B[x][y] = B[x - 1][y];
B[x - 1][y] = 0;
return 2;
}

// Tương tự, di chuyển từ dưới lên trên

if (( x < N - 1 ) && ( lastMove != 2 ) && ( tested < 3 )) {
B[x][y] = B[x + 1][y];
B[x + 1][y] = 0;
return 3;
}

// và từ phải sang trái

if (( y < N - 1 ) && ( lastMove != 1 ) && ( tested < 4 )) {
B[x][y] = B[x][y + 1];
B[x][y + 1] = 0;
return 4;
}

return 0; //
}

// Hàm main

void main() {
clrscr(); // Xoá màn hình
Nhap_Start(); // Nhập trạng thái đầu
Init_Goal(); // Thiết lập trạng thái đích

int lastMove = 0; // Lưu lần di chuyển cuối cùng
int realMove = 0; // Lưu cách di chuyển tốt nhất (tương ứng giá trị H1 tốt nhất)
int minH = H1 ( Start ); // Lưu giá trị H1 tốt nhất
int Htest; // Giá trị hàm H1 của khả năng đang xét
int tested = 0; // đã test được bao nhiêu khả năng rồi? (0,1,2 hoặc 3)

Xuat( Start ); // In ra trạng thái Start

if ( !minH ) // Nếu trạng thái Start chính là trạng thái đích
printf ( " I have nothing to do !!! :) " );
else {
// Lặp vô hạn, tôi ghét cách làm này, nhưng không có thời gian sửa
while (1) {
// test các khả năng di chuyển

do {
tested = Move ( Start, Test );
Htest = H1 ( Test );
if ( Htest < minH ) { // Nếu cách di chuyển vừa xét là tốt nhất
minH = Htest;
realMove = tested; // Lưu lại cách di chuyển đó
}
} while ( tested ); // Khi nào tested = 0 (xét hết trường hợp) thì thoát

if ( minH < H1 ( Start ) ) { // Nếu tốt hơn trạng thái cũ
tested = realMove - 1; // Chọn cách di chuyển tốt nhất
lastMove = Move ( Start, Start ); // Move thực sự
Xuat( Start ); // Xuất trạng thái mới
}
else break; // Hết giải pháp (hay hết thuốc :)) thoát vòng lặp
}

if ( minH ) // Nếu minH != 0, nghĩa là thất bại
printf ( "\n That bai !!! Khong tim duoc giai phap tiep theo");

getch();
}

CrazyKing
03-11-2002, 02:26
Hi ! Bây giờ đọc code của U lại thì mệt quá , Bài toán Taci tui đã từng làm rùi ! U tham khảo nhé !
Thuật giải:
Dùng AK
Hàm lượng giá : danhgia
Tìm vị trí dịch chuyển sao cho h nhỏ nhất
#include <stdio.h>
#include <conio.h>
#include <math.h>
int a[3][3]={ {2,8,3},{1,6,4},{7,0,5} };
int A[3][3]={ {1,2,3},{8,0,4},{7,6,5} };
int b[3][3]={ {2,8,3},{1,6,4},{7,0,5} };
int I,J,I1,J1,g=0,h;
void xuly();
int ketthuc();
int tinh();
int tim(int );
void timdinhtrong();
void swap(int & , int &);
void xetchon();
void chep1();
void chep2();
void main()
{
// clrscr();
xuly();
printf("\n So buoc lap la : %d",g);
getch();
}
void xuly()
{
while(!ketthuc())
{
g++;
xetchon();
printf("%d \n",h);
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
printf("%d ",a[i][j]);
printf("\n");
}
getch();
}

}
int ketthuc()
{
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
if (a[i][j]!=A[i][j]) return 0;
return 1;
}

int tinh()
{
int bac=0;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
{
if(tim(b[i][j])) bac+=abs(I1-i)+abs(J1-j);
}
return bac;
}
int tim(int x)
{
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
if (A[i][j]==x && x!=0 )
{
I1=i;
J1=j;
return 1;
}
return 0;
}
void timdinhtrong()
{
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
if (a[i][j]==0)
{
I=i;
J=j;
}
}
void swap( int &x , int &y)
{
int temp;
temp=x;
x=y;
y=temp;
}
void xetchon()
{
int min=100;
timdinhtrong();
for(int j=0;j<3;j++)
for(int l=0;l<3;l++)
{
if ((abs(I-j)+(abs(J-l))==1))
{
swap(b[j][l],b[I][J]);
h=tinh();
if(h<min)
{
min=h;
chep2();
}
swap(b[j][l],b[I][J]);
}
}
chep1();
h=min;
}
void chep1()
{
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
b[i][j]=a[i][j];
}
void chep2()
{
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
a[i][j]=b[i][j];
}
Hì hì , chúc U sẽ 10 điểm môn này ! Tui có code của mấy bài khác như 8 con hậu , đong nước, mã đi tuần , tic tic toe ....... U cần thì mail cho tui , tui send cho !!!

nnv82
05-11-2002, 08:56
Ồ bạn CrazyKing có thể cho mình bài toán 8 con Hậu và bài mã đi tuần (tất nhiên là Heuristic nha) nếu có cả đồ họa thì hay quá . email của mình là : nhuvinh@email.com . Rất mong thư trả lời của bạn .

phoenix
07-11-2002, 11:38
Nếu cần source thì tui cũng có nè, nhưng tui chỉ thích tự viết lấy thôi,
P biết rồi, vì Heuristic ko đúng cho mọi trường hợp nên chương trình chạy ko được, ok, thanks.

sonytram
07-05-2007, 23:15
yeah,chao may anh.e la thanh vien moi,crazyking co the giup minh bai code 8con hau,tic tic toe ko?e cam on nha.mail cua e la :tram_vn85@yahoo.com

hoai uit
08-05-2007, 15:03
chao cac ban minh rat muon hoc tot moc C/C++ nhung ngac noi minh mat kien thuc nhieu gio doc nhung doan code rat kho doi voi minh gio phai lam sao day ?
Co canh nao lay lai ma hieu qua khong ?chi cho minh voi ?hic minh dang can lam ! co lien he tai dien dan nay hoac qua mail giangsinhhong@yahoo.com Cam on nhieu !

hanhung
09-05-2007, 20:09
chào các anh chị và các bạn , em cũng đang học trí tuệ nhân tạo , em muốn tìm một số code của bài toán tháp hà nội,taci,mã đi tuần,8 con hậu , giải bằng thuật toán AK thì càng tốt,
em cảm ơn nhiều
xin các anh chị gởi qua mail nhung_ha2003@yahoo.com

hanhung
09-05-2007, 20:11
bài toán tô màu nữa ... xin các anh chị và các bạn gởi qua mail cho minh dùm
nhung_ha2003@yahoo.com

sonytram
10-05-2007, 00:16
moi lam xong 8con hau ne,ai co nhu cau,minh gui cho

nguoinhaque0909
15-10-2010, 15:27
mọi người có code bài toán 8 con hậu thì cho em nha. mail của em là nguoinhaque0909@gmail.com , viết = C, C++ thì càng tốt ạ. sonytram viết bằng j vậy? gửi qua cho mình dc ko ?