Phân tích

Bài toán tối ưu này chạm đến những chủ đề hơi xa so với các bài khác của chúng ta, nhưng rất nhiều cách giải hợp lý đều có thể thành công.

Ta bắt đầu bằng một số nhận xét tổng quát, rồi chuyển sang vài lời giải trong số rất nhiều khả năng.

Không bao giờ đến quá gần một hòn đảo

Tốc độ nhận liều bức xạ tăng mạnh khi tới gần đảo, nên mọi đường đi lướt quá sát một đảo đều tệ hơn một đường chịu mất thêm thời gian để vòng qua ở khoảng cách xa hơn.

Điều này hữu ích vì ta có thể tin tưởng hơn vào độ chính xác số khi xấp xỉ đường đi tốt nhất: vùng có tốc độ nhận liều thấp cũng là vùng mà đạo hàm của tốc độ nhận liều theo vị trí thấp.

Không bao giờ đi sang trái

Dù giới hạn đầu vào không cho phép tình huống này, giả sử thuyền bắt đầu cách một đảo 0.000001 km về bên trái. Khi đó ảnh hưởng của đảo lớn hơn rất nhiều bức xạ nền; ta sẽ muốn đi sang trái để “thoát” khỏi đảo nhanh nhất rồi cuối cùng vòng rộng quanh nó.

Ngoài ra, xét trường hợp chênh lệch tung độ hai đầu mút đủ lớn để góc nối chúng gần \(90^\circ\) so với phương ngang, và có một đảo ở giữa đoạn thẳng trực tiếp nối hai đầu. Một đường tối ưu có thể bắt đầu gần như thẳng đứng nhưng hơi chếch trái, vì như vậy cách đảo xa hơn mà gần như không tăng tổng độ dài đường đi.

Tuy nhiên, đầu vào đã được làm “đẹp”: thuyền luôn bắt đầu cách các đảo 10 km về bên trái, nơi tốc độ liều tối đa từ các đảo không quá \(0.02\,\mu\text{Sv}/\text{h}\); góc tối đa giữa hai đầu mút là \(45^\circ\) so với phương ngang. Vì vậy, đi sang trái ngay từ đầu là sai lầm.

Tương tự, đi trái ở giữa hành trình cũng không giúp ích. Một đường zích zắc quay lại và lặp một số hoành độ có thể được thay bằng đường trực tiếp hơn với tổng liều thấp hơn.

https://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_1_46d6bcd8.png

Lời giải 1: Leo đồi

Bài toán tối ưu này rất phù hợp với leo đồi vì dễ dàng lặp việc lấy một đường hợp lý rồi “đẩy nhẹ” nó về một đường tốt hơn sao cho nhanh chóng hội tụ tới cực tiểu cục bộ.

Có bao nhiêu cực tiểu cục bộ? Vì ta không bao giờ nên đi trái và chỉ có một hoặc hai đảo, đường tối ưu chỉ có một số ít dạng. Với một đảo, đường tối ưu đi phía trên hoặc phía dưới đảo. Với hai đảo, đường tối ưu đi phía trên cả hai, đi giữa hai đảo hoặc đi phía dưới cả hai.

Vì vậy, nếu bắt đầu bằng một đường hợp lý cho mỗi dạng rồi leo đồi từ đó, ta tìm được từng cực tiểu trong hai hoặc ba cực tiểu cục bộ.

Một cách dễ thực hiện là mô hình hóa đường đi thành nhiều đoạn thẳng nhỏ. Với mỗi đoạn, dùng giải tích để tìm lượng bức xạ nhận trên phần đường ấy. Xét đoạn từ \((x_1,y_1)\) đến \((x_2,y_2)\), đi trong khoảng thời gian từ 0 đến 1 (ta co giãn thời gian cho thuận tiện). Tọa độ theo thời gian \(t\) là

Giả sử có hai đảo — trường hợp một đảo chỉ là phiên bản đơn giản hơn — với tung độ \(y_{i1},y_{i2}\); hoành độ cả hai đều bằng 0. Khi ấy tổng bức xạ là tích phân từ 0 đến 1 của

Tích phân có thể giải chính xác, nhưng không cần thiết. Nếu dùng đủ nhiều đoạn, lấy độ dài đoạn nhân với trung bình tốc độ liều tại hai đầu là đủ chính xác.

Vấn đề là tìm đúng vị trí các đoạn. Ta có thể đặt một đường thô với các đầu mút có hoành độ cố định và cách đều từ \(-10\) đến \(+10\). Các tung độ lúc này tạo thành một vector số thực cần tối ưu.

Ta có thể dùng hạ gradient: lặp việc tìm một hướng dịch chuyển vector sao cho tổng bức xạ giảm.

