Đường dẫn một chiều ngắn nhất thông qua nhiều nút

Question

Tôi có một loạt tọa độ đồ thị và tôi cần tìm đường đi một chiều ngắn nhất thông qua tất cả các nút đó. Tôi không có điểm bắt đầu/kết thúc xác định trước nhưng mỗi điểm chỉ được chạm một lần và trở về nguồn gốc tối ưu là KHÔNG bắt buộc.

Tôi đã thử một vài phương pháp tiếp cận TSP, nhưng tất cả đều dường như dựa trên việc quay trở lại nguồn gốc ở cuối cho kết quả không hiệu quả khủng khiếp trong trường hợp này.

Ví dụ

1, 13
3, 0
3, 7
2, 21
2, 11
3, 12
1, 19
3, 6

sẽ giải quyết thành

3, 0
3, 6
3, 7
3, 12
2, 11
1, 13
1, 19
2, 21

Ghi chú:

Có, tôi đã cố gắng tìm kiếm chức năng, có một câu hỏi cơ bản giống hệt nhau Algorithm: shortest path between all points tuy nhiên câu trả lời thực sự duy nhất là một TSP, mà một lần nữa, mạch kín là không hiệu quả cho việc này.

Nó không cần phải chính xác 100%, tôi đã có một phương pháp hoán vị nhưng quá chậm, tôi cần phải xử lý ít nhất ~ 25-30 điểm, giải quyết với một xấp xỉ tốt làm việc cho tôi

Cảm ơn trước.

Chỉnh sửa để làm rõ, TSP có xu hướng giải quyết như trong img # 1, kết quả mong muốn của tôi là img # 2
img 3 là ví dụ trên được giải quyết thông qua một TSP và img # 4 là mong muốn (x coords chuyển trở lại - .5 cho tầm nhìn)

Couple hơn cho tốt biện pháp # 1 = TSP, # 2 = ý muốn

về cơ bản tôi muốn ngắn nhất chuỗi kết nối n điểm, sử dụng bất kỳ điểm bắt đầu và điểm kết thúc nào là hiệu quả nhất

Answer 1

Đây là trường hợp của all-pairs shortest path problem với tất cả các cạnh có trọng số = 1. Bạn sẽ tìm thấy các giải pháp phổ biến như thuật toán Dijkstra hoặc A-star trên trang được liên kết.
Cách tiếp cận ngây thơ là lặp qua các nút và tìm đường đi ngắn nhất đến mọi nút khác.

$paths = array(); 
foreach ($nodes as $start) { 
    foreach ($nodes as $end) { 
     if ($start !== $end) { 
      $path[$start][$end] = findShortestPath($graph, $start, $end); 
     } 
    } 
} 

Trong một cách tiếp cận phức tạp hơn findShortestPath sẽ nhớ subpath của chạy trước (hoặc sử dụng $paths cho mục đích đó) để đạt được hiệu suất tốt hơn.

Answer 2

Vì bạn không quan tâm đến việc tìm một vòng khép kín - tất cả những gì bạn cần là một đường dẫn duy nhất - bạn có thể thực hiện một sửa đổi nhỏ cho các điểm bạn phải tránh chi phí của vòng khép kín. Để làm điều này, thêm một điểm mới, gọi nó là v, mà bạn xác định là ở khoảng cách 0 từ tất cả các điểm khác. Bây giờ, hãy tìm một giải pháp TSP cho biểu đồ này. Tại một số điểm, bạn sẽ nhập và sau đó rời khỏi v. Nếu bạn lấy chu kỳ và sau đó loại bỏ các cạnh vào và ra khỏi v từ nó, sau đó bạn sẽ có một con đường truy cập mỗi nút chính xác một lần mà không có bất kỳ chu kỳ.

Điều này vẫn yêu cầu bạn giải quyết hoặc xấp xỉ TSP, nhưng nó giúp loại bỏ chi phí khổng lồ khi trở về điểm xuất phát của bạn.

Answer 3

có nhiều thuật toán tìm đường dẫn đóng ngắn nhất trong biểu đồ. Tôi nghĩ rằng nó không quá khó để thích nghi với một trong những thuật toán giải quyết vấn đề đó (a.k.a như là travelling salesman problem) theo nhu cầu của bạn (đường dẫn phải là một cách theo phong cách Hamilton không phải là một chu kỳ hamiltonian). Một số giải pháp nổi tiếng cho vấn đề nhân viên bán hàng là thuật toán của Dijkstra và thuật toán của Prim.