Phân tích: A.I. War

Trò chơi máy tính A.I. War ẩn chứa ít nhất một vài bài toán thuật toán hay. Tác giả hoàn toàn không phải là một chuyên gia, nhưng việc suy ngẫm về trò chơi đã làm nảy sinh cả bài toán này lẫn Space Emergency (ban đầu diễn ra trên một đồ thị giống đồ thị này). Trò chơi đưa ra một phiên bản khó hơn của bài toán: có hai hành tinh quê hương của A.I., nhiều hành tinh khác mà bạn có thể muốn ghé thăm, và lúc bắt đầu trò chơi bạn không biết có thể tìm thấy bất kỳ hành tinh nào trong số đó ở đâu. May thay, ở đây chúng ta xử lý một phiên bản đơn giản hóa và bạn không cần biết gì về trò chơi.

Trước tiên, hãy phát biểu bài toán bằng thuật ngữ lý thuyết đồ thị. Ta được cho một đồ thị vô hướng có \(P\) đỉnh và \(W\) cạnh. Ta cần tìm một dãy đỉnh bắt đầu bằng đỉnh 0 (hành tinh quê hương của ta) và kết thúc bằng một đỉnh kề với đỉnh 1 (hành tinh quê hương của A.I.), sao cho:

• mỗi đỉnh trong dãy kề với một trong các đỉnh đứng trước nó;
• dãy ngắn nhất có thể;
• với điều kiện trên, số đỉnh phân biệt nằm ngoài dãy nhưng kề với các đỉnh trong dãy là lớn nhất có thể.

Gọi \(D\) là khoảng cách từ đỉnh 0 đến đỉnh 1. Rõ ràng mọi dãy như vậy phải có ít nhất \(D\) phần tử. Ta cũng nhận thấy dãy có đúng \(D\) phần tử khi và chỉ khi nó tạo thành một đường đi ngắn nhất từ đỉnh 0 đến đỉnh 1. Vì vậy, ta đang tìm một đường đi ngắn nhất. Không may là có thể có nhiều đường đi ngắn nhất và ta phải chọn đường đi tối ưu hóa yêu cầu cuối cùng.

Việc tính toán sẽ đơn giản hơn nếu ta tính cả các hành tinh đã chinh phục vào nhóm hành tinh “bị đe dọa”. Vì đã biết phải chinh phục đúng \(D\) hành tinh theo quy ước đếm này, cuối cùng ta chỉ cần trừ \(D\).

Quan sát then chốt

Quan sát then chốt là: nếu một đỉnh cách 0 một khoảng \(d\), nó chỉ có thể bị đe dọa bởi một đỉnh ở khoảng cách \(d-1\), \(d\) hoặc \(d+1\). Điều này đúng vì khoảng cách tới 0 của hai đỉnh kề nhau chênh lệch không quá 1. Do đó, mỗi đỉnh của đồ thị chỉ bị đe dọa (hoặc bị chinh phục) trong phạm vi nhiều nhất ba đỉnh liên tiếp trên đường đi. Như ta sẽ thấy, quan sát này cho phép dùng quy hoạch động để tính các đường đi tốt nhất có độ dài tăng dần.

Thuật toán

Bước đầu tiên là chạy tìm kiếm theo chiều rộng để tính khoảng cách từ 0 tới mọi đỉnh \(v\): \(dist[v]\). Ta có \(dist[0]=0\) và \(dist[1]=D\). Mọi đường đi ngắn nhất bắt đầu ở đỉnh 0, rồi lần lượt đi qua các đỉnh ở khoảng cách 1, 2, ..., \(D-1\).

Với hai đỉnh kề nhau \(a,b\) thỏa \(dist[b]=dist[a]+1\), định nghĩa \(F(a,b)\) là số hành tinh bị đe dọa hoặc bị chinh phục lớn nhất trên một đường đi ngắn nhất \(0\to\dots\to a\to b\). Ta tính các giá trị này bằng quy hoạch động theo khoảng cách tăng dần từ 0.

Đáp án là giá trị lớn nhất của \(F(a,b)-D\), với \(a,b\) kề nhau, \(dist[a]=D-2\), \(dist[b]=D-1\), và \(b\) kề với đỉnh 1.

\(F(0,a)\) có thể được tính trực tiếp (chỉ có một đường đi khả dĩ). Còn lại là tính các giá trị \(F\) ở một khoảng cách từ các giá trị ở khoảng cách trước đó. Để tính \(F(b,c)\) với \(dist[b]=d\) và \(dist[c]=d+1\), thử mọi đỉnh \(a\) kề với \(b\) sao cho \(dist[a]=d-1\). Nói cách khác, ta xét các đường đi kết thúc bằng \(a\to b\to c\). Giá trị \(F(a,b)\) đã được tính ở vòng trước; câu hỏi là việc nối thêm \(c\) đưa vào bao nhiêu đỉnh bị đe dọa mới và phân biệt?

