ปัญหาเป้นเศษส่วน: อัลกอริธึมโลภพร้อมตัวอย่าง

กลยุทธ์โลภคืออะไร?

อัลกอริทึมที่โลภ เลือกตัวเลือกที่ดีที่สุดในแต่ละขั้นตอนโดยหวังว่าลำดับของค่าเหมาะสมที่สุดเฉพาะที่ จะนำไปสู่คำตอบที่เหมาะสมที่สุดโดยรวม เช่นเดียวกับการเขียนโปรแกรมเชิงพลวัต (Dynamic Programming) วิธีการนี้มุ่งเป้าไปที่ปัญหาการหาค่าเหมาะสมที่สุด แต่จะไม่หวนกลับไปพิจารณาการตัดสินใจก่อนหน้านี้อีก

อัลกอริทึมแบบโลภ (Greedy algorithms) มักเขียนง่าย รวดเร็ว (โดยส่วนใหญ่ใช้เวลาเชิงเส้นหรือกำลังสอง) แก้ไขข้อผิดพลาดได้ง่าย และใช้หน่วยความจำน้อย ข้อเสียคือผลลัพธ์อาจไม่เหมาะสมที่สุดเสมอไป ดังนั้นกลยุทธ์นี้จึงใช้ได้ผลเฉพาะกับปัญหาที่มีโครงสร้างที่ปลอดภัยต่อการใช้อัลกอริทึมแบบโลภเท่านั้น

กลยุทธ์แบบโลภ (Greedy strategies) แก้ปัญหาการหาค่าเหมาะสมที่สุดเชิงการจัดเรียง (combinatorial optimization) โดยการสร้างโซลูชัน A ที่มีส่วนประกอบ Ai ทีละส่วน ในแต่ละขั้นตอน คุณจะเลือก Ai อย่างเหมาะสมที่สุดภายใต้ข้อจำกัดที่มีอยู่ และลดขนาดปัญหาให้เหลือปัญหาย่อยที่เล็กลง

วิธีการแบบโลภ (greedy method) ที่ถูกต้องจะต้องมีคุณสมบัติสองประการดังนี้:

1. คุณสมบัติการเลือกอย่างโลภ: จุดเหมาะสมที่สุดเฉพาะที่ในแต่ละขั้นตอนจะนำไปสู่จุดเหมาะสมที่สุดโดยรวม การเลือกขึ้นอยู่กับการตัดสินใจในอดีต แต่ไม่ขึ้นอยู่กับการตัดสินใจในอนาคต
2. โครงสร้างพื้นฐานที่เหมาะสมที่สุด: คำตอบที่ดีที่สุดของปัญหาทั้งหมดนั้นประกอบด้วยคำตอบที่ดีที่สุดของปัญหาย่อยต่างๆ ด้วย

อัลกอริธึมที่มีความโลภมีห้าองค์ประกอบ:

1. ชุดตัวเลือกที่ใช้ในการสร้างโซลูชัน
2. ฟังก์ชันการคัดเลือกที่เลือกผู้สมัครที่ดีที่สุดถัดไป
3. ฟังก์ชันตรวจสอบความเป็นไปได้ที่ตรวจสอบว่าผู้สมัครสามารถต่อยอดจากวิธีแก้ปัญหาบางส่วนในปัจจุบันได้หรือไม่
4. ฟังก์ชันเป้าหมายที่ประเมินค่าของคำตอบที่สมบูรณ์หรือบางส่วน
5. ฟังก์ชันประเมินผลที่จะส่งสัญญาณเมื่อการแก้ปัญหาเสร็จสมบูรณ์

ความคิดของคนโลภ

Greedy One จัดเรียงแพ็กเกจตามมูลค่าเพียงอย่างเดียว:

• จัดเรียงพัสดุตามมูลค่าจากน้อยไปมาก
• ไล่ดูรายการที่จัดเรียงแล้ว และใส่พัสดุแต่ละชิ้นลงในกระเป๋าเป้หากยังมีพื้นที่เหลืออยู่

