Phân tích: The Bored Traveling Salesman

Chúng ta có thể mô hình hóa bài toán này dưới dạng đồ thị, trong đó các thành phố là các nút và các chuyến bay khứ hồi giữa các thành phố là các cạnh vô hướng nối các nút. Mỗi nút có một mã ZIP riêng biệt. Các ràng buộc về vé và cách sử dụng có thể được mô hình hóa như một dạng biến thể của duyệt đồ thị theo chiều sâu (DFS): khi chúng ta đến một nút, chúng ta không bắt buộc phải thăm tất cả các nút lân cận ngay lập tức, nhưng cuối cùng mọi nút phải được thăm. Khi một nút được thăm lần đầu, mã ZIP của nó được ghi lại (duyệt tiền thứ tự - pre-order). Khi tất cả các nút đã được thăm, chuỗi mã ZIP nối lại phải tạo thành số nhỏ nhất có thể.

Giải pháp Vét cạn (Brute Force):

Dữ liệu nhỏ (Small dataset) có tối đa 8 nút. Nó đủ nhỏ để chúng ta thử tất cả các đường đi khả thi theo quy tắc (bao gồm tất cả các nút bắt đầu có thể), và chọn đường đi có số nối lại nhỏ nhất. Độ phức tạp của giải pháp vét cạn có thể là \(O(N! \times N)\), trong đó \(N!\) đến từ việc liệt kê tất cả các hoán vị của các thành phố và với mỗi hoán vị, chúng ta kiểm tra tính hợp lệ của nó trong \(O(N)\). Vì dữ liệu lớn (Large dataset) có thể lên tới 50 thành phố, thuật toán này sẽ quá chậm.

Giải pháp Tham lam (Greedy):

Chúng ta có thể xếp hạng các nút dựa trên mã ZIP của chúng (nút nhỏ nhất là nút có mã ZIP nhỏ nhất). Vì tất cả các mã ZIP đều có cùng độ dài, để tạo ra số nối lại nhỏ nhất, chúng ta có thể tham lam nối các mã ZIP theo thứ tự tăng dần. Điều này có nghĩa là nút có mã ZIP nhỏ nhất nên là nút đầu tiên được thăm (nút gốc của quá trình duyệt). Để tối thiểu hóa số cuối cùng, chúng ta nên luôn thăm nút khả thi nhỏ nhất tiếp theo. Lưu ý rằng luôn có thể hoàn thành chuyến đi từ nút nhỏ nhất (hoặc bất kỳ nút nào) vì đồ thị đầu vào được đảm bảo liên thông.

Trước khi đi vào mã giả, hãy định nghĩa một số biến:

• DEAD: Tập hợp các nút chúng ta đã thăm và đã rời đi (không bao giờ quay lại nữa).
• ACTIVE: Một ngăn xếp (stack) chứa các nút dọc theo đường đi hiện tại (bắt đầu từ nút gốc).
• HEAD: Nút ở trên cùng của ngăn xếp ACTIVE, là nút chúng ta đang đứng hiện tại.

Tại mỗi bước, chúng ta có thể:

1. Thăm một nút lân cận chưa được thăm của HEAD, thêm nút đó vào đỉnh ngăn xếp ACTIVE và biến nó thành HEAD mới. Hành động này tương đương với việc bay đến một thành phố mới lần đầu tiên. Ghi lại mã ZIP của nó.
2. Rời khỏi HEAD, lấy HEAD ra khỏi ngăn xếp ACTIVE và đưa vào tập DEAD. Hành động này tương đương với việc đi chuyến bay về từ HEAD. Chúng ta không ghi lại mã ZIP khi thực hiện việc này.

Mã giả cho thuật toán tham lam:

  root = the node with smallest zip code
  DEAD = new Set()
  ACTIVE = new Stack()
  ACTIVE.push(root)
  answer = “”
  concatenate zipcode[root] to answer
  while ACTIVE is not empty:
    HEAD = ACTIVE.peek()
    next = next_smallest_feasible_node_to_visit()
    if next is EMPTY or no flight from HEAD to next:
      # leave the HEAD node
      insert HEAD to the DEAD set
      ACTIVE.pop()
    else:
      # visit the next node
      ACTIVE.push(next)
      concatenate zipcode[next] to answer
  print answer

