Duyệt theo chiều sâu

Ưu và nhược điểm của phương pháp tìm kiếm theo chiều sâu:

*Ưu điểm:
1) Nếu bài toán có lời giải, pp đảm bảo sẽ tìm ra lời giải.
2)Kỹ thuật tìm kiếm theo chiều sâu tập trung vào đích, con người hài lòng khi các câu hỏi tập trung vào vấn đề chính.
3) Do cách tìm của kỹ thuật này, nếu lời giải rất sâu kỹ thuật sẽ rất tiết kiệm thời gian.

*Nhược điểm:
1) Cách làm này có vẻ cứng nhắc do tìm lời giải theo một thuật toán đơn giản dựa vào việc tìm sâu vào không gian bài toán.

Trong quá trình tìm, nó không có một thông tin nào để hỗ trợ bài toán.

Nếu chọn nút ban đầu không phù hợp thì có thể dẫn tới việc không tìm ra lời giải cho bài toán.

2) Không phù hợp với bài toán lớn, kỹ thuật tìm kiếm theo chiều sâu có thể không cho ta lời giải trong một khoảng thời gian vừa phải.

Source:

1) http://mucdongblog.wordpress.com/2010/01/10/gi%E1%BA%A3i-thu%E1%BA%ADt-tim-ki%E1%BA%BFm-theo-chi%E1%BB%81u-sau/#comment-209

//Init_matrix.h
#define MAX 100

void Init(int &m, int &n, int a[][MAX], std::ifstream &infile)
{
     //std::cout<<"Nhap chi so hang va cot cua ma tran A :";
     //std::cin>>m>>n;
     infile>>m>>n;
     int i,j;
     for(i=0;i<m;++i)
     for(j=0;j<n;++j)
     {
                     //std::cout<<std::endl<<"a["<<i<<"]["<<j<<"] = ";
                     //std::cin>>a[i][j];
                     infile>>a[i][j];
     }
}

//cac_thao_tac_voi_stack.h
/*:
                          Khai bao kieu Stack
                          void Init_Stack(Stack &S); //Khoi tao Stack
                          bool IsEmpty_Stack(Stack S);//Kiem tra tinh rong cua Stack
                          void Push_Stack(Stack &S, int v); //Them mot node co gia tri v vao Stack
                          int Pop_Stack(Stack &S); //Xoa mot node cua Stack
                          void Print_Sack(const Stack &S);//Duyet toan bo stack va in chung 
                          */

//Khai bao
typedef struct pStack
{
        int Top;
        pStack *Next;
}*Stack;

//Khoi tao Stack rong
void Init_Stack(Stack &S)
{
     S = NULL;
}

bool IsEmpty_Stack(Stack S)
{
     if(S == NULL)
       return 1; //Neu Stack rong tra ve 1
       
     return 0; //Nguoc lai tra ve 0
}

void Push_Stack(Stack &S, int v)
{
     //Khai bao mot node moi
     pStack *p;
     p = new pStack; //Cap phat bo nho cho node moi
     
     if(p==NULL)
     {
                std::cout<<"Memory Empty."; //Neu p rong, thong bao het bo nho
                return;
     }
     
     p->Top = v;
     p->Next = S; //Tao link lien ket tu p den Stack
     S = p; //Bay gio p la Stack
}

int Pop_Stack(Stack &S)
{
    pStack *p; //p de luu node bi xoa
    if(IsEmpty_Stack(S))
    {
                        return 0; //Neu Stack rong thi thoat ra
    }
    p = S; //p la S
    S = p->Next; //S link toi node dang sau no
    int v = p->Top; // v luu gia tri cua node bi xoa
    delete(p); //Giai phong bo nho cho node bi xoa
    return v; //Tra ve gia tri cua node bi xoa
}

void Print_Stack(const Stack &S)
{
     pStack *p; //p tro vao node can in ra
     p = S ;// p la S
     while(!IsEmpty_Stack(p))//Trong khi p khong rong
     {
                                    std::cout<<" "<<p->Top;
                                    p = p->Next; // p link toi node ke tiep
     }
}
     
     

//mot_so_bai_toan_voi_do_thi.h



//******************************************************************************
//******************************************************************************

#include"Duyet_theo_chieu_sau_su_dung_stack.h"

