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

หรือติดต่อเข้ามาทาง 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
 5 1 1 2 4 8 3

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

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

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

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

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

สมมุติว่าเรามีขวดอยู่ 2 ขวด
ขวดที่หนึ่งบรรจุน้ำได้ 5 ลิตร
ขวดที่สองบรรจุน้ำได้ 9 ลิตร


ปัญหาคือว่า เราจะสามารถตวงน้ำให้มีปริมาตร 6 ลิตร ได้อย่างไร

วิธีที่หนึ่งที่จะแก้ปัญหานี้ได้ก็คือ การแก้แบบคิดย้อนกลับ ถ้าเราสามารถตวงน้ำขนาด 1 ลิตรได้ ก็สามารถนำน้ำลิตรนี้ใส่ลงไปในขวด 9 ลิตร ได้ และเติมน้ำลงไปในขวดนี้อีก 5 ลิตร ก็จะได้น้ำ 6 ลิตร ตามที่ต้องการ

น้ำ 1 ลิตร นั้นสามารถตวงน้ำได้ ถ้าขวดใหญ่ขาดน้ำอยู่อีก 4 ลิตร จึงจะเต็ม กรณีเช่นนี้ จะเกิดขึ้นได้เมื่อขวดใหญ่มีน้ำอยู่แล้ว 5 ลิตร

เริ่มต้นโดยการใส่น้ำลงไปในขวดเล็กให้เต็ม ในครั้งที่ 1 แล้วเทน้ำจากขวดเล็กไปใส่ไว้ในขวดใหญ่ ดังนั้นขณะนี้ขวดใหญ่จะมีน้ำอยู่ 5 ลิตร

ต่อไปเติมน้ำใส่เข้าไปในขวดเล็กให้เต็มอีกครั้ง แล้วเทน้ำจากขวดเล็กไปใส่ไว้ในขวดใหญ่ให้เต็ม ขณะนี้ขวดใหญ่จะบรรจุน้ำเต็ม 9 ลิตร ส่วนขวดเล็กก็จะเหลือน้ำอยู่อีก 1 ลิตร (ขวดเล็กขนาด 5 ลิตร เติม 2 ครั้งจะได้ 10 ลิตร แต่ขวดใหญ่มีเพียง 9 ลิตร)

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

การทำงานแบบย้อนกลับ จากคำตอบไปหาปัญหา เช่นนี้ ก็ช่วยให้เราหาคำตอบได้ ซึ่งคำตอบที่ได้นั้น อาจนำมาเรียงลำดับใหม่ ให้เป็นการแก้ปัญหาที่ทำในลักษณะที่คิดไปข้างหน้า (Forward Direction) ได้

ลองมาดูอีกหนึ่งตัวอย่าง

ถามว่ากบต้องกระโดดกี่ครั้ง เพื่อที่จะออกจากบ่อ ที่สูง 10 ฟุต
ถ้าในการกระโดดของกบนั้น ถ้ากบกระโดดขึ้นไปได้ 3 ฟุต กบจะต้องไหลลงมาเสีย 2 ฟุต ก่อนที่จะกระโดดครั้งต่อไป


ถ้าเราคิดแบบย้อนกลับ จะพบว่ากบสามารถกระโดดออกจากบ่อได้ ถ้าสามารถกระโดดขึ้นไปจนถึงฟุตที่ 7 ได้ (10 - 7 = 3 นั่นก็คือกบกระโดดอีกครั้งก็พ้นบ่อแล้ว) เนื่องจากกบขึ้นมาได้ทีละ
1 ฟุต ในการกระโดดแต่ละครั้ง (3 - 2 = 1) ดังนั้นกบต้องกระโดดทั้งหมด 7 ครั้ง จึงจะถึงฟุตที่ 7 ได้

ดังนั้นคำตอบก็คือ การกระโดดครั้งที่ 8 จึงจะทำให้กบกระโดดออกจากบ่อได้พอดี

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


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