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

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

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

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

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