กำหนดการพลวัตเบื้องต้น (Introduction to Dynamic Programming)

15 May, 2009 - 16:05 — winter_snow

(ต่อไปนี้จะขออนุญาตเรียก Dynamic Programming สั้น ๆ ว่า ไดนามิก หรือ “หมิก” นะคะ)

เนื้อหาในที่นี้มีความยากอยู่พอสมควร ผู้อ่านควรมีความรู้เรื่อง ฟังก์ชั่นเรียกตัวเอง (Recursive function) และ สัญกรณ์โอใหญ่ (Big-O notation) มาก่อน ขอไม่อธิบายหลักการทำงานมา ณ ที่นี้ ผู้อ่านสามารถหาอ่านเพิ่มเติมได้จากวิกิพีเดีย หรือ ที่นี่

คนที่เข้ามาอ่านก็คงสนใจเรื่องการหมิกใช่ไหมคะ ว่าหมิกคืออะไร ดังนั้นก่อนอื่นจะขอแนะนำว่า หลักการของหมิกก็คือ “จะแก้ปัญหาเล็ก ๆ ก่อน แล้วขยายไปยังปัญหาที่ใหญ่กว่าต่อไป”
อ่านแล้วอาจจะงง ไม่เป็นไรค่ะ มีคำอธิบายที่ละเอียดกว่านี้รออยู่

โจทย์: Fibonacci

เราจะเริ่มจากแนะนำปัญหาจำนวนฟีโบนักชี (Fibonacci Number) ก่อนนะคะ

ลำดับฟิโบนักชี คือ ลำดับที่เริ่มต้นด้วย $F_0$ และ $F_1$ (ในที่นี้จะกำหนด $F_0$ = 0 และ $F_1$ = 1) จากนั้น นิยามให้ $F_n = F_{n-1} + F_{n-2}$ สำหรับทุก $n>1$
(สามารถอ่านเรื่องลำดับฟิโบนัคชีเพิ่มเติมได้ที่วิกิพีเดีย)

คำถาม: เมื่อกำหนดค่า $k$ จงหาค่าของ $F_k$

อ๋อ ข้อนี้ไม่ยาก สิ่งแรกที่คุณอาจลองทำคือ เขียน Recursive function ขึ้นมา

int Fibonacci (int k)  {  
        if(n==0)  
                return 0;  
        if(n==1)  
                return 1;  
        return Fibonacci(k-1) + Fibonacci(k-2);  
}

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

เกิดอะไรขึ้น

สมมติว่าคุณใส่ค่า $n = 4$ ให้ฟังก์ชั่น Fibonacci ของคุณ

Fibonacci(4) จะเรียก Fibonacci(3) และ Fibonacci(2)    
        Fibonacci(3) จะเรียก Fibonacci(2) และ Fibonacci(1)  
                Fibonacci(2) จะเรียก Fibonacci(1) และ Fibonacci(0)  
                        Fibonacci(1) จะคืนค่า 1 มา  
                        Fibonacci(0) จะคืนค่า 0 มา  
                Fibonacci(1) จะคืนค่า 1 มา   
        Fibonacci(2) จะเรียก Fibonacci(1) และ Fibonacci(0)  
                Fibonacci(1) จะคืนค่า 1 มา  
                Fibonacci(0) จะคืนค่า 0 มา

อ่านแล้วไม่เข้าใจลำดับการเรียกซ้ำก็ไม่เป็นไร… แต่โปรแกรมนั้นจะรันนานมาก สังเกตได้ว่า ต้องคิดค่า Fibonacci เดิมซ้ำบ่อย ๆ ซึ่งเป็นสาเหตุให้เสียเวลา
ดังนั้น จะทำยังไงจะได้ไม่ต้องเรียกฟังก์ชั่นเดิมซ้ำ ๆ ?

เราสังเกตว่า เวลาเราเรียก Fibonacci(n) ถ้าเราเก็บค่า Fibonacci(n-1) และ Fibonacci(n-2) ไว้ก่อนแล้ว เราก็ไม่จำเป็นต้องคำนวณค่าต่าง ๆ ซ้ำใหม่
และ Fibonacci(n) หาได้จาก Fibonacci(เลขที่น้อยกว่า n) เสมอ เราสามารถปรับปรุงโปรแกรมให้เป็นแบบนี้ได้

F[0] = 0;
F[1] = 1;
for(i=2; i<=k; i++)
        F[i] = F[i-1] + F[i-2];

เวลาโปรแกรมนี้ทำงาน ก็จะใช้เวลา $O(n)$ เช่น สมมติใส่ค่า $n = 4$ เข้าไป

F[0] = 0;
F[1] = 1;
F[2] = F[1] + F[0] = 1;
F[3] = F[2] + F[1] = 2;
F[4] = F[3] + F[2] = 3;

