Thuật toán tìm kiếm đồ thị

Question

Tôi đang tìm thuật toán đồ thị với một số thuộc tính bất thường.

Mỗi cạnh trong biểu đồ là cạnh "lên" hoặc cạnh "xuống".

Đường dẫn hợp lệ có thể đi một số lượng không giới hạn "lên", theo sau là số lượng "không xác định" hoặc ngược lại. Tuy nhiên nó không thể thay đổi hướng nhiều hơn một lần.

Ví dụ, một đường dẫn hợp lệ có thể là A "lên" B "lên" C "xuống" E "xuống" F một con đường không hợp lệ có thể là A "lên" B "xuống" C "lên" D

Thuật toán tốt để tìm đường đi hợp lệ ngắn nhất giữa hai nút là gì? Điều gì về việc tìm kiếm tất cả các đường đi ngắn nhất bằng nhau?

Answer 1

Giả sử bạn không có bất kỳ phỏng đoán nào, biến thể của dijkstra's algorithm sẽ đủ tốt. Mỗi khi bạn xem xét một cạnh mới, lưu trữ thông tin về "tổ tiên" của nó. Sau đó, kiểm tra sự bất biến (chỉ có một thay đổi hướng) và quay lại nếu nó bị vi phạm.

Tổ tiên ở đây là tất cả các cạnh được di chuyển đến nút hiện tại, dọc theo đường đi ngắn nhất. Một cách tốt để lưu trữ thông tin tổ tiên sẽ là một cặp số. Nếu U tăng, và D giảm, tổ tiên của một cạnh cụ thể có thể là UUUDDDD, đó sẽ là cặp 3, 4. Bạn sẽ không cần số thứ ba, vì bất biến.

Vì chúng tôi đã sử dụng thuật toán của dijkstra, việc tìm kiếm nhiều đường đi ngắn nhất đã được thực hiện.

Answer 2

Có thể bạn có thể biến biểu đồ thành đồ thị được chỉ dẫn bình thường và sau đó sử dụng các thuật toán hiện có.

Một cách là chia biểu đồ thành hai biểu đồ, một với tất cả các cạnh lên và một với tất cả các cạnh xuống và với các cạnh được chỉ đạo giữa tất cả các nút trên biểu đồ một và nút tương ứng trên biểu đồ hai.

Giải quyết đầu tiên để bắt đầu trong biểu đồ một và kết thúc trong biểu đồ hai và sau đó theo cách khác, sau đó kiểm tra giải pháp ngắn nhất.

Answer 3

Người ta nghĩ tiêu chuẩn BFS của bạn sẽ hoạt động ở đây. Bất cứ khi nào bạn thêm một nút vào danh sách mở, bạn có thể bọc nó vào một cấu trúc giữ hướng mà nó đang sử dụng (lên hoặc xuống) và cờ boolean cho biết liệu nó đã chuyển hướng chưa. Đây có thể được sử dụng để xác định các cạnh đi từ nút đó là hợp lệ.

Để tìm tất cả các đường đi ngắn nhất có chiều dài bằng nhau, hãy bao gồm số cạnh được di chuyển đến nay trong cấu trúc của bạn. Khi bạn tìm thấy con đường ngắn nhất đầu tiên của mình, hãy ghi lại chiều dài đường dẫn và dừng thêm nút vào danh sách mở. Tiếp tục đi qua các nút còn lại trong danh sách cho đến khi bạn đã kiểm tra tất cả các đường dẫn của độ dài hiện tại, sau đó dừng lại.

Answer 4

A* với chi phí được thiết kế đặc biệt (điểm G) và hàm heuristic (H score) có thể xử lý.

Với chi phí bạn có thể theo dõi số lần thay đổi hướng trong đường dẫn và thêm chi phí vô hạn vào thay đổi thứ hai (ví dụ: cắt tìm kiếm các chi nhánh đó).

Các heuristic mất một số suy nghĩ nhiều hơn, đặc biệt là khi bạn muốn giữ cho heuristic chấp nhận được (không bao giờ đánh giá cao tối thiểu khoảng cách đến mục tiêu) và đơn điệu. (Chỉ có cách để đảm bảo A * tìm ra giải pháp tối ưu.)

Có thể có thêm thông tin về tên miền có sẵn để tạo heuristic? (tức là tọa độ x, y của các nút trong biểu đồ?)

Tất nhiên, tùy thuộc vào kích thước của đồ thị bạn muốn giải quyết, trước tiên bạn có thể thử các thuật toán đơn giản như tìm kiếm đầu tiên hoặc thuật toán Dijkstra. thuật toán tìm kiếm sẽ thực hiện, và đối với mọi thuật toán, bạn sẽ cần một hàm chi phí (hoặc tương tự).

Answer 5

Nếu bạn có một chức năng tìm kiếm đồ thị dưới tiêu chuẩn, nói Graph.shortest(from, to) trong thư viện, bạn có thể lặp và giảm thiểu, trong C#/giả:

[ (fst.shortest(A, C) + nxt.shortest(C, B)) 
    for C in nodes , (fst, nxt) in [(up, down), (down, up)] ].reduce(min) 

Nếu bạn cần phải nhớ những con đường/đường dẫn tối thiểu và nó để xảy ra rằng chức năng tiêu chuẩn của bạn trả về cho bạn những dữ liệu, bạn cũng có thể phát âm

[ [fst, nxt, C, fst.shortest(A, C), nxt.shortest(C,B)] 
    for C in nodes , (fst, nxt) in [(up, down), (down, up)] ].reduce(myMin) 

nơi myMin nên so sánh hai [fst, nxt, C, AC, BD] tuples và để lại một trong đó có khoảng cách thấp hơn, hoặc cả hai và giả định reduce là một chức năng thông minh.

Điều này có một số chi phí bộ nhớ nếu đồ thị của chúng tôi lớn và không sử dụng bộ nhớ nào cả (có thể nếu chúng được tạo động), nhưng không thực sự là bất kỳ chi phí tốc độ nào, imho.