1
Trí Tuệ Nhân Tạo
Bài thực hành 1: Tìm kiếm mù
—-oOo—-
Điểm số: 1/5
Ngày nộp:
o Lớp 05PV, 05MT: 21/4/2007
o Lớp 04DB: 24/4/2007
Nội dung:
Cho đồ thị vô hướng biểu diễn bởi ma trận kề trong tập tin dothi.inp với cấu trúc như sau:
o Dòng đầu tiên ghi số đỉnh đồ thị N
o dòng tiếp theo, dòng thứ ighi số nguyên , trong đó: NN],[jiA1],[=jiA nếu có cạnh nối giữa hai đỉnh ),1(,jjiji≤≤, và trong trường hợp ngược lại, mỗi số cách nhau bằng một ký tự tab. 0],[=jiA
Ví dụ:
1 2 3 4 Tập tin dothi.inp 4 0 1 0 1 1 0 0 0 0 0 0 1 1 0 1 0
Viết chương trình thực hiện các yêu cầu sau:
1. Nhập vào 2 đỉnh . Hãy in ra đường đi (thứ tự đỉnh) giữa và bằng tìm kiếm theo chiều rộng. vu,uv
2. Như câu 2, sử dụng thuật toán tìm kiếm theo chiều sâu. Lưu ý: dùng stack, không dùng đệ quy (tức là: hàm gọi lại chính nó).
Artificial Intelligence (03/2007) Nguyễn Anh Tuấn
Khoa CNTT - ĐH KHTN Tp. HCM
2
3. Cho biết đồ thị có bao nhiêu thành phần liên thông, và in ra danh sách đỉnh ứng với từng thành phần. Yêu cầu cài đặt bằng cả 2 phương pháp: tìm kiếm theo chiều rộng, tìm kiếm theo chiều sâu.
-------------------- Artificial Intelligence (03/2007) Nguyễn Anh Tuấn
Khoa CNTT - ĐH KHTN Tp. HCM
SOURCE:
#include "stdlib.h"
#include "stdio.h"
#include "conio.h"
#include "Stack.h"
#define MAX 253
struct GRAPH
{
long n;//so dinh
short k;//thuat toan
double arrGraph[MAX][MAX];
};
struct EDGE
{
int x;
int y;
};
EDGE ck[MAX];
EDGE lstEdge[MAX*(MAX-1)/2];
long nEdgeCount=0;
/*Stack*/
Stack stack;
double arrnLabel[MAX];
double nSoMienLienThong=0;
void init(GRAPH gr)
{
for(int i=0;i<gr.n;i++)
{
arrnLabel[i]=-1;
}
}
/*Ham duyet tim lien thong trong do thi*/
void Visit(GRAPH &gr, long i, double nLabel)
{
long x=0;
arrnLabel[i]=nLabel;
stack.Push(i);
while (stack.GetSize()>0 )
/*Khi chua het stack*/
{
/*queueindex--;
x = queue[queueindex]; */
stack.Pop(x);
for (long j=0;j<gr.n;j++)
if ((gr.arrGraph[x][j]!=0)&&(arrnLabel[j])==-1)
/*neu co lien ket tu 2 dinh x va j ,
dong thoi j chua duyet thi gan nLabel cho j*/
{
/*queue[queueindex] = j;
queueindex++;*/
stack.Push(j);
arrnLabel[j]=nLabel;
}
}
}
int XetLienThong(GRAPH& gr)
{
init(gr);
for (int i=0; i<gr.n; i++)
if (arrnLabel[i]==-1)//chua xet
{
Visit(gr,i, nSoMienLienThong);
nSoMienLienThong++;
}
if(nSoMienLienThong>1)
return 0; // khong lien thong
else
return 1;//co lien thong
}
void ReadFile(GRAPH &gr)
{
FILE *f;
f=fopen("KC.txt","rt");
if (f==NULL)
{
printf("\nFile khong ton tai");
exit (0);
}
else
{
fscanf(f,"%ld",&gr.n);
// fscanf(f,"%d",&gr.k);
printf("\nDo thi vua nhap vao la :\n");
printf("%ld\n",gr.n);
for(int i=0;i<gr.n;i++)
{
for(int j=0;j<gr.n;j++)
{
fscanf(f,"%lf",&gr.arrGraph[i][j]);
printf("%5.12lf\t",gr.arrGraph[i][j]);
}
printf("\n");
}
}
fclose(f);
}
void Sort(GRAPH gr,EDGE arrEdge[],long n)
{
EDGE tempEdge;
for(int i=0;i<n-1;i++)
for(int j=i+1;j<n;j++)
if(gr.arrGraph[arrEdge[i].x][arrEdge[i].y]>gr.arrGraph[arrEdge[j].x][arrEdge[j].y])
{
tempEdge= arrEdge[i];
arrEdge[i]=arrEdge[j];
arrEdge[j]=tempEdge;
}
}
void Kruskal(GRAPH gr)
{
double label[MAX];
long countCK=0;
for(int i=0;i<gr.n;i++)
label[i]=i;
nEdgeCount = 0;
for (i=0;i<gr.n-1;i++)
for (int j=i+1;j<gr.n;j++)
if (gr.arrGraph[i][j]!=0)
{
lstEdge[nEdgeCount].x = i;
lstEdge[nEdgeCount].y = j;
nEdgeCount++;
}
Sort(gr,lstEdge,nEdgeCount);
for(i=0;i<nEdgeCount;i++)
{
if(label[lstEdge[i].x]!=label[lstEdge[i].y])
{
label[lstEdge[i].y]=label[lstEdge[i].x];
ck[countCK]=lstEdge[i];
countCK++;
if(countCK==gr.n-1)
break;
}
}
}
void Prim(GRAPH gr)
{
int label[MAX];
int nCK=0;
for(int i=0;i<gr.n;i++)
label[i]=0;
label[0]=1;
EDGE edgeMin;
double nMinWeight = -1;
while (nCK<gr.n-1)
{
nMinWeight=-1;
for (int y=0;y<gr.n;y++)
if (label[y]==0)//chua xet
{
for (int x=0;x<gr.n;x++)
if (label[x]==1 && gr.arrGraph[x][y]!=0)
{
if (nMinWeight==-1 || nMinWeight>gr.arrGraph[x][y])
{
edgeMin.x = x;
edgeMin.y = y;
nMinWeight = gr.arrGraph[x][y];
}
}
}
ck[nCK] = edgeMin;
nCK++;
label[edgeMin.y]=1;
}
}
void OutPut(GRAPH gr,int KiemTraLienThong)
{
FILE *f;
double Sum=0.0;
f=fopen("output.txt","wt");
if(f==NULL)
{
printf("\nKhong du bo nho");
exit (0);
}
else
{
if(KiemTraLienThong==1)//co lien thong
{
/*printf("\nCay khung tim duoc la :\n");
fprintf(f,"\nCay khung tim duoc la :\n");*/
for(int i=0;i<gr.n-1;i++)
{
Sum=Sum + gr.arrGraph[ck[i].x][ck[i].y];
}
printf("\nTong trong so = %5.12lf",Sum);
fprintf(f,"\nTong trong so = %5.12lf",Sum);
printf("\nCac canh tuong ung la :\n");
fprintf(f,"\nCac canh tuong ung la :\n");
for(i=0;i<gr.n-1;i++)
{
printf("%d-%d",ck[i].x,ck[i].y);
fprintf(f,"%d-%d",ck[i].x,ck[i].y);
printf("\n");
fprintf(f,"\n");
}
}
else //khong lien thong
{
printf("\nDo thi khong lien thong");
printf("\nTong trong so = -1");
fprintf(f,"\nDo thi khong lien thong");
fprintf(f,"\nTong trong so = -1");
}
}
fclose(f);
}
void main()
{
GRAPH gr;
ReadFile(gr);
// if(XetLienThong(gr)==0)
// OutPut(gr,0);
// else
// switch(gr.k)
// {
// case 0:
// Prim(gr);
// OutPut(gr,1);
// break;
// case 1:
Kruskal(gr);
OutPut(gr,1);
/// break;
// }
getch();
}
#ifndef __STACK_H
#define __STACK_H
#include <iostream.h>
class Stack
{
private:
long Size;
long Top;
long *StackPtr;
public:
long GetSize();
long IsFull() const;
int IsEmpty() const;
int Pop(long &);
int Push(long &);
Stack(long);
Stack();
~Stack();
};
#endif
stack.cpp
Code:
#include "Stack.h"
Stack::~Stack()
{
delete [] StackPtr;
}
Stack::Stack()
{
}
Stack::Stack(long S)
{
Size = (S<1000 && S>0) ? S : 10;
Top = -1;
StackPtr = new long[Size];
}
int Stack::Push(long &Item)
{
if(!IsFull())
{
StackPtr[++Top] = Item;
return 1;
}
return 0;
}
int Stack::Pop(long &PopValue)
{
if(!IsEmpty())
{
PopValue = StackPtr[Top--];
return 1;
}
return 0;
}
int Stack::IsEmpty() const
{
return Top==-1;
}
long Stack::IsFull() const
{
return Top==Size - 1;
}
long Stack::GetSize()
{
return Size;
}
