Bitmask DP: nhớ tập đã chọn qua bài người du lịch

Vì sao không chỉ nhớ số lượng đã thăm?

Bài người du lịch trong ví dụ yêu cầu xuất phát ở đỉnh 0, thăm mỗi đỉnh còn lại đúng một lần rồi quay về 0, tổng chi phí nhỏ nhất. Ma trận cost[u][v] cho biết giá đi trực tiếp từ u sang v. Đây là một chu trình qua đủ đỉnh, khác chỉ tìm đường ngắn nhất giữa hai điểm.

Hai đường cùng thăm ba đỉnh nhưng khác tập đã dùng có những lựa chọn tương lai khác nhau. Ngay cả cùng một tập, nếu đang đứng ở hai đỉnh khác nhau thì chi phí bước tới đỉnh tiếp theo cũng khác. Do đó trạng thái cần giữ tập cụ thể và điểm kết thúc, không chỉ số lượng thành phố đã ghé.

Vét cạn mọi hoán vị n−1 đỉnh sau điểm 0 là cách đối chứng dễ hiểu, nhưng số thứ tự tăng theo giai thừa. DP gộp những lịch sử có cùng tập đã thăm và cùng điểm cuối, vì chúng có cùng khả năng tiếp diễn; chỉ giữ chi phí tốt nhất trong số đó.

Mask là tập, không phải một số đếm

Với n=4, dùng bốn bit từ 0 tới 3. Mask 0001 nghĩa chỉ có đỉnh 0; 1011 nghĩa có các đỉnh 0,1,3; 1111 là đủ cả bốn đỉnh. Bit thấp nhất ở bên phải, nên đỉnh 0 tương ứng bit ngoài cùng bên phải trong cách viết này.

Kiểm đỉnh v đã có bằng (mask >> v) & 1. Thêm đỉnh v dùng mask | (1 << v). Phép OR đặt bit thành 1 mà không làm đổi những bit khác. Không dùng cộng tùy ý để “thêm” nếu chưa bảo đảm bit đó đang bằng 0, vì có thể phát sinh nhớ sang bit khác.

Những phép này chỉ quản lý tập. Ý nghĩa DP đến từ việc chọn dữ liệu lưu cho từng tập và cách chuyển, không phải do mask tự chứa đáp án tối ưu.

Trạng thái và chuyển của TSP

Đặt dp[mask][u] là chi phí nhỏ nhất của một đường bắt đầu ở 0, đã thăm đúng tập mask, kết thúc ở u. Chỉ những trạng thái có bit 0 và bit u trong mask mới có ý nghĩa. Khởi tạo dp[1][0]=0; các trạng thái khác là INF.

Từ một trạng thái hữu hạn, chọn v chưa có trong mask. Tập mới là mask có thêm bit v, điểm cuối thành v, chi phí ứng viên dp[mask][u]+cost[u][v]. Cập nhật min. Vì chỉ thêm đỉnh chưa thăm, ta không lặp đỉnh ở phần đường đi đang xây.

Khi mask đã đủ, đường mới thăm xong mọi đỉnh nhưng chưa khép chu trình. Phải thử dp[full][u]+cost[u][0] qua các điểm cuối u. Quên cạnh quay về sẽ giải một bài đường Hamilton có đầu xuất phát cố định, không phải chu trình TSP của ví dụ.

Chạy tay vài trạng thái của bốn đỉnh

Chi phí giữa các cặp trong ma trận mẫu đối xứng: 0–1 là 10, 0–2 là 15, 0–3 là 20, 1–2 là 35, 1–3 là 25, 2–3 là 30. Code cũng xử lý được ma trận có hướng không đối xứng; mẫu đối xứng chỉ giúp nhìn chu trình dễ hơn.

Từ trạng thái cuối trong bảng, quay 2 → 0 tốn 15, tổng 80. Một điểm cuối khác cũng có thể tạo tổng 80, chẳng hạn đường 0 → 2 → 3 → 1 rồi về 0. DP chỉ trả giá trị tối ưu, không khẳng định chu trình là duy nhất.