Đây là lúc quan sát then chốt phát huy tác dụng. Nếu một đỉnh kề với \(c\) đã bị đe dọa (hoặc chinh phục) trước đó, nó phải kề với \(a\) hoặc \(b\). Vì vậy, ta phải cộng số đỉnh kề với \(c\) nhưng không kề với \(a\) và cũng không kề với \(b\). Gọi giá trị này là \(G(a,b,c)\). Ta có công thức truy hồi:

Tính \(G\): bốn thuật toán

Ta gần xong, nhưng tính các giá trị \(G\) thế nào và tổng thời gian chạy là bao nhiêu? Có \(O(W)\) giá trị \(F\) cần tính (nhiều nhất một giá trị cho mỗi cạnh), và với mỗi giá trị ta xét \(O(P)\) giá trị \(F\) khác (một giá trị ứng với mỗi \(a\)). Vì vậy, nếu đã biết mọi giá trị \(G\), việc tính mọi \(F\) và giải bài toán mất \(O(PW)\). Tuy nhiên, tính \(G\) mới là phần tốn thời gian nhất.

Ta có thể phải tính \(G(a,b,c)\) cho mọi đường con \(a\to b\to c\) có khoảng cách tăng dần. Có ít nhất bốn cách; trong cuộc thi thực tế, chọn cách nào cũng không quan trọng vì tất cả đều chạy dư sức, nhưng ta vẫn trình bày để tham khảo.

1. Cách 1. Ta cần đếm các đỉnh \(v\) kề với \(c\) nhưng không kề với \(a\) hoặc \(b\). Cách đơn giản nhất là kiểm tra điều kiện này với mọi \(v\), mất \(O(P)\) cho một giá trị. Có nhiều nhất \(O(P^3)\) giá trị cần tính, cho tổng thời gian \(O(P^4)\). Có thể ước lượng chặt hơn: vì \(a\) và \(b\) kề nhau nên có nhiều nhất \(W\) cặp như vậy, đưa tổng thời gian xuống \(O(P^2W)\).

2. Cách 2. Sửa cách 1 một chút: thay vì kiểm tra mọi đỉnh \(v\), chỉ kiểm tra các đỉnh kề với \(c\). Khi đó có \(O(W)\) cặp \(a,b\) và \(O(W)\) cặp \(c,v\), nên tổng thời gian là \(O(W^2)\).

3. Cách 3. Sửa cách 1 theo hướng khác: tính trước tập láng giềng của mỗi đỉnh dưới dạng bitmask \(neighbors[v]\). Khi đó ta cần đếm số bit 1 trong \(neighbors[c]\ \mathbf{and\ not}\ (neighbors[a]\ \mathbf{or}\ neighbors[b])\). Nhờ tính song song mức bit, phép tính này rất nhanh. Nếu từ máy có kích thước \(w\) (thường là 32 hoặc 64), lượng việc giảm đi hệ số \(w\). Điều này giả sử có thể đếm số bit 1 trong một từ bằng một bước, điều mà các bộ xử lý hiện đại hỗ trợ bằng một lệnh máy. Thời gian cuối cùng là \(O(P^2W/w)\).

4. Cách 4. Đây là cách thú vị về lý thuyết nhưng khá phức tạp khi cài đặt. Định nghĩa ma trận \(A\) kích thước \(W\times P\) và ma trận \(B\) kích thước \(P\times P\). Đặt \(A_{ij}=1\) nếu đỉnh \(j\) không kề với đầu mút nào của cạnh thứ \(i\), và bằng 0 nếu ngược lại. Đặt \(B_{ij}=1\) nếu hai đỉnh \(i,j\) kề nhau (hoặc trùng nhau), và bằng 0 nếu ngược lại. Tính tích ma trận \(C=A\times B\). Theo định nghĩa phép nhân ma trận, \(C\) có kích thước \(W\times P\) và các phần tử của nó chính là các giá trị \(G\): cụ thể, \(C_{ij}=G(a,b,j)\) nếu cạnh thứ \(i\) là \(a\leftrightarrow b\).

Nếu tính tích ma trận theo cách tự nhiên, ta nhận lại độ phức tạp của cách 1 là \(O(P^2W)\); thực chất chỉ là viết cách 1 bằng ký hiệu ma trận. Mẹo ở đây là tồn tại các thuật toán nhân ma trận nhanh hơn. Thuật toán nhanh nhất được biết tại thời điểm bài phân tích được viết là Coppersmith–Winograd. Nói ngắn gọn, nó cho thời gian tiệm cận lý thuyết \(O(P^{1.376}W)\).

Không nên dùng cách cuối trong cuộc thi. Nó không chỉ phức tạp không cần thiết mà còn không thực sự nhanh hơn với kích thước đồ thị đang xét. Ưu thế tiệm cận chỉ xuất hiện ở những đồ thị dày, khổng lồ đến mức không thực tế.

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