Phần khó nhất là: làm thế nào để tính next_smallest_feasible_node_to_visit()?

Giả sử chúng ta đang ở trạng thái như hình dưới đây, với S, A, B, C nằm trong ngăn xếp ACTIVE và C là HEAD:

Làm thế nào để chọn nút khả thi nhỏ nhất tiếp theo từ C? Chúng ta không thể chọn tùy tiện một nút nối với ngăn xếp ACTIVE. Hãy xem xét 3 kịch bản:

• Kịch bản 1: Mã ZIP của Z nhỏ hơn cả X và Y.
  Nếu chúng ta quay lại từ C -> B -> A -> S để thăm Z, các nút C, B, A sẽ bị đưa vào tập DEAD. Nếu nút X chưa được thăm và chỉ có thể đến được thông qua A, B hoặc C, thì X sẽ trở nên không thể tiếp cận được. Do đó, Z không khả thi nếu việc bỏ các nút trong ngăn xếp làm mất tính liên thông tới các nút chưa thăm.
• Kịch bản 2: Mã ZIP của X < Y < Z.
  Chúng ta có thể thăm X trực tiếp từ C. Sau đó quay về X -> C -> B để thăm Y, rồi từ Y thăm Z. Cuối cùng quay về S qua Z -> Y -> B -> A -> S.
• Kịch bản 3: Mã ZIP của Y < X < Z.
  Chúng ta có thể bỏ C, quay về B để thăm Y. Sau đó bỏ Y, B, quay về A để thăm X. Cuối cùng quay về S để thăm Z.

Một nút là không khả thi nếu bằng cách thăm nó (có thể phải bỏ một số nút trong ACTIVE), một số nút chưa được thăm khác trở nên không thể tiếp cận được từ các nút còn lại trong ACTIVE. Để kiểm tra điều này, chúng ta có thể thực hiện kiểm tra tính liên thông (bằng BFS hoặc DFS) từ nút gốc đến tất cả các nút chưa thăm, tránh các nút trong tập DEAD và các nút định bỏ khỏi ACTIVE.

Thuật toán tìm nút khả thi nhỏ nhất:

1. Kiểm tra các nút lân cận của HEAD hiện tại và ghi lại nút nhỏ nhất chưa thăm.
2. Thử bỏ HEAD hiện tại và quay lại nút trước đó trong ACTIVE. Nếu việc bỏ HEAD làm cho một số nút chưa thăm không thể tiếp cận được, dừng lại và trả về nút nhỏ nhất đã ghi lại. Ngược lại, tạm thời bỏ HEAD và lặp lại bước 1.

Mã giả chi tiết cho việc tìm nút tiếp theo:

  def next_smallest_feasible_node_to_visit():
    temp = new Stack()
    best = EMPTY
    while ACTIVE is not empty:
      HEAD = ACTIVE.top()
      # Check the neighbors of HEAD and record the 
      # next smallest node as best.
      for each neighbor i of HEAD that is not-yet-visited:
        if best == EMPTY or zipcode[i] < zipcode[best]:
          best = i

      # Abandon HEAD and go back up in the ACTIVE stack.
      insert HEAD to the DEAD set
      temp.push(HEAD)
      ACTIVE.pop()

      if there exists a not-yet-visited node that \
        is not reachable from the source node:
        break

    # Restore the ACTIVE nodes and the DEAD set.
    while temp is not empty:
      HEAD = temp.top()
      remove HEAD from the DEAD set
      temp.pop()
      ACTIVE.push(HEAD)

    return best

Độ phức tạp:

Thuật toán tham lam gọi hàm tìm nút khả thi tiếp theo \(N\) lần. Mỗi lần tìm kiếm duyệt qua ngăn xếp ACTIVE có tối đa \(O(N)\) nút. Với mỗi nút trong ACTIVE, chúng ta thực hiện kiểm tra tính liên thông mất \(O(N + M)\) và duyệt qua các nút lân cận. Tổng độ phức tạp là \(O(N^2 \times (N+M))\), với \(N=50\), thuật toán này chạy rất nhanh.

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