Thuật toán tìm kiếm chi phí đồng nhất (Uniform Cost Search – UCS)

Thuật toán

Định nghĩa: Hàng đợi ưu tiên PQ là cấu trúc dữ liệu lưu trữ các phần tử cùng với độ ưu tiên của nó và khi lấy phần tử ra khỏi hàng đợi sẽ căn cứ vào độ ưu tiên nhỏ nhất.

Cho một trạng thái n, ký hiệu g(n) là tổng chi phí đường đi ngắn nhất (hiện có) từ trạng thái ban đầu S đến trạng thái n. Thuật toán UCS sử dụng một hàng đợi ưu tiên (Priority Queue – PQ) để lưu trữ và duyệt các trạng thái trên đường đi. Thuật toán dùng thêm một danh sách CLOSE để lưu trữ các trạng thái đã được xét.

MÃ GIẢ

Khởi tạo: PQ rỗng, CLOSE rỗng.

Đưa trạng thái ban đầu START vào PQ, độ ưu tiên g(START) = 0

Lặp đến khi PQ rỗng

  Lấy một trạng thái n (có g thấp nhất) ra khỏi PQ. Đưa n vào CLOSE. 

  Nếu n là trạng thái đích GOAL thì “đã tìm thấy”. Dừng thuật toán.

  Nếu không, với mỗi trạng thái con n’ chưa xét (n’ không thuộc CLOSE) của n:

      Tính độ ưu tiên: g(n’) = g(n) + cost(n, n’)

      đưa (n’, g(n’)) vào PQ

Cuối lặp

Thông báo không có đường đi từ START đến GOAL.

CODE C++

#include 
#include 
typedef int ETYPE;
struct NODE
{
	ETYPE data;
	int uutien;
	NODE *next;
};

struct PRIQUEUE
{
	NODE *head;
};
void init(PRIQUEUE &pq)
{
	pq.head=NULL;
}
int isempty(PRIQUEUE pq)
{
	if(pq.head==NULL)
		return 1;
	return 0;
}
//layy pt dau
NODE *popleast(PRIQUEUE &pq)
{
	if(pq.head==NULL)
		return NULL;
	
	
		NODE *p;
		p=pq.head;
		pq.head=pq.head->next;
		return p;
}
//xoa ds
void dispose(PRIQUEUE &pq)
{
	NODE *q=NULL;
	NODE *p=pq.head;
	while(p!=NULL)
	{
		q=p;
		p=p->next;
		delete q;
	}
}
NODE * search(PRIQUEUE pq,ETYPE e,NODE *&prev)
{
	NODE *q=NULL;
	NODE *p=pq.head;
	while(p!=NULL)
	{
		if(p->data==e)
		{
			prev=q;
		
			return p;
	
		}
	q=p;
	p=p->next;
	}
	return NULL;
}
void remove(PRIQUEUE &pq,NODE *p,NODE *prev)
{
	if(prev==NULL)
	{
		pq.head=pq.head->next;
	}
	else
		prev->next=p->next;
	delete p;
}
NODE *createnode(ETYPE e,int pri)
{
	NODE *p=new NODE;
	p->data=e;
	p->uutien=pri;
	p->next=NULL;
	return p;
}
void addnew (PRIQUEUE &pq,ETYPE e,int pri)
{
	NODE *n=createnode(e,pri);
	NODE *q=NULL;
	NODE *p=pq.head;
	while(p!=NULL)
	{
		if(p->uutien>=pri)
		{
			
			n->next=p;
			if(q==NULL)
				pq.head=n;
			else
			{
				q->next=n;
				return;
				
			}
		}
		q=p;
		p=p->next;
	}
	
	if(q==NULL)
		pq.head=n;
	else
		q->next=n;

}
void insert(PRIQUEUE &pq,ETYPE e,int pri)
{
	NODE *prev;
	NODE *p=search(pq,e,prev);
	if(p!=NULL)
	{
		if(priuutien)
		{
			remove(pq,p,prev);
			addnew(pq,e,pri);
		}
	}
	else
		addnew(pq,e,pri);
}
void usc()
{

	int n,s,g;
	int c[100][100];
	FILE *f=fopen("input.txt","rt");
	while(!feof(f))
	{
		fscanf(f,"%d",&n);
		fscanf(f,"%d",&s);
		fscanf(f,"%d",&g);
		for(int i=0;ifor(int j=0;jfscanf(f,"%d",&c[i][j]);
			}

	}
	printf("%d\n",n);
	printf("%d",s);
	printf("%d\n",g);
	for(int k=0;kfor(int l=0;lprintf(" %d ",c[k][l]);
		}
		printf("\n");
	}
	PRIQUEUE pq;
	int close[100];
	int parent[100];
	init(pq);
	for(int  i=0;i0;
	insert(pq,s,0);
	parent[s]=-1;
	while(!isempty(pq))
	{
		NODE *p=popleast(pq);
		close[p->data]=1;
		if(p->data==g)
		{
			int path[100];
			int cost=0;
			path[0]=g;
			int t=1;
			int i=g;
			while(parent[i]>=0)
			{
				cost =cost+c[parent[i]][i];
				
				i=parent[i];
				path[t]=i;
				t++;
			}
			FILE *f1=fopen("output.txt","wt");
			fprintf(f1,"%d\n",cost);
			printf("cost:%d  ",cost);
			for(int k=t-1;k>=0;k--)
			{
				fprintf(f1,"%3d",path[k]);
				printf("  path[%d]:%d  ",k,path[k]);
			}
		return;
		}
		for(int i=0;iif(c[p->data][i]>0&&close[i]!=1)
			{
				int g=p->uutien+c[p->data][i];
				insert(pq,i,g);
				parent[i]=p->data;
			}
			
		
	}
	FILE *f1=fopen("output.txt","wt");
	fprintf(f1,"%3d",-1);
	


}
void main()
{


	usc();
	getch();
	
}