Bài toán tìm đường đi ngắn nhất trong nhà kho năm 2024

Bài toán tìm k đường đi ngắn nhất là một bài toán khá quan trọng, ở đây mình sẽ giới thiệu thuật toán Yen để giải quyết bài toán này.

Giới thiệu

Thuật toán Yen, là thuật toán tìm kiếm K đường đi ngắn nhất không lặp lại của đồ thị không tồn tại cạnh có trọng số âm. Thuật toán được phát minh bởi nhà khoa học Jin Y. Yen vào năm 1971.

Ý tưởng

Thuật toán lấy nền tảng từ đường đi ngắn nhất được tìm ra từ bất kỳ thuật toán tìm kiếm đường đi ngắn nhất, từ đó tìm kiếm K – 1 đường đi còn lại với độ lệch thấp nhất so với đường đi ngắn nhất được tìm thấy.

Thuật toán được chia thành 2 quá trình thực hiện. Trước tiên thuật toán sẽ sử dụng bất kỳ giải thuật tìm kiếm đường đi ngắn nhất để tìm ra đường đi ngắn nhất đầu tiên (A1), sau đó thuật toán sẽ căn cứ vào kết quả đường đi ngắn nhất A1 để chọn tiếp tục K – 1 (A2…Ak) kết quả còn lại. Thuật toán sử dụng tập hợp A lưu trữ kết quả K đường đi ngắn nhất, tập hợp B để lưu trữ những kết quả có khả năng trở thành một trong những đường đi ngắn nhất thuộc tập hợp A.

Để tìm lời giải cho đường đi Ak, thuật toán giả định ta đã tìm thấy K – 1 đường đi trước đó. Quá trình được thực hiện gồm 2 giai đoạn: giai đoạn 1, tìm kiếm tất cả cách đi có thể Ak-I. Giai đoạn 2, lựa chọn kết quả tốt nhất trở thành Ak, trong đó I từ 1 đến Qk-k. Giai đoạn một của quá trình tìm kiếm Ak được chia thành 3 bước cụ thể như sau:

• Chọn Rk-I từ Ak trong đó Rk-I chính là đường đi từ node-1 đến node-I trong đường đi A(k-1). Nếu Rk-I được tìm thấy, cạnh i->i+1 sẽ được đánh dấu không thể đi qua.
• Từ node-I đã được tìm thấy, thực hiện thuật toán đường đi ngắn nhất để xác định Sk-I (với cạnh i->i+1 đã được đánh dấu xóa khỏi đồ thị để đảm bảo rằng đường đi Ak-I = Rk-I + Sk-I chưa từng tồn tại trước đó trong A và B).
• Nếu tìm thấy Sk-I lưu trữ kết quả Rk-I + Sk-I vào B. Trả lại giá trị ban đầu của i->i+1, quay lại bước 1. Đến khi I = K -1 thì dừng lại.

Giai đoạn hai của quá trình tìm kiếm Ak. Lựa chọn kết quả tốt nhất hiện có của B và chuyển kết quả trở thành Ak, nếu K đã đạt được K-input ban đầu thì thuật toán kết thúc. Hoặc B rỗng thì thuật toán kết thúc do không thể tìm đủ K kết quả như mong muốn.

Mã giải

function YenKSP(Graph, source, sink, K):

_// Determine the shortest path from the source to the sink._
A[0] = Dijkstra(Graph, source, sink);
_// Initialize the set to store the potential kth shortest path._
B = [];
**for** k **from** 1 **to** K:
    _// The spur node ranges from the first node to the next to last node in the previous k-shortest path._
    **for** i **from** 0 **to** size(A[k − 1]) − 2:
        _// Spur node is retrieved from the previous k-shortest path, k − 1._
        spurNode = A[k-1].node(i);
        _// The sequence of nodes from the source to the spur node of the previous k-shortest path._
        rootPath = A[k-1].nodes(0, i);
        **for each** path p **in** A:
            **if** rootPath == p.nodes(0, i):
                _// Remove the links that are part of the previous shortest paths which share the same root path._
                remove p.edge(i,i + 1) **from** Graph;
        **for each** node rootPathNode **in** rootPath except spurNode:
            remove rootPathNode **from** Graph;
        _// Calculate the spur path from the spur node to the sink._
        _// Consider also checking if any spurPath found_
        spurPath = Dijkstra(Graph, spurNode, sink);
        _// Entire path is made up of the root path and spur path._
        totalPath = rootPath + spurPath;
        _// Add the potential k-shortest path to the heap._
        **if** (totalPath not in B):
            B.append(totalPath);
        _// Add back the edges and nodes that were removed from the graph._
        restore edges **to** Graph;
        restore nodes in rootPath **to** Graph;
    **if** B is empty:
        _// This handles the case of there being no spur paths, or no spur paths left._
        _// This could happen if the spur paths have already been exhausted (added to A),_ 
        _// or there are no spur paths at all - such as when both the source and sink vertices_ 
        _// lie along a "dead end"._
        break;
    _// Sort the potential k-shortest paths by cost._
    B.sort();
    _// Add the lowest cost path becomes the k-shortest path._
    A[k] = B[0];
    _// In fact we should rather use shift since we are removing the first element_
    B.pop();
**return** A;

Ở đây, mình sử dụng thuật toán Yen cho một nút giao thông thực tế với 5011 điểm giao để tìm 10 đường đi ngắn nhất thì mất tầm hơn 2,6 giây. Đây là một kết quả có thể chấp nhận được.