Problem Solving Greedy

Problem Solving by Searching : 

Problem Solving by Searching Pitak _Polkacha @ hotmail.com

Question : 

Question สมมติ ว่าเรามีเหรียญขนาดดังต่อไปนี้ เหรียญ 10 บาท , เหรียญ 5 บาท , เหรียญ 1 บาท ถ้าต้องการแลกเงิน 89 บาท เราจะได้เงินเหรียญ ทั้งหมดกี่เหรียญ โดยให้ได้จำนวนเหรียญน้อยที่สุด

การค้นหาแบบ Greedy Algorithms : 

การค้นหาแบบ Greedy Algorithms Pitak _Polkacha @ hotmail.com

Concept : Greedy Algorithms : 

Concept : Greedy Algorithms กรีดีอัลกอริธึม เป็นการค้นหาแบบดีที่สุดก่อน (Best first search) : ซึ่ง Greedy search นั้นจะสร้าง heuristic (h(n)) จากจุด n ไปยังgoal ที่ใกล้ที่สุด

Concept : Greedy Algorithms : 

Concept : Greedy Algorithms Evaluation function h(n) = estimate of cost from n to closest goal h(n) = ค่าประมาณต้นทุนจากจุด n ไป goal โดยเป็นระยะทางที่สั้นที่สุด

ขั้นตอนวิธีแบบ กรีดี : Greedy Algorithms : 

ขั้นตอนวิธีแบบ กรีดี : Greedy Algorithms 2. กำหนดโหนดที่เลือกมานี้เป็นสถานะปัจจุบัน 1. เลือกโหนดเริ่มต้นมาหนึ่งโหนด 3. ให้ทำตามขั้นตอนข้างล่าง จนกว่าจะไม่สามารถสร้างโหนดลูกได้อีก 3.1 สร้างสถานะใหม่ของโหนดลูกที่เป็นไปได้ทั้งหมดจากสถานะปัจจุบัน 3.2 จากสถานะใหม่ที่สร้างขึ้นมาทั้งหมด ให้โหนดลูกที่ดีที่สุดออกมาเพียงโหนดเดียว 4. กลับไปที่ขั้นตอนที่ 2

Algorithm : Greedy Algorithms : 

Algorithm : Greedy Algorithms Let S be a solution, Greedy(a[],n) { S=empty; for i from 1 to n { x = Select(a); if Feasible(S,x) S= Union(S,x); } return S; }

Exemple : Greedy Algorithms : 

Exemple : Greedy Algorithms การเดินทางของเซลแมนที่จะต้องเดินทางไปยังเมือง A B C D และ F ซึ่งจะต้องเดินตามเส้นทางเดินตามการแก้ปัญหาด้วยวิธีของ Greedy Algorithms

Exemple : Greedy Algorithms : 

Exemple : Greedy Algorithms B D F D C C B 30 20 50 20 40 15 25 A A F D C B รวมระยะทาง เท่ากับ 20 + 20 + 15 + 25 + 30 = 110

Exemple : Greedy Algorithms : 

Exemple : Greedy Algorithms A B D F เลือก เป็นเมืองเริ่มต้น จากนั้นสร้างโหนด และ หาระยะทางจาก A ถึงเมืองเหล่านี้ได้ 30 50 และ 20 ตามลำดับ จากนั้นเลือก เป็นเมืองเดินต่อ และสร้างโหนด และ ได้ระยะทาง 40 และ 20 ตามลำดับ เลือก เป็นเมืองที่จะเดินต่อ จากนั้นสร้างโหนด ระยะทางได้ 15 เลือก เป็นเมืองสุดท้ายก่อนกลับไปเมือง รวมระยะทาง เท่ากับ 20 + 20 + 15 + 25 + 30 = 110 ซึ่งเป็นระยะทางที่สั้นที่สุด F C D D C B A

Answer : 

Answer สมมติ ว่าเรามีเหรียญขนาดดังต่อไปนี้ เหรียญ 10 บาท , เหรียญ 5 บาท , เหรียญ 1 บาท ถ้าต้องการแลกเงิน 89บาท เราจะได้เงินเหรียญ ทั้งหมดกี่เหรียญ โดยให้ได้จำนวนเหรียญน้อยที่สุด เหรียญ 10 บาท 8 เหรียญ เหรียญ 5 บาท 1 เหรียญ เหรียญ 1 บาท 4 เหรียญ

สรุป : 

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

ขอขอบคุณครับ : 

ขอขอบคุณครับ