21.4 ตัดกิ่งและ branch and bound

backtracking ในหน้า 21.3 ตัดเฉพาะตัวเลือกที่ผิดกฎทันที แต่หลายโจทย์ทุกตัวเลือกถูกกฎหมด เช่น เลือกของชิ้นไหนก็ได้ ปัญหาอยู่ที่ว่าเลือกไปแล้วยังมีหวังได้คำตอบไหม การตัดกิ่ง (pruning) คือการเลิกลงไปในกิ่งของต้นไม้การค้นหาที่รู้แน่แล้วว่าไม่มีคำตอบ หรือไม่มีทางได้คำตอบที่ดีกว่าที่มีอยู่ หน้านี้วัดจำนวนกล่องในต้นไม้ก่อนและหลังตัดกิ่งให้เห็นจริงว่าต่างกันแค่ไหน และรู้จัก branch and bound สำหรับโจทย์หาค่าที่ดีที่สุด

ตัดกิ่งที่ไม่มีทางถูก

ร้านส่งของมีกล่องพัสดุ n กล่อง น้ำหนักต่างๆ รถคันหนึ่งต้องบรรทุกให้หนักเท่ากับ S กิโลกรัมพอดี เลือกกล่องได้กี่แบบ โครงเหมือนผลรวมเซตย่อยในหน้า 21.3 แต่นับแทนการพิมพ์ ระหว่างทางมีสองสถานการณ์ที่รู้ได้ทันทีว่ากิ่งนี้ไม่มีคำตอบ

• เกินไปแล้ว ผลรวมตอนนี้เกิน S น้ำหนักเป็นบวกทั้งหมด เลือกเพิ่มยิ่งหนักขึ้น
• ไม่มีทางถึง ผลรวมตอนนี้บวกน้ำหนักของทุกกล่องที่เหลือยังไม่ถึง S เลือกหมดทุกกล่องก็ยังไม่พอ

ข้อสองต้องรู้น้ำหนักรวมของกล่องที่ i ถึงกล่องสุดท้ายเร็วๆ เตรียมไว้ก่อนเป็นผลรวมสะสมจากท้าย rest[i] แบบในบทที่ 5

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

int n;
long long target;
vector<long long> weight, rest;
long long ways = 0, nodes = 0;

void go(int i, long long sum)
{
    nodes++;
    if (sum > target) { // (1)!
        return;
    }
    if (sum + rest[i] < target) { // (2)!
        return;
    }
    if (i == n) {
        if (sum == target) { // (3)!
            ways++;
        }
        return;
    }
    go(i + 1, sum + weight[i]);
    go(i + 1, sum);
}

int main()
{
    cin >> n >> target;
    weight.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> weight[i];
    }
    sort(weight.rbegin(), weight.rend()); // (4)!
    rest.assign(n + 1, 0);
    for (int i = n - 1; i >= 0; i--) {
        rest[i] = rest[i + 1] + weight[i];
    }
    go(0, 0);
    cout << "ways " << ways << '\n';
    cout << "nodes " << nodes << '\n';
    return 0;
}

1. ตัดกิ่งที่เกินไปแล้ว
2. ตัดกิ่งที่ไม่มีทางถึง rest[i] คือน้ำหนักรวมของกล่องที่ i ถึง n - 1
3. พอ i = n ค่า rest[n] เป็น 0 สองบรรทัดก่อนหน้าจึงบังคับให้ผลรวมเท่ากับ S พอดีอยู่แล้ว แต่ยังตรวจซ้ำตรงนี้ไว้ เพื่อให้ถอดการตัดกิ่งออกทีละอย่างได้โดยคำตอบไม่เพี้ยน
4. เรียงจากหนักไปเบา rbegin กับ rend คือไล่ vector จากท้ายมาหัว การเรียงไม่ทำให้คำตอบเปลี่ยน แต่กล่องหนักที่ถูกตัดสินใจก่อนทำให้ผลรวมเกินเร็วขึ้น กิ่งจึงถูกตัดใกล้ราก

8 20
7 3 12 5 8 2 9 4

ways 8
nodes 117

ลองถอดการตัดกิ่งออกทีละอย่างกับข้อมูลชุดเดียวกัน ทุกแบบได้ ways 8 เท่ากัน ต่างกันที่ nodes

