การเดินทางในเขาวงกต

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

เขาวงกตนี้มีกำแพงกั้นและมีทางเดิน สิ่งที่ต้องการคือเดินทางจากทางเข้า และเป้าหมายคือทางออก เราจะมีวิธีการเดินทางได้อย่างไร

สิ่งแรกที่จะต้องทำคือหาทางแทนปัญหา และหาวิธีแก้ปัญหาการแทนปัญหามีหลายวิธีเช่น แทนปัญหาเป็นกราฟ

วิธีที่นิยมแทนโหนดของกราฟ และระยะทางระหว่างโหนดไปโหนดเป็นระยะทางตามทิศทางการเดินจริงในเขาวงกต เช่นจากโหนด(1,1) ไปยังโหนด(2,3) มีค่าเท่ากับ 6 โดยถือว่าจุดเริ่มต้นของการเริ่มเดินทางอยู่ที่โหนด(1,1) และโหนด(2,3) ไปยังโหนด (2,4) มีระยะทางเท่ากับ 2 ดังนั้นกราฟที่ปรากฎจะเป็นกราฟที่มีระยะทาง โดยสิ่งที่ต้องการคือกำหนดสถานะของการเริ่มเดินทางและสถานะเป้าหมายคือการสิ้นสุดการเดินทาง ซึ่งสามารถกำหนดสถานะได้ดังนี้

        

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

0 0 0 0 0 0 0 1 1 0 1 0 1 1 0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 0 0 0 0

ข้อมูลชุดนี้มีขนาดข้อมูลเป็นเมตริกซ์ 7x7 แต่ภายในประกอบด้วยตัวเลข 0 และ 1 สถานะเริ่มต้นและสถานะเป้าหมายแสดงได้ดังนี้

0 0 0 0 0 0 0 1 1 0 1 0 1 1 0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 0 0 0	0 0 0 0 0 0 1 1 0 1 0 1 1 0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 0 0 0 0
สถานะเริ่มต้น	สถานะเป้าหมาย

เนื่องจากเขาวงกตนี้มีขนาดไม่ใหญ่มากนักการหาเส้นทางเดินคงไม่ยาก แต่ถ้าหากขนาดของเขาวงกตมีขนาดใหญ่ สภาพการคำนวณเพื่อหาเส้นทางที่ดีที่สุดก็จะยุ่งยากขึ้น

จากกรณีนี้พอจะเห็นคำตอบได้ชัดเจนดังนี้

0 0 D D D D D 1 1 D 1 0 1 1 D D D 1 0 0 0 D 1 0 1 0 1 0 D 1 0 0 0 1 0 D 1 0 1 0 1 0 D 1 0 0 0 0 0

เส้นทางเดินคือตัวอักษร D

 

---

ที่มา : รศ. ยืน ภู่วรวรรณ, สำนักบริการคอมพิวเตอร์ มหาวิทยาลัยเกษตรศาสตร์