Đây là một dự án mà tôi được yêu cầu triển khai phương pháp tối ưu hóa cho vấn đề tối ưu hóa nhân viên bán hàng đi du lịch. Tôi không cần trợ giúp với bản thân việc thực hiện, nhưng có một câu hỏi về hướng tôi sẽ tham gia.Sử dụng Bộ giải quyết Người bán hàng Đi du lịch để quyết định Đường dẫn Hamilton
Tôi đã có một TSP heuristic dựa trên thuật toán di truyền: nó giả định một đồ thị hoàn chỉnh, bắt đầu bằng một bộ các giải pháp ngẫu nhiên là dân số và hoạt động để cải thiện dân số cho một số thế hệ. Tôi cũng có thể sử dụng nó để giải quyết các vấn đề về đường đi hoặc chu kỳ Hamilton? Thay vì tối ưu hóa để có được con đường ngắn nhất, tôi chỉ muốn kiểm tra nếu có một con đường.
Bây giờ, bất kỳ biểu đồ hoàn chỉnh nào cũng sẽ có đường dẫn Hamilton trong đó, vì vậy phương pháp phỏng đoán TSP sẽ phải được mở rộng tới bất kỳ biểu đồ nào. Điều này có thể được thực hiện bằng cách đặt các cạnh thành một số giá trị vô hạn nếu không có đường dẫn giữa hai thành phố và trả về đường dẫn đầu tiên là một đường dẫn Hamilton hợp lệ.
Đó có phải là cách phù hợp để tiếp cận không? Hoặc tôi nên sử dụng một heuristic khác nhau cho con đường Hamilton? Mối quan tâm chính của tôi là liệu đó có phải là một cách tiếp cận khả thi vì tôi có thể chắc chắn rằng TSP tối ưu hóa (bởi vì bạn bắt đầu với các giải pháp và cải thiện chúng) nhưng không phải nếu một người quyết định Hamilton sẽ tìm thấy bất kỳ đường dẫn nào trong một số thế hệ cố định.
Tôi cho rằng cách tiếp cận tốt nhất là tự mình thử nghiệm, nhưng tôi bị hạn chế bởi thời gian và suy nghĩ tôi muốn hỏi trước khi đi xuống tuyến đường này ... (Tôi có thể tìm một cách khác để tìm đường dẫn Hamilton)
Không phải là câu trả lời, nhưng truyện tranh sau đây có thể nâng tinh thần của bạn lên một số: http://xkcd.com/399/ – samoz
Tôi sẽ sử dụng nó trong bản trình bày của dự án. : D –