25.5 DP ช่วงและ DP บน bitmask

หน้านี้มีสองแบบที่สถานะไม่ได้เป็นแค่ "i ตัวแรก" แบบหน้าก่อนๆ แบบแรกคือ DP ช่วง (interval DP) สถานะคือช่วงตั้งแต่ i ถึง j และคำตอบของช่วงยาวมาจากช่วงที่สั้นกว่าที่อยู่ข้างใน ใช้กับโจทย์ที่ลำดับการทำมีผลกับต้นทุน เช่น ตัดไม้ คูณเมทริกซ์ หรือรวมกองหิน แบบที่สองคือ DP บน bitmask สถานะคือ เซตของสิ่งที่ทำไปแล้ว เก็บเป็นบิตของจำนวนเต็มตามหน้า 12.3 ใช้กับโจทย์ที่ N เล็กมาก ไม่เกินราว 20 แต่ต้องเลือกลำดับของทุกตัว ซึ่งถ้าลองทุกลำดับจะเป็น N! ทั้งสองแบบเป็นหัวข้อท้ายของ DP ในค่าย 2 อ่านให้เห็นรูปแบบก่อน แล้วค่อยฝึกในแบบฝึกหัด

ตัดไม้ให้ต้นทุนน้อยที่สุด

ร้านไม้มีไม้ยาว L เมตร ลูกค้าขีดจุดที่ต้องตัดไว้ K จุด เลื่อยตัดได้ทีละครั้ง และคิดค่าตัดเท่ากับความยาวของท่อนที่กำลังถูกตัด ตัดจุดไหนก่อนก็ได้ แต่ลำดับการตัดทำให้ค่าตัดรวมต่างกัน ไม้ยาว 10 เมตร ตัดที่ 2 4 และ 7 เมตร มีลำดับให้เลือก 3! = 6 แบบ

ตัดที่ 4 เมตรก่อนดีที่สุด ได้ 20 ครั้งแรกเสียค่า 10 เสมอ เพราะท่อนแรกคือไม้ทั้งท่อน หลังจากนั้นไม้แยกเป็นสองท่อนที่ไม่เกี่ยวกันอีกเลย ท่อนซ้ายตัดยังไงก็ไม่มีผลกับท่อนขวา นี่คือโครงของ DP ช่วง

สถานะเป็นช่วง

เพิ่มจุด 0 กับ L เข้าไปเป็นจุดหัวท้าย ได้ point[0] = 0 ถึง point[K + 1] = L จุดต้องเรียงจากน้อยไปมาก ข้อมูลเข้าในตัวอย่างนี้เรียงมาแล้ว ถ้าโจทย์ไม่รับประกันให้ sort ก่อน

• นิยามสถานะ cost[i][j] คือค่าตัดน้อยที่สุด ที่ตัดทุกจุดที่อยู่ระหว่าง point[i] กับ point[j] ในท่อนที่มีหัวท้ายเป็นสองจุดนี้
• หาความสัมพันธ์ ในท่อนนี้ต้องมีจุดที่ถูกตัดเป็นครั้งแรก สมมติว่าเป็นจุด mid ครั้งแรกเสียค่าความยาวท่อน point[j] - point[i] แล้วเหลือสองท่อนที่แยกกัน จึงได้ cost[i][mid] + cost[mid][j] + (point[j] - point[i]) ลองทุก mid ที่อยู่ระหว่าง i กับ j แล้วเลือกน้อยสุด
• กรณีฐาน j = i + 1 ไม่มีจุดอยู่ระหว่าง ไม่ต้องตัด cost[i][i + 1] = 0
• ลำดับการเติมและคำตอบสุดท้าย ช่วงหนึ่งใช้แค่ช่วงที่สั้นกว่าที่อยู่ข้างใน จึงเติมตาม ความยาวของช่วง จากสั้นไปยาว คำตอบอยู่ที่ cost[0][K + 1]

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int length, k;
    cin >> length >> k;
    vector<int> point(k + 2);
    point[0] = 0;
    for (int i = 1; i <= k; i++) {
        cin >> point[i];
    }
    point[k + 1] = length;
    int m = k + 1;
    vector<vector<long long>> cost(m + 1, vector<long long>(m + 1, 0));
    for (int span = 2; span <= m; span++) { // (1)!
        for (int i = 0; i + span <= m; i++) {
            int j = i + span;
            cost[i][j] = LLONG_MAX; // (2)!
            for (int mid = i + 1; mid < j; mid++) {
                cost[i][j] = min(cost[i][j], cost[i][mid] + cost[mid][j]);
            }
            cost[i][j] += point[j] - point[i];
        }
    }
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= m; j++) {
            if (j <= i + 1) {
                cout << setw(4) << '-';
            } else {
                cout << setw(4) << cost[i][j];
            }
        }
        cout << '\n';
    }
    cout << "min cost = " << cost[0][m] << '\n';
    return 0;
}