กฎนี้ไม่ได้ให้คำตอบที่ดีที่สุดเสมอไป ตัวอย่างค้าน:

• พารามิเตอร์: n = 3, M = 19
• แพ็คเกจ: {i = 1; W = 14; V = 20}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 8} — มีมูลค่าสูงแต่ก็มีน้ำหนักมากด้วย
• ผู้เล่นที่โลภมากจะเลือกแพ็กเกจที่ 1 ซึ่งมีมูลค่ารวม 20 ในขณะที่ตัวเลือกที่เหมาะสมที่สุด (แพ็กเกจที่ 2, แพ็กเกจที่ 3) มีมูลค่ารวม 24

ความคิดของ Gredy Two

บริษัท Greedy Two คัดแยกพัสดุตามน้ำหนักเพียงอย่างเดียว:

• จัดเรียงพัสดุตามลำดับน้ำหนักจากมากไปน้อย
• ไล่ดูรายการที่จัดเรียงแล้ว และใส่พัสดุแต่ละชิ้นลงในกระเป๋าเป้หากยังมีพื้นที่เหลืออยู่

กฎนี้ก็ไม่ใช่กฎที่ดีที่สุดเช่นกัน ตัวอย่างค้าน:

• พารามิเตอร์: n = 3, M = 11
• แพ็คเกจ: {i = 1; W = 5; V = 10}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 28} — น้ำหนักเบาแต่มีมูลค่าต่ำ
• การเลือกแบบโลภ (แพ็คเกจ 1, แพ็คเกจ 2) มีมูลค่ารวม 26 ในขณะที่ตัวเลือกที่เหมาะสมที่สุด (แพ็คเกจ 3) มีมูลค่า 28

ความคิดของ Gredy Three

วิธีการ Greedy Three แก้ปัญหาทั้งสองอย่างโดยการรวมค่าและน้ำหนักเข้าไว้ในคีย์การจัดอันดับเดียว ซึ่งเป็นวิธีการมาตรฐานสำหรับปัญหา Fractional Knapsack Problem

• คำนวณต้นทุนต่อหน่วย V[i] / W[i] สำหรับทุกแพ็คเกจ
• จัดเรียงพัสดุตามลำดับราคาต่อหน่วยจากน้อยไปมาก
• ตรวจสอบรายการที่เรียงลำดับแล้ว และเพิ่มแพ็คเกจแต่ละรายการหากพื้นที่ว่างที่เหลืออยู่สามารถรองรับได้

การเรียงลำดับแบบโลภสามแบบตามต้นทุนต่อหน่วย V[i] / W[i]

ความคิด: คำนวณอัตราส่วนมูลค่าต่อน้ำหนัก V[i] / W[i] สำหรับทุกแพ็คเกจ เรียงลำดับจากมากไปน้อย และเลือกอัตราส่วนที่มากที่สุดที่มีอยู่ก่อน จนกว่ากระเป๋าจะเต็ม

เพื่อความจริง เป็นเศษส่วน อีกรูปแบบหนึ่งคือ เมื่อบรรจุภัณฑ์ชิ้นต่อไปไม่สามารถใส่ได้ทั้งหมด ให้เลือกเศษส่วนที่พอดีกับความจุที่เหลืออยู่ กฎเพิ่มเติมนี้เองที่ทำให้ Greedy Three เป็นวิธีที่ดีที่สุดอย่างพิสูจน์ได้ในเกม Fractional Knapsack

ขั้นตอนของอัลกอริธึม

สำหรับรูปแบบ branch-and-bound 0/1 รายการต้นทุนต่อหน่วยที่เรียงลำดับแล้วจะขับเคลื่อนโครงสร้างต้นไม้ค้นหา:

