หากมีคำถาม ขอให้ไปโพสต์ลง เว็บบอร์ดจีทูจีเน็ตดอตคอม ตัวใหม่แทนน่ะครับ

หรือติดต่อเข้ามาทาง Inbox ที่ เฟซบุ๊ค ผมครับ

หน้าหลัก
ข่าวสาร - บทความ ทั้งหมด
VB 6/VB.Net
ASP/ASP.Net
จับฉ่ายคอมพิวเตอร์
เรียนรู้ผ่าน Flash Movie
บทความที่มีผู้ตอบล่าสุด  
 RSS Feeds
 ดาวน์โหลดโปรแกรม RSS Reader ได้ที่นี่ ...   Download โปรแกรม RSS Reader

Forum - www.g2gnet.com
Webmaster - www.g2gnet.com
Visitors - Session views
 4 9 7 8 6 5 6

7 ธันวาคม พ.ศ.2549
687 Users On-Line.
Visitors - Page views
 8 2 3 6 5 7 4
1 กุมภาพันธ์ พ.ศ.2551

Google   
เว็บ g2gnet.com
ขนาดตัวอักษร:  

เทคนิคการออกแบบอัลกอริทึม (Algorithm Technique) - Greedy Algorithm

Category »  จับฉ่ายคอมพิวเตอร์
โดย : Webmaster เมื่อ 5/11/2549 10:12:00
(อ่าน : 20722) 

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

และสมมุติว่าเราต้องการแลกเงิน 89 บาท เราจะได้เงินเหรียญดังนี้

เหรียญ 10 บาท จะได้ 8 เหรียญ
เหรียญ 5 บาท จะได้ 1เหรียญ
เหรียญ 1 บาท จะได้ 4 เหรียญ


จะเห็นว่าอัลกอริทึมที่เราใช้ก็คือ เราเลือกเหรียญที่มีค่ามากที่สุด แต่ไม่มากกว่า 89 บาท ออกมาก่อน (เหรียญ 10 บาท ได้ 8 เหรียญ = 80 บาท) จากนั้นลบค่านี้ออกจาก 89 บาท ก็จะเหลือ 9 บาท หลังจากนั้นเราเลือกเหรียญที่มีค่ามากที่สุดแต่ไม่เกิน 9 บาท นั่นก็คือได้เหรียญ 5 บาทอีก 1 เหรียญ แล้วลบค่านี้ออกจาก 9 บาท จะเหลืออยู่อีก 4 บาท และในที่สุดเราก็จะได้เหรียญ 1 บาทอีก 4 เหรียญ

วิธีการนี้เราอาจเรียกได้ว่า "Greedy Algorithm"

อัลกอริทึมนี้มีหลักการอยู่ว่า ในขณะใดๆก็ตาม เราจะหาคำตอบที่ดีที่สุดของปัญหา โดยการเลือกเอาคำตอบที่ดีที่สุด ในสถานะนั้นออกมาก่อน โปรดสังเกตว่าปัญหาของการแลกเหรียญที่กล่าวมาข้างต้น จะใช้ได้ดีกับอัลกอริทึมนี้ เนื่องจากคุณสมบัติพิเศษ ของเหรียญนั่นเอง ทีนี้ลองมาดูตัวอย่างใหม่ จะทำให้เห็นอะไรได้ชัดเจนมากยิ่งขึ้น

สมมุติว่าเรามีเหรียญขนาดดังต่อไปนี้
เหรียญ 11 บาท, เหรียญ 5 บาท, และเหรียญ 1 บาท

และสมมุติว่าเราต้องการแลกเงิน 15 บาท ถ้าเราใช้ Greedy Algorithm เราจะได้เงินเหรียญดังนี้คือ
เหรียญ 11 บาท จะได้ 1 เหรียญ
เหรียญ 1 บาท จะได้ 4 เหรียญ


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

*** ควรจะต้องได้เหรียญ 5 บาท ทั้งหมด 3 เหรียญเท่านั้น ***

อย่างไรก็ตามขอย้ำไว้อีกครั้งหนึ่งว่าวิธีการแบบ Greedy Algorithm นี้ไม่ได้ให้คำตอบที่ดีที่สุดออกมา แต่สำหรับวิธีการนี้ก็ค่อนข้างจัดได้ว่าจะให้คำตอบที่จัดว่า ดี ออกมาได้ (ต้องพิจารณาแต่ละกรณี)

*** หากไปทดสอบเขียนเป็นโปรแกรม ต้องใช้วิธีการหารเอาเศษเข้ามาช่วยด้วยน่ะครับ ***


จี ทู จี เน็ต ดอต คอม - g2gNet Dot Com
เลขทะเบียนพาณิชย์อิเล็กทรอนิกส์ 0407314800231
CopyLeft © 2004 - 2099 g2gNet.Com All rights reserved.
Email: [email protected] หรือ โทร. 08-6862-6560