Chu kỳ trọng lượng tối đa trong biểu đồ

Question

Với biểu đồ có trọng số (hướng hoặc không được hướng dẫn), tôi cần phải tìm chu kỳ của biểu đồ có trọng số tối đa.

Trọng lượng của chu trình là tổng trọng lượng của các cạnh của biểu đồ.

Nó có thể là bất kỳ chu kỳ, không chỉ cơ sở chu kỳ mà chúng ta có thể

• tất cả chu kỳ cơ sở (xem Algorithms to Identify All the Cycle Bases in a UnDirected Graph)
• tính toán trọng lượng của mỗi chu kỳ cơ sở và tìm tối đa

Tôi có thể thử liệt kê tất cả các chu kỳ của đồ thị và sau đó tính toán tối đa nhưng tổng số chu kỳ có thể thực sự lớn (nếu đồ thị được hoàn thành thì bất kỳ chuỗi đỉnh nào trong đó đầu tiên và cuối cùng là giống nhau) .

Bạn có ý tưởng nào để tìm chu kỳ trọng lượng tối đa mà không liệt kê tất cả các chu kỳ không?

Nếu bạn cần giả thuyết trên biểu đồ (ví dụ như trọng số tích cực), hãy chỉ ra chúng.

Answer 1

Đây là NP-Hard.

Sự cố chu trình Hamilton có thể được giảm xuống mức này.

Đưa ra biểu đồ mà chúng tôi cần kiểm tra xem có tồn tại chu trình Hamilton hay không, chỉ định trọng số 1 cho mỗi cạnh.

Bây giờ hãy chạy thuật toán của bạn để nhận chu kỳ trọng lượng tối đa. Nếu trọng số là < n, thì biểu đồ ban đầu không có chu trình Hamilton, nếu không thì sẽ có.

Answer 2

Nếu bạn có thể tìm đường đi có trọng số tối thiểu trong trường hợp cụ thể của mình, chỉ cần đảo ngược các dấu hiệu của tất cả các trọng số và áp dụng thuật toán của bạn. Tất nhiên bạn đang thực hiện một số giả định unstated bởi vì đối số của Moron là chính xác (không có ý định chơi chữ). Các giả định bạn đang tạo ra có thể là trọng số dương hoặc không có chu kỳ trọng số âm. Tôi nghĩ bạn nên cố gắng để tuyên bố họ thay vì để mọi người tìm kiếm trong không gian vô hạn của các giả định có thể. Đối với kết quả độ cứng, điều này cũng khó có thể ước tính theo một số cách, hãy kiểm tra this paper. Cùng một bài báo có chứa một số kết quả tích cực cho các loại đồ thị quan trọng, nhưng nó liên quan đến đường dẫn không có trọng số dài nhất nên tôi đoán là hầu hết các thuật toán trong bài báo sẽ không trực tiếp trợ giúp trong trường hợp của bạn. Nếu bạn tìm kiếm "chu kỳ nặng", bạn sẽ tìm thấy một số giấy tờ thú vị, nhưng chúng có nhiều tính toán hơn. Nếu trọng số của bạn là số nguyên nhỏ (lên đến đa thức theo kích thước của biểu đồ), bạn có thể thử và thay thế mọi cạnh bằng một đường không có trọng số để giảm vấn đề của bạn cho trường hợp không trọng số. Tôi hy vọng điều này sẽ giúp ở một mức độ nào đó, nhưng bạn có thể có một vấn đề nghiên cứu mở trên tay của bạn.