• ขั้นตอนที่ 1: โหนดรากแทนกระเป๋าเป้ที่ว่างเปล่า มูลค่ารวม = 0 ขอบเขตบน = M × ต้นทุนต่อหน่วยสูงสุด
• ขั้นตอนที่ 2: แตกกิ่งรากตามจำนวนสำเนาของแพ็กเกจที่มีอัตราส่วนมากที่สุดที่สามารถบรรจุได้ สำหรับโหนดลูกแต่ละโหนด ให้คำนวณค่ารวม (TotalValue) ความจุที่เหลือ (M) และขอบเขตบน (UpperBound) ใหม่
• ขั้นตอนที่ 3: เริ่มขยายขอบเขตบนสุดที่ใหญ่ที่สุดของเด็กก่อน โดยหวังว่าจะได้คำตอบที่ดีอย่างรวดเร็ว
• ขั้นตอนที่ 4: ตัดโหนดใดๆ ที่มีค่า UpperBound ไม่ดีไปกว่าโซลูชันที่สมบูรณ์ที่ดีที่สุดในปัจจุบัน
• ขั้นตอนที่ 5: เมื่อทุกโหนดได้รับการขยายหรือตัดแต่งแล้ว โซลูชันที่สมบูรณ์และดีที่สุดในปัจจุบันจะถือว่าเหมาะสมที่สุด

รหัสเทียมสำหรับอัลกอริทึมโลภแบบ Fractional Knapsack บริสุทธิ์:

Fractional Knapsack (Array W, Array V, int M)
1. for i <- 1 to size(V)
2.     cost[i] <- V[i] / W[i]
3. Sort-Descending(cost)
4. total <- 0
5. i <- 1
6. while (i <= size(V) and M > 0)
7.     if W[i] <= M
8.         M <- M - W[i]
9.         total <- total + V[i]
10.        i <- i + 1
11.    else
12.        total <- total + V[i] * (M / W[i])
13.        M <- 0

ความซับซ้อนของอัลกอริทึม:

• การใช้การเรียงลำดับแบบง่าย (การเลือกหรือแบบฟอง): O(n²).
• การใช้ Quick Sort หรือ Merge Sort: O(n log n) โดยประสิทธิภาพส่วนใหญ่ขึ้นอยู่กับขั้นตอนการเรียงลำดับ

Java Code สำหรับ Greedy Three

กำหนด KnapsackPackage คลาสที่มีน้ำหนัก มูลค่า และต้นทุนที่ได้มา (อัตราส่วน V/W ที่ใช้ในการจัดเรียง):

public class KnapsackPackage {

    private double weight;
    private double value;
    private Double cost;

    public KnapsackPackage(double weight, double value) {
        super();
        this.weight = weight;
        this.value = value;
        this.cost = Double.valueOf(value / weight);
    }

    public double getWeight() { return weight; }

    public double getValue() { return value; }

    public Double getCost()  { return cost; }
}

จากนั้นสร้างฟังก์ชันที่ใช้หลักการ Greedy Three:

public void knapsackGreProc(int W[], int V[], int M, int n) {
    KnapsackPackage[] packs = new KnapsackPackage[n];
    for (int i = 0; i < n; i++) {
        packs[i] = new KnapsackPackage(W[i], V[i]);
    }

    Arrays.sort(packs, new Comparator<KnapsackPackage>() {
        @Override
        public int compare(KnapsackPackage a, KnapsackPackage b) {
            return b.getCost().compareTo(a.getCost());
        }
    });

    double remain = M;
    double result = 0d;

    for (int i = 0; i < n && remain > 0; i++) {
        if (packs[i].getWeight() <= remain) {
            remain -= packs[i].getWeight();
            result += packs[i].getValue();
            System.out.println("Pack " + i + " - Weight " + packs[i].getWeight()
                             + " - Value " + packs[i].getValue());
        } else {
            double fraction = remain / packs[i].getWeight();
            result += packs[i].getValue() * fraction;
            System.out.println("Pack " + i + " - Fraction " + fraction
                             + " - Value " + packs[i].getValue() * fraction);
            remain = 0;
        }
    }

    System.out.println("Max Value:\t" + result);
}

