Giới thiệu thuật toán tìm đường đi ngắn nhất trong mê cung

Hôm nay mình sẽ giới thiệu cho các bạn một cách để giúp chiếc xe dò đường trong mê cung của bạn trở nên "thông minh" hơn bằng cách tìm ra được đường đi ngắn nhất sau khi thoát khỏi mê cung ở lần chạy đầu tiên.

1. Mở đầu

Thông thường để giúp xe dò được đường trong mê cung, ta có nhiều thuật toán khác khau. Phổ biến và đơn giản nhất có lẽ là thuật toán tìm đường ngẫu nhiên và thuật toán bám tường. Với thuật toán tìm đường ngẫu nhiên, xe bạn sẽ mò mẫm trong mê cung theo kiểu "hên xui", may mắn thì sẽ tìm ra nhanh, còn không thì có thể đến "sáng mai" vẫn chưa ra nổi. Còn thuật toán bám tường có thể hiểu như sau:

Đặt tay phải hoặc trái lên tường và bắt đầu di chuyển sao cho tay luôn luôn chạm vào một bên tường. Với cách này, sau một lúc di chuyển, bạn cũng sẽ đến được đích. Một cách khác để diễn giải thuật toán này, đó là việc ưu tiên rẽ ở chỉ một phía. Ví dụ như ưu tiên phải, tại mỗi điểm rẽ, xe sẽ luôn luôn rẽ phải trước, nếu bên phải không có đường thì đi thẳng, nếu phía trước không có đường nữa thì mới rẽ trái. Như thế tay bạn sẽ luôn luôn chạm vào tường bên phải.

Các phương pháp kể trên có một nhược điểm, đó là quãng đường thu được sau khi đến đích thường  rất dài do trước đó gặp phải khá nhiều ngõ cụt (mà thực ra đi kiểu gì cũng vậy thôi, vì chúng ta đâu có biết trước mê cung để một phát đến được đích ngay ). Thế nên sau khi có được đường đi, ta cần phải tối ưu nó để ra được cách di chuyển ngắn nhất.

Và cách hôm nay mình giới thiệu là một phương pháp đơn giản giúp các bạn thực hiện được điều đó. 

2. Mô tả thuật toán

Trước tiên, để thực hiện được thuật toán, xe dò đường của bạn tất nhiên phải có chức năng ghi lại những hướng đã đi tại các điểm rẽ. Những hướng đó được lấy theo hê tọa độ cố định gắn với mê cung (ví dụ như lên, xuống, trái, phải). Ta lưu lại những hướng này vào một chuỗi để tiến hành rút gọn.

Nguyên tắc của thuật toán này là khử dần những đường đi ngược nhau, lặp lại liên tục, cho đến khi nào không thể rút gọn được nữa, thì đó sẽ là đường đi ngắn nhất. Trong chuỗi đã lưu sẽ có những cặp ký tự chỉ hướng ngược nhau và đứng liền nhau, ta sẽ nhận biết được đó là ngõ cụt. Để bỏ qua ngõ cụt đó, ta chỉ cần xóa chúng đi là xong.

Ví dụ 1: Cùng xem qua một ví dụ và ta sẽ rút gọn nó.

Quy ước viết tắt hướng đi:

Như vậy bắt đầu từ 1 ta có:

• 1: U
• 2: L
• 3: R
• 4: D

=> ULRD

Ta nhận thấy những hướng ngược chiều nhau và đứng cạnh nhau là ngõ cụt (ở trên là L,R). Do đó ta có thể bỏ đi.

ULRD => UD

Chỉ còn lại UD. UD lại tiếp tục ngược nhau, ta lại rút gọn thêm một lần nữa...

...và chuỗi ULRD đã không còn, do đó xe sẽ bỏ qua đường này. 

Ví dụ 2: Ví dụ tiếp theo với một đường đi thẳng và đường rẽ ngang.

Ta có chuỗi: LULRDL. Bắt đầu rút gọn:

LULRDL => LUDL => LL