Điều chỉnh từng giá trị riêng lẻ không hiệu quả. Ngay cả khi một điểm cần được đẩy lên, nếu chỉ đẩy riêng nó, đường đi sớm tạo một “góc gãy” làm tổng liều tăng. Nhưng hầu như mọi cách khác đều dùng được; chẳng hạn chọn một đoạn các điểm và đẩy tất cả lên hoặc xuống theo dạng tam giác, các điểm giữa dịch nhiều hơn các điểm đầu, sẽ giữ đường trơn.

Các kỹ thuật tối ưu phi tuyến tinh vi hơn như thuật toán BFGS cũng hoạt động.

Lời giải 2: Phép tính biến phân

Ta có thể coi tung độ của thuyền là một hàm theo hoành độ, viết tổng liều bức xạ thành một tích phân chứa hàm ấy, rồi dùng phép tính biến phân để cực tiểu hóa. Phương trình Euler–Lagrange cho một điều kiện dưới dạng phương trình vi phân mà mọi lời giải phải thỏa.

Điều kiện này hoàn toàn cục bộ. Nếu biết hướng ban đầu của thuyền, ta có thể tìm toàn bộ đường đi bằng một kỹ thuật tích phân số như phương pháp Runge–Kutta, giải phương trình vi phân từ điều kiện đầu đã biết. Nhưng ta không biết hướng ban đầu; ta chỉ biết vị trí đầu và cuối.

Nếu đoán một hướng ban đầu hợp lý rồi tích phân, ta vạch ra được một đường nhưng tung độ điểm cuối có lẽ không đúng. Vì vậy, có thể tìm kiếm nhị phân hướng ban đầu dẫn đúng đến điểm cuối mong muốn. Nếu lặp tìm kiếm nhị phân trên các khoảng tương ứng với từng dạng đường có thể có, ta sẽ tìm được đường tối ưu.

Các kỹ thuật tích phân số đơn giản dùng sai phân hữu hạn đủ chính xác để giải bài, nhưng phải cẩn thận với hướng ban đầu chỉ quá trực tiếp về phía một đảo hoặc có độ dốc quá lớn. Những trường hợp đó có sai số số học lớn và có thể khiến tìm kiếm nhị phân rẽ nhầm nhánh.

KalininN đã dùng phương pháp này để giải Test Set nhỏ; với vài chỉnh sửa nhỏ, lời giải của anh ấy cũng có thể chạy cho Test Set lớn.

Lời giải 3: Quy hoạch động

Một cách khác là phủ một lưới điểm lên bản đồ rồi dùng quy hoạch động tìm đường tối ưu qua các điểm. Cách này khả thi vì yêu cầu độ chính xác không quá nghiêm, nhưng vẫn khó làm đúng. Lưới quá thưa không mô hình hóa đường tối ưu đủ chính xác; lưới quá dày làm bài toán quy hoạch động quá lớn để giải kịp.

Gennady.Korotkevich, thí sinh duy nhất giải được Test Set lớn, đã dùng thành công cách này. Anh có hai nhận xét giúp phương pháp hoạt động.

Đường đi của thuyền chủ yếu nằm ngang và góc thay đổi từ từ; bài toán chủ yếu là điều chỉnh cẩn thận vị trí thẳng đứng. Vì vậy lưới có thể thưa theo phương ngang hơn phương dọc; Gennady dùng tỉ lệ 20:1. Trong những phút cuối cuộc thi, anh thử hai lời giải chỉ khác nhau ở độ mịn theo phương ngang. Lưới thưa hơn hóa ra chính xác hơn vì mô hình hóa góc tốt hơn. Một lưới mịn hơn theo cả hai chiều sẽ chính xác hơn nữa nhưng có thể quá chậm.

Nhận xét thứ hai là đường không nên có đoạn nào với góc quá dốc. Do đó khi tính giá trị tối ưu cho một điểm ở một cột, chỉ cần xét các điểm ở cột trước trong một khoảng dọc nhất định. Kích thước khoảng được điều khiển bởi hằng số MAGIC trong mã của Gennady. Lời giải chạy nhanh hơn nhiều so với giới hạn của Test Set lớn, và các đáp án nằm trong cận sai số khá rộng của đề.

Có thể nhanh chóng thu được kết quả rất chính xác bằng cách bắt đầu với lưới thô, tìm đường tối ưu trong lưới ấy, rồi lặp việc cải thiện bằng các lưới ngày càng mịn phủ vùng gần đường hiện tại.

Bạn có thể tải bài nộp của các thí sinh cho bài này và các bài khác từ bảng điểm Chung kết.

Nguồn

Bản dịch dựa trên phân tích chính thức Google Code Jam 2016 - World Finals - Radioactive Islands, kho Google Coding Competitions (Apache-2.0).