Thuật toán xấp xỉ cho biến thể TSP, bắt đầu và kết thúc cố định ở bất kỳ đâu nhưng điểm bắt đầu + nhiều lần truy cập tại mỗi đỉnh ALLOWED

Question

LƯU Ý: Do chuyến đi không kết thúc tại cùng một địa điểm bắt đầu và thực tế là mọi điểm có thể được truy cập nhiều lần miễn là tôi vẫn truy cập tất cả chúng, đây thực sự không phải là một biến thể TSP, nhưng tôi đặt nó do thiếu định nghĩa tốt hơn về vấn đề này.

Vì vậy, ..

Giả sử tôi đang đi trên một chuyến đi bộ đường dài với các điểm ưa thích. Những điểm này đều được kết nối bằng những lối mòn đi bộ đường dài. Tôi có một bản đồ hiển thị tất cả những con đường mòn với khoảng cách của họ, cho tôi một biểu đồ đạo diễn.

Vấn đề của tôi là làm cách nào để ước chừng chuyến tham quan bắt đầu tại điểm A và truy cập tất cả điểm ưa thích, trong khi kết thúc chuyến tham quan ở bất kỳ đâu nhưng điểm bắt đầu và tôi muốn chuyến tham quan càng ngắn càng tốt.

Do tính chất của đi bộ đường dài, tôi thấy điều này thật đáng buồn không phải là một vấn đề đối xứng (hoặc tôi có thể chuyển đổi đồ thị không đối xứng của mình thành đồ thị đối xứng?), Kể từ khi đi từ cao xuống thấp. xung quanh. Ngoài ra tôi tin rằng nó phải là một thuật toán hoạt động cho các đồ thị không phải số liệu, trong đó sự bất bình đẳng tam giác không thỏa mãn, vì đi từ a đến b đến c có thể nhanh hơn so với đường dài và kỳ lạ từ a đến c trực tiếp. Tôi đã xem xét nếu bất đẳng thức tam giác vẫn giữ, vì không có giới hạn về số lần tôi truy cập mỗi điểm, miễn là tôi truy cập tất cả chúng, nghĩa là tôi luôn chọn ngắn nhất hai đường dẫn khác nhau từ a đến c và do đó không bao giờ đi trên con đường dài và kỳ lạ.

Tôi tin rằng vấn đề của tôi dễ hơn TSP, vì vậy các thuật toán đó không phù hợp với vấn đề này. Tôi đã nghĩ đến việc sử dụng một cây bao trùm tối thiểu, nhưng tôi có một thời gian khó khăn thuyết phục bản thân rằng chúng có thể được áp dụng cho một đồ thị phi đối xứng phi số liệu.

Những gì tôi thực sự muốn là một số gợi ý như thế nào tôi có thể đưa ra một thuật toán xấp xỉ đó sẽ tìm thấy một tour du lịch tối ưu gần thông qua tất cả các điểm n

Answer 1

Bạn có thể đơn giản hóa vấn đề này cho một vấn đề TSP bình thường với n + 1 đỉnh. Để làm điều này, hãy chọn nút 'A' và tất cả các điểm quan tâm và tính toán một đường đi ngắn nhất giữa mỗi cặp của các điểm này. Bạn có thể sử dụng thuật toán đường dẫn ngắn nhất tất cả các cặp trên biểu đồ ban đầu. Hoặc, nếu n nhỏ hơn đáng kể so với kích thước biểu đồ ban đầu, hãy sử dụng thuật toán đường dẫn ngắn nhất nguồn đơn cho các đỉnh n + 1 này. Ngoài ra, bạn có thể đặt độ dài của tất cả các đường dẫn, kết thúc tại 'A', thành một số không đổi, lớn hơn bất kỳ đường dẫn nào khác, cho phép kết thúc chuyến đi ở bất kỳ đâu (điều này có thể chỉ cần cho thuật toán TSP, tìm đường đi khứ hồi) .

Kết quả là, bạn nhận được biểu đồ hoàn chỉnh, là số liệu, nhưng vẫn không đối xứng. Tất cả những gì bạn cần bây giờ là giải quyết một vấn đề TSP bình thường trên biểu đồ này. Nếu bạn muốn chuyển đổi biểu đồ bất đối xứng này thành một biểu đồ đối xứng, thì Wikipedia sẽ giải thích cách thực hiện.

Answer 2

Để giảm sự cố của bạn xuống TSP không đối xứng, hãy giới thiệu nút u mới và tạo vòng cung có độ dài L từ u đến A và từ tất cả các nút nhưng A đến u, trong đó L rất lớn (đủ lớn để không có giải pháp tối ưu nào). Xóa u khỏi chuyến tham quan để nhận đường dẫn từ A đến một nút khác qua tất cả các nút khác. Thật không may, việc giảm này duy trì mục tiêu chỉ bổ sung, điều này làm cho sự xấp xỉ đảm bảo tồi tệ hơn bởi một yếu tố không đổi.

Mục tiêu giảm Evgeny chỉ ra là không phải số liệu TSP đối xứng, vì vậy việc giảm không hữu ích cho bạn, vì xấp xỉ được biết là tất cả yêu cầu số liệu.Giả sử rằng tập hợp các đường nhỏ tạo thành một biểu đồ phẳng (hoặc gần với nó), có xấp xỉ yếu tố không đổi do Gharan and Saberi, rất tiếc để thực hiện và có thể không đưa ra kết quả hợp lý trong thực tế. Frieze, Galbiati, and Maffioli cung cấp một phép tính xấp xỉ log-factor đơn giản cho các đồ thị chung.

Nếu có số lượng đường nhỏ, chi nhánh và giới hạn hợp lý có thể cung cấp cho bạn giải pháp tối ưu. Cả hai G & S và chi nhánh và ràng buộc yêu cầu giải quyết chương trình tuyến tính Held-Karp cho ATSP, có thể hữu ích trong chính nó để đánh giá các phương pháp tiếp cận khác. Đối với nhiều trường hợp TSP đối xứng phát sinh trong thực tế, nó cho một giới hạn thấp hơn về chi phí của một giải pháp tối ưu trong vòng 10% giá trị thực.