MinMaxRouteFinder

MinMaxRouteFinder

อัลกอริธึม MiniMax เป็นที่รู้จักเป็นพิเศษและสามารถนำไปใช้ในการคำนวณการเคลื่อนไหวที่ดีที่สุด (การเคลื่อนไหวที่เหมาะสมที่สุด) ในเกมที่มีผู้เล่นสองคนซึ่งมีข้อมูลทั้งหมด

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

การป้อนข้อมูลเข้าสู่ระบบเป็นแบบไฟล์ ข้อมูลต่อไปนี้ถูกจัดเก็บไว้ในไฟล์ชื่อ “ourRoutes.txt” ourRoutes.txt มีลักษณะเช่นนี้

สิ่งแรกที่ผู้ใช้ควรทำเมื่อใช้โปรแกรมค้นหาเส้นทางโดยใช้อัลกอริธึม Min-Max คือการเตรียมแผนที่ รูปแบบของแผนที่ควรจะคล้ายกับรูปแบบข้างต้น

1. * ตัวคั่น แยกโหนดลูก (เส้นทาง) ออกจากโหนดหลัก
2. แต่ละหมายเลข (เช่น 1 หรือ 0) ที่ปรากฏหลังตัวคั่น ~ บอกเราว่าถึงตาของผู้เล่นคนไหนที่ต้องเลือกเส้นทาง (1 สำหรับตัวขยายขนาดและ 0 สำหรับตัวย่อขนาด)
3. หากชื่อโหนดถูกคั่นด้วย * ออกจากตัวเลข ตัวเลขดังกล่าวจะระบุระยะทางหรือต้นทุนของเส้นทางผ่านโหนดดังกล่าว

เช่น Stadium_*_9: นี่หมายถึงสนามกีฬาเป็นเส้นทางสุดท้ายไปยังจุดหมายปลายทาง และระยะทางคือ 9 กม. ถึง Saris ผ่านเส้นทางสนามกีฬา

เมื่อผู้ใช้รันโปรแกรม โปรแกรมค้นหาเส้นทางจะแสดง “แบบฟอร์ม” ขั้นแรก เลือกเส้นทางของไฟล์ที่มีพื้นที่สถานะและป้อนสถานที่ปลายทางในกล่องข้อความ ขั้นตอนคือ:

• คลิกที่ “…” เพื่อเลือกตำแหน่งไฟล์จากนั้น
• กรอกสถานที่ปลายทางในกล่องข้อความที่ให้ไว้
• คลิกที่ปุ่ม "ไป" หรือกดปุ่ม Enter / Return เพื่อรันโปรแกรม

ระบบจะดำเนินการดังต่อไปนี้โดยอัตโนมัติ:

1. จะตรวจสอบการมีอยู่ของไฟล์ที่มีพื้นที่สถานะในโฟลเดอร์ที่ระบุ
2. หากไฟล์มีอยู่/มีอยู่ ให้อ่านเนื้อหาของไฟล์และจัดเก็บไว้ใน “เนื้อหา” จากนั้นโทเค็นเส้นทางด้วยชื่อเส้นทาง
3. หลังจากโทเค็น เนื้อหาจะถูกจัดเก็บไว้ในโครงสร้างข้อมูลเป็นโหนด ตัวสืบทอด ระดับ MiniMax และระยะทางตามลำดับ
4. เนื้อหาไฟล์จะถูกจัดเก็บเป็นรายการโครงสร้าง