Phân tích: Crossing the Road

Một lưới các con đường; một người di chuyển từ nơi này sang nơi khác; bài toán này có tất cả các đặc điểm của một bài toán đồ thị, cụ thể là bài toán tìm đường đi ngắn nhất. Người đi bộ của chúng ta đang cố gắng đi từ một góc của bản đồ đến góc đối diện. Một số bước đi có thể thực hiện bất cứ lúc nào và mất 2 phút; đối với những bước khác, cô ấy phải đợi cho đến khi đèn chuyển sang màu xanh, và sau đó mất thêm 1 phút nữa. Làm thế nào chúng ta có thể giảm thiểu thời gian cô ấy đến đích?

Để giải quyết bài toán này, chúng ta cần mô tả trạng thái của thế giới. Người đi bộ có thể ở bất kỳ vị trí nào trong số \(2M\) vị trí theo hướng \(x\), bất kỳ vị trí nào trong số \(2N\) vị trí theo hướng \(y\), và tại một thời điểm \(t\). Vì người đi bộ luôn có thể đợi nếu cần, cô ấy sẽ luôn thích ở vị trí \((x, y, t)\) hơn là \((x, y, t+1)\); do đó, một thuật toán tính toán thời gian sớm nhất mà người đi bộ có thể đến \((x, y)\) sẽ giải quyết được bài toán này.

Bài toán này khác với bài toán đồ thị tiêu chuẩn ở chỗ, đối với hai địa điểm lân cận nằm đối diện nhau qua một con đường, trọng số của cạnh giữa chúng không cố định. Hóa ra đây chỉ là một sự phức tạp nhỏ, và chúng ta có thể sử dụng các phiên bản sửa đổi nhẹ của một số thuật toán tìm đường đi ngắn nhất tiêu chuẩn.

Từ mỗi vị trí, người đi bộ có thể đi theo hướng bắc, nam, đông hoặc tây, trừ khi hướng đó nằm ngoài mép bản đồ. Thời gian thực hiện việc này sẽ là 2 phút nếu đi dọc theo một khối nhà, hoặc (thời gian chờ cho đến khi đèn giao thông chuyển sang màu xanh) + 1 phút nếu là băng qua đường.

Thuật toán

Bellman-Ford có lẽ là thuật toán dễ cài đặt nhất cho bài này. Đường đi dài nhất sẽ mất tối đa \(O(N+M)\) bước, vì vậy thuật toán của bạn sẽ kết thúc sau tối đa ngần ấy giai đoạn. Tại mỗi giai đoạn, đối với mỗi điểm, bạn sẽ cố gắng cập nhật (tối đa) bốn điểm lân cận của nó. Thời gian chạy là \(O(NM(N+M))\).

Thuật toán Dijkstra thường hiệu quả hơn. Với \(4NM\) trạng thái và 4 hướng di chuyển từ mỗi trạng thái, thuật toán này sẽ hoàn thành trong thời gian \(O(NM \log(NM))\).

Tính đúng đắn của một trong hai thuật toán có thể được chứng minh theo cách gần giống như phiên bản tiêu chuẩn của chúng. Chúng tôi để lại những chứng minh này như những bài tập xứng đáng cho độc giả.

Cách tính thời gian chờ đèn xanh

Giả sử tại thời điểm hiện tại \(curr\_t\), bạn muốn băng qua đường theo hướng Bắc-Nam tại giao lộ có các tham số \(S, W, T\).
Chu kỳ của đèn là \(L = S + W\).
Thời điểm bắt đầu của một chu kỳ gần nhất trước hoặc tại \(curr\_t\) có thể được tính bằng cách dịch chuyển \(T\) về một giá trị tương đương trong khoảng thời gian hiện tại:
\(t_0 = (curr\_t - T) \pmod L\). Nếu kết quả âm, ta cộng thêm \(L\).
Thực tế, ta có thể tính \(start\_time = curr\_t - ((curr\_t - T) \pmod L + L) \pmod L\).

• Nếu \(curr\_t\) nằm trong khoảng thời gian đèn Bắc-Nam xanh (từ \(start\_time\) đến \(start\_time + S\)), và thời gian còn lại đủ để băng qua (\(start\_time + S - curr\_t \ge 1\)), bạn có thể đi ngay.
• Ngược lại, bạn phải đợi đến đầu chu kỳ tiếp theo hoặc giai đoạn xanh tiếp theo.

Tương tự cho hướng Đông-Tây.

Độ phức tạp

• Dijkstra: \(O(NM \log(NM))\)
• Bellman-Ford: \(O(NM(N+M))\)

Dựa trên phân tích chính thức của Google Code Jam.

Thông tin thêm:

• Thuật toán Dijkstra
• Thuật toán Bellman-Ford