Phân tích: Travel Plan

Giống như City Tour, bài toán này liên quan chặt chẽ đến chu trình Hamilton. Tin tốt là ở đây, đồ thị chỉ gồm các điểm trên một đường thẳng nên dễ phân tích hơn nhiều. Tin xấu là ta không tìm một chu trình Hamilton bất kỳ, thậm chí cũng không chỉ tìm chu trình ngắn nhất; ta tìm một chu trình có độ dài cụ thể. Một yêu cầu chính xác như vậy đòi hỏi một kiểu tìm kiếm đầy đủ.

Cách đơn giản nhất là lần lượt thử mọi kế hoạch du hành có thể. Cách này quá chậm cho dữ liệu lớn, nhưng đủ dùng cho dữ liệu nhỏ.

Vì trong mọi trường hợp \(Nle30\), ý tưởng tiếp theo có thể là một lời giải quy hoạch động theo dõi tổng quãng đường đã đi và những nút đã thăm. Đáng tiếc, cách này cũng quá chậm: các giá trị lớn của \(F\) là một vấn đề nghiêm trọng!

Lời giải \(3^N\)

Bước then chốt đầu tiên là giảm thời gian từ \(N!\) xuống \(3^N\).

Trước hết, ta chia đường thẳng thành các khoảng \(I_1,I_2,ldots,I_{N-1}\). Gọi \(t_j\) là số lần kế hoạch du hành băng qua khoảng \(I_j\), và \(d_j\) là độ dài của khoảng \(I_j\). Khi đó tổng độ dài kế hoạch chính xác là

$
t_1d_1+t_2d_2+cdots+t_{N-1}d_{N-1}.
$

Vì vậy, tất cả những gì cần làm là xác định mỗi \(t_j\) phải bằng bao nhiêu.

Câu hỏi lớn là những giá trị \(t_j\) nào có thể xảy ra? Hãy cùng xem xét.

Mỗi \(t_j\) phải dương.

Lý do: Nếu \(t_j=0\), kế hoạch không bao giờ băng qua khoảng tương ứng, vì thế không thể thăm mọi hành tinh.

Với mỗi \(j\), \(t_j-t_{j-1}\) phải là \(-2\), \(0\) hoặc \(2\).

Lý do: Gọi \(P\) là hành tinh nằm giữa hai khoảng \(I_{j-1}\) và \(I_j\). Trong kế hoạch du hành, ta chỉ có thể dừng tại \(P\) nhiều nhất một lần. Trong mọi lần khác, ta phải đi xuyên qua, đóng góp \(1\) cho cả \(t_{j-1}\) và \(t_j\). Trong lần duy nhất thực sự ghé hành tinh, ta đi vào theo một khoảng rồi rời đi theo một khoảng; hai khoảng này có thể giống hoặc khác nhau. Phần này của kế hoạch đóng góp hoặc (a) \(1\) cho cả \(t_{j-1}\) và \(t_j\), hoặc (b) \(2\) cho một giá trị và \(0\) cho giá trị kia. Trong mọi trường hợp, \(t_j-t_{j-1}\) phải là \(-2\), \(0\) hoặc \(2\).

\(t_0\) và \(t_{N-1}\) đều phải bằng \(2\).

Lý do: Xét “khoảng bên ngoài” \(I_{-1}\) nằm quá các hành tinh xa nhất. Kế hoạch không thể đi qua khoảng này, nên \(t_{-1}=0\). Nhận xét trên lập tức dẫn tới kết luận này.

Mọi cách chọn các \(t_j\) thỏa những điều kiện trên đều có thể được hiện thực hóa bằng một kế hoạch du hành hợp lệ.

Lý do: Ta có thể xây dựng một kế hoạch như vậy bằng cách quét các khoảng từ trái sang phải. Ở mỗi thời điểm trong quá trình dựng, ta đã quyết định kế hoạch làm gì ở bên trái một hành tinh \(P\). Cụ thể, với mỗi chuyến đi ở bên trái \(P\), ta biết chuyến đó làm gì cho tới khi nó lại đi sang bên phải \(P\). Tuy nhiên, ta chưa biết điều gì xảy ra giữa các lần ghé này, thậm chí cũng chưa biết thứ tự của chúng.

