Chu kỳ trọng lượng trung bình tối thiểu - Giải thích trực quan

Question

Trong đồ thị có hướng, chúng tôi đang tìm chu kỳ có trọng số cạnh trung bình thấp nhất. Ví dụ: biểu đồ có các nút 1 và 2 có đường dẫn từ 1 đến 2 chiều dài 2 và từ 2 đến 1 chiều dài 4 sẽ có chu kỳ trung bình tối thiểu là 3.

Không tìm kiếm phương pháp phức tạp (Karp), nhưng một giải pháp cắt xén đơn giản với backtacking wtih. Một giải thích được đưa ra là "Khả năng giải quyết với backtracking với cắt tỉa quan trọng khi chạy hiện tại có nghĩa là lớn hơn chi phí chu kỳ trung bình được tìm thấy tốt nhất."

Tuy nhiên, tại sao phương pháp này hoạt động? Nếu chúng ta đang ở giữa chu kỳ và trọng lượng lớn hơn giá trị trung bình, thì không phải là với các cạnh trọng lượng nhỏ, chúng ta có thể đạt được một tình huống mà chu kỳ hiện tại của chúng ta có thể thấp hơn mức trung bình tìm thấy tốt nhất?

Edit: Đây là một bài toán mẫu: http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2031

Answer 1

Cho phép giải pháp tối ưu cho đồ thị cho là một chu kỳ với trọng lượng trung bình cạnh X.

Có một số chu kỳ tối ưu với cạnh e_1, e_2 ... e_n , chẳng hạn như avg(e_i) = X.

Đối với bằng chứng của tôi, tôi giả định tất cả chỉ mục modulo n, vì vậy e_(n + 1) là e_1.

phép nói rằng dựa trên kinh nghiệm của chúng tôi không thể tìm thấy giải pháp này, có nghĩa là: với mỗi i (cạnh bất cứ điều gì chúng tôi đã đầu tiên) tồn tại như j (chúng tôi theo tất cả các cạnh i-j cho đến nay) mà trọng lượng cạnh trung bình trong trình tự e_i ... e_j lớn hơn X (heuristic prunes giải pháp này). Sau đó chúng tôi có thể chỉ ra rằng trọng lượng cạnh trung bình không thể bằng X. Cho phép lấy một chuỗi dài nhất contiguos không bị cắt xén bởi heuristic (có trọng số cạnh trung bình không lớn hơn X đối với mỗi phần tử). Ít nhất một e_i <= X, do đó, các chuỗi đó tồn tại. Đối với phần tử đầu tiên e_k của các chuỗi như vậy, có p sao cho avg(e_k ... e_p) > X. Chúng tôi đầu tiên như vậy p. Bây giờ, hãy dành k' = p + 1 và nhận một số p' khác. Chúng tôi sẽ lặp lại quá trình này cho đến khi chúng tôi lần nữa nhấn lần nữa k. Cuối cùng p không thể chạy nhanh hơn ban đầu k, điều này có nghĩa là các hậu tố cuối cùng chứa số [e_k, e_p - 1] ban đầu, mâu thuẫn với việc xây dựng của chúng tôi cho e_k. Bây giờ trình tự của chúng tôi e_1 ... e_n hoàn toàn được bao phủ bởi các dãy không chồng chéo e_k ... e_p, e_k'...e_p' v.v., mỗi trong số đó có trọng số cạnh trung bình lớn hơn X. Vì vậy, chúng tôi có mâu thuẫn là avg(e_i) = X.

Đối với câu hỏi của bạn:

Nếu chúng ta nửa chừng một chu kỳ và trọng lượng lớn hơn là tốt nhất tìm thấy trung bình, không phải là nó có thể là có lợi thế cạnh trọng lượng nhỏ chúng ta có thể đạt một tình huống nơi chu kỳ hiện tại của chúng tôi có thể thấp hơn mức tốt nhất có nghĩa là có nghĩa là gì?

Tất nhiên rồi. Nhưng chúng ta có thể an toàn cắt tỉa giải pháp này, vì sau này chúng ta sẽ khám phá ra cùng chu kỳ bắt đầu từ một cạnh khác, mà sẽ không bị cắt xén. Bằng chứng của tôi nói rằng nếu chúng ta xem xét mọi chu kỳ có thể có trong biểu đồ, sớm hay muộn chúng ta sẽ tìm thấy một chu kỳ tối ưu.