1. span คือระยะระหว่าง i กับ j นับเป็นจำนวนจุด ช่วงที่ span เป็น 1 คือกรณีฐาน เป็น 0 อยู่แล้ว จึงเริ่มที่ 2
2. เริ่มด้วยค่าที่ใหญ่กว่าทุกคำตอบ แล้วหาค่าน้อยสุด ค่าความยาวท่อนเหมือนกันทุก mid จึงบวกทีหลังครั้งเดียว

10 3
2 4 7

   -   -   4  11  20
   -   -   -   5  13
   -   -   -   -   6
   -   -   -   -   -
   -   -   -   -   -
min cost = 20

แถวคือ i คอลัมน์คือ j จุดคือ 0 2 4 7 10 ช่องแถว 0 คอลัมน์ 2 คือท่อน 0 ถึง 4 ที่ต้องตัดที่ 2 ค่า 4 ช่องแถว 1 คอลัมน์ 4 คือท่อน 2 ถึง 10 ที่ต้องตัดที่ 4 กับ 7 ได้ 13 ช่องคำตอบมุมขวาบนลอง mid ทั้งสามจุด ตัดที่ 2 ก่อนได้ 0 + 13 + 10 = 23 ตัดที่ 4 ก่อนได้ 4 + 6 + 10 = 20 ตัดที่ 7 ก่อนได้ 11 + 0 + 10 = 21 น้อยสุดคือ 20 ตรงกับตารางที่ลองมือ ช่อง - คือช่องที่ไม่ใช้ เพราะ j ไม่มากกว่า i + 1

มีช่วงราว K²/2 ช่วง แต่ละช่วงลอง mid ไม่เกิน K ตัว เป็น O(K³) K เป็นร้อยสบาย K เป็นพันยังทันถ้าคอมไพล์ -O2

เร็วขึ้นแค่ไหน

วิธีตรงไปตรงมาคือลองทุกลำดับการตัดด้วย next_permutation แบบบทที่ 21 แต่ละลำดับใช้ set ของจุดที่ตัดแล้วในบทที่ 20 หาท่อนที่กำลังตัด เป็น O(K! · K log K) วัดบนเครื่องเดียวกับหน้า 19.1 ไม้ยาว 10⁶ จุดตัดสุ่ม วิธี DP คือโปรแกรม cut-wood-dp ที่ตัดการพิมพ์ตารางออก และเรียงจุดก่อน รันแต่ละแบบ 5 รอบ

จุดตัดเพิ่มทีละจุด วิธีลองทุกลำดับช้าลงราวสิบเท่าขึ้นไปทุกครั้ง เพราะ K! โตเร็วกว่ากำลังสองหรือกำลังสามไปมาก ส่วน DP ที่ K = 1000 ทำงานราว 1.7 × 10⁸ รอบในลูปใน แบบ Code::Blocks ใช้เกินสามวินาที แต่ -O2 ใช้ไม่ถึงหนึ่งในห้าวินาที

ลองทำให้พัง เติมตาม i แทนความยาว

เขียนลูปแบบตารางสองมิติทั่วไป i จากน้อยไปมาก j จากน้อยไปมาก แทนที่จะเติมตามความยาวช่วง

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int length, k;
    cin >> length >> k;
    vector<int> point(k + 2);
    point[0] = 0;
    for (int i = 1; i <= k; i++) {
        cin >> point[i];
    }
    point[k + 1] = length;
    int m = k + 1;
    vector<vector<long long>> cost(m + 1, vector<long long>(m + 1, 0));
    for (int i = 0; i <= m; i++) {
        for (int j = i + 2; j <= m; j++) {
            cost[i][j] = LLONG_MAX;
            for (int mid = i + 1; mid < j; mid++) {
                cost[i][j] = min(cost[i][j], cost[i][mid] + cost[mid][j]);
            }
            cost[i][j] += point[j] - point[i];
        }
    }
    cout << "min cost = " << cost[0][m] << '\n';
    return 0;
}

10 3
2 4 7

min cost = 10

