Thuật toán Yen: Tìm kiếm K đường đi tốt nhất trong mạng

(Bài dịch, nguồn http://en.wikipedia.org/wiki/Yen%27s_algorithm)

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. Thuật toán lấy nền tản 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.

Một số ký hiệu được sử dụng trong thuật toán:

• ·        N: Tổng số node của đồ thị.
• ·        Ith: node thứ I của đồ thị, theo đó i1 là node xuất phát và in là node đích.
• ·        Dij: là khoảng cách từ i->j với I != j và dij > 0.
• ·        Ak: là cách đi tốt nhất thứ k.
• ·        Ak-I: là cách đi tốt nhất có thể bắt đầu từ node thứ I của A(k-1) và có cách đi khác với A(k -1).
• ·        Rk-I: là cách di chuyển từ node-1 đến node-I của Ak giống với Ak-1 và bắt đầu khác nhau từ I + 1.
• ·        Sk-I: là cách di chuyển từ node-I đến node-n của Ak. Với i->i+1 khác với Ak-1.
• ·        Qk-i: là số bước đi của Ak nếu Ak = Rk-I + Sk-i.

Để 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ả thực hiện thuật toán Yen.

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

   // Tính toán đường đi ngắn nhất đầu tiên nhờ vào thuật toán Dijkstra. Từ node bắt đầu đến node đích.

   A[0] = Dijkstra(Graph, source, sink);

   // Khởi tạo tập hợp B lưu trữ những đường đi có khả năng trở thành K đường đi ngắn nhất.

   B = [];

  

   for k from 1 to K:

       // Giả định node-I thỏa mãn Ak-I = Rk-I + Sk-I, với node-I thuộc Ak-1

       for i from 0 to size(A[k − 1]) − 1:

          

           // Xác định node-I trung gian là node bắt đầu để tính Sk-i

           spurNode = A[k-1].node(i);

           // Xác định Rk-I là đường đi từ node-1 đến node-I bằng cách đi Ak-1

           rootPath = A[k-1].nodes(0, i);

          

           for each path p in A:

               if rootPath == p.nodes(0, i):

                   // Xác định cạnh i->i+1 trong cách đi Ak-1 là cờ cấm, từ đó cho phép xây dựng Ak = Rk-1 + Sk-1 khác với Ak-1

                   remove p.edge(i, i + 1) from Graph;

          

           for each node rootPathNode in rootPath except spurNode:

               remove rootPathNode from Graph;

          

           // Tính toán Sk-I với điểm bắt đầu là I và điểm kết thúc là node-n bằng thuật toán Dijkstra.

           spurPath = Dijkstra(Graph, spurNode, sink);

          

           // Kết quả đường đi với node-I trung gian được tính từ kết quả Rk-I + Sk-i

           totalPath = rootPath + spurPath;

           // Lưu kết quả đường đi thành một kết quả có khả năng trở thành một đường đi ngắng nhất.

           B.append(totalPath);

          

           // Trả về các cạnh đã bị đánh dấu cấm.

           restore edges to Graph;

           restore nodes in rootPath to Graph;

                  

       if B is empty:

           // Nếu tập hợp B là rỗng, xác định thuật toán kết thúc, không thể tìm đủ k đường đi.

           break;

       // Sắp xếp tập hợp B theo giá trị độ dài những đường đi khả dĩ tăng dần.

       B.sort();

       // Lưu giá trị của đường đi thứ k bằng đường đi ngắn nhất có trong B.

       A[k] = B[0];

       // Loại kết quả Ak ra khỏi B.

       B.pop();

  

   return A;

 

Thực hiện thuật toán Yen với Pgrouting – hàm Ksp.

 

·        sql:      câu lệnh truy vấn dữ liệu với dữ liệu trả về là danh sách cạnh của đồ thị có định dạng như sau:

SELECT id, source, target, cost, [,reverse_cost] FROM edge_table

o   id: mã xác định duy nhất node.

o   source: đỉnh bắt đầu của 1 cạnh.

o   target: đỉnh kết thúc của 1 cạnh.

o   cost: trọng số của cạnh.

o   reverse_cost: trọng số của cạnh nếu cạnh được đi từ target đến source.

·        source: Node bắt đầu của đường đi cần tìm kiếm.

·        target: Node kết thúc của đường đi cần tìm kiếm.

·        paths: Số k-input xác định số lượng đường đi cần tìm.

·        has_rcost: True nếu là đồ thị có hướng.

Kết quả trả về là kiểu dữ liệu  pgr_costResult[]:

·        seq:     Thứ tự node của đường đi thứ k.

·        id1:     Thứ tự đường đi thứ k.

·        id2:     Mã xác định node.

·        id3:     Mã xác định cạnh.

·        cost:    Chiều dài đoạn đường qua id2.