21.5 state space และ meet in the middle

ทุกหน้าที่ผ่านมาสร้างคำตอบทีละช่องจนครบ แต่โจทย์อีกแบบให้สถานการณ์เริ่มต้นมา แล้วถามว่าทำการกระทำที่อนุญาตไปเรื่อยๆ จะไปถึงเป้าหมายได้ไหม เช่น ปริศนาข้ามแม่น้ำ การเทน้ำระหว่างขวด หรือการเลื่อนแผ่นป้ายตัวเลข แบบนี้เรียกว่า state space search (การค้นหาในปริภูมิสถานะ) หน้านี้สอนวิธีแทนสถานะในโปรแกรมและค้นด้วย DFS ส่วนครึ่งหลังเป็นหัวข้อเสริม meet in the middle ที่ทำให้โจทย์ N ≤ 40 ซึ่งลองครบ 2^N ไม่ไหว กลายเป็นทันเวลา

สถานะคืออะไร

สถานะ (state) คือข้อมูลที่น้อยที่สุดที่บอกสถานการณ์ตอนนี้ได้ครบ จนรู้ว่าทำอะไรต่อได้บ้าง ส่วนการเปลี่ยนสถานะ (transition) คือการกระทำหนึ่งครั้งที่พาจากสถานะหนึ่งไปอีกสถานะหนึ่ง ก่อนเขียนโค้ดต้องตอบให้ได้สามข้อ

1. สถานะเก็บอะไรบ้าง และเก็บเป็นตัวแปรแบบไหน ยิ่งกะทัดรัดยิ่งดี ถ้าเก็บเป็นจำนวนเต็มตัวเดียวได้ จะจำว่าเคยมาแล้วด้วยอาเรย์ธรรมดาได้
2. จากสถานะหนึ่งไปสถานะไหนได้บ้าง และสถานะไหนผิดกฎ
3. มีสถานะทั้งหมดกี่แบบ ตัวเลขนี้คือขอบเขตของงาน แบบเดียวกับการนับก่อนลองในหน้า 21.1

ต่างจาก backtracking ตรงที่การกระทำย้อนกลับได้ เดินวนกลับมาที่สถานะเดิมได้ จึงต้องจำว่าสถานะไหนเคยไปแล้ว ไม่อย่างนั้นจะวนไม่รู้จบ

ปริศนาข้ามแม่น้ำ

ชาวนา (F) พาหมาป่า (W) แพะ (G) และกะหล่ำปลี (C) อยู่ฝั่งซ้ายของแม่น้ำ เรือลำเล็กมีชาวนาพายได้คนเดียว และพาของไปได้ครั้งละไม่เกินหนึ่งอย่าง ถ้าชาวนาไม่อยู่ หมาป่ากินแพะ และแพะกินกะหล่ำปลี จะพาทุกอย่างข้ามไปฝั่งขวาได้ยังไง

สถานะคือแต่ละตัวอยู่ฝั่งไหน สี่ตัว ตัวละสองฝั่ง เก็บเป็น bitmask 4 bit ได้ bit ที่ 0 ถึง 3 คือ F W G C ตามลำดับ 0 คือฝั่งซ้าย 1 คือฝั่งขวา สถานะเริ่มต้นคือ 0 เป้าหมายคือ 15 (1111) มีสถานะทั้งหมดแค่ 16 แบบ การข้ามหนึ่งครั้งคือสลับ bit ของชาวนา กับ bit ของของที่พาไปด้วยถ้ามี ซึ่งต้องอยู่ฝั่งเดียวกับชาวนา

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

const string letter = "FWGC";
bool visited[16];
vector<int> path;

bool safe(int state)
{
    int farmer = state & 1;
    int wolf = (state >> 1) & 1;
    int goat = (state >> 2) & 1;
    int cabbage = (state >> 3) & 1;
    if (wolf == goat && goat != farmer) {
        return false;
    }
    if (goat == cabbage && goat != farmer) {
        return false;
    }
    return true;
}

