Duyệt theo chiều rộng

Giải thuật tìm kiếm theo chiều rộng:

*Ưu điểm của phương pháp này:

1) Đây là kỹ  thuật vét cạn không gian trạng thái bài toán vì vậy sẽ tìm được lời giải nếu có
2) Đường đi tìm được đi qua ít đỉnh nhất

*Nhược điểm:
1) PP này không phù hợp với bài toán không gian kích thước lớn. Đối với bài toán này, pp duyệt theo chiều rộng phải đối mặt với các vấn đề sau:
+Cần nhiều bộ nhớ theo số nút cần lưu  trữ.
+Cần nhiều công sức để xử lý các nút, nhất là khi nhánh dài và số nút tăng.
+Dễ xử lý những thao tác không thích hợp, thừa, đưa đến việc tăng đáng kể số nút cần xử lý.

2) Tìm kiếm lời giải theo một cách giải cho trước, do vậy tìm kiếm một cách máy móc, khi không có thông tin hỗ trợ thì không tìm được ngay ra lời giải.

3) Không hiệu quả nếu lời giải ở sâu. Phương pháp này không hiệu quả nếu bài toán có nhiều nhánh và các nhánh đều sâu.
4) Giao tiếp với người dùng không thân thiện. Do duyệt qua tất cả các nút, mà không tập trung vào một chủ đề.











Nguồn :
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-r%E1%BB%99ng/

//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];
     }
}

//Duyet theo chieu rong su dung queue
#include<iostream>
#include<fstream>
#include<conio.h>
#include"Init_matrix.h"
#include"print_matrix.h"
#define True 1
#define False 0

int n,a[MAX][MAX];
bool daxet[MAX];

//Khai bao tep

std::ifstream infile("src1.txt");
std::ofstream outfile("src1_3output.txt");

//*************************************************************************************
//Khoi tao mang daxet[]
//**********************************************************************************
void Init_daxet()
{
     for(int i =0;i<n;++i)
       daxet[i] = False;
}

//***********************************************************************************
//Cac thao tac voi Queue
//***********************************************************************************

//Khai bao queue
typedef struct pNode
{
       int Infor;
       pNode *Next;
}Node;

typedef struct pQueue
{
      Node *Head;
      Node *Tail;
}Queue;

//Khoi tao queue
void InitQueue( Queue &Q)
{
     Q.Head = NULL;
     Q.Tail = NULL;
}

//Kiem tra rong
bool Empty(Queue Q)
{
     if(Q.Head == NULL)
     {
               return 1;
     }
     
     return 0;
}

//Chen them mot node
void EnQueue(Queue &Q, int v)
{
     Node *P;     
     //Cap phat bo nho cho P
     P = new Node;
     if(P==NULL){
               //  std::cout<<"Khong cap duoc bo nho.";
                 return;
                 }
     
     P->Infor = v;  //P luu gia tri can them vao
     
     P->Next = NULL; //P khong tro vao dau ca

     
     if(Empty(Q)) //Neu Queue rong
     {
               Q.Head = P;  //P vua la Head vua la Tail
     }
     else  Q.Tail->Next = P; //Q.Tail link liên ket toi P
     
     Q.Tail = P; // P la Tail
     
}

//Loai mot node cua Queue
int DeQueue(Queue &Q)
{
    Node *P;
    if(Empty(Q))
    {
              return -1;
    }
    P = Q.Head;  //P la Head
    Q.Head = P ->Next;
    if(Q.Head ==NULL)Q.Tail = Q.Head;
    int v = P->Infor;
    delete(P);
    return v;
}

//**********************************************************
//Giai thuat tim kiem theo chieu rong BFS
//*************************************************************
void BFS(int v)
{
     int i; //Bien dem
     
     Queue Q;
     InitQueue(Q);
     
     daxet[v] = True;//Danh dau da tham dinh v
     EnQueue(Q,v); 
    
     
     do
     {
                     v = Q.Head->Infor;
                     for(i=0;i<n;++i)
                     {
                                     if(a[i][v] && daxet[i] == False)
                                     {
                                                EnQueue(Q,i); //Queue Q chua tat ca cac dinh ke voi dinh v
                                                daxet[i] = True;
                                     }
                     }
                     outfile<<DeQueue(Q)+1<<" "; //Loai mot node dau
     }while(!Empty(Q));
}

void kiem_tra_tinh_lien_thong()
{
     for(int i=0;i<n;++i)
     {
                if(daxet[i] == False)
        {
                       outfile<<std::endl<<"Do thi khong lien thong. ";
                     return ;
        }
     }
     
     outfile<<std::endl<<std::endl<<"Do thi da cho lien thong.";
}



main()
{
      Init(n,n,a,infile);
      Init_daxet();
      BFS(0);
      kiem_tra_tinh_lien_thong();
      in_ma_tran(n,n,a,outfile);
     // system("pause ");
      
}