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(); }