bool dfs(int state)
{
    path.push_back(state);
    if (state == 15) {
        return true;
    }
    visited[state] = true; // (1)!
    int farmer = state & 1;
    for (int k = 0; k < 4; k++) {
        if (((state >> k) & 1) != farmer) { // (2)!
            continue;
        }
        int next = state ^ 1;
        if (k > 0) {
            next ^= 1 << k; // (3)!
        }
        if (safe(next) && !visited[next]) {
            if (dfs(next)) {
                return true;
            }
        }
    }
    path.pop_back();
    return false;
}

string show(int state)
{
    string left, right;
    for (int k = 0; k < 4; k++) {
        if ((state >> k) & 1) {
            right += letter[k];
        } else {
            left += letter[k];
        }
    }
    if (left.empty()) {
        left = "-";
    }
    if (right.empty()) {
        right = "-";
    }
    return left + " | " + right;
}

int main()
{
    if (dfs(0)) {
        for (int state : path) {
            cout << show(state) << '\n';
        }
        cout << "crossings " << path.size() - 1 << '\n';
    }
    return 0;
}

1. จดว่ามาถึงสถานะนี้แล้ว ต่างจาก used ใน backtracking ตรงที่ ไม่คืนสภาพ สถานะที่เคยค้นจากตรงนี้แล้วไม่เจอเป้าหมาย มาจากทางไหนก็ไม่เจอเหมือนเดิม ไม่ต้องค้นซ้ำ
2. k = 0 คือข้ามไปคนเดียว ผ่านเงื่อนไขนี้เสมอเพราะ bit ที่ 0 คือตัวชาวนาเอง k = 1 ถึง 3 คือพาของชิ้นที่ k ไปด้วย ซึ่งต้องอยู่ฝั่งเดียวกับชาวนา
3. XOR กับ 1 สลับฝั่งของชาวนา XOR กับ 1 << k สลับฝั่งของของที่พาไป ตามตารางในหน้า 12.3

FWGC | -
WC | FG
FWC | G
C | FWG
FGC | W
G | FWC
FG | WC
- | FWGC
crossings 7

อ่านทีละบรรทัด ซ้ายของ | คือฝั่งซ้าย พาแพะไปก่อน กลับมาตัวเปล่า พาหมาป่าไป แล้วพาแพะกลับมา ซึ่งเป็นจุดที่คนส่วนใหญ่คิดไม่ถึง พากะหล่ำปลีไป กลับมาตัวเปล่า แล้วพาแพะไปเป็นเที่ยวสุดท้าย

เพราะมี visited DFS จึงเข้าแต่ละสถานะไม่เกินครั้งเดียว งานรวมเป็น O(จำนวนสถานะ × จำนวนการกระทำต่อสถานะ) ข้อนี้ไม่เกิน 16 × 4 ครั้ง เล็กมาก โจทย์สถานะจึงทันหรือไม่ทันขึ้นกับว่ามีสถานะกี่แบบ ไม่ใช่ว่าต้องทำกี่ขั้นถึงเป้าหมาย

DFS ได้เส้นทางหนึ่งเส้น ข้อมูลชุดนี้บังเอิญได้ 7 เที่ยวซึ่งน้อยที่สุดพอดี แต่ DFS ไม่ได้รับประกันว่าได้เส้นทางที่สั้นที่สุด เพราะมันเดินลึกไปทางแรกที่เจอก่อนเสมอ ถ้าโจทย์ถามจำนวนครั้งที่น้อยที่สุด ต้องใช้ BFS บนสถานะ ซึ่งไล่สถานะทีละระดับตามจำนวนครั้ง จะเรียนในบทที่ 27 พร้อมกับ BFS บนกราฟ การแทนสถานะที่ฝึกในหน้านี้ใช้ได้ทันที

แทนสถานะแบบอื่น

ถ้าสถานะแปลงเป็นตัวเลขเล็กๆ ไม่ได้ ใช้ set จำสถานะที่เคยไปแทนอาเรย์ได้ ช้ากว่าแต่ใช้ได้กับสถานะทุกแบบ