ฟังก์ชัน knapsackGreProc() ใน Java

คำอธิบายของรหัส:

1. ห่ออินพุตทั้งหมดไว้ใน KnapsackPackage ดังนั้นคีย์การจัดเรียง (อัตราส่วน V/W) จึงถูกคำนวณไว้ล่วงหน้าแล้ว
2. เรียงลำดับตามราคาจากมากไปน้อย
3. ถ้ากล่องแต่ละกล่องใส่ได้พอดี ให้ยกไปทั้งกล่อง
4. นำส่วนหนึ่งของบรรจุภัณฑ์ถัดไปมาเติมลงในช่องว่างที่เหลืออยู่
5. หยุดทันทีที่ความจุที่เหลืออยู่เป็นศูนย์

หมายเหตุการแก้ไข: ต้นตำรับ Java ลูปขั้นสูง i เฉพาะในกรณีที่พัสดุไม่พอดี ซึ่งทำให้ต้องหยิบพัสดุชิ้นเดิมซ้ำๆ เวอร์ชันข้างต้นจะเพิ่มพัสดุทีละชิ้นต่อรอบ และเพิ่มขั้นตอนการเติมแบบเศษส่วน ซึ่งตรงกับกฎ Fractional Knapsack ที่แท้จริง

Java ไดรเวอร์ที่รันอัลกอริทึมกับตัวอย่างที่ใช้งานแล้ว:

public void run() {
    int W[] = new int[]{15, 10, 2, 4};
    int V[] = new int[]{30, 25, 2, 6};
    int M = 37;
    int n = V.length;
    knapsackGreProc(W, V, M, n);
}

Python3 Code สำหรับ Greedy Three

ขั้นแรกให้กำหนดนิยามของ KnapsackPackage ชั้นเรียน __lt__ วิธีการนี้ทำให้สามารถจัดเรียงตามต้นทุนได้โดยตรง:

class KnapsackPackage(object):
    """Knapsack Package Data Class"""

    def __init__(self, weight, value):
        self.weight = weight
        self.value  = value
        self.cost   = value / weight

    def __lt__(self, other):
        return self.cost < other.cost

จากนั้นให้ดำเนินการตามขั้นตอน Fractional Knapsack:

class FractionalKnapsack(object):

    def knapsackGreProc(self, W, V, M, n):
        packs = [KnapsackPackage(W[i], V[i]) for i in range(n)]
        packs.sort(reverse=True)

        remain = M
        result = 0

        for i in range(n):
            if remain == 0:
                break
            if packs[i].weight <= remain:
                remain -= packs[i].weight
                result += packs[i].value
                print("Pack", i, "- Weight", packs[i].weight, "- Value", packs[i].value)
            else:
                fraction = remain / packs[i].weight
                result += packs[i].value * fraction
                print("Pack", i, "- Fraction", fraction,
                      "- Value", packs[i].value * fraction)
                remain = 0

        print("Max Value:", result)

ฟังก์ชัน knapsackGreProc() ใน Python

หมายเหตุการแก้ไข: ต้นตำรับ Python คลาสได้กำหนดค่าว่างไว้ __init__ โดยไม่มีร่างกาย ซึ่งทำให้เกิดการยกขึ้น IndentationErrorเวอร์ชันด้านบนได้ลบตัวสร้างที่ว่างเปล่าออกไป เนื่องจากไม่จำเป็นต้องใช้

ไดรเวอร์ที่รันอัลกอริทึมในตัวอย่างแรก:

if __name__ == "__main__":
    W = [15, 10, 2, 4]
    V = [30, 25, 2, 6]
    M = 37
    n = 4

    proc = FractionalKnapsack()
    proc.knapsackGreProc(W, V, M, n)

C# Code สำหรับ Greedy Three