ไม่ตัดเลยได้ 511 = 2⁹ - 1 คือทุกกล่องของต้นไม้ที่แตกสองทางครบ 8 ชั้น ข้อมูล 8 กล่องยังเล็กไป ลองกล่อง 30 กล่องน้ำหนักสุ่ม 100 ถึง 999 กิโลกรัม รวมกัน 17431 กิโลกรัม กับเป้าหมายสามค่า วัดบนเครื่องเดียวกับหน้า 21.1 ค่ากลางของ 3 ครั้ง

อ่านตารางนี้ได้สามเรื่อง

• เป้าหมายเล็ก การตัดเมื่อเกินทำงานหนัก จาก 2 × 10⁹ กล่องเหลือไม่ถึงสองแสน
• เป้าหมายใหญ่เกือบเท่าผลรวมทั้งหมด การตัดเมื่อเกินแทบไม่ช่วย เพราะกว่าจะเกินก็ต้องเลือกเกือบทุกกล่อง แต่การตัดเมื่อไม่มีทางถึงช่วยแทน การตัดสองแบบจึงเสริมกัน
• เป้าหมายครึ่งหนึ่งของผลรวม ยังเหลือ 1.3 × 10⁸ กล่อง เพราะคำตอบมีถึงสองแสนกว่าแบบ และแบบที่เฉียดๆ ก็มีอีกมาก การตัดกิ่งไม่ได้ทำให้เลขชี้กำลังหายไป ถ้า n ใหญ่กว่านี้ต้องใช้วิธีอื่น เช่น meet in the middle ในหน้า 21.5

branch and bound

โจทย์ที่ถามว่า "ดีที่สุดเท่าไร" ตัดกิ่งได้มากกว่านั้นอีก น้องจัดเพลย์ลิสต์เพลงสำหรับเดินทางไปโรงเรียน ใช้เวลาไม่เกิน T นาที มีเพลง n เพลง เพลงที่ i ยาว len นาที และน้องให้คะแนนความชอบ score ควรเลือกเพลงไหนบ้างให้คะแนนรวมมากที่สุด โดยเวลารวมไม่เกิน T

branch and bound (แตกกิ่งและจำกัดเขต) มีสองส่วน

• เก็บคำตอบที่ดีที่สุดที่เจอแล้ว ไว้ในตัวแปร best
• ประมาณขอบเขต (bound) ที่แต่ละกล่อง ประมาณว่าถ้าลงไปในกิ่งนี้ ดีที่สุดจะได้ไม่เกินเท่าไร ถ้าค่าประมาณนั้นไม่มากกว่า best กิ่งนี้ลงไปก็ไม่มีทางได้อะไรดีขึ้น ตัดทิ้งได้

ค่าประมาณต้องมองโลกในแง่ดีเสมอ คือต้องไม่น้อยกว่าคำตอบจริงที่ดีที่สุดของกิ่งนั้น ประมาณเกินไม่เป็นไร แค่ตัดได้น้อยลง แต่ถ้าประมาณต่ำกว่าความจริงแม้แต่ครั้งเดียว อาจตัดกิ่งที่มีคำตอบที่ดีที่สุดทิ้ง แล้วได้คำตอบผิด

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

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

struct Song {
    long long length, score;
};

int n;
long long limit_time;
vector<Song> song;
long long best = 0, nodes = 0;

bool better_ratio(const Song& a, const Song& b)
{
    return a.score * b.length > b.score * a.length; // (1)!
}

long long bound(int i, long long time_left, long long score)
{
    for (int k = i; k < n; k++) {
        if (song[k].length <= time_left) {
            time_left -= song[k].length;
            score += song[k].score;
        } else {
            return score + song[k].score * time_left / song[k].length; // (2)!
        }
    }
    return score;
}

void go(int i, long long time_left, long long score)
{
    nodes++;
    best = max(best, score); // (3)!
    if (i == n || bound(i, time_left, score) <= best) { // (4)!
        return;
    }
    if (song[i].length <= time_left) {
        go(i + 1, time_left - song[i].length, score + song[i].score); // (5)!
    }
    go(i + 1, time_left, score);
}

