STDIO
Tìm kiếm gần đây

    Nội dung

    Thuật toán Depth First Search

    19/09/2015
    10/12/2017
    Thuật toán Depth First Search - DFS (tìm kiếm theo chiều sâu) cùng với Thuật toán Breadth First Search - BFS là một trong hai thuật toán tìm kiếm cơ bản trong bộ môn Trí tuệ nhân tạo, là tiền đề chuẩn bị để tìm hiểu các thuật toán phức tạp hơn.

    Giới thiệu

    Bài viết giới thiệu, nêu khái quát và trình bày về thuật toán Depth First Search (DFS – Tìm kiếm theo chiều sâu), cùng với thuật toán Breadth First Search là hai thuật toán cơ bản để chuẩn bị ra các thuật toán phức tạp hơn trong bộ môn Trí tuệ nhân tạo. Những người muốn tìm hiểu về kiến thức cơ bản về trí tuệ nhân tạo nói chung, các thuật toán tìm kiếm nói riêng.

    Thuật toán Depth First Search

    Thuật toán Depth First Search (DFS – Tìm kiếm theo chiều sâu) là một dạng thuật toán duyệt hoặc tìm kiếm trên cây hoặc đồ thị. Trong lý thuyết khoa học máy tính, thuật toán DFS nằm trong chiến lược tìm kiếm mù (tìm kiếm không có định hướng, không chú ý đến thông tin, giá trị được duyệt) được ứng dụng để duyệt hoặc tìm kiếm trên đồ thị.

    Ý tưởng thuật toán

    Từ đỉnh (nút) gốc ban đầu, thuật toán duyệt đi xa nhất theo từng nhánh, khi nhánh đã duyệt hết, lùi về từng đỉnh để tìm và duyệt những nhánh tiếp theo. Quá trình duyệt chỉ dừng lại khi tìm thấy đỉnh cần tìm hoặc tất cả đỉnh đều đã được duyệt qua.

    Thuật giải

    Trước khi bắt đầu, tôi sẽ nêu ra một số quy ước để dễ dàng trong trình bày:

    • Open: là tập hợp các đỉnh chờ được xét ở bước tiếp theo theo ngăn xếp (ngăn xếp: dãy các phần tử mà khi thêm phần tử vào sẽ thêm vào đầu dãy, còn khi lấy phần tử ra sẽ lấy ở phần tử đứng đầu dãy).
    • Close: là tập hợp các đỉnh đã xét, đã duyệt qua.
    • s: là đỉnh xuất phát, đỉnh gốc ban đầu trong quá trình tìm kiếm.
    • g: đỉnh đích cần tìm.
    • p: đỉnh đang xét, đang duyệt.

    Trình bày thuật giải:

    • Bước 1: Tập Open chứa đỉnh gốc s chờ được xét.
    • Bước 2: Kiểm tra tập Open có rỗng không.
      • Nếu tập Open không rỗng, lấy một đỉnh ra khỏi tập Open làm đỉnh đang xét p. Nếu p là đỉnh g cần tìm, kết thúc tìm kiếm.
      • Nếu tập Open rỗng, tiến đến bước 4.
    • Bước 3: Đưa đỉnh p vào tập Close, sau đó xác định các đỉnh kề với đỉnh p vừa xét. Nếu các đỉnh kề không thuộc tập Close, đưa chúng vào đầu tập Open. Quay lại bước 2.
    • Bước 4: Kết luận không tìm ra đỉnh đích cần tìm.

    Code

    Tôi sẽ hiện thực thuật toán này theo ma trận kề bằng ngôn ngữ C++.

    #include <stdio.h>
    #include <stack>
    using namespace std;
    
    // dinh nghia lop do thi
    class Graph
    {
    private:
    	int n;
    	int **edge;
    public:
    	Graph(int size = 2);
    	~Graph();
    	bool isConnected(int, int);
    	void addEdge(int x, int y);
    	void depthFirstSearch(int, int);
    };
    
    Graph::Graph(int size)
    {
    	int i, j;
    
    	// xac dinh so dinh cua do thi
    	if (size < 2)
    		n = 2;
    	else 
    		n = size;
    
    	// tao ra cac dinh trong do thi
    	edge = new int*[n];
    	for (i = 0; i < n; i++)
    		edge[i] = new int[n];
    	
    	// mac dinh giua cac dinh khong co ket noi voi nhau (= 0)
    	for (i = 0; i < n; i++)
    		for (j = 0; j < n; j++)
    			edge[i][j] = 0;
    }
    
    Graph::~Graph()
    {
    	for (int i = 0; i < n; ++i)
    		delete[] edge[i];
    	delete[] edge;
    }
    
    // kiem tra giua hai dinh co ke nhau hay khong
    bool Graph::isConnected(int x, int y)
    {
    	if (edge[x - 1][y - 1] == 1)
    		return true;
    
    	return false;
    }
    
    // thêm cạnh nối đỉnh x và đỉnh y
    void Graph::addEdge(int x, int y)
    {
    	if (x < 1 || x > n || y < 1 || y > n)
    		return;
    
    	edge[x - 1][y - 1] = edge[y - 1][x - 1] = 1;
    }
    
    void Graph::depthFirstSearch(int s, int g)
    {
    	if (s > n || s < 0 || g > n || g < 0)
    	{
    		printf("Could not traverse this graph with your request\n");
    		return;
    	}
    
    	stack <int> open;
    	bool *close = new bool[n];
    	int i;
    	int p;
    
    	// mac dinh cac dinh chua duoc duyet
    	for (i = 0; i < n; i++)
    		close[i] = false;
    
    	// dua dinh goc s vao stack open, chuan bi duyet
    	open.push(s);
    	
    	printf("With Depth first Search , we have vertex(s):\n");
    
    	while (!open.empty())
    	{
    		// lay mot dinh ra khoi open tro thanh dinh dang xet p
    		do
    		{
    			if (open.empty())
    				return;
    
    			p = open.top();
    			open.pop();
    		} while (close[p - 1] == true);
    
    		// in ra dinh dang xet
    		printf("%d ", p);
    
    		// p da duyet qua
    		close[p - 1] = true;
    
    		// ket thuc duyet khi tim ra ket qua can tim		
    		if (p == g)
    			return;
    		
    		// tim dinh ke voi dinh dang xet, dinh nao chua duoc duyet dua vao open
    		for (i = 1; i <= n; i++)
    		{
    			if (isConnected(p, i) && !close[i - 1])
    			{
    				open.push(i);
    			}
    		}
    	}
    	printf("\n");
    
    	delete[] close;
    }

    Ví dụ

    Tôi có một đồ thị như hình vẽ.

    Tôi khởi tạo một đồ thị có 8 đỉnh và có cạnh nối các đỉnh kề như hình vẽ.

    void main()
    {
       // khoi tao do thi
    	Graph g(8);
    
    	// tao canh noi giua cac dinh ke
    	g.addEdge(1, 2);
    	g.addEdge(1, 3);
    	g.addEdge(1, 4);
    	g.addEdge(1, 5);
    	g.addEdge(2, 6);
    	g.addEdge(3, 4);
    	g.addEdge(3, 8);
    	g.addEdge(4, 8); 
    	g.addEdge(5, 8);
    	g.addEdge(6, 7); 
    	g.addEdge(6, 8);
    }

    Tôi chọn đỉnh gốc để duyệt là đỉnh 1 và cần tìm đỉnh 4, tôi thực hiện duyệt ngay sau khi tạo cạnh nối giữa các đỉnh kề.

    void main()
    {
       // khoi tao do thi
    	Graph g(8);
    
    	// tao canh noi giua cac dinh ke
    	g.addEdge(1, 2);
    	g.addEdge(1, 3);
    	g.addEdge(1, 4);
    	g.addEdge(1, 5);
    	g.addEdge(2, 6);
    	g.addEdge(3, 4);
    	g.addEdge(3, 8);
    	g.addEdge(4, 8); 
    	g.addEdge(5, 8);
    	g.addEdge(6, 7); 
    	g.addEdge(6, 8);
    
        // duyet bang Depth First Search
    	g.depthFirstSearch(1, 4);
    }

    Bảng bên dưới thể hiện quá trình duyệt từ đỉnh 1 đến đỉnh 4.

    Đỉnh đang xét Các đỉnh kề Open Close
        {1} {}
    1 {2; 3; 4; 5} {5; 4; 3; 2} {1}
    5 {1; 8} {8; 4; 3; 2} {1; 5}
    8 {3; 4; 5; 6} {6; 4; 3; 4; 3; 2} {1; 5; 8}
    6 {2; 7; 8} {7; 2; 4; 3; 4; 3; 2} {1; 5; 8; 6}
    7 {6} {2; 4; 3; 4; 3; 2} {1; 5; 8; 6; 7}
    2 {1; 6} {4; 3; 4; 3; 2} {1; 5 ;8 ;6; 7; 2}
    4 {1; 3; 8} {3; 4; 3; 3; 2} {1; 5; 8; 6; 7; 2; 4}

    Nhận xét

    Ưu điểm

    • Xét duyệt tất cả các đỉnhđể trả về kết quả.
    • Nếu số đỉnh là hữu hạn, thuật toán chắc chắn tìm ra kết quả.

    Khuyết điểm

    • Mang tính chất vét cạn, không nên áp dụng nếu duyệt số đỉnh quá lớn.
    • Mang tính chất mù quáng, duyệt tất cả đỉnh, không chú ý đến thông tin trong các đỉnh để duyệt hiệu quả, dẫn đến duyệt qua các đỉnh không cần thiết.

    Download mã nguồn

    Để tiện lợi, bạn có thể download mã nguồn của giải thuật này tại đây.

    Bài viết liên quan

    Thuật toán Breadth First Search

    Thuật toán Breadth First Search (Tìm kiếm theo chiều rộng) cùng với Thuật toán Depth First Search là một trong hai thuật toán tìm kiếm cơ bản trong bộ môn Trí tuệ nhân ...

    Trần Minh Thắng19/09/2015

    Thuật Toán Quick Sort

    Quick Sort (đôi khi được gọi là partition-exchange sort hiểu đại khái là sắp xếp phân vùng và chuyển đổi) là một thuật toán sắp xếp tương đối hiệu quả, phục vụ dựa trên ...

    Trung Nguyễn24/09/2014

    Linear Search - Tìm Kiếm Tuyến Tính

    Tìm kiếm là một nhu cầu thiết yếu trong cuộc sống, và đương nhiên, cũng không phải là ngoại lệ trong lập trình. Tôi sẽ bắt đầu với thuật toán tìm kiếm đơn giản nhất: ...

    Trương Diễm Hương15/08/2015

    Thuật Toán PID Trong Điều Khiển Tự Động

    Đây là thuật toán được sử dụng phổ biến để tự động điều chỉnh, giúp động cơ luôn hoạt động ở giá trị cân bằng và ít độ lỗi nhất. Bài viết nhằm giúp độc giả nắm được thuật ...

    Kim Uyên03/06/2016

    Thuật Toán Vẽ Đường Thẳng DDA - Digital Differential Analyzer

    Thuật toán DDA - Digital Differential Analyzer được dùng để xác định các điểm ảnh được vẽ của đường thẳng trên màn hình. Bài viết giới thiệu về thuật toán DDA, một thuật ...

    Vũ Trọng Quang01/06/2017

    Thuật Toán Vẽ Đường Thẳng Bresenham

    Với thuật toán Bresenham, ta có thể xác định được điểm cần tìm dựa vào khoảng cách giữa đường thẳng thực tế với các điểm nằm trong vùng lựa chọn. Bài viết giới thiệu bạn ...

    Amy Lê15/07/2015

    Thuật Toán Midpoint Vẽ Đường Tròn

    Nếu bạn đã sử dụng hàm circle trong thư viện graphics.h hay DrawEllipse để vẽ đường tròn, có bao giờ bạn hỏi là bên dưới những hàm đó được hiện thực như thế nào, sữ dụng ...

    Nguyễn Nghĩa10/10/2015

    Heap Sort - Thuật Toán Sắp Xếp Vun Đống

    Với độ phức tạp trong trường hợp xấu nhất bằng O (n log n), giải thuật sắp xếp vung đống Heapsort vẫn thường được sử dụng do có tốc độ chạy nhanh và không quá phức tạp. ...

    Nguyễn Hoàng Vinh04/09/2017

    Giải Thuật Cắt Tỉa Alpha-beta

    Giải thuật cắt tỉa Alpha-beta cực kỳ quan trọng khi lập trình các trò chơi như cờ vua hay cờ tướng, khi các không gian trạng thái của những trò chơi này có độ phức tạp ...

    Vũ Trọng Quang03/06/2017

    Tìm Hiểu Về Thuật Toán

    ­­­­Thuật toán là một tập hợp hữu hạn các thao tác được thực hiện liên tục nhằm đạt được một mục đích xác định trước. Trong bài viết này, tôi sẽ trình bày lại những hiểu ...

    @ TOMBSTONE25/08/2015

    STDIO
    Trang chính
    Công ty TNHH STDIO

    30, Trịnh Đình Thảo, Hòa Thạnh, Tân Phú, Hồ Chí Minh
    +84 28.36205514 - +84 942.111912
    [email protected]

    383/1 Quang Trung, Phường 10, Quận Gò Vấp, Hồ Chí Minh
    Số giấy phép ĐKKD: 0311563559 do sở Kế hoạch và Đầu Tư TPHCM cấp ngày 23/02/2012

    ©STDIO, 2013 - 2020