Thứ tự mask tăng dùng được vì khi thêm một bit chưa có, giá trị mask mới lớn hơn mask cũ. Tất cả chuyển đi sang tập lớn hơn nên không có vòng phụ thuộc. Có thể duyệt theo số bit 1 hoặc dùng top-down có nhớ, miễn giữ cùng định nghĩa trạng thái.

Code C++ và Python

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
long long tsp(const vector<vector<long long>>& cost){
    int n=cost.size(),limit=1<<n;const long long INF=1LL<<60;
    vector<vector<long long>> d(limit,vector<long long>(n,INF));d[1][0]=0;
    for(int mask=1;mask<limit;++mask)for(int u=0;u<n;++u)if(d[mask][u]!=INF){
        for(int v=0;v<n;++v)if(!(mask>>v&1)){
            int next=mask|(1<<v);
            d[next][v]=min(d[next][v],d[mask][u]+cost[u][v]);
        }
    }
    long long answer=INF;
    for(int u=0;u<n;++u)answer=min(answer,d[limit-1][u]+cost[u][0]);
    return answer;
}
int main(){
    int n=4;vector<vector<long long>> c={{0,10,15,20},{10,0,35,25},{15,35,0,30},{20,25,30,0}};
    if(cin>>n){c.assign(n,vector<long long>(n));for(auto& row:c)for(auto& x:row)cin>>x;}
    cout<<tsp(c)<<'\n';
}

import sys

def tsp(cost):
    n=len(cost);limit=1<<n;inf=1<<60
    d=[[inf]*n for _ in range(limit)];d[1][0]=0
    for mask in range(1,limit):
        for u in range(n):
            if d[mask][u]==inf:
                continue
            for v in range(n):
                if not (mask>>v)&1:
                    nxt=mask|(1<<v)
                    d[nxt][v]=min(d[nxt][v],d[mask][u]+cost[u][v])
    return min(d[-1][u]+cost[u][0] for u in range(n))

if __name__=='__main__':
    a=list(map(int,sys.stdin.buffer.read().split()))
    cost=[[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]]
    if a:
        n=a[0];cost=[a[1+i*n:1+(i+1)*n] for i in range(n)]
    print(tsp(cost))

Không nhập dữ liệu thì in 80. Input riêng có n rồi ma trận n×n. Hợp đồng ví dụ: 1<=n<=16, mọi cạnh trực tiếp đều tồn tại, chi phí nguyên từ 0 tới một tỷ, đường chéo bằng 0. Đỉnh xuất phát cố định 0, phải quay về 0. Với n=1, kết quả 0 theo quy ước không phải di chuyển.

C++ dùng long long và INF bằng 2 mũ 60; tổng một chu trình trong miền trên nhỏ hơn INF. Nếu đề có cặp đỉnh không nối trực tiếp, cần thêm quy ước INF cho cạnh thiếu, kiểm trước khi cộng và xử lý trường hợp không có chu trình. Không dùng một số 0 để biểu diễn “không có cạnh” khi 0 cũng có thể là giá đi thật.

Hàm hiện trả chi phí, chưa in thứ tự đỉnh. Muốn truy vết, lưu đỉnh trước ở mỗi trạng thái được cải thiện, chọn điểm cuối tối ưu rồi bỏ dần các bit khi đi ngược. Nếu đề cho phép nhiều đáp án, phải phân biệt tối ưu chi phí với một quy tắc phụ chọn thứ tự cụ thể.

Vì sao hai lịch sử có thể gộp vào một ô?

Giả sử hai đường đều bắt đầu ở 0, dùng đúng tập S và kết thúc ở u. Tất cả đỉnh chưa thăm giống nhau, còn cạnh bước tiếp chỉ phụ thuộc u và đỉnh mới. Đường có chi phí thấp hơn không kém hơn đường kia cho mọi phần nối tiếp, nên giữ một giá trị min là đủ.