int main()
{
    cin >> n >> limit_time;
    song.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> song[i].length >> song[i].score;
    }
    sort(song.begin(), song.end(), better_ratio);
    go(0, limit_time, 0);
    cout << "best " << best << '\n';
    cout << "nodes " << nodes << '\n';
    return 0;
}

1. เทียบคะแนนต่อนาที a.score / a.length กับ b.score / b.length โดยคูณไขว้แทนการหาร จึงไม่ต้องใช้ทศนิยม และไม่มีปัญหาปัดเศษ ฟังก์ชันนี้ใช้แทน lambda ได้ คือส่งแค่ชื่อ better_ratio ให้ sort เป็นตัวที่สาม แบบที่หน้า 16.3 บอกไว้และแบบที่ส่งชื่อฟังก์ชันให้ qsort ในหน้า 13.4 ฟังก์ชันต้องคืน true เมื่อ a ต้องมาก่อน b ตามกติกาเดียวกับ lambda
2. เพลงที่ใส่ไม่พอดี ใส่แค่ time_left นาที ได้คะแนนตามสัดส่วน การหารปัดเศษลงไม่ทำให้ค่าประมาณต่ำกว่าความจริง เพราะคะแนนจริงเป็นจำนวนเต็ม และไม่เกินค่าก่อนปัดอยู่แล้ว
3. เพลงที่เลือกมาถึงตรงนี้เป็นเพลย์ลิสต์ที่ใช้ได้จริงแล้ว ไม่ต้องรอถึงชั้นล่างสุด เทียบกับ best ได้เลย
4. ตัดกิ่งเมื่อค่าประมาณที่ดีที่สุดของกิ่งนี้ไม่มากกว่าที่มีอยู่ ใช้ <= เพราะเท่ากันก็ไม่ได้ดีขึ้น
5. ลองเลือกเพลงก่อนไม่เลือก เพลงถูกเรียงตามความคุ้มแล้ว ทางนี้จึงมักพาไปเจอคำตอบดีๆ เร็ว best สูงเร็ว กิ่งอื่นก็ถูกตัดง่ายขึ้น

6 20
6 45
9 59
6 38
7 47
4 21
9 42

best 130
nodes 18

คำตอบคือเพลงยาว 6 7 และ 6 นาที รวม 19 นาที คะแนน 45 + 47 + 38 = 130 ข้อมูลเล็กแค่นี้ต่างกันไม่มาก ถ้าไม่ตัดอะไรเลยแตกครบทุกกิ่งได้ 127 กล่อง ตัดเฉพาะเพลงที่ใส่ไม่ลงได้ 81 กล่อง เพิ่ม bound เหลือ 18 กล่อง พอเพิ่มจำนวนเพลงที่ความยาวและคะแนนสุ่ม 100 ถึง 1000 และ T เท่ากับครึ่งหนึ่งของความยาวรวม ความต่างจะชัดมาก

จากสองพันล้านกล่องเหลือ 67 กล่อง และ n = 100 ก็ยังไม่ถึงสี่ร้อยกล่อง ซึ่งลองครบ 2¹⁰⁰ แบบไม่มีทางทันในชีวิตนี้ แต่ต้องระวังอย่าคิดว่าเร็วแบบนี้เสมอ ข้อมูลสุ่มแบบอิสระเป็นกรณีที่ bound ทำงานง่าย ลองข้อมูลที่คะแนนเท่ากับความยาวบวก 100 ทุกเพลง ทำให้ทุกเพลงคุ้มพอๆ กัน ที่ n = 50 ต้องค้นถึง 908,926 กล่อง ยังเร็วอยู่ (0.018 วินาทีแบบ -O2) แต่มากกว่าข้อมูลสุ่มหลายพันเท่า branch and bound ไม่ได้รับประกันเวลา ต้องลองกับข้อมูลที่แย่ที่สุดที่นึกออกเสมอ

ทำให้ตัดกิ่งได้มาก