กำหนด KnapsackPackage ระดับ:

using System;

namespace KnapsackProblem
{
    public class KnapsackPackage
    {
        private double weight;
        private double value;
        private double cost;

        public KnapsackPackage(double weight, double value)
        {
            this.weight = weight;
            this.value  = value;
            this.cost   = value / weight;
        }

        public double Weight { get { return weight; } }
        public double Value  { get { return value; } }
        public double Cost   { get { return cost; } }
    }
}

ใช้ Greedy Three ร่วมกับขั้นตอนการเติมแบบเศษส่วน:

public void KnapsackGreProc(int[] W, int[] V, int M, int n)
{
    KnapsackPackage[] packs = new KnapsackPackage[n];
    for (int k = 0; k < n; k++)
        packs[k] = new KnapsackPackage(W[k], V[k]);

    Array.Sort<KnapsackPackage>(packs,
        (a, b) => b.Cost.CompareTo(a.Cost));

    double remain = M;
    double result = 0d;

    for (int i = 0; i < n && remain > 0; i++)
    {
        if (packs[i].Weight <= remain)
        {
            remain -= packs[i].Weight;
            result += packs[i].Value;
            Console.WriteLine("Pack " + i + " - Weight " + packs[i].Weight
                            + " - Value " + packs[i].Value);
        }
        else
        {
            double fraction = remain / packs[i].Weight;
            result += packs[i].Value * fraction;
            Console.WriteLine("Pack " + i + " - Fraction " + fraction
                            + " - Value " + packs[i].Value * fraction);
            remain = 0;
        }
    }

    Console.WriteLine("Max Value:\t" + result);
}

ฟังก์ชัน KnapsackGreProc() ใน C#

ตัวอย่างค้าน: Greedy Three บน Knapsack 0/1

Greedy Three เหมาะที่สุดสำหรับรูปแบบ Fractional แต่ใน Knapsack แบบ 0/1 (ที่ไม่สามารถแบ่งไอเท็มได้) อาจมีกลยุทธ์อื่นที่ดีกว่า ตัวอย่างค้าน:

• พารามิเตอร์: n = 3, M = 10
• แพ็คเกจ: {i = 1; W = 7; V = 9; ราคา = 9/7}, {i = 2; W = 6; V = 6; ราคา = 1}, {i = 3; W = 4; V = 4; ราคา = 1}
• ตัวเลือกแบบโลภมาก (Greedy Three) เลือกแพ็กเกจ 1 ซึ่งมีมูลค่ารวม 9 ในขณะที่ตัวเลือกที่เหมาะสมที่สุด 0/1 (แพ็กเกจ 2, แพ็กเกจ 3) จะมีมูลค่ารวม 10

บทเรียน: ใช้ Greedy Three เฉพาะเมื่ออนุญาตให้ใช้เศษส่วนเท่านั้น สำหรับกรณี 0/1 ให้ใช้ การเขียนโปรแกรมแบบไดนามิก แทน.

การประยุกต์ใช้กระเป๋าเป้สะพายหลังแบบเศษส่วน

• การขนถ่ายสินค้าที่สามารถแบ่งตามน้ำหนักได้ ไม่ว่าจะเป็นของเหลว ผง หรือสินค้าเทกอง
• การจัดสรรพอร์ตการลงทุนในตัวเลือกการลงทุนที่ยอมรับการระดมทุนบางส่วน
• การแบ่งปันแบนด์วิดท์บนคลาวด์ที่ช่วยให้การรับส่งข้อมูลใช้แบนด์วิดท์เพียงเศษเสี้ยวของลิงก์
• การจัดตารางการทำงานของ CPU ภายใต้โมเดลการแบ่งเวลาใช้งานร่วมกัน โดยมีภาระงานที่สามารถแบ่งได้
• การจัดสรรทรัพยากร AI ที่งานฝึกฝนสามารถใช้ GPU เพียงบางส่วนได้

คำถามที่พบบ่อย