ได้ 10 ซึ่งน้อยกว่า 20 ที่ดีที่สุดจริง เป็นไปไม่ได้ เพราะ 10 คือค่าตัดครั้งแรกอย่างเดียว ตอนเติม cost[0][4] ต้องใช้ cost[1][4] cost[2][4] cost[3][4] ซึ่งอยู่แถวล่างกว่า ยังไม่ถูกเติม ยังเป็น 0 อยู่ ลอง mid = 1 จึงได้ cost[0][1] + cost[1][4] = 0 + 0 โปรแกรมคิดว่าท่อนขวาตัดฟรี DP ช่วงทุกโจทย์ให้วนความยาวช่วงเป็นลูปนอกสุด หรือวน i ถอยหลัง จาก K + 1 ลงมา แล้ว j เดินหน้า ซึ่งก็ทำให้ช่วงข้างในเสร็จก่อนเหมือนกัน

DP บน bitmask

บุรุษไปรษณีย์ต้องออกจากที่ทำการ (จุด 0) ไปส่งของให้บ้านอีก N - 1 หลัง หลังละครั้ง แล้วกลับที่ทำการ รู้ระยะทางระหว่างทุกคู่ ต้องเลือกลำดับบ้านให้ระยะรวมสั้นที่สุด โจทย์นี้ชื่อ travelling salesman problem (TSP) ลองทุกลำดับมี (N - 1)! แบบ N = 13 ก็เกือบห้าร้อยล้านแบบแล้ว

สังเกตว่าระหว่างทาง สิ่งที่มีผลกับเส้นทางที่เหลือมีแค่สองอย่าง คือ ไปบ้านไหนมาแล้วบ้าง กับ ตอนนี้อยู่ที่ไหน ลำดับที่ไปมาแล้วไม่มีผล เก็บ "ไปบ้านไหนมาแล้ว" เป็นจำนวนเต็มหนึ่งตัว ที่บิตที่ k เป็น 1 ถ้าไปจุด k มาแล้ว เรียกว่า bitmask ใช้ตัวดำเนินการระดับบิตจากหน้า 12.3

• นิยามสถานะ best[mask][last] คือระยะทางสั้นที่สุดที่ออกจากจุด 0 ไปครบทุกจุดใน mask พอดี และตอนนี้อยู่ที่จุด last
• หาความสัมพันธ์ จากสถานะหนึ่ง ไปจุด next ที่ยังไม่อยู่ใน mask ได้สถานะ best[mask | (1 << next)][next] ที่อาจสั้นลงเป็น best[mask][last] + dist[last][next]
• กรณีฐาน best[1][0] = 0 ช่องอื่นเริ่มเป็นค่าที่ใหญ่มาก
• ลำดับการเติมและคำตอบสุดท้าย เพิ่มจุดแล้ว mask ใหม่มากกว่า mask เดิมเสมอ จึงวน mask จากน้อยไปมาก คำตอบคือ best[full][last] + dist[last][0] ที่น้อยสุด ซึ่งบวกระยะกลับที่ทำการ

ครั้งนี้เขียนแบบ "ส่งค่าไปข้างหน้า" จากสถานะที่รู้ค่าแล้ว ไปปรับสถานะที่ใหญ่กว่า แทนการดึงค่าจากสถานะที่เล็กกว่าแบบหน้าก่อนๆ ได้ผลเท่ากัน เพราะตอนวนถึง mask ใด ทุก mask ที่เล็กกว่าได้ส่งค่ามาให้ครบแล้ว

#include <bits/stdc++.h>
using namespace std;

const int INF = 1000000000;

int main()
{
    int n;
    cin >> n;
    vector<vector<int>> dist(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> dist[i][j];
        }
    }
    int full = (1 << n) - 1;
    vector<vector<int>> best(1 << n, vector<int>(n, INF));
    best[1][0] = 0;
    for (int mask = 1; mask <= full; mask++) {
        for (int last = 0; last < n; last++) {
            if (best[mask][last] == INF) { // (1)!
                continue;
            }
            for (int next = 0; next < n; next++) {
                if ((mask & (1 << next)) == 0) { // (2)!
                    int grown = mask | (1 << next);
                    best[grown][next] = min(best[grown][next], best[mask][last] + dist[last][next]);
                }
            }
        }
    }
    int answer = INF;
    for (int last = 1; last < n; last++) {
        answer = min(answer, best[full][last] + dist[last][0]);
    }
    cout << "shortest round trip = " << answer << '\n';
    return 0;
}

1. สถานะนี้ยังไปไม่ถึง เช่น mask ที่ไม่มีจุด 0 หรือ last ไม่อยู่ใน mask ข้ามไป และกันไม่ให้ INF บวกระยะจนล้น
2. วงเล็บรอบ mask & (1 << next) จำเป็น ดูในส่วนลองทำให้พัง

