หลังจากที่เขียนในบทความก่อนหน้าถึงโครงสร้างข้อมูลแบบ Graph และ เทคนิคการเดินทางใน Graph (Graph Traversal) เพื่อหาเส้นทาง Shortest Path โดย Dijkstra’s กับ Bellman-Ford’s Algorithms แล้ว
ในบทความนี้เราจะมาแนะนำเทคนิคอีกเทคนิคหนึ่งที่มีชื่อว่า A* (อ่านว่าเอ-สตาร์) Search Algorithm
The English version is available here.
สารบัญ
- A* Search Algorithm
- ขั้นตอนการทำงาน
- เขียนโค้ด
- Complexity Analysis
- การนำไปใช้
- นำ A* Search Algorithm หาเส้นทางในเขาวงกต
- เพิ่มเติม
- สรุป
- แหล่งข้อมูลอ้างอิง
A* Search Algorithm
A* Search Algorithm [1] เป็นพื้นฐานที่ใช้ในการทำ Artificial Intelligence สำหรับการทำ Graph Traversal เพื่อหา Path ที่เหมาะสมที่สุดระหว่าง 2 โหนดจากโหนดเริ่มต้น ไปยังโหนดสิ้นสุดใน Graph ที่เป็น Directed Unweighted ที่ไม่มี Negative Edge Weights
เทคนิคนี้คล้ายกันกับเทคนิค Dijkstra’s Algorithm ที่กล่าวถึงในบทความก่อนหน้า แต่มีข้อแตกต่างคือเทคนิคนี้จะฟังก์ชันสำหรับการประเมิน [2] ที่มีส่วนประกอบ ได้แก่
- Heuristic คือค่าสำหรับการตัดสินในการผ่านโหนด
- Cost คือค่าที่บ่งบอกค่าใช้จ่าย ระยะเวลา หรืออะไรก็ตามแต่ ที่ช่วยพิจารณาว่าโหนดนั้นเหมาะสมต่อการผ่านหรือไม่
- Priority คือค่าที่ได้จากทั้ง Heuristic และ Cost จะได้เป็นค่านี้ออกมา เพื่อบ่งบอกว่าโหนดนั้นเหมาะสมหรือไม่
เรากำหนดให้
- Heuristic คือ h(x)
- Cost คือ g(x)
- และ Priority คือ f(x)
เราอธิบายได้ตามสมการทางคณิตศาสตร์ได้ตามด้านล่างนี้
f(x) = g(x) + h(x)ขั้นตอนการทำงาน
เทคนิคนี้มีหน้าที่ค้นหาเส้นทางที่เหมาะสมสำหรับการเดินทางระหว่างโหนดเริ่มต้น (S) ไปยังโหนดสิ้นสุด (G) โดยใช้ cost การเดินทางที่ต่ำที่สุด
เทคนิคนี้จำเป็นต้องมี 2 อาเรย์ ได้แก่
- Open list หรือ priority queue เป็นอาเรย์สำหรับการเก็บโหนดต่อไปที่จำเป็นต้องการสำรวจ ข้อมูลที่นำมาเก็บในอาเรย์นี้ได้มาจากโหนดที่ผ่านการพิจารณาโดยการใช้ฟังก์ชันแล้วว่าให้ค่าต่ำที่สุด โดยตอนเริ่มต้นการทำงานของเทคนิคนี้ เราจะเป็นข้อมูลโหนดเริ่มต้น (S) ไว้ก่อน
- Closed List มีหน้าที่เก็บข้อมูลโหนดที่ผ่านการสำรวจเพื่อค้นหาโหนดที่ให้ cost ต่ำที่สุดเรียบร้อยแล้ว
เมื่อกำหนดอาเรย์เรียบร้อยแล้ว เราจะใช้ Open list สำหรับสร้าง Tree สำหรับการเก็บข้อมูลที่ต่ำที่สุดไว้ข้างบน แล้วค่อย ๆ ไล่ลงมาจนถึงโหนดที่มีค่าสูงที่สุดอยู่ระดับล่าง ลักษณะนี้ทำให้นึกถึง Min Heap Tree ที่อธิบายในบทความก่อนหน้า
เราสามารถสรุปการทำงานเป็นขั้นตอนได้ตามด้านล่างนี้
- กำหนดให้โหนดทุกโหนดยกเว้นโหนดเริ่มต้น (S) มีค่า cost เป็น Infinity ส่วนโหนดเริ่มต้น (S) สำหรับให้ cost เป็น 0
- เริ่มต้นการสร้าง Tree โดยให้รูทเป็นโหนดเริ่มต้น (S)
- ลบโหนดรูท สำหรับการนำโหนดที่ดึงออกมาเพื่อสำรวจในโหนดนั้น
- เพิ่มโหนดที่ดึงออกมาลงไปใน Closed List
- สำรวจโหนดนั้น ๆ เพื่อค้นหาโหนดที่เชื่อมต่อกัน แล้ววนลูปในแต่ละโหนดสำหรับการประเมินโดยใช้ฟังก์ชันเพื่อหา cost ที่ต่ำที่สุด และอัพเดทค่า cost นั้น ๆ
- เพิ่มโหนดที่ให้ cost ที่ต่ำที่สุดลงไปใน Tree
- จากนั้นวนลูปตั้งแต่ข้อ 3 จนถึงข้อ 6 จนกว่าเราจะได้โหนดสิ้นสุด (G)
เราแสดงขั้นตอนการทำงานได้ตามด้านล่างนี้ โดยใช้กราฟตัวอย่างตามด้านล่างนี้
เรากำหนด
- ระยะทาง: ให้โหนดทุกโหนด ยกเว้นโหนดเริ่มต้น (โหนดที่ 1) มีค่าเท่ากับ Infinity ส่วนโหนดเริ่มต้นเรากำหนดให้ cost เป็น 0
- อาเรย์ Open List: กำหนดให้เป็นโหนดเริ่มต้น ที่คำนวณค่า cost โดยฟังก์ชัน f(x) = g(x) + h(x) ที่กำหนดให้
- g(x) = 0 เนื่องจากไม่มีโหนดก่อนหน้า
- และ h(x) = 0 ตามที่ระบุในกราฟ
- อาเรย์ Closed List: กำหนดให้ทุกโหนดเป็น False
ผลลัพธ์การกำหนดค่าเริ่มต้นแสดงตามด้านล่างนี้
ต่อมา เราสำรวจเข้าไปดูที่โหนดเริ่มต้น โดยการดึงโหนด 1 ออกจาก Open List (ถ้ามองเป็น Min-Heap โหนด 1 ที่ดึงออกมานั้นมันเป็นโหนดรูท)
เมื่อดึงโหนดที่ 1 ออกมาแล้ว เรากำหนดในอาเรย์ Closed List ให้โหนดที่ 1 มีค่าเป็น True
โหนดที่ 1 นี้มีโหนดที่เชื่อมต่อกันอยู่ทั้งหมด 2 โหนด ได้แก่โหนดที่ 2 และโหนดที่ 3 ที่มีค่า h(x) เท่ากับ 2 และ 7 ตามลำดับ และมีค่า g(x) เท่ากับ 3 และ 2 ตามลำดับ เรามาคำนวณเพื่อหาค่า cost ได้ตามด้านล่างนี้
- f_node2(x) = h_node2(x) + g_node2(x) = 2 + 3 = 5
- f_node3(x) = h_node3(x) + g_node3(x) = 7 + 2 = 9
ผลลัพธ์ที่ได้เราจะเห็นว่า ค่า cost ที่มาจากโหนดที่ 2 มีค่าต่ำที่สุด และค่า cost ที่มาจากโหนดที่ 3 อยู่รองลงมา
ให้เราเพิ่มค่าทั้งสองค่าลงไปใน Open List โดยกำหนดให้โหนดที่ 2 ที่มีค่า cost น้อยกว่าอยู่ข้างบนตามหลักของ Min-Heap
เมื่อสำรวจโหนดที่ 1 เสร็จแล้ว ให้เราดึงโหนด 2 ออกจาก Open List
เมื่อดึงโหนดที่ 2 ออกมาแล้ว เรากำหนดในอาเรย์ Closed List ให้โหนดที่ 2 มีค่าเป็น True
ในโหนดนี้มีโหนดที่เชื่อมต่อกันอยู่เพียงโหนดเดียว คือโหนดที่ 3 ที่มีค่า h(x) เท่ากับ 7 และมีค่า g(x) เท่ากับ 1 เราคำนวณเพื่อหาค่า cost ได้ตามด้านล่างนี้
- f_node3(x) = h_node3(x) + g_node3(x) = 7 + 1 = 8
ผลลัพธ์ที่ได้เราจะเห็นว่า ค่า cost จากโหนด 3 ที่เชื่อมกับโหนดที่ 2 มีค่าที่ต่ำกว่าค่า cost ที่เป็นโหนดที่ 3 ที่มาจากโหนดที่ 1 ให้เราเพิ่มโหนดนี้พร้อมกับค่า cost ที่เพิ่งคำนวณได้ลงไปใน Open List โดยให้อยู่ข้างบนเหนือกว่าโหนดที่ 3 ที่มีค่า cost เท่ากับ 9
เมื่อสำรวจโหนดที่ 2 เสร็จแล้ว ให้เราดึงโหนด 3 ที่มีค่า cost เท่ากับ 8 ออกจาก Open List และกำหนดใน Closed List ให้โหนดที่ 3 เป็น True
ในโหนดนี้มีโหนดที่เชื่อมต่อกันอยู่ทั้งหมด 2 โหนด ได้แก่โหนดที่ 4 และโหนดที่ 5 ที่มีค่า h(x) เท่ากับ 2 และ 7 ตามลำดับ และมีค่า g(x) เท่ากับ 3 และ 2 ตามลำดับ เรามาคำนวณเพื่อหาค่า cost ได้ตามด้านล่างนี้
- f_node4(x) = h_node4(x) + g_node4(x) = 4 + 4 = 8
- f_node5(x) = h_node5(x) + g_node5(x) = 10 + 3 = 13
ผลลัพธ์ที่ได้เราจะเห็นว่า
- ค่า cost ที่มาจากโหนดที่ 4 มีค่าต่ำที่สุด
- และค่า cost ที่มาจากโหนดที่ 5 มีค่ามากที่สุด
ให้เราเพิ่มลงไปในตาราง โดยกำหนดให้โหนดที่ 4 อยู่บนสุด แต่โหนดที่ 5 อยู่ล่างสุดตามหลัก Min-Heap อีกเช่นเคย
เมื่อสำรวจโหนดที่ 3 เสร็จแล้ว ให้เราดึงโหนด 4 ที่มีค่า cost เท่ากับ 8 ออกจาก Open List และกำหนดใน Closed List ให้โหนดที่ 4 เป็น True
โหนดที่ 4 โหนดนี้มีโหนดที่เชื่อมต่อกันอยู่เพียงโหนดเดียว คือโหนดที่ 5 ที่มีค่า h(x) เท่ากับ 10 และมีค่า g(x) เท่ากับ 3 เรามาคำนวณเพื่อหาค่า cost ได้ตามด้านล่างนี้
- f_node5(x) = h_node5(x) + g_node5(x) = 10 + 3 = 13
ผลลัพธ์ที่ได้เราจะเห็นว่า ค่า cost นี้ไม่ได้มีค่าต่ำกว่าค่า Cost ที่เป็นโหนดที่ 5 ที่เชื่อมกับโหนดที่ 3
ดังนั้นเราจะไม่อัพเดทอะไรใน Open List
เมื่อสำรวจโหนดที่ 4 เสร็จแล้ว ให้เราดึงโหนด 3 ที่มีค่า cost เท่ากับ 9 ออกจาก Open List และกำหนดใน Closed List ให้โหนดที่ 3 เป็น True
ในโหนดที่ 3 โหนดนี้มีโหนดที่เชื่อมต่อกันอยู่ทั้งหมด 2 โหนด ได้แก่โหนดที่ 4 และโหนดที่ 5 แต่โหนดที่ 4 ได้รับการเยือนไปเรียบร้อยแล้ว (ค่าใน Closed List เป็น True)
ดังนั้นเราจะพิจารณาเฉพาะในโหนดที่ 5 ที่มีค่า h(x) เท่ากับ 7 และมีค่า g(x) เท่ากับ 2 เรามาคำนวณเพื่อหาค่า cost ได้ตามด้านล่างนี้
- f_node5(x) = h_node5(x) + g_node5(x) = 10 + 3 = 13
ผลลัพธ์ที่ได้เราจะเห็นว่า ค่า cost ที่คำนวณได้ไม่ได้มีค่าต่ำกว่าที่คำนวณในขั้นตอนก่อนหน้า ดังนั้นเราจะไม่อัพเดทค่าในตาราง
สุดท้าย ให้เราดึงโหนด 5 ที่มีค่า cost เท่ากับ 13 ออกจาก Open List และกำหนดใน Closed List ให้โหนดที่ 5 เป็น True
เรามาสำรวจในโหนดที่ 5 โหนดนี้ไม่มีโหนดที่เชื่อมต่อกันอีก ดังนั้นเราสามารถสรุป Path ที่ได้ในกราฟได้ตามด้านล่างนี้
โดยเราเดินจากโหนด 1 -> 2 -> 3 -> 5 ตามเส้น และวงกลมสีแดงตามภาพด้านล่างนี้
เขียนโค้ด
เราสามารถสรุปได้โดยการเขียนโค้ดตามด้านล่างนี้
ส่วนแรกเป็นการนำเข้าไลบรารี
import heapq, copyส่วนที่สองเป็นการกำหนด Graph
graph = [
{
'h': 0,
'neighbor': [(1, 3), (2, 2)],
'f': float('inf'), 'g': 0,
'parent': 0
},
{
'h': 2,
'neighbor': [(2, 1)],
'f': float('inf'), 'g': float('inf'),
'parent': None
},
{
'h': 7,
'neighbor': [(3, 4), (4, 3)],
'f': float('inf'), 'g': float('inf'),
'parent': None
},
{
'h': 4,
'neighbor': [(4, 3)],
'f': float('inf'), 'g': float('inf'),
'parent': None
},
{
'h': 10,
'neighbor': [],
'f': float('inf'), 'g': float('inf'),
'parent': None
}
]ต่อมาเป็นการเขียนโค้ดสำหรับเทคนิค A* Search Algorithm
def a_star_search(graph_orig, source = 0, destination = 4):
if source == destination:
print("We are already at the destination.")
return
# Create Open and Closed List
open = []
close = [False for i in range(len(graph_orig))]
# Copy the original array
graph = copy.deepcopy(graph_orig)
graph[source]['parent'] = None
graph[source]['f'] = graph[source]['g'] + graph[source]['h']
heapq.heappush(open, [graph[source]['f'], source])
# destination
found_dest = False
while len(open) > 0:
print(list(open))
vertex = heapq.heappop(open)[1]
close[vertex] = True
# Check if we found the destination.
if vertex == destination:
print("We found the destination")
found_dest = True
# Trace back
dest_vertex = vertex
path = []
print(dest_vertex)
while True:
path.append(dest_vertex)
dest_vertex = graph[dest_vertex]['parent']
if dest_vertex is None:
break
path.reverse()
return path
# Look into neighbors
for neighbor_vertex, g_neighbor in graph[vertex]['neighbor']:
# Check whether is visited or not
if close[neighbor_vertex]:
continue
new_f = g_neighbor + graph[neighbor_vertex]['h']
if graph[neighbor_vertex]['f'] == float('inf') or \
new_f < graph[neighbor_vertex]['f']:
graph[neighbor_vertex]['parent'] = vertex
graph[neighbor_vertex]['f'] = new_f
graph[neighbor_vertex]['g'] = g_neighbor
heapq.heappush(open, [graph[neighbor_vertex]['f'], neighbor_vertex])
if not found_dest:
print("We cannot found dest.")
result = a_star_search(graph, 0, 4)
print(result)Complexity Analysis
ต่อมา เรามาวิเคราะห์ Computational Complexity ของเทคนิคนี้ เราจะเห็นว่าเทคนิคนี้มี
- Time Complexity เท่ากับ O(b^d) โดย b is คือ branching factor ที่เป็นจำนวนเส้นเฉลี่ยในแต่ละโหนด และ d เป็นจำนวนโหนดบน Path ผลลัพธ์
- Space Complexity เท่ากับ O(b^d)
สำหรับรายละเอียดเกี่ยวกับ Time Complexity, Space Complexity และตัว Big-O อ่านได้ที่บทความที่แล้ว
การนำไปใช้
เทคนิค A* Search Algorithm นำไปประยุกต์ใช้ในงานทางด้านการค้นหา Path และงานทางด้านการทำ Optimization โดยนำไปใช้ [3] สำหรับวงการ
- Robotics: เทคนิค A* Search Algorithm ช่วยหุ่นยนต์เดินทางผ่านอุปสรรค และค้นหาเส้นทางที่เหมาะสม
- Video Games: ช่วย NPCs (Non-player character) เดินทางภายในเกมได้อย่างชาญฉลาด
- Route Planning: วางแผนเส้นทางที่สั้นที่สุด หรือเส้นทางที่เดินทางได้เร็วที่สุด
- Logistics: ช่วยวางแผนการเดินทางของรถขนส่ง
- Artificial Intelligence: ช่วยในงานทางด้าน Natural Language Processing และ Machine Learning
ในบทความนี้ เราจะยกตัวอย่างการประยุกต์ใช้เทคนิค A* Search Algorithm นั่นก็คือการค้นหาเส้นทางในเขาวงกต
A* Space Algorithm กับการเดินทางในเขาวงกต
เอาล่ะ เรามาเข้าเรื่องหลักของบทความนี้แล้ว หลังจากที่เกริ่นนาน 555
โจทย์ปัญหา
เราต้องการเดินทางในเขาวงกตหนึ่งตามภาพด้านล่างนี้ โดย
- กำหนดจุดเริ่มต้นที่มุมบนซ้าย และจุดสิ้นสุดที่มุมล่างขวา
- และกำหนดให้สีดำแสดงพื้นที่ที่เราเดินได้่ ส่วนสีขาวคือพื้นที่ที่เราเดินไม่ได้
เราต้องการให้คอมพิวเตอร์ประมวลผลเพื่อหาเส้นทางที่เหมาะสมที่สุด
การแก้ปัญหา
เราสามารถนำเทคนิค A* Search Algorithm ไปใช้ได้โดยการประมวลผลตามขั้นตอนด้านล่างนี้
- สร้างตัวแปร Maze ที่ระบุรายละเอียดตัวแปรใน Class ที่มี
- รายละเอียดของแผนที่ว่าเดินผ่านได้หรือไม่ (1 = เดินผ่านได้, 0 = ผ่านไม่ได้)
- พิกัดแกน x และ y
- ระบุโหนดก่อนหน้า (parent)
- ระบุค่า Heuristic (h(x)) กับ Cost (g(x)) และ Priority (f(x)) ให้เป็น Infinity ทั้งหมด ยกเว้นโหนดเริ่มต้นที่มีค่าเท่ากับ 0
- สร้าง Open List ที่เป็น Min-Heap Tree โดยกำหนดให้พิกัดเริ่มต้น (0, 0) เป็นรูท และสร้าง Closed List โดยให้ทุกพิกัดในเขาวงกตเป็น False
- ดึงโหนดรูทออกมา ประมวลผลเพื่อหาโหนดที่เชื่อมกันอยู่โดยพิจารณาจากทิศทางทั้งหมด 8 ทิศทาง (Up, Down, Left, Right, Up-left, Up-right, Down-left และ Down-right) โดย
- พิจารณาว่าพิกัดนั้นของเขาวงกตผ่านได้หรือไม่ (เช็คว่ามีค่าเท่ากับ 0 หรือไม่)
- เช็คว่าอยู่ใน Closed List หรือไม่
- และใช้ฟังก์ชันเพื่อหา cost ที่ต่ำที่สุด โดยกำหนดให้ h(x) มีค่าเท่ากับ h(x) ปัจจุบันบวกด้วย 1 กับ g(x) เท่ากับฟังก์ชันการค้นหาระยะทางที่ใช้ Euclidian Distance และค่า f(x) = h(x) + g(x)
- นำโหนดที่ผ่านการคำนวณ f(x) ที่ได้ค่าต่ำที่สุดเพิ่มเข้าไปใน Open List โดยโหนดที่ให้ค่า f(x) ต่ำที่สุดจะอยู่โหนดรูทตามหลัก Min-Heap
- เพิ่มพิกัดที่ดึงจากโหนดรูทเข้าไปใน Closed List โดยกำหนดให้เป็น True
- วนลูปตั้งแต่ข้อ 3 ถึง 5 จนกว่าจะถึงพิกัดสิ้นสุดของเขาวงกต
เราสามารถเขียนโค้ดได้สำหรับการทำ A* Search Algorithm ตามด้านล่างนี้
import heapq, copy, math
def isvalid(x, y, size_x, size_y):
return x >= 0 and x < size_x and y >= 0 and y < size_y
def maze_astar(maze_orig, source_x = 0, source_y = 0,
dest_x = 8, dest_y = 8, size_x = 4, size_y = 4):
if source_y == dest_y and source_x == dest_x:
print("This is a destination.")
return [[source_x, source_y]]
# Create Maze, Open and Closed List
maze = [[Cell(j, i, maze_orig[i][j]) for j in range(size_x)] for i in range(size_y)]
open = []
heapq.heappush(open, (0.0, source_x, source_y))
close = [[False for j in range(size_x)] for i in range(size_y)]
# Direction
direction = [
('U', 0, -1),
('D', 0, 1),
('F', 1, 0),
('B', -1, 0),
('UF', 1, -1),
('UB', -1, -1),
('DF', 1, 1),
('DB', -1, 1)
]
# Initial
maze[source_y][source_x].parent = None
maze[source_y][source_x].f = 0
maze[source_y][source_x].g = 0
maze[source_y][source_x].h = 0
found_dest = False
while len(open) > 0:
q = heapq.heappop(open)
source_x, source_y = q[1:]
close[source_y][source_x] = True
# Check if we found the destination.
if source_y == dest_y and source_x == dest_x:
print("We found the destination")
found_dest = True
# Trace back
dest_vertex = [source_x, source_y]
path = []
while True:
path.append(dest_vertex)
dest_vertex = maze[dest_vertex[1]][dest_vertex[0]].parent
if dest_vertex is None:
break
path.reverse()
return path
# Find Direction
for name, add_x, add_y in direction:
# New Coordinates
neighbor_x, neighbor_y = source_x + add_x, source_y + add_y
# Is not valid continue
if not isvalid(neighbor_x, neighbor_y, size_x, size_y) or \
maze[neighbor_y][neighbor_x].detail == '0' or \
close[neighbor_y][neighbor_x]:
continue
new_g = maze[source_y][source_x].g + 1
new_h = calculate_h(source_x, source_y, neighbor_x, neighbor_y)
new_f = new_h + new_g
if maze[neighbor_y][neighbor_x].f == float('inf') or \
new_f < maze[neighbor_y][neighbor_x].f:
maze[neighbor_y][neighbor_x].parent = [source_x, source_y]
maze[neighbor_y][neighbor_x].f = new_f
maze[neighbor_y][neighbor_x].g = new_h
maze[neighbor_y][neighbor_x].h = new_g
heapq.heappush(open, (new_f, neighbor_x, neighbor_y))
if not found_dest:
print("We cannot found dest.")
return []
return Noneโดยเรากำหนดฟังก์ชันการหา cost ของโหนดด้วยฟังก์ชัน Euclidian Distance ด้วยการเขียนโค้ดตามด้านล่างนี้
# Calculate_h by Euclidian Distance
def calculate_h(source_x, source_y, dest_x, dest_y):
return math.sqrt((source_x - dest_x) ** 2 +
(source_y - dest_y) ** 2)เรากำหนดให้เขาวงกตมีอาเรย์ตามด้านล่างนี้
class Cell:
def __init__(self, x, y, detail):
self.detail = detail
self.x = x
self.y = y
self.parent = [None, None]
self.h = float('inf')
self.g = float('inf')
self.f = float('inf')
maze = [
['1', '0', '0', '0', '0', '0', '0'],
['1', '1', '1', '1', '1', '1', '0'],
['1', '1', '0', '0', '0', '1', '0'],
['0', '1', '1', '0', '0', '0', '0'],
['0', '0', '1', '1', '1', '1', '0'],
['1', '1', '1', '1', '0', '1', '0'],
['1', '0', '0', '1', '0', '1', 'F'],
]
size_y = len(maze)
size_x = len(maze[0])เราสามารถแสดงเขาวงกตเป็นภาพได้ตามด้านล่างนี้ โดยให้ 0 เป็นสีขาว ส่วน 1 เป็นสีดำ
ต่อมา เราเขียนโค้ดสำหรับการรันคำสั่ง A* Search Algorithm สำหรับการเดินทางในเขาวงกตที่แสดงได้ตามด้านล่างนี้
output = maze_astar(maze, 0, 0,
size_x - 1, size_y - 1,
size_x, size_y)
visualize_maze = copy.deepcopy(maze)
for x, y in output:
visualize_maze[y][x] = 'X'
for i in range(size_y):
for j in range(size_x):
print(visualize_maze[i][j], end = '')
print('')จากนั้น สั่งให้รันเข้าไปในเขาวงกต
ผลลัพธ์ของการเดินในเขาวงกต เราแสดงตามภาพด้านล่างนี้ โดยสีฟ้าแสดงถึงการเดินในเขาวงกตตั้งแต่จุดเริ่มต้น ไปยังจุดสิ้นสุด
เพิ่มเติม
การค้นหาระยะทางในทางคณิตศาสตร์ เราสามารถใช้ฟังก์ชันการค้นหาระยะทาง (distance) ได้ตามด้านล่างนี้
Manhattan Distance ที่หาระยะทางโดยค่าสัมบูรณ์ (absolute) ของผลต่างระหว่างพิกัดเริ่มต้น กับพิกัดปลายทางในแกน x และ y
distance = |x_dist - x_source| + |y_dist - y_source|Euclidian Distance เราค้นหาระยะทางระหว่างพิกัดปลายทาง กับพิกัดต้นทางโดยการใช้รากที่สอง (Square Root) ของผลรวมยกกำลังสองของผลต่างระหว่างแกน x และแกน y
distance = sqrt((x_dist - x_source)^2 + (y_dist - y_source)^2)สรุป
เทคนิคการทำ Graph Traversal เพื่อหา Path ที่เหมาะสมที่สุด นอกจากเทคนิค Dijkstra’s กับ Bellman-Ford’s Algorithms แล้วยังมีเทคนิคที่ดีกว่าสองเทคนิคก่อนหน้า นั่นก็คือเทคนิค A* (อ่านว่าเอ-สตาร์) Search Algorithm
เทคนิคนี้เป็นเทคนิคที่ได้รับความนิยมมาก โดยนำไปใช้แก้ปัญหาในหลายด้าน ได้แก่ Robotics, Video Games, Route Planning, Logistics และ Artificial Intelligence
ในบทความนี้เรายกตัวอย่างการประยุกต์ใช้เทคนิคนี้ในการทำ Route Planning โดยวางแผนการเดินในเขาวงกตที่ให้ผลลัพธ์ตามที่เราต้องการ
สำหรับผู้อ่านที่เห็นว่าบทความนี้ดี มีประโยชน์ ให้กดไลค์ หรือกดแชร์ไปยังแพลตฟอร์มโซเชียลต่าง ๆ นอกจากนี้ ผู้อ่านยังติดตามได้่ใน Linkedin หรือ X (หรือ Twitter) ได้ครับ