แบบนี้ก็เรียกว่า “หมิก” แล้ว เพราะว่าเราใช้คำตอบของปัญหาที่เล็กกว่า (หรือก็คือ Fibonacci[i-1], Fibonacci[i-2]) ในการคำนวณคำตอบของปัญหาที่ใหญ่กว่า (ในที่นี้ก็คือ Fibonacci[i])

เหนื่อยหรือยังคะ พักก่อนก็ได้นะคะ ^-^

ลองทำเอง

มีตารางขนาด 2×n และมีกระเบื้องขนาด 1×2 และ 2×1 อยู่ (หมุนไม่ได้) ถามว่า จะวางกระเบื้องในตารางนี้ให้เต็มได้กี่วิธี

โจทย์: เลือกตัวเลขที่ไม่ติดกัน

ต่อมา จะขอแนะนำโจทย์ที่ยากขึ้นนะคะ

มีตัวเลขจำนวนเต็มบวกอยู่ n ตัว $(a_1,a_2,\cdots,a_n)$ เราต้องการเลือกตัวเลขหลาย ๆ ตัวในจำนวนนี้ให้ผลรวมตัวเลขมากที่สุด แต่มีเงื่อนไขว่า เราเลือกตัวเลขที่อยู่ติดกันไม่ได้
เช่น สำหรับลำดับตัวเลข

3, 2, 7, 4, 3, 6

ทางเลือกที่ดีที่สุดคือ เลือก 3, 7 และ 6 ได้ผลรวม 16

วิธีคิด

ขอเริ่มจากนิยามค่า $dp_k$ ให้แทน ผลรวมที่มากที่สุดที่เป็นไปได้ เมื่อเราพิจารณาเฉพาะ k ตัวแรก $(a_1,a_2,\cdots,a_k)$ และเราเลือก $a_k$ ด้วย

จะสังเกตได้ว่า $dp_1 = a_1$ และ $dp_2 = a_2$ และ $dp_k = max(dp_{k-2}, dp_{k-3}) + a_k$

ที่เป็นเช่นนี้เพราะว่า พอเราเลือก $a_k$ เราก็เลือก $a_{k-1}$ ไม่ได้ เราก็ต้องไปเลือก $a_{k-2}$ หรือ $a_{k-3}$ แทน แล้วแทนที่เราจะย้อนคิดไปเรื่อยๆว่าจะเอาตัวไหนบ้าง เราก็ใช้ค่า $dp_{k-2}$ หรือ $dp_{k-3}$ ให้เป็นประโยชน์

ตัวอย่าง: เมื่อลำดับที่ให้มาคือ 3, 2, 7, 4, 3, 6

$dp_1$ มีค่า 3 เพราะพิจารณาลำดับย่อย 3 เลือกตัวที่ 1
$dp_2$ มีค่า 2 เพราะพิจารณาลำดับย่อย 3, 2 เลือกตัวที่ 2
$dp_3$ มีค่า 10 เพราะพิจาณาลำดับย่อย 3, 2, 7 เลือกตัวที่ 1 และ 3
$dp_4$ มีค่า 7 เพราะพิจาณาลำดับย่อย 3, 2, 7, 4 เลือกตัวที่ 1 และ 4 — $(max(dp_1,dp_2)+a_4)$
$dp_5$ มีค่า 13 เพราะพิจาณาลำดับย่อย 3, 2, 7, 4, 3 เลือกตัวที่ 1, 3 และ 5 — $(max(dp_2,dp_3)+a_5)$
$dp_6$ มีค่า 16 เพราะพิจาณาลำดับย่อย 3, 2, 7, 4, 3, 6 เลือกตัวที่ 1, 3 และ 6 — $(max(dp_3,dp_4)+a_6)$

คำตอบคือ $max(dp_5,dp_6)$ โดยไม่ต้องพิจารณา $dp_4,dp_3,\cdots$ เพราะในกรณีเหล่านั้น สามารถเพิ่ม $a_6$ แล้วทำให้ได้ผลรวมมากขึ้นได้

เหตุผลที่เราคำนวณ $dp_k = max(dp_{k-2}, dp_{k-3}) + a_k$ ได้ โดยไม่ต้องพิจารณา $dp_{k-4}$ เป็นเพราะว่า เราแน่ใจว่า ค่าจาก $dp_{k-4}$ บวกกับ $a_k$ ไม่ใช่คำตอบที่ดีที่สุด เนื่องจาก เราสามารถเลือก $a_{k-2}$ เพิ่มเข้ามาได้โดยไม่ผิดเงื่อนไข และกรณีนั้นจะอยู่ในกรณีที่เราพิจารณา $dp_{k-2}$

อ่าว ถ้าอย่างงี้ก็จะรู้แค่ว่าค่ามากสุดเป็นเท่าไหร่สิ