4
0 4 8 5
4 0 3 7
8 3 0 2
5 7 2 0

shortest round trip = 14

เส้นที่สั้นที่สุดคือ 0 ไป 1 ไป 2 ไป 3 แล้วกลับ 0 ได้ 4 + 3 + 2 + 5 = 14 มี 2^N × N สถานะ แต่ละสถานะลอง next N ตัว เป็น O(2^N · N²) และใช้หน่วยความจำ 2^N × N ช่อง ที่ N = 20 คือ int ราว 21 ล้านช่อง โปรแกรมนี้ใช้หน่วยความจำจริงสูงสุด 125 MB บนเครื่องเดียวกับหน้า 19.1 เพิ่ม N อีกหนึ่งก็เป็นสองเท่า นี่คือเหตุที่ DP บน bitmask ใช้ได้กับ N ไม่เกินราว 20 ถ้าเห็นโจทย์ที่ N เล็กผิดปกติแบบนี้ ให้นึกถึง bitmask ก่อน

เร็วขึ้นแค่ไหน

วิธีตรงไปตรงมาคือลองทุกลำดับของบ้าน N - 1 หลังด้วย next_permutation แล้วรวมระยะ เป็น O((N - 1)! · N) วัดบนเครื่องเดียวกับหน้า 19.1 ระยะระหว่างทุกคู่สุ่มตั้งแต่ 1 ถึง 1000 รันแต่ละแบบ 5 รอบ

ลองทุกลำดับช้าลงราว 7 ถึง 12 เท่าทุกครั้งที่เพิ่มบ้านหนึ่งหลัง ตาม (N - 1)! ที่คูณเพิ่มด้วย N - 1 ส่วน bitmask เพิ่มบ้านหนึ่งหลัง งานตามทฤษฎีเพิ่มแค่ราวสองเท่า ที่ N = 20 ลูปในทำงานไม่เกินราว 4 × 10⁸ รอบ ก็ยังไม่ถึงครึ่งวินาทีแบบ -O2 ส่วนวิธีลองทุกลำดับที่ N = 20 ต้องลอง 19! ซึ่งเกิน 10¹⁷ ลำดับ

ลองทำให้พัง ลืมวงเล็บ

ในโปรแกรม delivery-tsp เขียนเงื่อนไขเป็น if (mask & 1 << next == 0) ซึ่งอ่านด้วยตาเหมือนถูก compiler ของ Code::Blocks เตือนว่า

delivery.cpp:25:38: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   25 |                 if (mask & 1 << next == 0) {
      |                            ~~~~~~~~~~^~~~

ถ้าไม่สนคำเตือนแล้วรันกับข้อมูลเข้าชุดเดิม ได้

shortest round trip = 1000000000

== ทำก่อน & และ << ทำก่อน == นิพจน์นี้จึงเป็น mask & ((1 << next) == 0) ซึ่ง (1 << next) == 0 เป็นเท็จเสมอ ได้ 0 เงื่อนไขจึงไม่เคยจริง ไม่มีสถานะไหนถูกขยายเลย ทุกช่องของ full ยังเป็น INF คำตอบจึงไม่เคยถูกปรับ พิมพ์ค่าเริ่มต้น INF ออกมา ทุกครั้งที่ใช้ & | หรือ ^ คู่กับการเปรียบเทียบ ให้ใส่วงเล็บเสมอ และอย่าข้ามคำเตือน -Wparentheses

สรุป

• DP ช่วง cost[i][j] ลองทุกจุดแบ่ง mid ระหว่าง i กับ j แล้วรวมสองช่วงย่อย เติมตามความยาวช่วงจากสั้นไปยาว เป็น O(K³)
• ตัดไม้แบ่งที่ "ครั้งแรก" คูณเมทริกซ์ลูกโซ่แบ่งที่ "ครั้งสุดท้าย" โครงเดียวกัน
• เติมผิดลำดับ ช่วงยาวจะใช้ช่วงสั้นที่ยังเป็น 0 ได้คำตอบน้อยเกินจริง
• DP บน bitmask เก็บเซตที่ทำแล้วเป็นบิต best[mask][last] เป็น O(2^N · N²) ใช้เมื่อ N ไม่เกินราว 20
• ใส่วงเล็บรอบ mask & (1 << k) ทุกครั้ง

กลับไปเช็กรายการ ผ่านบทนี้เมื่อ แล้วไปทำแบบฝึกหัด