Trí Tuệ Nhân Tạo P3
(Tìm kiếm có kinh nghiệm)
Các thuật toán tìm kiếm giải quyết những bài toán không thể vét cạn nổi ngay cả trên máy tính để ra đáp án chính xác nhất
ví dụ: cờ vua, mây,...
thực tế: ví dụ có 4 triệu mua điện thoại , Ta không có thời gian để đi dùng thử tất cả các máy <=4 triệu trên thị trường rồi mới mua,,,=> phần này sẽ gq
=> phần code ở dưới cùng Nội Dung
2 Hàm đánh giá
=> Việc tìm hàm đánh giá rất quan trọng nếu đánh giá đúng Bản Chất => hiệu quả => ngược lại => kém hq
=> Việc xây dựng tùy thuộc vào vấn đề cần giải quyết
Ở bước 2 chia 2 loại: đánh giá càng gần thực tế càng tốt
minimum: h(u)<= chi phí thực tế
maximum: h(u)>= chi phí thực tế
Ví dụ 1:
=> kết hợp: ví dụ với đường cao tốc => h(u)= đường chim bay, với đường ngõ ngách => h(u) => khoảng cách thực
Ví dụ 2:
3 Best First Search
Ví dụ: h(u) là hàm đánh giá từ hiện tại=> đích
=> ta thấy BFS quan tâm cả tới các node trước đó nó đã qua != với Greedy BFS dưới đây
+ Cài Đặt:
4 Greedy- Best First Search
Ý Tưởng= f(n) : ước lượng đến trạng thái đích+ Tìm kiếm theo chiều sâu
+ Ví dụ:
Như với ví dụ trên A=> D vì min (xong E,C don't care)=> I( F no care)=> B => đây là TH ngon
=> giả sử I không nối đk tới B(h(u) không tốt) => hóc tại đây
+ Ví dụ 2: Có 25 000đ ăn trưa=> mục đích ngon,bổ,rẻ,.....
đầu tiên vào nhìn chọn món=> biết quái ngon,bổ,.. không => đánh giá tạm thời dựa vào dẻ cứ cái nào dẻ hơn thì chọn=> hehe(đúng thuật toán thế)=> sau chọn xong mới biết=> không nuốt nổi
+ hay mua nồi, quạt, tivi... => tiêu chuẩn: dẻ, bền,sịn,.
=> biết đâu được bền mới xịn=> h(u) chủ yếu dựa trên dẻ=> mấy tháng hỏng=> FF Tàu đểu thế
=> Giải thuật gặp khó khăn như vậy trong TH h(u) đánh giá không tôt: đã ngon,bổ còn đòi rẻ, mà đã rẻ lại còn đòi bền, hịn,....
5 Tìm kiếm Leo đồi
Ý tưởng: gần giống Greedy Best First Search khac:
+ Không cần xét tất cả vị trí xung quanh, chỉ cần chọn vị trí đủ tốt so với vị trí hiện tại=> sử dụng Stack ưu tiên
+ Ví dụ:
+ Cài Đặt:
Có nhiều cách đi=> bài toán đa hướng=> thuận lợi tìm nghiệm tốt toàn cục=> với những bài toán chưa có đích đến cụ thể
Ví dụ: thi đại học: với kiến thức hạn hẹp của Ta chỉ biết 1 vài trường ,, thi xong toẹt hết,, vậy là khỏi tìm hiểu các trường khác,, chọn đại trường nào biết => vẫn tốt hơn ở nhà làm gì bây giờ => hhhh
6 Tìm Kiếm Chùm
Ý tưởng: Best First Search + K node để phát triển
=> tức Ta không chỉ chọn 1 node tốt nhất mà chọn k node tốt nhất để phát triển => số đỉnh phát triển ở mức(tầng) d là k^d
Ví dụ:
ví dụ: trong kinh tế: hay vì đầu tư 1 công ty,, ta sẽ đầu tư vào nhiều nguồn khác giảm thiểu rủi ro(đương nhiên giảm lãi suất)
=> đây cũng là cách mà các thần đề sử dụng thay vì đánh hết 1 con,, các anh sẽ dải ra đánh k con theo hàm heuristic mà các anh cho là tốt nhất .
7 Heuristic chấp nhận được
heuristic quan trọng như thế nào trong AI khỏi nhắc lại => điều tìm ra heuristic tuyệt đối là gần như không thể mà nếu chon h(u) sai mọi thứ sẽ vô ích,,,, => chọn như nào để không bị sai=> ở trên có nói rồi minimum và maximum đó
8 A* Search
Ý Tương= TK Chiều Rộng+ f(u)
Hàm Lượng Giá: f(u)= g(u)+ h(u) (tổng giá đến đích)
g(u): chi phí thực tế đến u
h(u): heuristic đánh giá từ u đến đích
Ví dụ:
+ Cài đặt thuật toán:
=> heuristic chấp nhận được thì A* là tối ưu
ví dụ: rõ ràng 3 vấn đề ta hay mắc phải
+ cóc biết đích là gì( h(u) hên xui không đánh giá dk) : không biết mục đích việc sống, học,làm 1 việc nào đó
+ h(u) : đánh giá h(u) không thể chấp nhận dk
ví dụ: ảo giác bản thân....
+ g(u): quá luyến tiếc vào cái đã bỏ ra mà quên rằng còn có h(u)
ví dụ: giành 1 năm để....=> biết làm nó sẽ rất khó... nhưng lại sợ tốn chi phí của 1 năm đó,, he
9 TK Nhánh và Cận
Ý tương: với f(u) như ở trên
Ví dụ:
+ Cài Đặt:
=> Nhánh cận Tối ưu nêu h(u):
+ Đánh giá thấp và độ dài các cung không nhỏ hơn 1 số dương alpha nào đó
10 Tìm kiếm đối tượng tốt nhất
+ Kỹ thuật TK leo đồi
+ Kỹ thuật TK gradient
+ Kỹ thuật TK mô phỏng luyện kim
10.1 Leo đồi để Tk đối tượng tốt nhất
+ Cài Đặt
+ Nhận Xét:
10.2 Tk địa phương trong tối ưu không ràng buộc
+ TK Gradient
+ Thuật toán giảm Gradient
=> g(k) : đạo hàm riêng tại vị trí x(k)
alpha(k): hệ số học => lựa chọn = thử = thực nghiệm
+ Cài Đặt:
+ Ví dụ:
10.3 Tìm Kiếm Mô phỏng Luyện Kim
+ Cài Đặt:
+ Nhận Xét:
11 Thuật toán GENE ( phần sau)
Code in C++:
#include<iostream>
#include<stdlib.h>
#include<stack>
#include<queue>
using namespace std;
///ma tran trong so, mac dinh so dinh =10
int mat[20][20]={
{0 ,0 ,9 ,7 ,13,20,0 ,0 ,0 , 0},
{0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,5 , 6},
{9 ,0 ,0 ,0 ,0 ,0 ,0 ,8 ,0 , 0},
{7 ,0 ,0 ,0 ,4 ,0 ,0 ,8 ,0 , 0},
{13,0 ,0 ,4 ,0 ,0 ,0 ,0 ,3 , 4},
{20,0 ,0 ,0 ,0 ,0 ,4 ,0 ,6 , 0},
{0 ,0 ,0 ,0 ,0 ,4 ,0 ,0 ,0 , 0},
{0 ,0 ,8 ,8 ,0 ,0 ,0 ,0 ,0 , 5},
{0 ,5 ,0 ,0 ,3 ,6 ,0 ,0 ,0 , 9},
{0 ,6 ,0 ,0 ,4 ,0 ,0 ,5 ,9 , 0}
};
// mac dinh start =0, finish=1;=> vi ko biet ham danh gia nen e tao bang
int h[10]={14,0,15,6,8,7,12,10,4,2};
void printPath(int start,int finish,int back[20])//ham xuat duong di
{// ban chat back chinh la father
while(start!=finish)
{
cout<<finish<<"=>";
finish=back[finish];
}
cout<<start;
}
struct cmp{// phuc vu hang doi uu tien
bool operator() (int a,int b) {return h[a]>h[b];}
};
// luon chon nhung nut co h[i] nho nhat co dk
bool Best_First_Search(int start,int finish,bool chuaxet[20],int father[20])
{
priority_queue < int , vector <int> , cmp > pQ;//hang doi uu tien
// so nao co mang h[i] lon hon se ra sau cung
pQ.push(start);
while(true)
{
if(pQ.empty()==true) return false;
int u=pQ.top();
pQ.pop();
if(u==finish) return true;
chuaxet[u]=false;
for(int v=0;v<10;v++)
{
if(mat[u][v]!=0 && chuaxet[v]){
pQ.push(v);
father[v]=u;
}
}
}
}
// chon nut be nhat bo qua cac nut kia,,
bool Greedy_Best_First_Search(int start,int finish,bool chuaxet[20],int father[20])
{
int u=start;
while(u!=finish){
chuaxet[u]=false;
int min=20000,index=-1;
for(int v=0;v<10;v++)
{
if(mat[u][v]!=0 && chuaxet[v] && min>h[v]){
min=h[v];
index=v;
}
}
if(index<0) return false;
else{
father[index]=u;
u=index;
}
}
return true;
}
//tim kiem chieu sau(cu the: dong gia)+ h(u)
bool Hill_Climbing_Search(int start,int finish,bool chuaxet[20],int father[20])
{
stack <int> S;
S.push(start);
while(true){
if(S.empty()==true) return false;
int u=S.top();
S.pop();
if(u==finish) return true;
chuaxet[u]=false;
int L1[10],countL1=0;
for(int v=0;v<10;v++)//tim cac nude ke voi u
{
if(mat[u][v]!=0 && chuaxet[v]){
L1[countL1]=v;
countL1++;
}
}
for(int i=0;i<countL1-1;i++)//sap xep tang dan
{
for(int j=i+1;j<countL1;j++){
if(h[L1[i]]>h[L1[j]]){
int temp=L1[i];
L1[i]=L1[j];
L1[j]=temp;
}
}
}
for(int i=countL1-1;i>=0;i--)//them vao stack (to vao truoc) de lay be truoc
{
S.push(L1[i]);
father[L1[i]]=u;
}
}
}
//tim kiem chum: giong Greed_Best_First_Search : nhung phat trien k node thay //vi 1
bool Beam_Search(int start,int finish,bool chuaxet[20],int father[20],int k)
{
queue<int> Q;
Q.push(start);
while(true)
{
if(Q.empty()==true) return false;
int u=Q.front();
Q.pop();
if(u==finish) return true;
chuaxet[u]=false;
int L1[10],countL1=0;
for(int v=0;v<10;v++)//tim cac nude ke voi u
{
if(mat[u][v]!=0 && chuaxet[v]){
L1[countL1]=v;
countL1++;
}
}
for(int i=0;i<countL1-1;i++)//sap xep tang dan
{
for(int j=i+1;j<countL1;j++){
if(h[L1[i]]>h[L1[j]]){
int temp=L1[i];
L1[i]=L1[j];
L1[j]=temp;
}
}
}
int dem=k;
for(int i=0;i<countL1;i++)//them vao Queue
{
if(dem>0){
Q.push(L1[i]);
father[L1[i]]=u;
dem--;
}
}
}
}
////// Dang moi f[i]= h[i]+ g[i] trong do g[i] duong di tu dau-> i
//h[i] phai la ham chap nhan dk : h[i]<= chi phi thuc te tu i den dich
int Tinh_g(int cur,int father[20])//chi de test ket qua
{
int s=0;
while(cur>0){
s+=mat[cur][father[cur]];
cur=father[cur];
}
return s;
}
//A* search: best first search voi ham danh gia moi
bool A_Search(int start,int finish,bool chuaxet[20],int father[10])
{
int f[20],g[20];
queue < int > pQ;//hang doi
pQ.push(start);
g[start]=0;
f[start]=g[start]+h[start];
while(true)
{
if(pQ.empty()==true) return false;
int u=pQ.front();
pQ.pop();
if(u==finish) return true;
chuaxet[u]=false;
for(int v=0;v<10;v++)
{
if(mat[u][v]!=0 && chuaxet[v]){
father[v]=u;
pQ.push(v);
g[v]=g[u]+mat[u][v];
f[v]=g[v]+h[v];
}
}
//lay ra sap xep roi day lai vao trong queue
int size=pQ.size(),index[20];
for(int i=0;i<size;i++)//lay ra
{
index[i]=pQ.front();
pQ.pop();
}
for(int i=0;i<size-1;i++)//sap xep
{
for(int j=i+1;j<size;j++){
if(f[index[i]]>f[index[j]]){
int temp=index[i];
index[i]=index[j];
index[j]=temp;
}
}
}
for(int i=0;i<size;i++)//day vao
{
pQ.push(index[i]);
}
}
}
//Branch and Bound(nhanh va can): leo doi(dong gia)+ f(u) + phat trien toi uu
bool Branch_and_Bound(int start,int finish,bool chuaxet[20],int father[10])
{
int f[20],g[20];
for(int i=0;i<10;i++) f[i]=20000;
stack<int> S;
S.push(start);
g[start]=0;
f[start]=g[start]+h[start];
int cost=20000;//cost: gia tri ve dich tam thoi
int chaEnd=-1;//luu lai cha cua finish
bool xong=false;//co de nhan biet co den dk finish ko
while(true)
{
if(S.empty()==true) break;
int u=S.top();
S.pop();
chuaxet[u]=false;
if(u==finish){//toi dich,g[finish] tinh theo duong cu da toi dich
xong=true;
chuaxet[u]=true;//dich van con xet tiep nen ko the cho =false
if(cost>=g[u]){// neu dich hien tai tot hon dich cu
cost=g[u];// thay doi dich
chaEnd=father[u];//luu lai cha cua finish
cout<<"cost tam: "<<cost<<endl;
continue;// quay lai tim co hoi khac nua
}
else{//toi dich moi nho hon
father[u]=chaEnd;//tra lai cha cu cho finish
}
}
if(f[u]>cost) continue;//neu ngay tu buoc nay> cost thi luc den finish>> tnao
int L1[10],countL1=0;//chua trang thai ke voi u
int fTemp,gTemp;// bien tam => tranh viec duong di sau(xau hon) lam doi cha
for(int v=0;v<10;v++){
if(mat[u][v]!=0 && chuaxet[v]){
gTemp=g[u]+mat[u][v];
fTemp=gTemp+h[v];
if(fTemp<f[v]){//neu ham danh gia moi tot hon cu//=> ta moi doi cha
f[v]=fTemp;
g[v]=gTemp;
father[v]=u;
L1[countL1]=v;
countL1++;
}
}
}
for(int i=0;i<countL1-1;i++)//sap xep tang dan
{
for(int j=i+1;j<countL1;j++){
if(f[L1[i]]>f[L1[j]]){
int temp=L1[i];
L1[i]=L1[j];
L1[j]=temp;
}
}
}
for(int i=countL1-1;i>=0;i--)//them vao stack (to vao truoc) de lay be truoc
{
S.push(L1[i]);
}
}
return xong;
}
//TIM DOI TUONG TOT NHAT(de phan sau lam tiep)
// khac voi truoc: ko xac dinh dk dich cua qua trinh tim kiem
//tim kiem leo doi de tim doi tuong tot nhât:
//chi can nut tiep theo du tot so voi nut hien tai,, lay luon cost[u]=h[u] cho de
int Hill_Climbing_Search_TN(int start,bool chuaxet[20],int father[20])
{
int u=start;
while(true){
chuaxet[u]=false;
bool stop=true;
for(int v=0;v<10;v++)
{
if(mat[u][v]!=0 && chuaxet[v] ){
if(h[u]>h[v]){// neu nut tiep theo tot hon nut hien tai => chon luon
father[v]=u;
u=v;
stop=false;
break;
}
}
}
if(stop) return u;//khong co nut con nao tm=> ket thuc
}
}
int main()
{
int father[20];
bool chuaxet[20];
int start=0,finish=1;//mac dinh ko doi
for(int i=0;i<10;i++){
chuaxet[i]=true;
father[i]=-1;
}
///LUY Y VI khoi tao cac bien chuaxet va father 1 lan nen chi goi dk tung ham 1
//if(Best_First_Search(start,finish,chuaxet,father))
// if(Greedy_Best_First_Search(start,finish,chuaxet,father))
// if(Hill_Climbing_Search(start,finish,chuaxet,father))
// if(Beam_Search(start,finish,chuaxet,father,1))//sai cho nao ko biet => ...?
// if(A_Search(start,finish,chuaxet,father))
if(Branch_and_Bound(start,finish,chuaxet,father))
printPath(start,finish,father);
else cout<<"Khong tim dk duong di";
cout<<endl;
cout<<Tinh_g(finish,father);
system("pause");
// return 0;
}
(Tìm kiếm có kinh nghiệm)
Các thuật toán tìm kiếm giải quyết những bài toán không thể vét cạn nổi ngay cả trên máy tính để ra đáp án chính xác nhất
ví dụ: cờ vua, mây,...
thực tế: ví dụ có 4 triệu mua điện thoại , Ta không có thời gian để đi dùng thử tất cả các máy <=4 triệu trên thị trường rồi mới mua,,,=> phần này sẽ gq
=> phần code ở dưới cùng Nội Dung
2 Hàm đánh giá
=> Việc xây dựng tùy thuộc vào vấn đề cần giải quyết
Ở bước 2 chia 2 loại: đánh giá càng gần thực tế càng tốt
minimum: h(u)<= chi phí thực tế
maximum: h(u)>= chi phí thực tế
Ví dụ 1:
Ví dụ 2:
3 Best First Search
Ví dụ: h(u) là hàm đánh giá từ hiện tại=> đích
+ Cài Đặt:
4 Greedy- Best First Search
Ý Tưởng= f(n) : ước lượng đến trạng thái đích+ Tìm kiếm theo chiều sâu
+ Ví dụ:
Như với ví dụ trên A=> D vì min (xong E,C don't care)=> I( F no care)=> B => đây là TH ngon
=> giả sử I không nối đk tới B(h(u) không tốt) => hóc tại đây
+ Ví dụ 2: Có 25 000đ ăn trưa=> mục đích ngon,bổ,rẻ,.....
đầu tiên vào nhìn chọn món=> biết quái ngon,bổ,.. không => đánh giá tạm thời dựa vào dẻ cứ cái nào dẻ hơn thì chọn=> hehe(đúng thuật toán thế)=> sau chọn xong mới biết=> không nuốt nổi
+ hay mua nồi, quạt, tivi... => tiêu chuẩn: dẻ, bền,sịn,.
=> biết đâu được bền mới xịn=> h(u) chủ yếu dựa trên dẻ=> mấy tháng hỏng=> FF Tàu đểu thế
=> Giải thuật gặp khó khăn như vậy trong TH h(u) đánh giá không tôt: đã ngon,bổ còn đòi rẻ, mà đã rẻ lại còn đòi bền, hịn,....
5 Tìm kiếm Leo đồi
Ý tưởng: gần giống Greedy Best First Search khac:
+ Không cần xét tất cả vị trí xung quanh, chỉ cần chọn vị trí đủ tốt so với vị trí hiện tại=> sử dụng Stack ưu tiên
+ Ví dụ:
Có nhiều cách đi=> bài toán đa hướng=> thuận lợi tìm nghiệm tốt toàn cục=> với những bài toán chưa có đích đến cụ thể
Ví dụ: thi đại học: với kiến thức hạn hẹp của Ta chỉ biết 1 vài trường ,, thi xong toẹt hết,, vậy là khỏi tìm hiểu các trường khác,, chọn đại trường nào biết => vẫn tốt hơn ở nhà làm gì bây giờ => hhhh
6 Tìm Kiếm Chùm
Ý tưởng: Best First Search + K node để phát triển
=> tức Ta không chỉ chọn 1 node tốt nhất mà chọn k node tốt nhất để phát triển => số đỉnh phát triển ở mức(tầng) d là k^d
Ví dụ:
ví dụ: trong kinh tế: hay vì đầu tư 1 công ty,, ta sẽ đầu tư vào nhiều nguồn khác giảm thiểu rủi ro(đương nhiên giảm lãi suất)
=> đây cũng là cách mà các thần đề sử dụng thay vì đánh hết 1 con,, các anh sẽ dải ra đánh k con theo hàm heuristic mà các anh cho là tốt nhất .
7 Heuristic chấp nhận được
heuristic quan trọng như thế nào trong AI khỏi nhắc lại => điều tìm ra heuristic tuyệt đối là gần như không thể mà nếu chon h(u) sai mọi thứ sẽ vô ích,,,, => chọn như nào để không bị sai=> ở trên có nói rồi minimum và maximum đó
8 A* Search
Ý Tương= TK Chiều Rộng+ f(u)
Hàm Lượng Giá: f(u)= g(u)+ h(u) (tổng giá đến đích)
g(u): chi phí thực tế đến u
h(u): heuristic đánh giá từ u đến đích
Ví dụ:
=> heuristic chấp nhận được thì A* là tối ưu
ví dụ: rõ ràng 3 vấn đề ta hay mắc phải
+ cóc biết đích là gì( h(u) hên xui không đánh giá dk) : không biết mục đích việc sống, học,làm 1 việc nào đó
+ h(u) : đánh giá h(u) không thể chấp nhận dk
ví dụ: ảo giác bản thân....
+ g(u): quá luyến tiếc vào cái đã bỏ ra mà quên rằng còn có h(u)
ví dụ: giành 1 năm để....=> biết làm nó sẽ rất khó... nhưng lại sợ tốn chi phí của 1 năm đó,, he
9 TK Nhánh và Cận
Ý tương: với f(u) như ở trên
Ví dụ:
+ Cài Đặt:
=> Nhánh cận Tối ưu nêu h(u):
+ Đánh giá thấp và độ dài các cung không nhỏ hơn 1 số dương alpha nào đó
10 Tìm kiếm đối tượng tốt nhất
+ Kỹ thuật TK leo đồi
+ Kỹ thuật TK gradient
+ Kỹ thuật TK mô phỏng luyện kim
10.1 Leo đồi để Tk đối tượng tốt nhất
+ Cài Đặt
+ Nhận Xét:
10.2 Tk địa phương trong tối ưu không ràng buộc
+ TK Gradient
+ Thuật toán giảm Gradient
alpha(k): hệ số học => lựa chọn = thử = thực nghiệm
+ Cài Đặt:
+ Ví dụ:
10.3 Tìm Kiếm Mô phỏng Luyện Kim
+ Nhận Xét:
11 Thuật toán GENE ( phần sau)
Code in C++:
#include<iostream>
#include<stdlib.h>
#include<stack>
#include<queue>
using namespace std;
///ma tran trong so, mac dinh so dinh =10
int mat[20][20]={
{0 ,0 ,9 ,7 ,13,20,0 ,0 ,0 , 0},
{0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,5 , 6},
{9 ,0 ,0 ,0 ,0 ,0 ,0 ,8 ,0 , 0},
{7 ,0 ,0 ,0 ,4 ,0 ,0 ,8 ,0 , 0},
{13,0 ,0 ,4 ,0 ,0 ,0 ,0 ,3 , 4},
{20,0 ,0 ,0 ,0 ,0 ,4 ,0 ,6 , 0},
{0 ,0 ,0 ,0 ,0 ,4 ,0 ,0 ,0 , 0},
{0 ,0 ,8 ,8 ,0 ,0 ,0 ,0 ,0 , 5},
{0 ,5 ,0 ,0 ,3 ,6 ,0 ,0 ,0 , 9},
{0 ,6 ,0 ,0 ,4 ,0 ,0 ,5 ,9 , 0}
};
// mac dinh start =0, finish=1;=> vi ko biet ham danh gia nen e tao bang
int h[10]={14,0,15,6,8,7,12,10,4,2};
void printPath(int start,int finish,int back[20])//ham xuat duong di
{// ban chat back chinh la father
while(start!=finish)
{
cout<<finish<<"=>";
finish=back[finish];
}
cout<<start;
}
struct cmp{// phuc vu hang doi uu tien
bool operator() (int a,int b) {return h[a]>h[b];}
};
// luon chon nhung nut co h[i] nho nhat co dk
bool Best_First_Search(int start,int finish,bool chuaxet[20],int father[20])
{
priority_queue < int , vector <int> , cmp > pQ;//hang doi uu tien
// so nao co mang h[i] lon hon se ra sau cung
pQ.push(start);
while(true)
{
if(pQ.empty()==true) return false;
int u=pQ.top();
pQ.pop();
if(u==finish) return true;
chuaxet[u]=false;
for(int v=0;v<10;v++)
{
if(mat[u][v]!=0 && chuaxet[v]){
pQ.push(v);
father[v]=u;
}
}
}
}
// chon nut be nhat bo qua cac nut kia,,
bool Greedy_Best_First_Search(int start,int finish,bool chuaxet[20],int father[20])
{
int u=start;
while(u!=finish){
chuaxet[u]=false;
int min=20000,index=-1;
for(int v=0;v<10;v++)
{
if(mat[u][v]!=0 && chuaxet[v] && min>h[v]){
min=h[v];
index=v;
}
}
if(index<0) return false;
else{
father[index]=u;
u=index;
}
}
return true;
}
//tim kiem chieu sau(cu the: dong gia)+ h(u)
bool Hill_Climbing_Search(int start,int finish,bool chuaxet[20],int father[20])
{
stack <int> S;
S.push(start);
while(true){
if(S.empty()==true) return false;
int u=S.top();
S.pop();
if(u==finish) return true;
chuaxet[u]=false;
int L1[10],countL1=0;
for(int v=0;v<10;v++)//tim cac nude ke voi u
{
if(mat[u][v]!=0 && chuaxet[v]){
L1[countL1]=v;
countL1++;
}
}
for(int i=0;i<countL1-1;i++)//sap xep tang dan
{
for(int j=i+1;j<countL1;j++){
if(h[L1[i]]>h[L1[j]]){
int temp=L1[i];
L1[i]=L1[j];
L1[j]=temp;
}
}
}
for(int i=countL1-1;i>=0;i--)//them vao stack (to vao truoc) de lay be truoc
{
S.push(L1[i]);
father[L1[i]]=u;
}
}
}
//tim kiem chum: giong Greed_Best_First_Search : nhung phat trien k node thay //vi 1
bool Beam_Search(int start,int finish,bool chuaxet[20],int father[20],int k)
{
queue<int> Q;
Q.push(start);
while(true)
{
if(Q.empty()==true) return false;
int u=Q.front();
Q.pop();
if(u==finish) return true;
chuaxet[u]=false;
int L1[10],countL1=0;
for(int v=0;v<10;v++)//tim cac nude ke voi u
{
if(mat[u][v]!=0 && chuaxet[v]){
L1[countL1]=v;
countL1++;
}
}
for(int i=0;i<countL1-1;i++)//sap xep tang dan
{
for(int j=i+1;j<countL1;j++){
if(h[L1[i]]>h[L1[j]]){
int temp=L1[i];
L1[i]=L1[j];
L1[j]=temp;
}
}
}
int dem=k;
for(int i=0;i<countL1;i++)//them vao Queue
{
if(dem>0){
Q.push(L1[i]);
father[L1[i]]=u;
dem--;
}
}
}
}
////// Dang moi f[i]= h[i]+ g[i] trong do g[i] duong di tu dau-> i
//h[i] phai la ham chap nhan dk : h[i]<= chi phi thuc te tu i den dich
int Tinh_g(int cur,int father[20])//chi de test ket qua
{
int s=0;
while(cur>0){
s+=mat[cur][father[cur]];
cur=father[cur];
}
return s;
}
//A* search: best first search voi ham danh gia moi
bool A_Search(int start,int finish,bool chuaxet[20],int father[10])
{
int f[20],g[20];
queue < int > pQ;//hang doi
pQ.push(start);
g[start]=0;
f[start]=g[start]+h[start];
while(true)
{
if(pQ.empty()==true) return false;
int u=pQ.front();
pQ.pop();
if(u==finish) return true;
chuaxet[u]=false;
for(int v=0;v<10;v++)
{
if(mat[u][v]!=0 && chuaxet[v]){
father[v]=u;
pQ.push(v);
g[v]=g[u]+mat[u][v];
f[v]=g[v]+h[v];
}
}
//lay ra sap xep roi day lai vao trong queue
int size=pQ.size(),index[20];
for(int i=0;i<size;i++)//lay ra
{
index[i]=pQ.front();
pQ.pop();
}
for(int i=0;i<size-1;i++)//sap xep
{
for(int j=i+1;j<size;j++){
if(f[index[i]]>f[index[j]]){
int temp=index[i];
index[i]=index[j];
index[j]=temp;
}
}
}
for(int i=0;i<size;i++)//day vao
{
pQ.push(index[i]);
}
}
}
//Branch and Bound(nhanh va can): leo doi(dong gia)+ f(u) + phat trien toi uu
bool Branch_and_Bound(int start,int finish,bool chuaxet[20],int father[10])
{
int f[20],g[20];
for(int i=0;i<10;i++) f[i]=20000;
stack<int> S;
S.push(start);
g[start]=0;
f[start]=g[start]+h[start];
int cost=20000;//cost: gia tri ve dich tam thoi
int chaEnd=-1;//luu lai cha cua finish
bool xong=false;//co de nhan biet co den dk finish ko
while(true)
{
if(S.empty()==true) break;
int u=S.top();
S.pop();
chuaxet[u]=false;
if(u==finish){//toi dich,g[finish] tinh theo duong cu da toi dich
xong=true;
chuaxet[u]=true;//dich van con xet tiep nen ko the cho =false
if(cost>=g[u]){// neu dich hien tai tot hon dich cu
cost=g[u];// thay doi dich
chaEnd=father[u];//luu lai cha cua finish
cout<<"cost tam: "<<cost<<endl;
continue;// quay lai tim co hoi khac nua
}
else{//toi dich moi nho hon
father[u]=chaEnd;//tra lai cha cu cho finish
}
}
if(f[u]>cost) continue;//neu ngay tu buoc nay> cost thi luc den finish>> tnao
int L1[10],countL1=0;//chua trang thai ke voi u
int fTemp,gTemp;// bien tam => tranh viec duong di sau(xau hon) lam doi cha
for(int v=0;v<10;v++){
if(mat[u][v]!=0 && chuaxet[v]){
gTemp=g[u]+mat[u][v];
fTemp=gTemp+h[v];
if(fTemp<f[v]){//neu ham danh gia moi tot hon cu//=> ta moi doi cha
f[v]=fTemp;
g[v]=gTemp;
father[v]=u;
L1[countL1]=v;
countL1++;
}
}
}
for(int i=0;i<countL1-1;i++)//sap xep tang dan
{
for(int j=i+1;j<countL1;j++){
if(f[L1[i]]>f[L1[j]]){
int temp=L1[i];
L1[i]=L1[j];
L1[j]=temp;
}
}
}
for(int i=countL1-1;i>=0;i--)//them vao stack (to vao truoc) de lay be truoc
{
S.push(L1[i]);
}
}
return xong;
}
//TIM DOI TUONG TOT NHAT(de phan sau lam tiep)
// khac voi truoc: ko xac dinh dk dich cua qua trinh tim kiem
//tim kiem leo doi de tim doi tuong tot nhât:
//chi can nut tiep theo du tot so voi nut hien tai,, lay luon cost[u]=h[u] cho de
int Hill_Climbing_Search_TN(int start,bool chuaxet[20],int father[20])
{
int u=start;
while(true){
chuaxet[u]=false;
bool stop=true;
for(int v=0;v<10;v++)
{
if(mat[u][v]!=0 && chuaxet[v] ){
if(h[u]>h[v]){// neu nut tiep theo tot hon nut hien tai => chon luon
father[v]=u;
u=v;
stop=false;
break;
}
}
}
if(stop) return u;//khong co nut con nao tm=> ket thuc
}
}
int main()
{
int father[20];
bool chuaxet[20];
int start=0,finish=1;//mac dinh ko doi
for(int i=0;i<10;i++){
chuaxet[i]=true;
father[i]=-1;
}
///LUY Y VI khoi tao cac bien chuaxet va father 1 lan nen chi goi dk tung ham 1
//if(Best_First_Search(start,finish,chuaxet,father))
// if(Greedy_Best_First_Search(start,finish,chuaxet,father))
// if(Hill_Climbing_Search(start,finish,chuaxet,father))
// if(Beam_Search(start,finish,chuaxet,father,1))//sai cho nao ko biet => ...?
// if(A_Search(start,finish,chuaxet,father))
if(Branch_and_Bound(start,finish,chuaxet,father))
printPath(start,finish,father);
else cout<<"Khong tim dk duong di";
cout<<endl;
cout<<Tinh_g(finish,father);
system("pause");
// return 0;
}
Nhận xét
Đăng nhận xét