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

thongkorn

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

สมมุติว่า เรามีขวดอยู่ 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 จึงจะทำให้กบกระโดดออกจากบ่อได้พอดี

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