Find the exit of the maze. (Search)

จัดทำโดย นายวชิรเมษฐ์ กุลธนาเรืองนนท์ 66340700405

เริ่มจากการศึกษาวิธีหาทางออกจากเขาวงกต โดยได้ศึกษามา 2 วิธีคือ

1.BFS หรือ Breadth-First Search (การค้นหาแบบกว้าง)

เป็นอัลกอริทึมที่ใช้ในการค้นหาข้อมูลหรือกราฟ โดยการท่องไปทางระดับแรกของกราฟก่อน จากนั้นท่องไปทางระดับถัดไป โดยมีการท่องในทุกๆ โหนดที่อยู่ในระดับปัจจุบันก่อนที่จะขยับไปยังระดับถัดไป อัลกอริทึมนี้มักถูกใช้ในการหาทางที่สั้นที่สุด (Shortest Path) ในกราฟ หรือในการค้นหาข้อมูลในโครงสร้างข้อมูลแบบกราฟ.

ขั้นตอนการทำงานของ BFS ได้แก่:

1. เริ่มต้นที่โหนดเริ่มต้น (start node) และทำเครื่องหมายว่าโหนดนั้นถูกเยือนแล้ว.

2. ท่องไปยังโหนดลูกทุกตัวของโหนดปัจจุบัน (ถ้ามี) และทำเครื่องหมายว่าลูกของโหนดนั้นถูกเยือน.

3. ทำซ้ำขั้นตอน 2 สำหรับทุกๆ โหนดลูกที่ยังไม่ได้เยือน.

4. ทำซ้ำขั้นตอน 3 สำหรับโหนดลูกของโหนดล่าสุดที่ยังไม่ได้เยือน.

5. ทำซ้ำขั้นตอน 4 จนกว่าทุกโหนดที่เป็นไปได้จะถูกเยือน.

BFS มักถูกใช้ในการหาทางที่สั้นที่สุด, ค้นหาคำตอบในปัญหา Maze (ปัญหาทางใน Labrynth), หรือในการค้นหาโครงสร้างข้อมูลแบบกราฟ เพื่อตรวจสอบความสัมพันธ์ระหว่างโหนดและระยะทางที่ใกล้ที่สุด.

2.DFS หรือ Depth-First Search (การค้นหาแบบลงลึก)

คือ เป็นอัลกอริทึมที่ใช้ในการค้นหาข้อมูลหรือกราฟ โดยการท่องไปในลูกของโหนดปัจจุบันในลำดับลงลึกลงไปในกราฟ จนกว่าจะไม่สามารถทำต่อไปได้แล้วจึงย้อนกลับมาและทดลองทางอื่น ๆ ในกรณีที่ยังไม่ได้เยือนทุกลูกของโหนดนั้น ๆ อัลกอริทึม DFS มักถูกใช้ในการแก้ปัญหาที่เกี่ยวข้องกับการค้นหาแบบกราฟ เช่น การหาเส้นทางระหว่างจุดสองจุดในกราฟ หรือการค้นหาคำตอบในปัญหา (Maze solving) และปัญหาทางที่มีคำตอบหลายทาง (Multiple solutions).

ขั้นตอนการทำงานของ DFS ได้แก่:

1. เริ่มต้นที่โหนดเริ่มต้น (start node) และทำเครื่องหมายว่าโหนดนั้นถูกเยือนแล้ว.

2. ท่องลงไปยังลูกของโหนดปัจจุบัน (ถ้ามี) และทำเครื่องหมายว่าลูกของโหนดนั้นถูกเยือน.

3. ทำซ้ำขั้นตอน 2 สำหรับโหนดลูกทุกตัว.

4. ทำซ้ำขั้นตอน 2-3 สำหรับโหนดลูกของโหนดล่าสุดที่ยังไม่ได้เยือน.

5. ทำซ้ำขั้นตอน 4 จนกว่าทุกโหนดที่เป็นไปได้จะถูกเยือน.

DFS มีความยืดหยุ่นและสามารถปรับใช้กับหลายลักษณะของกราฟได้ เพราะนอกจากการท่องลงลึกแบบปกติแล้ว ยังสามารถใช้ Recursive หรือ Iterative ได้ตามต้องการ.

ผลสรุปการเลือกวิธี

จากการทดสอบมาทั้ง 2 วิธี สรุปได้ว่า จะเลือกใช้วิธี BFS เนื่องจากหากเขาวงกตนั้นมีเส้นทางที่ไปยังทางออกได้ 2 หรือมากกว่า 2 เส้นทาง วิธี BFS จะเป็นวิธีที่เหมาะกว่าวิธี DFS เพราะทั้งสองวิธีจะหยุด Search เมื่อหาทางออกได้ ดังนั้นวิธี DFS อาจจะไม่ได้คำตอบของเส้นทางที่สั้นที่สุด แต่ BFS นั้นสามารถหาทางออกที่สั้นที่สุดได้

