Giải thuật Leo đồi

1. Kỹ thuật tìm kiếm leo đồi
Tìm kiếm leo đồi là tìm kiếm theo độ sâu được hướng dẫn bởi hàm đánh giá. Song khác với tìm kiếm theo độ sâu, khi phát triển một đỉnh u thì bước tiếp theo ta chọn trong số các đỉnh con của u, đỉnh có hứa hẹn nhiều nhất để phát triển, đỉnh này được xác định bởi hàm đánh giá.
2. Giải thuật
Input:
    Đồ thị G = (V,E), đỉnh xuất phát n0.
    Hàm đánh giá h(n) đối với mỗi đỉnh n.
    Tập đỉnh đích DICH
Output:
    Đường đi từ đỉnh n0 đến DICH

            bool result = false;
            openList.Push(n0);
            while (!openList.IsEmpty())
            {
                node = openList.Pop();
                if (node.Equals(n*))
                {
                    result = true;
                    break;
                }

                closeList.Push(node);
                Stack list = new Stack();
                for (n in Tn(node))
                {
                    if (!openList.InList(n) && !closeList.InList(n))
                    {
                        n.Cost = node.Cost + Edge(node, n).Value + n.Huerictis;
                        BeforeOfNode(n, node);
                        list.Push(n);
                    }
                }
                list.Sort(SortType.DESCENDING);//sắp xếp các đỉnh phát triển tiếp theo theo thứ tự hàm đánh giá
                while (!list.IsEmpty())
                {
                    openList.Push(list.Pop());//chuyển các đỉnh tiếp theo vào danh sách OPEN theo thứ tự hàm đánh giá
                }
            }
            if (result)
            {
                DisplayResult();
            }
            else
            {
                NotFound();
            }

3. Ví dụ

Cho đồ thị như hình vẽ

Với giá trị Hueristic của mỗi đỉnh như sau

H(1) = 1  H(2) = 3  H(3) = 5   H(4) = 6  H(5) = 4
H(6) = 1  H(7) = 2  H(8) = 3   H(9) = 1  H(10) = 6

Đỉnh xuất phát là (1), đỉnh đích là (10)

Các bước chi tiết thực hiện giải thuật

Kết quả 

Chi phí 24




Mã nguồn tham khảo tại đây 

Giải thuật A* - Tìm kiếm cực tiểu

1. Tìm kiếm cực tiểu sử dụng hàm đánh giá - Thuật toán A*

Đối với nhiều bài toán, việc tìm kiếm đường đi cực tiểu sẽ được định hướng tập trung xung quanh  đường đi tốt nhất; nếu sử dụng các thông tin đặc tả về bài toán gọi là các heuristic.
Đối với việc tìm kiếm đường đi với chi phí cực tiểu, người ta sử dụng hàm đánh giá heuristic như sau:
    Gọi g(n): giá cực tiểu đường đi từ n0->n. Tại đỉnh n, g(n) xác định được.
    Gọi h(n): giá cực tiểu đường đi từ n->DICH, h(n) không xác định được Þ người ta tìm cách ước lượng giá trị này.
    Đặt f0(n)=g0(n)+h0(n): dự đoán chi phí cực tiểu của đường đi từ n0->DICH có đi qua đỉnh n.
    g0(n) là chi phí của đường đi từ đỉnh xuất phát đến đỉnh n tại thời điểm đang xét. h0(n) là ước lưọng (dự đoán) chi phí đường đi từ đỉnh n đến đích. Việc chọn giá trị xấp xỉ h0(n) của h(n) không có một phương pháp tổng quát và được xem như một nghệ thuật. Giá trị này sẽ do các chuyên gia đưa ra.
Lúc này giải thuật tìm kiếm cực tiểu sẽ thay việc xét hàm g bởi hàm f.
2. Giải thuật
Input:
    Đồ thị G = (V,E), Đỉnh xuất phát n0
    Hàm chi phí c: c(i,j): xác định chi phí chuyển từ đỉnh i sang đỉnh j
    h: h(n) xác định dự đoán chi phí tối ưu của đường đi từ đỉnh n đến đích.
