ชุมชนคนรักภาษาเบสิค - Visual Basic Community

 ลืมรหัสผ่าน
 ลงทะเบียน
ค้นหา
ดู: 1123|ตอบกลับ: 0

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

[คัดลอกลิงก์]

213

กระทู้

301

โพสต์

2407

เครดิต

ผู้ดูแลระบบ

Rank: 9Rank: 9Rank: 9

เครดิต
2407

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

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

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

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

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

เริ่มต้นโดยการ ใส่น้ำลงไปในขวดเล็กขนาด 5 ลิตรให้เต็ม แล้วเทน้ำจากขวดเล็กไปใส่ไว้ในขวดใหญ่ ดังนั้นขณะนี้ขวดใหญ่จะมีน้ำอยู่ 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.com  

GMT+7, 2020-1-22 04:18 , Processed in 0.529359 second(s), 5 queries , File On.

Powered by Discuz! X3.3 R20170401, Rev.54

© 2001-2017 Comsenz Inc.

ตอบกระทู้ ขึ้นไปด้านบน ไปที่หน้ารายการกระทู้