meet in the middle

หัวข้อนี้เป็นหัวข้อเสริม ถ้าอ่านครั้งแรกแล้วยังไม่เข้าใจ ข้ามไปก่อนได้

กลับมาที่การนับเซตย่อยที่ผลรวมเท่ากับ S พอดี ในหน้า 21.4 เห็นแล้วว่าเมื่อ S อยู่กลางๆ ตัดกิ่งแล้วยังเหลือเป็นร้อยล้านกล่องตั้งแต่ n = 30 ถ้า n = 40 ลองครบต้อง 2⁴⁰ ≈ 1.1 × 10¹² แบบ ไม่มีทางทัน

แนวคิดคือ แบ่งของเป็นสองครึ่ง ครึ่งละ 20 ชิ้น เซตย่อยหนึ่งชุดของทั้งหมดคือการเลือกเซตย่อยจากครึ่งซ้ายหนึ่งชุด กับครึ่งขวาหนึ่งชุด ผลรวมรวมกันได้ S ก็ต่อเมื่อ ผลรวมฝั่งซ้าย x บวกผลรวมฝั่งขวา y เท่ากับ S หรือ y = S - x

1. หาผลรวมทุกเซตย่อยของครึ่งซ้าย ได้ 2²⁰ ค่า และของครึ่งขวาอีก 2²⁰ ค่า ด้วย bitmask ในหน้า 21.2
2. เรียงผลรวมของฝั่งขวา
3. สำหรับผลรวม x แต่ละค่าของฝั่งซ้าย นับว่าฝั่งขวามีค่า S - x กี่ตัว ด้วย upper_bound ลบ lower_bound แบบในบทที่ 19

สองฝั่ง "เดินมาพบกันตรงกลาง" แทนที่จะลองคู่ซ้ายขวาครบ 2²⁰ × 2²⁰ คู่ ใช้งานแค่ราว 2²⁰ × 20 ทั้งตอนสร้าง ตอนเรียง และตอนค้น คือ O(2^n/2 · n)

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

vector<long long> all_sums(const vector<long long>& items)
{
    int m = items.size();
    vector<long long> sums(1 << m);
    for (int mask = 0; mask < (1 << m); mask++) { // (1)!
        long long total = 0;
        for (int i = 0; i < m; i++) {
            if ((mask >> i) & 1) {
                total += items[i];
            }
        }
        sums[mask] = total;
    }
    return sums;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long target;
    cin >> n >> target;
    vector<long long> first_half, second_half;
    for (int i = 0; i < n; i++) {
        long long price;
        cin >> price;
        if (i < n / 2) { // (2)!
            first_half.push_back(price);
        } else {
            second_half.push_back(price);
        }
    }
    vector<long long> left = all_sums(first_half);
    vector<long long> right = all_sums(second_half);
    sort(right.begin(), right.end());
    long long ways = 0;
    for (long long x : left) {
        long long need = target - x;
        ways += upper_bound(right.begin(), right.end(), need) - lower_bound(right.begin(), right.end(), need); // (3)!
    }
    cout << ways << '\n';
    return 0;
}

1. ผลรวมของทุกเซตย่อยแบบในหน้า 21.2 แต่เก็บลง vector แทนการหาค่าที่ดีที่สุด ช่องที่ mask คือผลรวมของเซตที่ mask แทน
2. ครึ่งซ้ายได้ n / 2 ชิ้น ครึ่งขวาได้ที่เหลือ ถ้า n เป็นเลขคี่ ฝั่งขวาจะมากกว่าหนึ่งชิ้น ยังใช้ได้ถูกต้อง
3. ช่วงของค่าที่เท่ากับ need ใน vector ที่เรียงแล้ว เริ่มที่ lower_bound และจบก่อน upper_bound ลบกันได้จำนวนตัว ถ้าไม่มีเลย iterator สองตัวชี้ที่ตำแหน่งเดียวกัน ได้ 0