Tập các đỉnh đích DICH
Output:
Đường đi từ đỉnh n0 đến đỉnh n* thuộc DICH với giá thành cực tiểu


            bool result = false;
            openList.Push(n0);
            while (!openList.IsEmpty())
            {
                node = openList.Pop();
                if (node.Equals(n*))
                {
                    result = true;
                    break;
                }

                closeList.Push(node);
                for (n in Tn(node))
                {
                    if (!openList.InList(n) && !closeList.InList(n))
                    {
                        openList.Push(n);
                        n.Cost = node.Cost + Edge(node, n).Value + n.Huerictis;
                        BeforeOfNode(n, node);
                    }
                    else if (!closeList.InList(n) && n.Cost > node.Cost + Edge(node, n).Value + n.Huerictis)
                    {
                        n.Cost = node.Cost + Edge(node, n).Value + n.Huerictis;
                        BeforeOfNode(n, node);
                    }
                }
                openList.Sort(SortType.ASCENDING);//sắp xếp theo chi phí của mỗi đỉnh, giá trị Min ở đỉnh Stack
            }

            if (result)
            {
                DisplayResult();
            }
            else
            {
                NotFound();
            }

3. Ví dụ

Cho đồ thị như hình vẽ

Với giá trị Hueristic của mỗi đỉnh như sau

H(1) = 1  H(2) = 3  H(3) = 5   H(4) = 6  H(5) = 4
H(6) = 1  H(7) = 2  H(8) = 3   H(9) = 1  H(10) = 6

Đỉnh xuất phát là (1), đỉnh đích là (10)

Các bước chi tiết thực hiện giải thuật

Kết quả

Với chi phí cực tiểu là 18

Mã nguồn tham khảo tại đây 

 

Giải thuật AT - giá thành cực tiểu

1. Tìm kiếm đường đi có giá thành cực tiểu - Thuật toán AT
Cho đồ thị G= (V, E) biểu diễn bài toán với đỉnh xuất phát n0 và tập đích DICH xác định.
Với mỗi phép chuyển trạng thái n(i)->n(i+1) tốn chi phí c(i, i+1), ở đây có thể xem là trọng số của cung nối n(i) và n(i+1)
Phương pháp
Tương tự phương pháp tìm kiếm theo chiều sâu, nhưng tại mỗi biết ta tính giá thành của mỗi đỉnh và chọn đỉnh có giá thành tối ưu nhất
2. Giải thuật
Input:
    Đồ thị G = (V,E), Đỉnh xuất phát n0
    Hàm chi phí c
    Tập các đỉnh đích DICH
Output:
Đường đi từ đỉnh n0 đến đỉnh n* in DICH sao cho g(n*) = MIN

            bool result = false;
            openList.Push(n0);
            while (!openList.IsEmpty())
            {
                node = openList.Pop();
                if (node.Equals(n*))
                {
                    result = true;
                    break;
                }
                closeList.Push(node);
                for (n in Tn(node))
                {
                    if (!openList.InList(n) && !closeList.InList(n))
                    {
                        openList.Push(n);
                        n.Cost = node.Cost + Edge(node, n).Value;
                        BeforeOfNode(n, node);
                    }
                    else if (!closeList.InList(n) && n.Cost > node.Cost + Edge(node, n).Value)
                    {
                        n.Cost = node.Cost + Edge(node, n).Value;
                        BeforeOfNode(n, node);
                    }
                }
                openList.Sort(SortType.ASCENDING);//sắp xếp lại để chọn đỉnh tối ưu nhất ở đỉnh Stack
            }

            if (result)
            {
                DisplayResult();
            }
            else
            {
               NotFound();
            }

3. Ví dụ

Cho đồ thị như hình vẽ

Đỉnh xuất phát là (1), đỉnh đích là (10)

Các bước chi tiết thực hiện giải thuật

 

Kết quả

 

Chi phí là 6

Mã nguồn tham khảo tại đây 

 

Giải thuật tìm kiếm tốt nhất đầu tiên