//Kiem tra tinh lien thong cua do thi 
//va dem so thanh phan lien thong neu do thi khong lien thong
void dem_so_thanh_phan_lien_thong()
{
     int so_TP_lien_thong = 1;
      Init_daxet();  //Khoi tao mang da xet
     DFS(0); // Depth_First_Stravelse 
     for(int i=0;i<n;++i)
     {
                if(daxet[i] == False)
                {
                            ++so_TP_lien_thong;
                            DFS(i);
                }
        {
                       
        }
     }
     if(so_TP_lien_thong>1)
     {
              std::cout<<std::endl<<"Do thi da cho khong lien thong. ";
              std::cout<<std::endl<<"So thanh phan lien thong la: "<<so_TP_lien_thong;
     }
     else
         std::cout<<std::endl<<std::endl<<"Do thi da cho lien thong.";
}

//Ham chi kiem tra tinh lien thong cua do thi
bool kiem_tra_lien_thong()
{
     int i;
     for(i=0;i<n;++i)
       if(daxet[i] == False)
                  return 0; //do thi khong lien thong tra ve 0
     return 1; //Nguoc lai tra ve 1
}
     
       
     
bool kiem_tra_dinh_tru(int v)
{
     int i = 0;
      Init_daxet();  //Khoi tao mang da xet
      daxet[v] = True; //Danh dau dinh v da xet
      while(daxet[i]==True &&i<n)++i;
     DFS(i); // Depth_First_Stravelse from '0';
     if(kiem_tra_lien_thong())return False; // v khong phai dinh tru
     return True; // v la dinh tru
     
}

//Tim_dinh_tru
void tim_dinh_tru()
{
     
     int i;
     for(i=0;i<n;++i)
     {
                     if( kiem_tra_dinh_tru(i))
                     {
                         std::cout<<"dinh tru: "<<i+1<<std::endl;
                     }
     }
}


bool kiem_tra_canh_cau(int v, int k)
{
     int i = 0;
      Init_daxet();  //Khoi tao mang da xet
      daxet[v]=daxet[k] = True; //Danh dau dinh v va dinh k da xet
      while(daxet[i]==True &&i<n)++i;
     DFS(i); // Depth_First_Stravelse from '0';
     if(kiem_tra_lien_thong())return False; // v-k khong phai canh cau
     return True; // v-k la canh cau
     
}
 
void tim_canh_cau()
{
     
     int i,j;
     for(i=0;i<n-1;++i)
      for(j=i+1;j<n ;++j)
      {
                     if( kiem_tra_canh_cau(i,j))
                     {
                         std::cout<<"canh cau noi giua 2 dinh : "<<i+1<<" "<<j+1<<std::endl;
                     }
     }
}
                    

//Duyet_theo_chieu_sau_su_dung_stack.h
/*:
     Chuong trinh nhap du lieu tu file src1.txt
    
     */

#include<iostream>
#include"cac_thao_tac_voi_stack.h"
#include"Init_Matrix.h" //file B

#define True 1
#define False 0

int n,a[MAX][MAX],so_TP_lien_thong = 1;
bool daxet[MAX];
/*:
     n = so dinh cua do thi
     a[][] = ma tran lien ke bieu dien do thi
     so_TP_lien_thong = dem so thanh phan lien thong cua do thi
     daxet[] = danh dau cac dinh da duoc tham
     */
     

//************************************************************************
//************************************************************************ 
//Khai bao nguyen mau ham
void Init_Stack(Stack &Q);
bool IsEmpty_Stack(Stack Q);
void Push_Stack(Stack &Q, int v);
int Pop_Stack(Stack &Q);
void Init_daxet();

//************************************************************************
//************************************************************************

void Init_daxet()
{
     
     for(int i =0;i<n;++i)
       daxet[i] = False;
}
     
void DFS(int v)
{
     Stack P;
     Init_Stack(P);
     daxet[v] = True;
     Push_Stack(P,v);
     int i;
     while(!IsEmpty_Stack(P))
     {
                     v = P->Top;                   
                     for(i=0;i<n;++i)
                     {
                         if(a[i][v] && daxet[i] == False)
                         {
                                    Push_Stack(P,i);
                                    daxet[i] = True;
                                    v = i;
                                    i =-1;
                         }
                       
                     } 
                    Pop_Stack(P);
                    //   std::cout<<" "<<Pop_Stack(P)+1;        
     }
}