ถ้าจะทำความเข้า Dynamic Programming ต้องที่นี่

http://peam.blogspot.com/2005/09/dynamic-programming.html

http://peam.blogspot.com/2005/09/dynamic-programming-2.html

http://peam.blogspot.com/2005/10/dynamic-programming-3.html

http://peam.blogspot.com/2005/10/dynamic-programming-4.html

http://peam.blogspot.com/2005/10/dynamic-programming-5.html

ตัวอย่าง .. อธิบายได้ง่ายจริงๆ

Dynamic Programming

…… คุณสมบัติที่ทำให้เราไม่ต้องแบ่ง…
นั่นก็คือ “Optimal Substructure”

มันคืออะไรหว่า???

เอางี้ดีกว่า เอาตัวอย่างไป
สมมุติว่าในห้องมี A, B, P, D มีเงิน 300, 200, -10000000, 900
ถามว่าใครรวยสุดในห้องตอนนี้?
ก็ตอบนาย D ใช่มั้ย?
ถ้านาย T เดินเข้ามาในห้องมีตัง 10000000000 บาท
ถามว่าใครรวยสุดในห้องนี้? ก็ตอบนาย T
แต่ D ก็ยังรวยรองจากนาย T และรวยกว่า A, B, P
ปัญหานี้มี optimal substructure ครับ
เพราะการมาของ T ไม่ทำให้ D จนลงหรือ A, B, P รวยขึ้น

แต่ถ้าเกิด สมมุติว่านาย T เป็นนักการเมือง
เดินมาแล้วแจกเงินคนที่อยู่ในห้องอยู่ก่อนแล้ว ตามความสนิทสนม
เช่น นาย B เป็นคนสวนของนาย T นาย T โอนทรัพย์สินให้ 3000000000 แก่นาย B
นาย P เป็นลูกของนาย T นาย T โอนทรัพย์สินให้ 7000000000 แก่นาย P
นาย D ก็ไม่รวยที่สุดเมื่อพิจารณาในวงเดิม: คือในกลุ่ม A, B, P แล้ว
กลับกลายเป็น นาย P รวยกว่า
ปัญหานี้ไม่มี optimal substructure ครับ

ลองพิจารณา:
เมื่อ T อยู่ในห้องคนเดียว T รวยสุด: 10000000000
เมื่อในห้องมี A,B,P,D, D รวยสุด: 900
เรา จะรวมคำตอบ : ห้องมี A, B, P, D, T โดยไม่อ่าน A, B, P, D, T ทุกตัวใหม่ โดยพิจารณาแค่สิ่งที่เราบันทึกไว้ก่อนตอนที่เราแยกทำ{A,B,P,D}กับ {T}ไว้ก่อนหน้า ไม่ได้
เพราะ T ดันแจกเงินให้คนอื่น ดังนั้นจึงไม่มี optimal substructure ครับ

นั่นก็คือ…
ถ้าไม่มีนักการเมืองชั่วๆ… เอ้ย
ถ้า คำตอบของปัญหาย่อยยังคงเดิม ไม่เปลี่ยนไปตามการเพิ่มขนาดของปัญหา (ซึ่งจะเกิดขึ้นในขั้นตอนรวม) แล้วปัญหานั้นจะมี optimal substructure ครับ

Del.icio.us : ,
Technorati : ,

Advertisements

ใส่ความเห็น

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / เปลี่ยนแปลง )

Twitter picture

You are commenting using your Twitter account. Log Out / เปลี่ยนแปลง )

Facebook photo

You are commenting using your Facebook account. Log Out / เปลี่ยนแปลง )

Google+ photo

You are commenting using your Google+ account. Log Out / เปลี่ยนแปลง )

Connecting to %s