A D V A N C E     S E A R C H
การแก้ปัญหา การหาเส้นทางเพื่อนำไปสู่เป้าหมายสุดท้าย (Goal) ของ Puzzle-8
Simulation

ข้อมูลที่รับเข้ามา เป้าหมาย
(846730125) (123456780)
หรือ หรือ
8     4     6 จะต้องเลื่อนอย่างไรเพื่อให้ได้มา 1    2     3
7     3     - ====================> 4     5     6
1     2     5 ซึ่งเส้นทางเพื่อนำไปสู่เป้าหมาย 7     8     -

              การดำเนินงาน จะเริ่มด้วยการ input สถานะเริ่มต้น ( Pattern ) ตามแต่ที่จะป้อนเฃ้ามา โดยมีค่า ตั้งแต่ 1 ถึง 8 สำหรับช่องที่ไม่มีค่า ให้ป้อน '-' ดังตัวอย่างฃ้างต้น โปรแกรม จะหาเส้นทางที่ เหมาะสมเพื่อนำไปสู่สถานะสุดท้าย หรือเป้าหมาย ( Goal ) ให้ ใน บางครั้งสถานะเริ่มต้น จะไม่มีคำตอบหมายความว่าไม่มีเส้นทาง ที่จะนำไปสู่คำตอบเลย, จากการศึกษา การค้นหาเส้นทางเพื่อนำไปสู่คำตอบ หรือ เป้าหมายสุดท้าย พอสรุปได้ดังนี้
                  1) การค้นหาในแนวลึกก่อน (Deapth first search) จะไม่เหมาะสมเป็นอย่างยิ่ง สำหรับปัญหานี้ เพราะโอกาสประสบความสำเร็จ น้อยมาก และปัญหาที่ตามมาคือ หน่วยความจำไม่เพียงพอ
                  2) การค้นหาตามแนวกว้างก่อน (Breadth first search) ไม่ว่าจะขยายจาก เป้าหมาย เพื่อค้นหาสถานะเริ่มต้น หรือ ขยายจากสถานะเริ่มต้น ไปสู่เป้าหมาย จะสามารถค้นหา ได้เพียงบาง กรณี ที่มีสถานะเริ่มต้น ใกล้ เป้าหมายเท่านั้น หากออยู่ที่ลึก ๆ หรือ ห่างไกล จะไม่สามารถ หาเจอ โดยจะเกิดปัญหา หน่วยความจำ เต็ม ไม่ว่าจะอยู่บน Dos, Windows หรือบน Linux
                  3) การค้นหาตามแนวกว้างแบบสองทาง (Sendwich) โดยการขยายเป้าหมาย ออกระดับหนึ่งก่อน จากนั้นจึงทำการ ขยายสถานะเริ่มต้น วิธีนี้จะให้ผลดีกว่าสองวิธีแรก สามารถหาคำตอบ ได้หลายๆ กรณี แต่ถึงอย่างไรก็ตาม ก็ไม่สามารถหาได้ทุกกรณี หรือ แม้ในกรณี ที่ ลึกๆ หรือไกลมาก ๆ ก็ไม่สามารถหาได้     ในการขยาย โหนด จากเป้าหมาย ทุกครั้งที่ขยาย จะตรวจสอบว่าเท่ากับสถานะเริ่มต้นหรือไม่ ถ้า เท่ากันแสดงว่าพบเส้นทางไปยังเป้าหมาย และจะแสดงเส้นทาง โดยทำการย้อนกับ (Back tracking) ไปที่เป้าหมาย ถ้าไม่พบต้องตรวจสอบกับทุก โหนด ที่ขยายไปแล้ว ว่าซ้ำหรือไม่ ถ้าซ้ำก็จะขยาย โหนด ใหม่ต่อไป แต่ถ้าไม่ ซ้ำก็ใส่เข้าไปในส่วนขยาย แล้วขยาย โหนด ใหม่ต่อไป
        สำหรับโหนด ที่เกิดจากการขยายจากสถานะเรี่มต้น จะต้องนำไปตรวจกับทุกโหนด ที่เกิดจากการขยายของเป้าหมาย ถ้าซ้ำแสดงว่าพบเส้นทางไปยังเป้าหมาย และจะทำการย้อนกับ (Back tracking) ไปที่เป้าหมาย ขณะเดียวกันในส่วนขยาย ของสถานะเริ่มต้น ก็จะย้อนกลับไปที่จุดเริ่มต้นเช่นกัน ดังนั้นเราจะได้เส้นทางไปสู่เป้าหมายตามจุดประสงค์ แต่ถ้าไม่พบในส่วนขยายของเป้าหมาย ก็จะตรวจดูว่า มีซ้ำในส่วนขยายของสถานะเริ่มต้น หรือไม่ ถ้าซ้ำก็ขยาย โหนด ใหม่ต่อไป ถ้าไม่ซ้ำ ก็ใส่เข้าไปใน ส่วนขยาย จากนั้นจึงขยาย โหนด ใหม่ ต่อไป         ข้อสังเกตจากการดำเนินการด้วยวิธีการนี้ คือ ถ้าขยายจากเป้าหมาย ออกไปมากๆ จะทำให้การค้นหาเร็วขึ้น โดยเฉพาะ กรณีที่อยู่ใกล้ เป้าหมาย แต่ถ้าไม่พบก็จะหาช้าลง และช้าลง อย่างรวจเร็ว จนในที่สุดจะไม่สามารถค้นหาต่อได้ ทั้งนี้เพราะ ใน การขยาย ไม่ว่า จะขยาย จากเป้าหมาย หรือขยายจากสถานะเริ่มต้น จะขยายในทุกกรณี และต้องตรวจหา การซ้ำ จากทุก โหนด ซึ่งนี้ก็เป็นสาเหตุทำให้หน่วยความจำเต็ม ในการขยาย
                  4) เป็นการดำเนินการตามแบบข้อสาม แต่จะขยายเป้าหมายทุกกรณี ออกประมาณ 10 - 15 ระดับ เพราะ ถ้าขยายมาก ๆ จะทำให้ การค้นหา ช้า เพราะ โดยรวมการค้นหาจะ ไม่พบ สำหรับ การขยาย โหนด จากสถานะเริ่มต้น จะขยายล่วงหน้า 3 ระดับ ทุก โหนด จะตรวจสอบกับ ส่วนขยายเป้าหมาย เช่นเดียวกับข้อ 3 จากนั้นถ้าไม่พบ จึงทำการเลือกเอา เฉพาะ โหนด ที่มี Huristic ดีที่สุด เพื่อขยายต่อไป ส่วน โหนด ที่มี Heuristic ไม่ดี จะถูกตัดทิ้งไป
                  5) ในการ Implement ใช้โครงสร้างข้อมูลแบบ Link list เพื่อความยึดหยุ่นในการจอง หน่วยความจำ ซึ่งก็เป็น ปัญหาอย่ามากๆ เพราะควบคุมยุ่งอยากมาก ยิ่งถ้าข้อมูลมากๆ (search space มาก ๆ ) ดูเหมือน จะพันกันไปหมด โดยเฉพาะ การรับส่งค่าระหว่าง Function จน สุดท้ายบางกรณี จำต้องใช้ Array .
        โปรแกรม Puzzle1.c เป็นการหาแบบตรงไปตรงมา แบบ Breadth-first search และเป็นการ sendwich ทั้งสองทาง เมื่อพบจึงทำการ Backtracking กับไปหาจุดเริ่มต้น
        โปรแกรม Puzzle2.c เป็นกาหาแบบ Breadth-first search และเป็นการ sendwich ทั้งสอง ทาง นอกจากนี้ยังเป็นการใชหลักวิธี Best-first search ด้วย โดยการหาค่า ที่ดีที่สุด 3 ระดับล่วงหน้า แล้วจึงเลือกเอาดีที่สุด     สำหรับ Puzzle3.c มีการทำงานแบบ วนลูป

        ตัวอย่างบางตัวอย่าง สำหรับใช้ในทดสอบ

Succsessfull                             6728-4153
12345-786 84673-125
12-453786 86731-542
1234-5786 86457-321
1235764-8 87654321-
1234-5867* 87341-265
1875-6243 8754-3612 **
13245-687*   failed
3287-6541 8754-3621 **
375421-86 5748-3621
37862-154 8234567-1
Back to MENU