1. Kỹ thuật tìm kiếm tốt nhất đầu tiên
Kỹ thuật tìm kiếm tốt nhất đầu tiên tìm lời giải có dùng tri thức về bài toán để hướng dẫn. Tri thức này hướng việc tìm kiếm về nút lời giải trong không gian bài toán.
Tại mỗi nút được xem xét, người ta sẽ quyết định việc tìm kiếm tiếp tục theo nhánh nào tin tưởng sẽ dẫn đến lời giải.
Trong các chương trình trí tuệ nhân tạo, kỹ thuật tìm kiếm tốt nhất đầu tiên sử dụng hàm đánh giá. Hàm này dùng các thông tin hiện tại về mức độ quan trọng của bài toán tại nút đó để gán giá trị cho nút này, gọi là trọng số của nút. Giá trị này được xem xét trong lúc tìm kiếm. Thông thường, nút có trọng số nhỏ (lớn) nhất sẽ được chọn trong quá trình tìm kiếm.    

2. Hàm đánh giá               
Trong nhiều vấn đề, ta có thể sử dụng kinh nghiệm, tri thức của chúng ta về vấn đề đó để đánh giá các trạng thái của vấn đề.
Với mỗi trạng thái u, ta sẽ xác dịnh một giá trị số h(u), số này đánh giá “sự gần đích” của trạng thái u. Hàm h(u) được gọi là hàm đánh giá.
Phương pháp tìm kiếm kinh nghiệm là phương pháp tìm kiếm có sử dụng đến hàm đánh giá. Trong quá trình tìm kiếm, tại mỗi bước ta sẽ chọn trạng thái kế tiếp là trạng thái có nhiều hứa hẹn dẫn tới đích nhiều nhất.
Quá trình tìm kiếm trong không gian trạng thái có sử dụng hàm đánh giá bao gồm các bước cơ bản sau:
Biểu diễn thích hợp các trạng thái và các toán tử chuyển trạng thái
Xây dựng hàm đánh giá
Thiết kế chiến lược chọn trạng thái ở mỗi bước

3. Giải thuật

            bool result = false;
            openList.Push(n0);
            while (!openList.IsEmpty())
            {
                node = openList.Pop();
                if (node.Equals(n*))
                {
                    result = true;
                    break;
                }

                closeList.Push(node);
                for (n in Tn(Node))
                {
                    if (!openList.InList(n) && !closeList.InList(n))
                    {
                        n.Cost = n.Huerictis;
                        openList.Push(n);
                        BeforeOfNode(n, node);
                    }
                }
                openList.Sort(SortType.ASCENDING);//sắp xếp theo thứ tự giảm dần theo Cost từ đỉnh Stack
            }

            if (result)
            {
                DisplayResult();
            }
            else
            {
                NotFound();
            }
4. Ví dụ

Cho đồ thị như hình vẽ

Với giá trị Hueristic của mỗi đỉnh như sau

H(1) = 1  H(2) = 3  H(3) = 5   H(4) = 6  H(5) = 4
H(6) = 1  H(7) = 2  H(8) = 3   H(9) = 1  H(10) = 6

Đỉnh xuất phát là (1), đỉnh đích là (10)

Các bước chi tiết thực hiện giải thuật

Kết quả

 

 
 5. Ưu và nhược điểm của phương pháp tìm kiếm tốt nhất đầu tiên
Ưu điểm
- Phương pháp tìm kiếm tốt nhất đầu tiên tổ hợp các ưu điểm của phương pháp tìm kiếm rộng và tìm kiếm sâu.
- Ưu điểm chủ yếu của phương pháp tìm kiếm tốt nhất đầu tiên là dùng tri thức để dẫn dắt việc tìm kiếm. Tri thức này giúp người ta bắt đầu từ đâu là tốt nhất và cách tốt nhất để tiến hành tìm lời giải.
- Tìm kiếm tốt nhất đầu tiên tuân theo cách suy lý của một chuyên gia. Do đó có thể thấy rõ đường đi hơn tìm kiếm rộng và tìm kiếm sâu.
Nhược điểm
- Quá trình tìm kiếm có thể đi xa khỏi lời giải. Kỹ thuật này chỉ xét một phần của không gian và coi đó là phần hứa hẹn hơn cả.

Mã nguồn tham khảo tại đây

Giải thuật tìm kiếm sâu dần