Bây giờ, giả sử ta muốn mở rộng kế hoạch bộ phận qua khoảng kế tiếp \(I_j\). Nếu \(t_j=t_{j-1}-2\), ta cần nối hai chuyến hiện tại thông qua một lần dừng tại \(P\), rồi kéo dài các chuyến còn lại dọc theo \(I_j\). Nếu \(t_j=t_{j-1}+2\), ta thêm một chuyến mới đi dọc \(I_j\), dừng tại \(P\), rồi quay trở lại. Trong trường hợp cuối cùng, ta chỉ kéo dài mỗi chuyến dọc theo \(I_j\), với một lần dừng tại \(P\) nhưng không đổi hướng.

Nếu suy nghĩ kỹ một chút, bạn sẽ thấy phương pháp này thực sự luôn tạo ra một kế hoạch du hành hợp lệ.

Đến đây ta có thể mô tả lời giải thời gian \(3^N\). Khi đã biết \(t_{j-1}\), có nhiều nhất ba lựa chọn cho \(t_j\). Lần lượt thử từng lựa chọn, ta có thể duyệt mọi phép gán cho các \(t_j\), rồi chọn phép gán dẫn tới kế hoạch có độ dài tối ưu.

Lời giải \(3^{N/2}\)

Tuy nhiên, ngay cả thuật toán \(3^N\) vẫn quá chậm. May mắn là có một mẹo rất hữu ích cho những tình huống như thế này.

Xét khoảng giữa \(I_{N/2}\) và một giá trị cố định của \(t_{N/2}\). Dùng cách trên, trong thời gian \(3^{N/2}\) ta có thể liệt kê mọi cách chọn \(t_1,t_2,ldots,t_{N/2-1}\) nhất quán với \(t_{N/2}\). Gọi \(A\) là tập mọi giá trị có thể đạt được của

$
t_1d_1+t_2d_2+cdots+t_{N/2}d_{N/2}.
$

Tương tự, ta có thể tính \(B\), tập mọi giá trị

$
t_{N/2+1}d_{N/2+1}+t_{N/2+2}d_{N/2+2}+cdots+t_{N-1}d_{N-1}
$

nhất quán với \(t_{N/2}\). Toàn bộ việc này mất thời gian \(3^{N/2}\). Phần còn lại là tìm hai số trong \(A\) và \(B\) có tổng gần \(F\) nhất nhưng không vượt quá \(F\). Một cách hiệu quả là sắp xếp \(B\), rồi với mỗi phần tử của \(A\), dùng tìm kiếm nhị phân để xác định phần tử nào trong \(B\) nên được ghép với nó. Điều đó cho lời giải \(O(3^{N/2}N)\).

Có thể cải thiện thành \(O(3^{N/2})\) bằng cách biến đổi công thức một chút:

$
t_1(d_1+cdots+d_{N/2})+(t_2-t_1)(d_2+cdots+d_{N/2})+cdots+(t_{N/2}-t_{N/2-1})d_{N/2}.
$

Danh sách các tổng này có thể được sinh trực tiếp theo thứ tự tăng dần bằng cách liên tục trộn các danh sách khi thêm hạng tử mới. Hiệu \(t_{j+1}-t_j\) luôn là một trong \(-2\), \(0\), \(2\), nên để thêm một hạng tử mới, ta cần trộn ba danh sách đã sắp xếp.

Khi hai danh sách \(A\) và \(B\) đều đã được sắp xếp, ta có thể xử lý chúng trong thời gian tuyến tính bằng một lượt quét với hai con trỏ.

Nguồn

Bản dịch đầy đủ dựa trên phân tích chính thức của Google Code Jam 2010 - Travel Plan, thuộc kho Google Coding Competitions (Apache-2.0).