6 50
20 15 30 10 5 25

5

ได้ 5 ตรงกับห้าชุดที่โปรแกรม subset-sum ในหน้า 21.3 พิมพ์ออกมา ตารางนี้เทียบกับการลองครบ 2ⁿ แบบด้วย recursion ที่ไม่ตัดกิ่ง ซึ่งเป็นคนละโปรแกรมกับแถวไม่ตัดในหน้า 21.4 งานในแต่ละกล่องต่างกัน เวลาสองหน้านี้จึงเทียบกันตรงๆ ไม่ได้ ราคาสุ่ม 1 ถึง 10⁶ และ S เท่ากับครึ่งหนึ่งของผลรวม วัดบนเครื่องเดียวกับหน้า 21.1 ค่ากลางของ 3 ถึง 5 ครั้ง

ลองครบเพิ่มขึ้นราว 4 เท่าทุกครั้งที่ n เพิ่ม 2 ถ้าคิดต่อจาก 1.45 วินาทีที่ n = 30 ไปถึง n = 40 จะเป็นราว 1.45 × 1024 ≈ 1,500 วินาที หรือ 25 นาที ส่วน meet in the middle ที่ n = 40 ใช้ไม่ถึงครึ่งวินาที

meet in the middle ใช้ได้เมื่อแบ่งคำตอบเป็นสองส่วนที่ไม่ขึ้นต่อกัน แล้วรวมผลของสองส่วนด้วยการค้นในข้อมูลที่เรียงแล้วได้ ข้อเสียคือใช้หน่วยความจำ 2^n/2 ช่องต่อฝั่ง n = 40 คือราวหนึ่งล้านช่อง ยังสบาย แต่ถ้า n = 60 ต้องใช้ฝั่งละพันล้านช่อง หน่วยความจำไม่พอแล้ว

ลองทำให้พัง

ลืมเช็กว่าเคยมาแล้ว

ในโปรแกรม river เปลี่ยน if (safe(next) && !visited[next]) เป็น if (safe(next)) คอมไพล์ผ่านโดยไม่มีคำเตือน แต่พอรัน หน้าต่างดำไม่พิมพ์อะไรเลย แล้ว Code::Blocks ขึ้นว่า

Process returned -1073741571 (0xC00000FD)

0xC00000FD คือ stack overflow แบบในหน้า 9.1 ชาวนาพาแพะข้ามไป (สถานะ 5) จากนั้นตัวเลือกแรกคือข้ามกลับมาคนเดียว (สถานะ 4) แล้วตัวเลือกแรกของสถานะ 4 ก็คือข้ามกลับไปคนเดียวอีก ได้สถานะ 5 เดิม วนสองสถานะนี้ไปเรื่อยๆ ทุกรอบเรียก dfs ซ้อนเพิ่มอีกชั้น จน stack เต็ม การกระทำที่ย้อนกลับได้ทำให้ state space มีวงวนเสมอ ต้องจำสถานะที่เคยไปทุกครั้ง

สรุป

• สถานะคือข้อมูลที่น้อยที่สุดที่บอกสถานการณ์ได้ครบ แทนให้กะทัดรัด เช่น bitmask หรือเลขไม่กี่ตัว แล้วนับว่ามีกี่แบบ
• DFS บนสถานะต้องจำ visited และไม่คืนสภาพ ลืมเช็กแล้วจะวนจน stack overflow
• DFS หาเส้นทางได้ แต่ไม่รับประกันว่าสั้นที่สุด ต้องการน้อยครั้งที่สุดใช้ BFS บนสถานะในบทที่ 27
• meet in the middle แบ่งเป็นสองครึ่ง หาคำตอบทุกแบบของแต่ละครึ่ง เรียงฝั่งหนึ่ง แล้วค้นคู่ด้วย binary search ลดจาก O(2ⁿ) เป็น O(2^n/2 · n) ทำให้ n = 40 ทันเวลา

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