ในเมื่อเราอยากรู้ว่าเราเลือกตัวไหนไปบ้าง ไม่ใช่แค่คำตอบ เราก็จะสร้าง array $B$ อีกตัวมาบอกว่า $dp_k$ แต่ละตัวของเรามาจาก $dp_{k-2}$ หรือ $dp_{k-3}$
จากนั้น จะ recursive แสดงคำตอบออกมา

$B_1$ มีค่า -1 (เพราะไม่ได้มาจากตัวไหนเลย)
$B_2$ มีค่า -1
$B_3$ มีค่า 1 เพราะ $dp_3$ มาจาก $dp_1$
$B_4$ มีค่า 1 เพราะ $dp_4$ มาจาก $dp_1$
$B_5$ มีค่า 3 เพราะ $dp_5$ มาจาก $dp_3$
$B_6$ มีค่า 3 เพราะ $dp_6$ มาจาก $dp_3$

คำตอบสุดท้ายของเราคือ $dp_6$ ดังนั้น $a_6 = 6$ เป็นหนึ่งในตัวเลขที่เราเลือก

$B_6$ มีค่า 3 ดังนั้นพิจารณา $dp_3$

พิจารณา $dp_3$ ดังนั้น $a_3 = 7$ เป็นหนึ่งในตัวเลขที่เราเลือก

$B_3$ มีค่า 1 ดังนั้นพิจารณา $dp_1$

พิจารณา $dp_1$ ดังนั้น $a_1 = 3$ เป็นหนึ่งในตัวเลขที่เราเลือก

$B_1$ มีค่า -1 ดังนั้นเราไม่ต้องทำต่อแล้ว

สุดท้าย เราจะได้คำตอบเป็น 3, 7, 6 ตามต้องการ

มีอีกวิธีหนึ่ง

เราไม่ต้องใช้ array $B$ ก็ได้ เวลาเราจะพิจารณาว่า คำตอบเรามาจากตัวไหน ก็ใช้แนวคิดเดียวกับตอนหมิกครั้งแรก
เช่น พิจารณา $dp_6$ ว่ามาจากตัวไหน เราก็ดูว่า $dp_3$ กับ $dp_4$ ตัวไหนมากกว่า แล้วก็ไปทำตัวนั้นต่อ
แต่ว่าโปรแกรมจะทำงานนานขึ้นเล็กน้อย

ถ้าไม่เข้าใจลองอ่านซ้ำดูนะคะ หรือคอมเมนท์ถามไว้ก็ได้ค่ะ

ลองทำเอง

โจทย์ข้อเดิม แต่ตัวเลขอาจติดลบหรือเป็นศูนย์ได้
ก้านกล้วย (โจทย์จากค่ายสสวท.เดือนมกรา 2550)

มีกล้วยลอยอยู่บนฟ้าทุก ๆ 1 เมตร กล้วยแต่ละหวีมีจำนวนกล้วยไม่เท่ากัน
สมมติก้านกล้วยต้องการกินกล้วยหวีที่ i ก้านกล้วยจะต้องเตรียมตัวกระโดดตั้งแต่เมตรที่ i-1 และจะต้องเตรียมตัวลงสู่พื้นตอนเมตรที่ i+1
ก้านกล้วยจะวิ่งตั้งแต่เมตรที่ 1 ถึงเมตรที่ N รอบเดียวเท่านั้นจะกินกล้วยได้มากที่สุดกี่ลูก
ก้านกล้วยไม่สามารถเตรียมกระโดดก่อนเมตรที่หนึ่งได้ แต่สามารถลงสู่พื้นหลังเมตรสุดท้ายได้

ตัวอย่าง
3 4 1 7 2 7 6 — กล้วย
1 2 3 4 5 6 7 8 — เมตรที่

ก้านกล้วยต้องเตรียมกระโดดเมตรที่สาม กระโดดเมตรที่สี่เพื่อเอากล้วยหวีที่มี 7 ลูก ลงสู่พื้นเมตรที่ห้า
เตรียมกระโดดอีกครั้งเมตรที่หก กระโดดเมตรที่ 7 เพื่อเอากล้วยหวีที่มี 6 ลูก ลงสู่พื้นเมตรที่ 8 (ที่ไม่มีกล้วย)
จะกินกล้วยได้ทั้งหมด 13 ลูกด้วยกัน

ขอจบเพียงเท่านี้ละกันนะคะ สำหรับการแนะนำหมิกแบบเบื้องต้น (เดี๋ยวมีภาคต่อ ^^)
ถ้ามีคำแนะนำ ข้อสงสัย อ่านไม่เข้าใจ (ถ้าใช่ก็ขออภัยด้วยค่ะ เพิ่งเคยเขียนบล็อก) ฯลฯ ฝากคอมเมนท์ไว้ได้เลยค่ะ