1. ตรวจให้เร็ว การตัดกิ่งตรวจทุกกล่อง ถ้าตรวจช้าก็เสียเปรียบ เตรียมผลรวมสะสมหรืออาเรย์จำสถานะไว้ก่อน แบบ rest และ col_used
2. ตัดสินใจเรื่องที่มีผลมากก่อน เรียงกล่องจากหนักไปเบา เรียงเพลงตามความคุ้ม เลือกช่องซูโดกุที่มีตัวเลือกน้อยที่สุดก่อน กิ่งที่ไม่มีหวังจะตายใกล้ราก
3. หาคำตอบดีๆ ให้เจอเร็ว ใน branch and bound ลองทางที่น่าจะดีก่อน หรือตั้ง best เริ่มต้นด้วยคำตอบจากวิธีโลภที่คิดง่ายๆ ยิ่ง best สูงเร็ว ยิ่งตัดได้มาก
4. วัด nodes ทุกครั้ง เพิ่มตัวนับแบบในหน้านี้ แล้วลองกับข้อมูลที่แย่ที่สุด ก่อนส่งให้ลบบรรทัดที่พิมพ์ nodes ออก

ลองทำให้พัง

ค่าประมาณที่ไม่ได้มองโลกในแง่ดี

บางคนคิดว่าการตัดเพลงเป็นท่อนเป็นเรื่องเพ้อฝัน เลยประมาณแบบที่ทำได้จริง คือเติมเพลงที่คุ้มที่สุดเต็มเพลงไปเรื่อยๆ เจอเพลงที่ใส่ไม่ลงก็หยุด ในฟังก์ชัน bound เปลี่ยนบรรทัดที่บวกคะแนนตามสัดส่วนเป็น

            return score;

คอมไพล์ผ่านโดยไม่มีคำเตือน ป้อนข้อมูลชุดเดิมได้

best 118
nodes 17

ได้ 118 ทั้งที่คำตอบจริงคือ 130 ค่าประมาณใหม่คือคะแนนของเพลย์ลิสต์ที่ทำได้จริงแบบหนึ่ง ซึ่งอาจแย่กว่าแบบที่ดีที่สุดของกิ่งนั้น ไล่ดูตามลำดับการค้น โปรแกรมเลือกเพลงคุ้มสุดสองเพลงก่อน คือยาว 6 นาที 45 คะแนน กับยาว 7 นาที 47 คะแนน ถึงกล่องนี้ได้ 92 คะแนน best เป็น 92 และเหลือเวลา 7 นาที ค่าประมาณแบบใหม่เจอเพลงถัดไปยาว 9 นาทีใส่ไม่ลงก็หยุดที่ 92 ซึ่งไม่มากกว่า best กิ่งนี้จึงถูกตัด ทั้งที่เพลงยาว 6 นาที 38 คะแนนที่อยู่ถัดไปอีกเพลงยังใส่ได้ และให้ 130 พอดี ค่าประมาณแบบตัดเพลงเป็นท่อนให้ 92 + 59 × 7 / 9 ปัดลงเป็น 137 จึงไม่ตัดกิ่งนี้ ค่าประมาณที่ใช้ตัดกิ่งต้องไม่มีวันน้อยกว่าคำตอบจริง ถ้าไม่แน่ใจ ให้เทียบผลกับวิธีที่ไม่ตัดกิ่งบนข้อมูลสุ่มขนาดเล็กหลายๆ ชุด แบบ stress test ในหน้า 21.1

สรุป

• ตัดกิ่งคือเลิกลงไปในกิ่งที่รู้แน่ว่าไม่มีคำตอบ หรือไม่มีทางดีกว่าที่มีอยู่
• ผลรวมเซตย่อยตัดได้สองทาง ผลรวมเกินแล้ว และรวมของที่เหลือทั้งหมดก็ยังไม่ถึง สองแบบเสริมกัน
• branch and bound เก็บ best แล้วตัดกิ่งที่ค่าประมาณไม่มากกว่า best ค่าประมาณต้องมองโลกในแง่ดีเสมอ ประมาณต่ำกว่าจริงแล้วได้คำตอบผิด
• เรียงตัวเลือกให้เรื่องสำคัญตัดสินก่อน และหาคำตอบดีๆ ให้เจอเร็ว กิ่งจะถูกตัดใกล้รากมากขึ้น
• การตัดกิ่งไม่ได้รับประกันเวลา วัดจำนวน nodes กับข้อมูลที่แย่ที่สุดที่นึกออกทุกครั้ง