BFS Algorithm

กระบวนการทั้งหมด

เริ่มจากรับค่าจากเพื่อนที่ทำเรื่อง “การสร้างแผนที่เขาวงกต” แล้วนำค่าออกมาเป็น csv file หลังจากนั้นจะนำค่าที่ได้มา มาใส่ในโปรแกรม BFS เพื่อให้โค้ดสามารถประมวลผลแผนที่เขาวงกตแล้ว Search หาเส้นทางที่สั้นที่สุดออกมา แล้วนำค่าที่ออกมานั้นไปส่งต่อให้เพื่อนที่ทำเรื่อง “กระบวนการการเคลื่อนที่ทีละblock โดยประมาณ 30 cm. ต่อ block”

CSV File

ใน Python, CSV file หรือ Comma-Separated Values file เป็นไฟล์ที่เก็บข้อมูลแบบแผ่นปกติที่มีโครงสร้างเป็นตาราง โดยข้อมูลจะถูกแบ่งแยกด้วยตัวอักษรพิเศษ เช่น จุลภาค (,) หรือเครื่องหมายอื่น ๆ เช่น จุด (.) หรือเครื่องหมายทางการ

Python มีไลบรารีที่ชื่อว่า csv ที่ช่วยในการอ่านและเขียนไฟล์ CSV ได้อย่างสะดวก ด้วยฟังก์ชันที่ช่วยในการอ่านข้อมูลจากไฟล์ CSV และแปลงเป็นรายการ (list) หรือโครงสร้างข้อมูลอื่น ๆ เช่น dictionaries สำหรับการจัดการข้อมูลอย่างมีประสิทธิภาพใน Python

จากรูป คือ ค่าจากการสร้างแผนที่เขาวงกตมาเป็นค่าใน CSV File ซึ่งจะนำค่าในไฟล์นี้มาใส่ในโปรแกรม BFS

ตัวอย่างการใช้ CSV File ใน BFS

ผลสรุปของ csv file

คือ ได้ค่า csv file มาใหม่แล้วนำค่ามาเช็คกับโปรแกรมและแก้ให้ได้ตามรูปแบบที่ได้กำหนดไว้ ผลที่ได้ออกมาสำเร็จได้แผนที่เขาวงกตและค่าผลลัพธ์ที่ต้องการออกมา (ค่าทิศทางการเคลื่อนที่ของหุ่นยนต์จากจุด Start ไปยัง Goal) หลังจากนั้นจะส่งค่าที่ได้ออกมาไปที่กระบวนการถัดไป

ค่าจาก csv file ที่ได้รับมาแล้วแก้ให้ตรงตามรูปแบบที่ได้กำหนดไว้

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

จากรูปด้านบน คือ ผลลัพธ์ที่ได้ หลังจากได้รับค่า csv file มาแล้วนำค่าไปคำนวนหาเส้นทางที่สั้นที่สุด โดยกำหนดจุด Start = (1,5) และ จุด Goal = (10,1)

คลิปแสดงการ Search จากรูปด้านบนแบบ BFS ที่ได้หลังจากใส่ค่า csv file

Sending direction values

คือ การส่งค่าที่ได้จากการประมวลผลทิศทางที่สั้นที่จุดจากจุด Start ไปยัง Goal แปลงมาเป็นค่าเส้นทางว่ามีการเดินทางเป็นอย่างไร โดยวางหุ่นยนต์ที่จุด Start และหัวของหุ่นยนต์หันไปทางทิศใต้ของแผนที่เริ่มต้น

จากรูปคือหลังจากการหาเส้นทางที่สั้นที่สุด ก็จะประมวลผลออกมาเป็นค่าทิศทางที่ต้องการออกมา

ผลสรุปที่ได้จาก Sending direction values คือ

สามารถเขียนโปรแกรมใน BFS ให้สามารถอ่านค่าการเดินทางของหุ่นยนต์ออกจากเขาวงกต ได้สำเร็จ หลังจากนั้นจะส่งมอบค่าที่ได้มาไปยังส่วนของเพื่อนที่ทำเรื่อง “ส่งค่านี้ไปยังหุ่นยนต์ให้เดินทางตามค่าที่ออกมา” ในส่วนต่อไป

ค่าการเดินทางที่ได้มา และนำค่านี้ส่งต่อให้เพื่อนที่ทำเรื่อง “ส่งค่านี้ไปยังหุ่นยนต์ให้เดินทางตามค่าที่ออกมา”