Có lẽ bạn có thể tạo dữ liệu thử nghiệm của riêng mình?
Điều này chắc chắn sẽ không được thử nghiệm toàn diện, nhưng nó có thể hữu ích. Lưu ý: dưới đây là về con đường hamiltonian, và nếu bạn đang tìm kiếm chu kỳ, một cái gì đó tương tự sẽ làm việc.
Bạn có thể thực hiện các thao tác sau:
Giả sử bạn được cung cấp đồ thị vô hướng G có nút n.
Bây giờ bạn tạo biểu đồ có trọng số G ', bằng cách đặt trọng số của các cạnh trong G bằng 1 và thêm các cạnh không có trong G và cho chúng một trọng số ngẫu nhiên> 1, tức là G' là biểu đồ hoàn chỉnh trọng số được gán cho tất cả các cạnh của nó.
Bây giờ, nếu bạn chạy thuật toán TSP hợp lệ trên G 'và nó tạo ra một đường dẫn có kích thước n-1, thì G có đường dẫn hamiltonian. Nếu không G không có một con đường hamiltonian. Vì vậy, bây giờ bạn có thể sử dụng đồ thị bạn biết có/không có đường dẫn hamiltonian (ví dụ: Hypercube có đường dẫn hamiltonian) và tạo dữ liệu thử nghiệm cho thuật toán TSP của bạn.
trang này có một số điều kiện đủ mà có thể hữu ích trong việc tạo ra các đồ thị mà có Đường đi Hamilton: http://www-math.cudenver.edu/~wcherowi/courses/m4408/gtln12.html
Tôi cho rằng bạn sẽ không có một thời gian khó khăn để tìm dữ liệu trên đồ thị có/không có Đường đi Hamilton.
Hy vọng điều đó sẽ hữu ích. Chúc may mắn!
Nguồn
2010-06-02 16:33:06
Luôn bán hàng trên eBay, hiển nhiên là O (1). :-P http://xkcd.com/399/ –