1. Kỹ thuật tìm kiếm sâu dần
Kỹ thuật tìm kiếm sâu dần là thực hiện việc tìm kiếm với độ sâu ở mức giưói hạn d nào đó. Nếu không tìm ra nghiệm ta tăng độ sâu lên d+1 và lại tìm kiếm theo độ sâu tới mức d+1. Quá trình trên được lặp lại với d lần lượt là 1, 2,...đến độ sâu max nào đó. 
Kỹ thuật tìm kiếm sâu dần thường được thực hiện khi cây tìm kiếm chứa nhánh vô hạn, và nếu sử dụng tìm kiếm theo độ sâu ta có thể mắc kẹt ở một nhánh nào đó (thuật toán không dừng) và không tìm ra nghiệm
2. Giải thuật
Thuật toán tìm kiếm sâu dần sử dụng thuật toán tìm kiếm sâu hạn chế như thủ tục con. Đó là thủ tục tìm kiếm theo chiều sâu nhưng chỉ tới độ sâu d nào đó rồi quay lên.

            bool result = false;
            openList.Push(n0);
            deepOfNode(no, 0);//độ sâu của đỉnh xuất phát là 0
            while (!openList.IsEmpty())
            {
                node = openList.Pop();
                if (node.Equals(n*))
                {
                    result = true;
                    break;
                }

                closeList.Push(node);
                int deep = deepOfNode[node];
                if (deep < limitedDeep)
                {
                    for (n in Tn(node))
                    {
                        if (!openList.InList(n) && !closeList.InList(n))
                        {
                            openList.Push(n);
                            BeforeOfNode(n, node);
                            deepOfNode.Add(n, deep + 1);//độ sâu của đỉnh n
                        }
                    }
                }
            }

            if (result)
            {
                DisplayResult();
            }
            else
            {
                NotFound();
            }

3. Ví dụ

Cho đồ thị như hình vẽ

Đỉnh xuất phát là (1), đỉnh đích là (11), độ sâu giới hạn là 3

Các bước chi tiết thực hiện giải thuật

Kết quả

Mã nguồn tham khảo tại đây 

 

Giải thuật tìm kiếm theo chiều sâu

1. Kỹ thuật tìm kiếm sâu 
Tìm kiếm sâu trong không gian bài toán được bắt đầu từ một nút rồi tiếp tục cho đến khi hoặc đến ngõ cụt hoặc đến đích. Tại mỗi nút có luật trong tài, chẳng hạn, “đi theo nút cực trái”, hướng dẫn việc tìm. Nếu không đi tiếp được, gọi là đến ngõ cụt, hệ thống quay lại một mức trên đồ thị và tìm theo hướng khác, chẳng hạn, đến nút “sát nút cực trái”. Hành động này gọi là quay lui.
Thuật toán tìm kiếm theo chiều sâu được hình dung như việc khảo sát một cây bắt đầu từ gốc đi theo mọi cành có thể được, khi gặp cành cụt thì quay lại xét cành chưa đi qua.
- Ở bước tổng quát, giả sử đang xét đỉnh i, khi đó các đỉnh kề với i có các trường hợp:
  + Nếu tồn tại đỉnh j kề i chưa được xét thì xét đỉnh này (nó trở thành đỉnh đã xét) và bắt đầu từ đó tiếp tục quá trình tìm kiếm với đỉnh này..
  + Nếu với mọi đỉnh kề với i đều đã được xét thì i coi như duyệt xong và quay trở lại tìm kiếm từ đỉnh mà từ đó ta đi đến được i.

2. Giải thuật
Input:
Cây/Đồ thị G = (V,E) với đỉnh gốc là n0 (trạng thái đầu)
    Tập đích Goals
Output:
Một đường đi p từ n0 đến một đỉnh n* in Goals
Method:
Sử dụng hai danh sách hoạt động theo nguyên tắc LIFO (Stack)  OPENLIST và CLOSELIST

            openList.Push(n0);
            while (!openList.IsEmpty())
            {
                node = openList.Pop();
                if (node.Equals(n*))
                {
                    result = true;
                    break;
                }

                closeList.Push(node);
                for (n in Tn(Node))
                {
                    if (!openList.InList(n) && !closeList.InList(n))
                    {
                        openList.Push(n);
                BeforeOfNode(n, node);////node trước của n là node trong quá trình tìm đường đến đích
                    }
                }
            }

            if (result)
            {
                DisplayResult();
            }
            else
            {
                NotFound();
            }