Như vậy, ban đầu xe đi về phía bên trái tại số 1. Đến ngã rẽ, xe sẽ bỏ qua để tiếp tục đi về phía trái. Như thế ta đã rút gọn bớt được một ngõ cụt.

Ví dụ 3: Đây sẽ là một mê cung hoàn chỉnh đơn giản. Nếu bạn hiểu rồi thì hãy thử tự giải và rút gọn trước khi xem đáp án.

Giả sử xe dò đường của chúng ta sử dụng thuật toán bám tường phải. Sau một hồi mò mẫm ta có đường đi như hình, tại mỗi điểm rẽ ta đều ghi lại hướng tiếp theo sẽ di chuyển. Chuỗi đường đi sẽ như sau: URDD URRL URDU LLUR DURD (mình viết cách ra cho dễ nhìn thôi nhé, thực tế chuỗi được ghi liền)

Tiến hành khử các cặp UD, DU, LR, RL cạnh nhau, cho đến khi không còn nữa thì thôi.

URDD URRL URDU LLUR DURD => URDRRLURLLURRD => URDRULURRD

Hãy thử dùng kết quả và dò trên hình, bạn sẽ thấy con đường tới đích đã ngắn hơn rất nhiều.

Vấn đề còn lại cho bạn tự giải quyết, đó là làm thế nào để ghi lại hướng đi tại từng điểm rẽ theo hệ tọa độ gắn với mê cung, làm thế nào để triển khai thuật toán trên dưới dạng code C++ nhằm rút gọn chuỗi đường đi, và cuối cùng để xe tự di chuyển theo lộ trình của chuỗi đã rút gọn.

Trên đây là toàn bộ mô tả về thuật toán tìm đường đi ngắn nhất trong mê cung của mình. Hy vọng với ý tưởng này, các bạn có thể triển khai thành công vào việc chế tạo xe dò đường. Nếu có thời gian, mình sẽ viết tiếp cách để có thể triển khai thuật toán này dưới dạng code C++, giúp thuận tiện hơn cho các bạn khi lập trình cho xe.

===================================

Bổ sung code của thành viên Minh Nghia Pham

#include <iostream>
#include <stdio.h>
#include <conio.h>
#include <cstring>
using namespace std;

int Search_street(char x[], int a[], int size1)
{
    // quy chuoi ra man tran
    for (int i = 0; i < size1; i++) {
        if (x[i] == 'L')
            a[i] = 3;
        else if (x[i] == 'R')
            a[i] = 2;
        else if (x[i] == 'D')
            a[i] = 10;
        else if (x[i] == 'U')
            a[i] = 1;
        // cout << a[i] << endl;
    }
    int i = 0;
    while (i < size1) {
        int size_current = size1;
        if (a[i] * a[i + 1] == 10 || a[i] * a[i + 1] == 6) { // co su rut gon
            if (a[i + 2] == size1)
                a[i] = a[i + 2];
            else {
                for (int j = i; j < size1 - 2; j++) {
                    a[j] = a[j + 2];
                }
            }
            // XOA PHAN TU CU THUA
            for (int j = size1 - 2; j < size1; j++) {
                a[j] = 0;
            }
            size1 = size1 - 2;
        }
        // neu k cos su rut gon thi tag i;
        if (size_current == size1)
            i++;
    }
    // doc nguoc tu mang a de ra mang x
    for (int j = 0; j < size1; j++) {
        if (a[j] == 1)
            x[j] = 'U';
        else if (a[j] == 10)
            x[j] = 'D';
        else if (a[j] == 3)
            x[j] = 'L';
        else if (a[j] == 2)
            x[j] = 'R';
    }
    x[size1] = '\0';
    cout << " duong di ngan nhat " << x << endl;
    return 0;
}

int main()
{
    int H[30];
    char Street[30];
    cout << " U la len, D la xuong, L la re trai, R la re phai " << endl;
    cout << " hay nhap duong di thu thap dc " << endl;
    fflush(stdin);
    gets(Street);
    Search_street(Street, H, strlen(Street));
    return 0;
}
// CODE BLOCK, GUUGC , ĐÃ TEST OKIE