Phân tích thiết kế giải thuật

                     Trí Tuệ Nhân Tạo P2

     Không gian trạng Thái  và các Phương pháp                                   Tìm kiếm Mù
=> CODE o duoi

I Không gian trạng thái
(các trạng thái trong nó là ứng viên cho lời giải)

+ Các chiến lược tìm kiếm KGTT

+ Phương pháp đánh giá chiến lược Tìm Kiếm 

+ Các chiến lược tìm kiếm Mù

1 Tìm kiếm Theo chiều Rộng
tìm kiếm theo từng tầng, phát triển các node gần nút nhất

=> đầu tiên duyệt A cất B và C trong hàng đợi=> Lấy trong hàng đợi ra B=> duyệt=> cất D, E trong hàng đợi=> C.......
A=> B=> C=>D=>E=> F=>G

2 Tìm Kiếm đều giá

=> ví dụ như khi duyệt A => cất B,C vào hàng đợi , thằng nào giá rẻ hơn thì cất vào trước,, tuong tự,,

3 Tìm kiếm theo chiều sâu

=> duyệt A cất C,B trong Stack, lấy trong stack (v trí đầu) B=> cất E,D trong Stack=> lấy D=> cất I,H trong stack=> lấy H=> đáy=> lấy I=> đáy=> lấy E=> cất K,J=>....... đến hết

4 Tìm kiếm với độ sâu giới hạn
là DFS với độ sâu giới hạn d, node ở độ sâu d ko đk tính là có node con

+ giải mã:

5 Tìm kiếm sâu dần

=> Sử dụng trong cây trò chơi 

6 Trạng thái Trùng Lặp
Nếu không được xử lý dẫn tới bùng nổ về mặt thời gian cũng như không gian trạng thái

+ Chia để trị
Ví dụ:

Ví dụ 2:

+ Tìm kiếm trên đồ thị hoặc và

+ CODE= DEV 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 ,20,0 ,0 ,21,19,0 ,0 , 0},
{0 ,0 ,0 ,0 ,0 ,21,19,0 ,8 , 0},
{20,0 ,0 ,4 ,5 ,0 ,0 ,0 ,0 , 0},
{0 ,0 ,4 ,0 ,0 ,0 ,4 ,0 ,0 , 0},
{0 ,0 ,5 ,0 ,0 ,0 ,0 ,0 ,0 , 4},
{21,21,0 ,0 ,0 ,0 ,2 ,0 ,0 , 0},
{19,19,0 ,4 ,0 ,2 ,0 ,0 ,0 , 0},
{0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 , 0},
{0 ,8 ,0 ,0 ,0 ,0 ,0 ,0 ,0 , 3},
{0 ,0 ,0 ,0 ,4 ,0 ,0 ,0 ,3 , 0}
};

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;
}
//Breadth First Search: tim kiem theo chieu rong
bool BFS(int start,int finish,bool chuaxet[20],int father[20])//tim kiem chieu rong
{
queue <int> Q ;
Q.push(start);
while(true)
{
if(Q.empty()==true) return false;
int u=Q.front();//lay phan tu
Q.pop();//bo phan tu
if(u==finish) return true;
chuaxet[u]=false;
for(int v=0;v<10;v++){
if(mat[u][v]!=0 && chuaxet[v]){
Q.push(v);
father[v]=u;
}
}
}
}
//uniform - cost search: tim kiem dong gia
bool UCS(int start,int finish,bool chuaxet[20],int father[20])//tim kiem deu gia
{
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 cost[10];//them gia tri vao mang nay=> sap xep=> truyen vao queue
for(int v=0;v<10;v++){
cost[v]=-1;
if(mat[u][v]!=0 && chuaxet[v]){
cost[v]=mat[u][v];
}
}
//sap xep mang cost theo gia tri tang dan
for(int v=0;v<9;v++){
if(cost[v]>0){
for(int i=v+1;i<10;i++){
if(cost[i]>0 && cost[v]>cost[i]){
int temp=cost[v];
cost[v]=cost[i];
cost[i]=temp;
}
}
}
}
//them vao queue
for(int v=0;v<10;v++)
{
if(cost[v]>0){
Q.push(v);
father[v]=u;
}
}
}
}
//depth first search: tim kiem chieu sau
bool DFS(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();//lay phan tu
S.pop(); // xoa phan tu
if(u==finish) return true;
chuaxet[u]=false;

for(int v=0;v<10;v++){
if(mat[u][v]!=0 && chuaxet[v]){
S.push(v);
father[v]=u;
}
}
}
}
//Depth Limited Search: tim kiem voi do sau gioi han
bool DLS(int start,int finish,bool chuaxet[20],int father[20],int d)
{
stack<int> S;
S.push(start);

if(d>=0){//neu do sau chua toi han
while(true){
if(S.empty()==true) return false;
int u=S.top();
S.pop();
if(u==finish) return true;
chuaxet[u]=false;
for(int v=0;v<10;v++){
if(mat[u][v]!=0 && chuaxet[v]){
S.push(v);
father[v]=u;
d--;
}
}
}
}
}
//Depth Deepening Search: tim kiem sau dan=> tang max
bool DDS(int start,int finish,bool chuaxet[20],int father[20],int max)
{
for(int d=0;d<max;d++){
if(DLS(start,finish,chuaxet,father,d)) return true;
}
return false;
}

int main()
{
int father[20];
bool chuaxet[20];
int start=1,finish=2;

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(BFS(start,finish,chuaxet,father)) printPath(start,finish,father);
// else cout<<"khong tim dk duong di theo BFS"<<endl;
// cout<<endl;

// if(UCS(start,finish,chuaxet,father)) printPath(start,finish,father);
// else cout<<"khong tim dk duong di theo UCS"<<endl;
// cout<<endl;

// if(DFS(start,finish,chuaxet,father)) printPath(start,finish,father);
// else cout<<"khong tim dk duong di theo DFS"<<endl;
// cout<<endl;

if(DLS(start,finish,chuaxet,father,2)) printPath(start,finish,father);
else cout<<"khong tim dk duong di theo DLS"<<endl;
cout<<endl;

// if(DDS(start,finish,chuaxet,father,4)) printPath(start,finish,father);
// else cout<<"khong tim dk duong di theo DDS"<<endl;
// cout<<endl;

system("pause");
return 0;
}