3. Ví dụ

Cho đồ thị như hình vẽ

Đỉnh xuất phát là (1), đỉnh đích là (11)

Các bước chi tiết thực hiện giải thuật

 

 Kết quả đường đi là:

4. Ưu và nhược điểm của phương pháp tìm kiếm sâu
Ưu điểm:
- Nếu bài toán có lời giải, phương pháp tìm kiếm sâu bảo đảm tìm ra lời giải.
- Kỹ thuật tìm kiếm sâu tập trung vào đích, con người cảm thấy hài lòng khi các câu hỏi tập trung vào vấn đề chính.
- 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 tìm sâu sẽ tiết kiệm thời gian.
Nhược điểm:
- Tìm sâu khai thác không gian bài toán để tìm lời giải theo thuật toán đơn giản một cách cứng nhắc. Trong quá trình tìm nó không có thông tin nào hổ trợ để phát hiện lời giải. Nếu chọn nút ban đầu không thích hợp có thể không dẫn đến đích của bài toán.
- Không phù hợp với không gian bài toán lớn, kỹ thuật tìm kiếm sâu có thể không đến lời giải trong khoảng thời gian vừa phải.

Mã nguồn tham khảo tại đây 

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

1. Kỹ thuật tìm kiếm rộng
Kỹ thuật tìm kiếm rông là tìm kiếm trên tất cả các nút của một mức trong không gian bài toán trước khi chuyển sang các nút của mức tiếp theo.
Kỹ thuật tìm kiếm rộng bắt đầu từ mức thứ nhất của không gian bài toán, theo hướng dẫn của luật trọng tài, chẳng hạn “đi từ trái sang phải”. Nếu không thấy lời giải tại mức này, nó chuyển xuống mức sau để tiếp tục … đến khi định vị được lời giải nếu có.
 
2. Giải thuật
Input:
Cây/Đồ thị G = (V,E) với đỉnh gốc là n0 (trạng thái đầu)
    Tập đích Goals
Output:
Một đường đi p từ n0 đến một đỉnh n* in Goals
Method:
Để thực hiện giải thuật này ta sử dụng hai danh sách hoạt động theo nguyên tắc FIFO (queue)  OPENLIST và CLOSELIST


            bool result = false;

            openList.Append(n0);


            while (!openList.IsEmpty())
            {
                node = openList.Take();

                if (node.Equals(n*))//là node đích
                {
                    result = true;
                    break;
                }

                closeList.Append(node);
                for (n in Tn(Node))
                {
                    if (!openList.InList(n) && !closeList.InList(n))
                    {
                        openList.Append(n);
                        BeforeOfNode(n, node);//node trước của n là node trong quá trình tìm đường đến đích
                    }
                }
            }

            if (result)
            {
                DisplayResult();
            }
            else
            {
                NotFound();
            }
        }
 
3. Ví dụ


Cho đồ thị như hình vẽ

Đỉnh xuất phát là (1), đỉnh đích là (11)

Các bước chi tiết thực hiện giải thuật

 

Kết quả đường đi là: 

4. Ưu và nhược điểm của phương pháp tìm kiếm rộng
Ưu điểm
- Kỹ thuật tìm kiếm rộng 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ó.
- Đường đi tìm được đi qua ít đỉnh nhất.
Nhược điểm
- Tìm kiếm lời giải theo thuật toán đã định 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ợ cho quá trình tìm kiếm, không nhận ra ngay lời giải.
- Không phù hợp với không gian bài oán kích thước lớn. Đối với loại bài toán này, phương pháp tìm rộng đối mặt với các nhu cầu:
  + 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 các nhánh cây dài, số nút tăng. 
  + Dễ thực hiện các thao tác không thích hợp, thừa, đưa đến việc tăng đáng kể số nút phải xử lý.
- Không hiệu qủa nếu lời giải ở sâu. Phương pháp này không phù hợp cho trường hợp có nhiều đường dẫn đến kết quả nhưng đều sâu.
- 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, việc tìm kiếm không tập trung vào một chủ đề. 

Mã nguồn tham khảo tại đây