Nếu đề thêm chi phí phụ thuộc thứ tự đã ghé, lượng nhiên liệu còn lại hoặc một điều kiện lịch sử khác chưa được suy ra từ S,u, hai lịch sử không còn tương đương. Khi đó trạng thái có thể phải thêm dữ liệu. Đừng thấy n nhỏ rồi mặc định mask và last luôn giải được toàn bộ điều kiện.

Một bài phân công công việc đôi khi chỉ cần dp[mask]: số người đã phân công suy ra từ số bit 1, nên không cần last. Ngược lại, TSP không suy điểm đang đứng từ tập đã thăm, vì vậy bỏ last sẽ gộp nhầm các lựa chọn tương lai khác nhau.

Chi phí tăng nhanh theo số phần tử

Có tối đa n·2 mũ n ô, mỗi ô thử n đỉnh tiếp, nên thời gian O(n²·2^n), bộ nhớ O(n·2^n) cho bảng này. Với n=16, có 1.048.576 ô trong cách cấp phát đầy đủ. Không phải ô nào cũng có nghĩa, nhưng code vẫn cấp phát chúng; không dùng số trạng thái hữu hạn để ước lượng thiếu bộ nhớ của bảng.

Python list chứa tham chiếu và số nguyên có chi phí riêng; không lấy 8 byte nhân số ô rồi gọi đó là toàn bộ dung lượng chương trình Python. Tăng n thêm 1 gần như nhân đôi số tập, còn số chiều theo n cũng tăng. Vì vậy không hứa n=20 hoặc 25 sẽ chạy tốt chỉ dựa vào một ví dụ n=4.

Vòng lặp thử mọi tập con của mỗi mask lại có cận khác, thường gặp O(3^n) cho một số kiểu gộp. Không phải mọi DP có bitmask đều là O(n²2^n); hãy đếm số trạng thái và số chuyển của đúng cách cài.

Mask trên lưới hẹp hoặc kết hợp với cây

Với lưới 3×N, mask có thể biểu diễn những ô được chọn trong một cột. Kiểm điều kiện trong cột, rồi xem hai mask ở hai cột kề có tương thích hay không. Khi chiều cao nhỏ, số mẫu cột nhỏ dù N lớn; đây là lý do chọn chiều nào đưa vào mask rất quan trọng.

DP bitmask trên cây có thể dùng mask để biểu diễn một tập thuộc tính hoặc yêu cầu đã đáp ứng trong cây con, rồi gộp giữa các nhánh. Không nhất thiết mask luôn đánh dấu tất cả đỉnh của cây. Cần giải thích mỗi bit là đối tượng gì và vì sao số bit đủ nhỏ trước khi viết phép OR.

Kiểm bằng hoán vị độc lập

Để tự kiểm tra bài toán TSP trên đồ thị nhỏ (n ≤ 8), bạn có thể duyệt mọi hoán vị của các đỉnh từ 1 tới n - 1 (next_permutation trong C++ hoặc itertools.permutations trong Python), cộng tổng trọng số chu trình quay về 0 rồi đối chiếu với bảng quy hoạch động bitmask trên cả ma trận đối xứng lẫn không đối xứng.

Các ca tự thử nên phân biệt đường với chu trình bằng cách làm cạnh quay về rất đắt; thử trường hợp một thứ tự đi rẻ ở đầu nhưng đắt ở cuối. Khi cần truy vết, còn phải kiểm mỗi đỉnh xuất hiện đúng một lần trước khi quay gốc và tổng cạnh khớp chi phí đã báo.

Luyện ngay trên Big-O Coding

Bài người du lịch luyện tập đã thăm và điểm cuối. Lưới 3×N chuyển cách hiểu bit sang mẫu của một cột. Bài bitmask trên cây là phần nâng cao, cần gộp trạng thái các nhánh. Đọc giới hạn và ý nghĩa từng bit ở mỗi đề; code TSP chỉ minh họa một kiểu trạng thái, không giải sẵn hai biến thể còn lại.

Câu hỏi thường gặp

Nguồn tham khảo

• USACO Guide: Bitmask DP
• CP-Algorithms: Bit manipulation
• Python: functools.cache