ใใฎ่จไบใฏ
ใA *ใขใซใดใชใบใ ใฎ็ดนไปใฎ็ถใ
ใงใ ใ ใใฎไธญใงใๅน
ๅชๅ
ๆค็ดขใใใคใฏในใใฉใฎใขใซใดใชใบใ ใๆ้ฉใชๆๅใฎไธ่ดใๆฑใใ่ฒชๆฌฒใชๆค็ดขใใใใณA *ใฎๅฎ่ฃ
ๆนๆณใ็คบใใพใใใ ่ชฌๆใใงใใ้ใ็ฐก็ด ๅใใใใจใใพใใใ
ใฐใฉใๆค็ดขใฏใ้กไผผใฎใขใซใดใชใบใ ใฎใใกใใชใผใงใใ ใขใซใดใชใบใ ใจใใฎๅฎ่ฃ
ใซใฏ
ๅคใใฎใใชใจใผใทใงใณใใใใพใใ ใใฎ่จไบใฎใณใผใใฏใใขใซใดใชใบใ ใฎๆ็ตใใผใธใงใณใงใฏใชใใใในใฆใฎ็ถๆณใซ้ฉใใ้ๅง็นใจใใฆๆฑใใพใใ
1. Pythonใฎๅฎ่ฃ
ไปฅไธใงใฏใใปใจใใฉใฎใณใผใใซใคใใฆ่ชฌๆใใพใใ
implementation.pyใใกใคใซใฏๅฐใๅบใใชใฃใฆใใพใใ ใณใผใใฏ
Python 3ใไฝฟ็จใใใใใPython 2ใไฝฟ็จใใๅ ดๅใฏใๅผใณๅบใใ
super()ใซๅคๆดใใ
print้ขๆฐใPython 2ใฎ้กไผผ็ฉใซๅคๆดใใๅฟ
่ฆใใใใพใใ
1.1ใฏใคใๆค็ดข
Pythonใงๅน
ๅชๅ
ๆค็ดขใๅฎ่ฃ
ใใพใใใใ ๆๅใฎ่จไบใงใฏใๆค็ดขใขใซใดใชใบใ ใฎPythonใณใผใใ็คบใใฆใใพใใใไฝฟ็จใใใฐใฉใใๆฑบๅฎใใๅฟ
่ฆใใใใพใใ ็งใไฝฟ็จใใใใใคใใฎๆฝ่ฑกๅใไปฅไธใซ็คบใใพใใ
ใฐใฉใ ๏ผๅใใคใณใใฎ่ฟๅใใฌใใผใใงใใใใผใฟๆง้ ๏ผ
ใใฎใใฅใผใใชใขใซใๅ็
ง๏ผ
ใใคใณใ๏ผๅ ดๆ๏ผ ๏ผใฐใฉใๅ
ใฎใใคใณใใใใผใฏใใๅ็ดใชๅค๏ผintใstringใtupleใชใฉ๏ผ
ๆค็ดข ๏ผใฐใฉใใ้ๅง็นใใใใณ๏ผใชใใทใงใณใง๏ผไธ้จใพใใฏใในใฆใฎ็นใฎๆ็จใชๆ
ๅ ฑ๏ผ่จชๅใ่ฆช่ฆ็ด ใธใฎใใคใณใฟใผใ่ท้ข๏ผใ่จ็ฎใใ็ตไบ็นใๅใๅใใขใซใดใชใบใ
ใญใฅใผ ๏ผๆค็ดขใขใซใดใชใบใ ใใใคใณใใฎๅฆ็้ ๅบใ้ธๆใใใใใซไฝฟ็จใใใใผใฟๆง้ ใ
ๆๅใฎ่จไบใงใฏใ็งใฏไธปใซ
ๆค็ดขใซใคใใฆ่ฆใฆใใพใใใ ใใฎ่จไบใงใฏใๅฎๅ
จใซๆฉ่ฝใใใใญใฐใฉใ ใไฝๆใใใใใซๅฟ
่ฆใชไปใฎใในใฆใ่ชฌๆใใพใใ
ใฐใฉใใใๅงใใพใใใ๏ผ
class SimpleGraph: def __init__(self): self.edges = {} def neighbors(self, id): return self.edges[id]
ใฏใใๅฟ
่ฆใชใฎใฏใใใ ใใงใ๏ผ ใใชใใฏๅฐใญใใใจใใงใใพใ๏ผใใผใใชใใธใงใฏใ๏ผใใผใ๏ผใฏใฉใใงใใ๏ผ ๅ็ญ๏ผใใผใใชใใธใงใฏใใฏใปใจใใฉไฝฟ็จใใพใใใ ๆดๆฐใๆๅญๅใใพใใฏใฟใใซใใใคใณใใจใใฆไฝฟ็จใใ้
ๅใพใใฏใใใทใฅใใผใใซใไฝฟ็จใใฆใใคใณใใใคใณใใใฏในใจใใฆไฝฟ็จใใๆนใ็ฐกๅใชใใใงใใ
ใจใใธใซใฏ
ๆนๅใใใใใจใซๆณจๆใใฆใใ ใใ๏ผAใใBใฎใจใใธใไฝฟ็จใงใใพใใใBใใAใฎใจใใธใฏไฝฟ็จใงใใพใใใใฒใผใ ใซใผใใงใฏใใจใใธใฏไธปใซๅๆนๅใงใใใๅ ดๅใซใใฃใฆใฏไธๆนๅใฎใใขใพใใฏๆฃใใใฎใธใฃใณใใใใใใใใฏๆๅใจใใธใจใใฆๆๅฎใใใพใใ
ใใคใณใใๆๅญAEใง็คบใใใใฐใฉใใฎไพใไฝๆใใฆใฟใพใใใใ
ๅใใคใณใใซใคใใฆใใใใๅฐใใใคใณใใฎใชในใใๅฟ
่ฆใงใใ
example_graph = SimpleGraph() example_graph.edges = { 'A': ['B'], 'B': ['A', 'C', 'D'], 'C': ['A'], 'D': ['E', 'A'], 'E': ['B'] }
ๆค็ดขใขใซใดใชใบใ ใไฝฟ็จใใๅใซใ
ใญใฅใผใ่จญๅฎใใๅฟ
่ฆใใใ
ใพใ ใ
import collections class Queue: def __init__(self): self.elements = collections.deque() def empty(self): return len(self.elements) == 0 def put(self, x): self.elements.append(x) def get(self): return self.elements.popleft()
ใใฎใญใฅใผใฏใฉในใฏใ็ตใฟ่พผใฟใฎ
collections.dequeใฏใฉในใฎๅใชใใฉใใใผใงใใ ใณใผใใง
deque็ดๆฅไฝฟ็จใงใใพใใ
ใใฎใญใฅใผใจๅใฎ่จไบใฎๅน
ๅชๅ
ใฎๆค็ดขใณใผใใงใฐใฉใใฎไพใไฝฟ็จใใฆใฟใพใใใใ
from implementation import * def breadth_first_search_1(graph, start):
Visiting 'A'
Visiting 'B'
Visiting 'C'
Visiting 'D'
Visiting 'E'ใฐใชใใใฏใฐใฉใใจใใฆ่กจ็พใใใใจใใงใใพใใ ๆฌกใซใใฟใใซใฎ๏ผintใint๏ผ
ใใคใณใใไฝฟ็จใใฆใๆฐใใ
SquareGrid ใฐใฉใใๅฎ็พฉใใพใใ ใจใใธใๆ็คบ็ใซไฟๅญใใไปฃใใใซใ
neighbors้ขๆฐใงใจใใธใ่จ็ฎใใพใใ
class SquareGrid: def __init__(self, width, height): self.width = width self.height = height self.walls = [] def in_bounds(self, id): (x, y) = id return 0 <= x < self.width and 0 <= y < self.height def passable(self, id): return id not in self.walls def neighbors(self, id): (x, y) = id results = [(x+1, y), (x, y-1), (x-1, y), (x, y+1)] if (x + y) % 2 == 0: results.reverse()
ๅใฎ่จไบใฎๆๅใฎใฐใชใใใงใในใใใฆใฟใพใใใใ
from implementation import * g = SquareGrid(30, 15) g.walls = DIAGRAM1_WALLS
. . . . . . . . . . . . . . . . . . . . . ####. . . . . . .
. . . . . . . . . . . . . . . . . . . . . ####. . . . . . .
. . . . . . . . . . . . . . . . . . . . . ####. . . . . . .
. . . ####. . . . . . . . . . . . . . . . ####. . . . . . .
. . . ####. . . . . . . . ####. . . . . . ####. . . . . . .
. . . ####. . . . . . . . ####. . . . . . ##########. . . .
. . . ####. . . . . . . . ####. . . . . . ##########. . . .
. . . ####. . . . . . . . ####. . . . . . . . . . . . . . .
. . . ####. . . . . . . . ####. . . . . . . . . . . . . . .
. . . ####. . . . . . . . ####. . . . . . . . . . . . . . .
. . . ####. . . . . . . . ####. . . . . . . . . . . . . . .
. . . ####. . . . . . . . ####. . . . . . . . . . . . . . .
. . . . . . . . . . . . . ####. . . . . . . . . . . . . . .
. . . . . . . . . . . . . ####. . . . . . . . . . . . . . .
. . . . . . . . . . . . . ####. . . . . . . . . . . . . . .ใในใๅไฝๆใใใซใฏใๅ
ใฎใใคใณใใไฟๅญใใๅฟ
่ฆใใใใใใ
visited ๏ผTrue / False๏ผใ
came_from ๏ผpoint๏ผใซๅคๆดใใพใใใ
from implementation import * def breadth_first_search_2(graph, start):
โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ ####โ โ โ โ โ โ โ
โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ ####โ โ โ โ โ โ โ
โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ ####โ โ โ โ โ โ โ
โ โ โ ####โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ ####โ โ โ โ โ โ โ
โ โ โ ####โ โ โ โ โ โ โ โ ####โ โ โ โ โ โ ####โ โ โ โ โ โ โ
โ โ โ ####โ โ โ โ โ โ โ โ ####โ โ โ โ โ โ ##########โ โ โ โ
โ โ โ ####โ โ โ โ โ โ โ โ ####โ โ โ โ โ โ ##########โ โ โ โ
โ โ โ ####โ โ โ A โ โ โ โ ####โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ
โ โ โ ####โ โ โ โ โ โ โ โ ####โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ
โ โ โ ####โ โ โ โ โ โ โ โ ####โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ
โ โ โ ####โ โ โ โ โ โ โ โ ####โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ
โ โ โ ####โ โ โ โ โ โ โ โ ####โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ
โ โ โ โ โ โ โ โ โ โ โ โ โ ####โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ
โ โ โ โ โ โ โ โ โ โ โ โ โ ####โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ
โ โ โ โ โ โ โ โ โ โ โ โ โ ####โ โ โ โ โ โ โ โ โ โ โ โ โ โ โไธ้จใฎๅฎ่ฃ
ใงใฏใNodeใชใใธใงใฏใใไฝๆใใใใจใซใใใใฐใฉใๅ
ใฎๅใใผใใฎ
came_fromใใใณใใฎไปใฎๅคใๆ ผ็ดใใใใใซ
ๅ
้จในใใฌใผใธใไฝฟ็จใใใพใใ ไปฃใใใซใ
ๅค้จในใใฌใผใธใไฝฟ็จใใฆใใฐใฉใๅ
ใฎใในใฆใฎใใผใใใ
came_fromใๆ ผ็ดใใๅไธใฎใใใทใฅใใผใใซใไฝๆใใใใจใซใใพใใใ ใใใไธใฎใใคใณใใซๆดๆฐใคใณใใใฏในใใใใใจใใใใฃใฆใใๅ ดๅใฏใๅฅใฎใชใใทใงใณใใใใพใ-้
ๅใไฝฟ็จใใฆ
came_fromใๆ ผ็ดใ
came_from ใ
1.2ๆฉๆ้ๅบ
ๅใฎ่จไบใฎใณใผใใ็นฐใ่ฟใใฆใใกใคใณใซใผใใซ
ifใณใณในใใฉใฏใใ่ฟฝๅ ใใใ ใใงใใ ใใฎใใงใใฏใฏๅน
ๅชๅ
ๆค็ดขใจใใคใฏในใใฉใฎใขใซใดใชใบใ ใงใฏใชใใทใงใณใงใใใๆ้ฉใชๆๅใฎไธ่ดใจA *ใฎ่ฒชๆฌฒใชๆค็ดขใงใฏๅฟ
้ ใงใใ
from implementation import * def breadth_first_search_3(graph, start, goal): frontier = Queue() frontier.put(start) came_from = {} came_from[start] = None while not frontier.empty(): current = frontier.get() if current == goal: break for next in graph.neighbors(current): if next not in came_from: frontier.put(next) came_from[next] = current return came_from g = SquareGrid(30, 15) g.walls = DIAGRAM1_WALLS parents = breadth_first_search_3(g, (8, 7), (17, 2)) draw_grid(g, width=2, point_to=parents, start=(8, 7), goal=(17, 2))
. โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ . . . . ####. . . . . . .
โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ . . . ####. . . . . . .
โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ Z . . . ####. . . . . . .
โ โ โ ####โ โ โ โ โ โ โ โ โ โ โ โ โ โ . . ####. . . . . . .
. โ โ ####โ โ โ โ โ โ โ โ ####โ โ โ . . . ####. . . . . . .
. . โ ####โ โ โ โ โ โ โ โ ####โ โ . . . . ##########. . . .
. . . ####โ โ โ โ โ โ โ โ ####โ . . . . . ##########. . . .
. . . ####โ โ โ A โ โ โ โ ####. . . . . . . . . . . . . . .
. . . ####โ โ โ โ โ โ โ โ ####. . . . . . . . . . . . . . .
. . โ ####โ โ โ โ โ โ โ โ ####. . . . . . . . . . . . . . .
. โ โ ####โ โ โ โ โ โ โ โ ####. . . . . . . . . . . . . . .
โ โ โ ####โ โ โ โ โ โ โ โ ####. . . . . . . . . . . . . . .
โ โ โ โ โ โ โ โ โ โ โ โ โ ####. . . . . . . . . . . . . . .
โ โ โ โ โ โ โ โ โ โ โ โ โ ####. . . . . . . . . . . . . . .
. โ โ โ โ โ โ โ โ โ โ โ โ ####. . . . . . . . . . . . . . .ใ่ฆงใฎใจใใใใขใซใดใชใบใ ใฏใฟใผใฒใใ
Z่ฆใคใใใจๅๆญขใ
Z1.3ใใคใฏในใใฉใฎใขใซใดใชใบใ
ใใใฏใขใซใดใชใบใ ใฎ่ค้ใใๅขใใพใใใๅ
็้ ใใ ใใงใชใใๆนๅใใใ้ ๅบใงใใคใณใใฎๅฆ็ใ้ๅงใใใใใงใใ ใฉใฎๅๅใไฝฟ็จใใพใใ๏ผ
- ใซใฆใณใใฏ็งปๅใฎใณในใใ็ฅใๅฟ
่ฆใใใใพใใ
- ใญใฅใผใฏใใผใใ็ฐใชใ้ ๅบใง่ฟใๅฟ
่ฆใใใใพใใ
- ๆค็ดขใฏใฐใฉใใงใใฎๅคใ่ฟฝ่ทกใใใญใฅใผใซๆธกใๅฟ
่ฆใใใใพใใ
1.3.1้ใฟไปใใซใฆใณใ
ใใคใณใ
from_nodeใใ้ฃๆฅใใ
to_nodeใซ็งปๅใใใณในใใไผใใ้ขๆฐ
cost(from_node, to_node)ใ่ฟฝๅ ใใพใใ ใใฎใใฉใฌในใใใใใงใฏใ็งปๅใฏ
to_nodeใฎใฟใซไพๅญใใใใจใๆฑบๅฎใใพใใใใ
ไธกๆนใฎใใผใใไฝฟ็จใใไปใฎใฟใคใใฎ็งปๅใใใใพใ ใ ๅฎ่ฃ
ใฎไปฃๆฟๆนๆณใฏใ
neighbors้ขๆฐใซใใผใธใใใใจใงใใ
class GridWithWeights(SquareGrid): def __init__(self, width, height): super().__init__(width, height) self.weights = {} def cost(self, from_node, to_node): return self.weights.get(to_node, 1)
1.3.2ๅชๅ
ๅบฆใญใฅใผ
ๅชๅ
ๅบฆใญใฅใผใฏใๅ่ฆ็ด ใซใๅชๅ
ๅบฆใใจๅผใฐใใ็ชๅทใ้ข้ฃไปใใพใใ ใขใคใใ ใ่ฟใใใใจใๆใๅฐใใ็ชๅทใฎใขใคใใ ใ้ธๆใใใพใใ
insert ๏ผใขใคใใ ใใญใฅใผใซ่ฟฝๅ ใใพใ
remove ๏ผๆๅฐใฎ็ชๅทใๆใค่ฆ็ด ใๅ้คใใพใ
reprioritize ๏ผ๏ผใชใใทใงใณ๏ผๆขๅญใฎใขใคใใ ใฎๅชๅ
ๅบฆใไฝใๆฐๅคใซๅคๆดใใพใใ
ใใใฏใ
ใใคใใชใใผใใไฝฟ็จใ
ใพใใใreprioritizeใงใฏใตใใผใใใใชใใใใชใ้ซ้ใชๅชๅ
ๅบฆใญใฅใผใงใใ ๆญฃใใ้ ๅบใๅๅพใใใซใฏใใฟใใซ๏ผๅชๅ
้ ไฝใ่ฆ็ด ๏ผใไฝฟ็จใใพใใ ใใงใซใญใฅใผใซใใใขใคใใ ใๆฟๅ
ฅใใใจใ้่คใใพใใ ๆ้ฉๅใปใฏใทใงใณใงใใใ็งใใกใซ้ฉใใฆใใ็็ฑใ่ชฌๆใใพใใ
import heapq class PriorityQueue: def __init__(self): self.elements = [] def empty(self): return len(self.elements) == 0 def put(self, item, priority): heapq.heappush(self.elements, (priority, item)) def get(self): return heapq.heappop(self.elements)[1]
1.3.3ๆค็ดข
ใใใซใฏๅฎ่ฃ
ใฎใใชใใญใผใช็ฌ้ใใใใพใใ็งปๅใฎใณในใใใคใพใใใใ่ฏใ
cost_so_farใๆใคใใคใณใใธใฎ็นฐใ่ฟใ่จชๅใฎ็ขบ็ใ่ฟฝๅ ใใใใ
cost_so_far ใ ใใใฏ
if next not in came_fromใซใชใ
if next not in came_fromใๆฉ่ฝใใชใใใจใๆๅณใใพใใ ไปฃใใใซใๆๅพใฎ่จชๅไปฅ้ใซใณในใใๆธๅฐใใใใฉใใใ็ขบ่ชใใๅฟ
่ฆใใใใพใใ ๏ผ่จไบใฎๅ
ใฎใใผใธใงใณใงใฏใใใใใงใใฏใใพใใใงใใใใใณใผใใฏใจใซใใๆฉ่ฝใใพใใใ
ใใฎใจใฉใผใซ้ขใใใกใขใๆธใใพใใ ใ๏ผ
ใใฎๆฃฎๆๅฐๅณใฏ
ๅใฎ่จไบใใๅใใใพใใใ
def dijkstra_search(graph, start, goal): frontier = PriorityQueue() frontier.put(start, 0) came_from = {} cost_so_far = {} came_from[start] = None cost_so_far[start] = 0 while not frontier.empty(): current = frontier.get() if current == goal: break for next in graph.neighbors(current): new_cost = cost_so_far[current] + graph.cost(current, next) if next not in cost_so_far or new_cost < cost_so_far[next]: cost_so_far[next] = new_cost priority = new_cost frontier.put(next, priority) came_from[next] = current return came_from, cost_so_far
ๆค็ดขๅพใใในใไฝๆใใๅฟ
่ฆใใใใพใใ
def reconstruct_path(came_from, start, goal): current = goal path = [current] while current != start: current = came_from[current] path.append(current) path.append(start)
ใในใฏใจใใธใฎใทใผใฑใณในใจใใฆๆใใใ็่งฃใใใพใใใใใผใใฎใทใผใฑใณในใจใใฆไฟๅญใใๆนใไพฟๅฉใงใใ ใในใไฝๆใใใซใฏใๆๅพใใๅงใใฆใๅใฎใใผใใๆใ
came_fromใใใใซๅพใใพใใ ๆๅใซๅฐ้ใใใจใไปไบใฏๅฎไบใงใใ ใใใ
ๆปใใในใงใใใใใใฃใฆใ
reconstruct_pathใฎๆๅพใงใ็ดๆฅใทใผใฑใณในใงๆ ผ็ดใใๅฟ
่ฆใใใๅ ดๅใฏใ
reverse()ใๅผใณๅบใใพใใ ๅฎ้ใใในใ้ใซไฟๅญใใๆนใไพฟๅฉใชๅ ดๅใใใใพใใ ใใใซใ้ๅงใใผใใใชในใใซไฟๅญใใใจไพฟๅฉใชๅ ดๅใใใใพใใ
่ฉฆใใฆใฟใพใใใ๏ผ
from implementation import * came_from, cost_so_far = dijkstra_search(diagram4, (1, 4), (7, 8)) draw_grid(diagram4, width=3, point_to=came_from, start=(1, 4), goal=(7, 8)) print() draw_grid(diagram4, width=3, number=cost_so_far, start=(1, 4), goal=(7, 8)) print() draw_grid(diagram4, width=3, path=reconstruct_path(came_from, start=(1, 4), goal=(7, 8)))
โ โ โ โ โ โ โ โ โ โ
โ โ โ โ โ โ โ โ โ โ
โ โ โ โ โ โ โ โ โ โ
โ โ โ โ โ โ โ โ โ .
โ A โ โ โ โ . . . .
โ โ โ โ โ โ . . . .
โ โ โ โ โ โ โ . . .
โ #########โ โ โ . . .
โ #########โ โ โ Z . .
โ โ โ โ โ โ โ โ โ .
5 4 5 6 7 8 9 10 11 12
4 3 4 5 10 13 10 11 12 13
3 2 3 4 9 14 15 12 13 14
2 1 2 3 8 13 18 17 14 .
1 A 1 6 11 16 . . . .
2 1 2 7 12 17 . . . .
3 2 3 4 9 14 19 . . .
4 #########14 19 18 . . .
5 #########15 16 13 Z . .
6 7 8 9 10 11 12 13 14 .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
@ @ . . . . . . . .
@ . . . . . . . . .
@ . . . . . . . . .
@ #########. . . . . .
@ #########. . @ @ . .
@ @ @ @ @ @ @ . . .if next not in cost_so_far or new_cost < cost_so_far[next]ใฎ่ก
if next not in cost_so_far or new_cost < cost_so_far[next] if new_cost < cost_so_far.get(next, Infinity)ใซ็ฐก็ฅๅใงใใพใใใๅๅใฎ่จไบใง
get() Pythonใ่ชฌๆใใใใชใใฃใใฎใงใใใฎใพใพใซใใพใใใ ใพใใ
collections.defaultdictใใใใฉใซใใฎ็ก้ๅคใงไฝฟ็จใใใใจใใงใใพใใ
1.4ๆค็ดขA *
ๆ้ฉใชๆๅใฎไธ่ดใฎ่ฒชๆฌฒใชๆค็ดขใจA *ใฎไธกๆนใงใใใฅใผใชในใใฃใใฏ้ขๆฐใไฝฟ็จใใใพใใ ๅฏไธใฎ้ใใฏใA *ใใใฅใผใชในใใฃใใฏใจใใคใฏในใใฉใฎใขใซใดใชใบใ ใฎ้ ๅบใฎไธกๆนใไฝฟ็จใใใใจใงใใ ใใใงA *ใ่กจ็คบใใพใใ
def heuristic(a, b): (x1, y1) = a (x2, y2) = b return abs(x1 - x2) + abs(y1 - y2) def a_star_search(graph, start, goal): frontier = PriorityQueue() frontier.put(start, 0) came_from = {} cost_so_far = {} came_from[start] = None cost_so_far[start] = 0 while not frontier.empty(): current = frontier.get() if current == goal: break for next in graph.neighbors(current): new_cost = cost_so_far[current] + graph.cost(current, next) if next not in cost_so_far or new_cost < cost_so_far[next]: cost_so_far[next] = new_cost priority = new_cost + heuristic(goal, next) frontier.put(next, priority) came_from[next] = current return came_from, cost_so_far
่ฉฆใใฆใฟใพใใใ๏ผ
from implementation import * came_from, cost_so_far = a_star_search(diagram4, (1, 4), (7, 8)) draw_grid(diagram4, width=3, point_to=came_from, start=(1, 4), goal=(7, 8)) print() draw_grid(diagram4, width=3, number=cost_so_far, start=(1, 4), goal=(7, 8))
. . . . . . . . . .
. โ โ โ . . . . . .
โ โ โ โ โ . . . . .
โ โ โ โ โ . . . . .
โ A โ โ โ . . . . .
โ โ โ โ โ . . . . .
โ โ โ โ โ โ . . . .
โ #########โ . โ . . .
โ #########โ โ โ Z . .
โ โ โ โ โ โ โ โ . .
. . . . . . . . . .
. 3 4 5 . . . . . .
3 2 3 4 9 . . . . .
2 1 2 3 8 . . . . .
1 A 1 6 11 . . . . .
2 1 2 7 12 . . . . .
3 2 3 4 9 14 . . . .
4 #########14 . 18 . . .
5 #########15 16 13 Z . .
6 7 8 9 10 11 12 13 . .1.4.1็ด็ทใใน
็ฌ่ชใฎใใญใธใงใฏใใซใใฎใณใผใใๅฎ่ฃ
ใใใจใไธ้จใฎใในใๅธๆใฉใใใฎใ็ดๆฅใใงใฏใชใใใจใใใใใพใใ
ใใใฏๆญฃๅธธใงใใ
ใฐใชใใ ใ็นใซๅในใใใใฎ็งปๅใณในใใๅใใฐใชใใใไฝฟ็จใใๅ ดๅใ
ๅ็ญใฎใชใใทใงใณใๅพใใ
ใพใ ใๅคใใฎใในใฎใณในใใฏใพใฃใใๅใใงใใ *ใฏๅคใใฎใทใงใผใใซใใใฎ1ใคใ้ธๆ
ใใพใใใ้ๅธธใซใใใใซ่ฆใใชใใใจใ้ๅธธใซๅคใ
ใใใพใ ใ
ๅ็ญใฎใชใใทใงใณใ
ๆ้คใใใฏใคใใฏใใใฏใ้ฉ็จใงใใพใใใๅธธใซๅฎๅ
จใซ้ฉๅใงใใใจใฏ้ใใพใใใ
ใใใใฎ่กจ็พใ
ๅคๆดใใใจใ A *ใๅคงๅน
ใซๅ ้ใใใใใ็ดๆฅ็ใงๅฟซ้ฉใชใในใไฝๆใใใพใใ ใใ ใใใใใฏใๅในใใใใซ1ใคใฎ็งปๅใณในใใใใ้็ใซใผใใซ้ฉใใฆใใพใใ ็งใฎใใผใธใฎใใขใงใฏใ็ฐกๅใชใใใฏใไฝฟ็จใใฆใใพใใใๅชๅ
ๅบฆใฎไฝใใญใฅใผใงใฎใฟๆฉ่ฝใใพใใ ใใ้ซ้ใชๅชๅ
ๅบฆใญใฅใผใซๅใๆฟใใๅ ดๅใฏใๅฅใฎใฏใคใใฏใใใฏใๅฟ
่ฆใงใใ
2 C ++ๅฎ่ฃ
ๆณจ๏ผใตใณใใซใณใผใใฎไธ้จใๅฎ่กใใใซใฏใ
redblobgames / pathfinding / a-star / implementation.cppใ่ฟฝๅ ใ
ใพใ ใ ใใฎใณใผใใซใฏ
C ++ 11ใไฝฟ็จใใฆใใใใใๅคใใใผใธใงใณใฎC ++ๆจๆบใไฝฟ็จใใฆใใๅ ดๅใฏใ้จๅ็ใซๅคๆดใใๅฟ
่ฆใใใใพใใ
2.1ใฏใคใๆค็ดข
ๆๅใซPythonใปใฏใทใงใณใ็ขบ่ชใใฆใใ ใใใ ใใฎใปใฏใทใงใณใซใฏใณใผใใใใใพใใใๅใ่ชฌๆใฏใใใพใใใ ใพใใไธ่ฌ็ใชใฐใฉใใฏใฉในใ่ฟฝๅ ใใพใใ
template<typename L> struct SimpleGraph { typedef L Location; typedef typename vector<Location>::iterator iterator; unordered_map<Location, vector<Location> > edges; inline const vector<Location> neighbors(Location id) { return edges[id]; } };
charใไฝฟ็จใใฆใใคใณใใใใผใฏใใPythonใณใผใใฎๅใใฐใฉใใฎไพ๏ผ
SimpleGraph<char> example_graph {{ {'A', {'B'}}, {'B', {'A', 'C', 'D'}}, {'C', {'A'}}, {'D', {'E', 'A'}}, {'E', {'B'}} }};
ใญใฅใผใฏใฉในใๅฎ็พฉใใไปฃใใใซใC ++ๆจๆบใฉใคใใฉใชใฎใฏใฉในใไฝฟ็จใใพใใ ใใใงใๅน
ๅชๅ
ใฎๆค็ดขใ่ฉฆใฟใใใจใใงใใพใใ
#include "redblobgames/pathfinding/a-star/implementation.cpp" template<typename Graph> void breadth_first_search(Graph graph, typename Graph::Location start) { typedef typename Graph::Location Location; queue<Location> frontier; frontier.push(start); unordered_set<Location> visited; visited.insert(start); while (!frontier.empty()) { auto current = frontier.front(); frontier.pop(); std::cout << "Visiting " << current << std::endl; for (auto& next : graph.neighbors(current)) { if (!visited.count(next)) { frontier.push(next); visited.insert(next); } } } } int main() { breadth_first_search(example_graph, 'A'); }
Visiting A
Visiting B
Visiting C
Visiting D
Visiting EใณใผใใฏPythonใใใๅฐใ้ทใใชใใพใใใใใใฏ้ๅธธใซๆญฃๅธธใงใใ
ๆญฃๆนๅฝขใฐใชใใใฏใฉใใงใใ๏ผ ๅฅใฎใฏใฉในใฎใฐใฉใใๅฎ็พฉใใพใใ ใฐใฉใใฎๅใฎใฏใฉในใจใฏ้ขไฟใใชใใใจใซๆณจๆใใฆใใ ใใใ ็ถๆฟใงใฏใชใใใณใใฌใผใใไฝฟ็จใใพใใ ใฐใฉใใฏใtypedef
Locationใจ
neighbors้ขๆฐใฎใฟใๆไพใใๅฟ
่ฆใใใใพใใ
struct SquareGrid { typedef tuple<int,int> Location; static array<Location, 4> DIRS; int width, height; unordered_set<Location> walls; SquareGrid(int width_, int height_) : width(width_), height(height_) {} inline bool in_bounds(Location id) const { int x, y; tie (x, y) = id; return 0 <= x && x < width && 0 <= y && y < height; } inline bool passable(Location id) const { return !walls.count(id); } vector<Location> neighbors(Location id) const { int x, y, dx, dy; tie (x, y) = id; vector<Location> results; for (auto dir : DIRS) { tie (dx, dy) = dir; Location next(x + dx, y + dy); if (in_bounds(next) && passable(next)) { results.push_back(next); } } if ((x + y) % 2 == 0) {
ใใซใใผใใกใคใซ
implementation.cppใฐใชใใใใฌใณใใชใณใฐใใใใใฎ้ขๆฐใๅฎ็พฉใใพใใใ
#include "redblobgames/pathfinding/a-star/implementation.cpp" int main() { SquareGrid grid = make_diagram1(); draw_grid(grid, 2); }
. . . . . . . . . . . . . . . . . . . . . ####. . . . . . .
. . . . . . . . . . . . . . . . . . . . . ####. . . . . . .
. . . . . . . . . . . . . . . . . . . . . ####. . . . . . .
. . . ####. . . . . . . . . . . . . . . . ####. . . . . . .
. . . ####. . . . . . . . ####. . . . . . ####. . . . . . .
. . . ####. . . . . . . . ####. . . . . . ##########. . . .
. . . ####. . . . . . . . ####. . . . . . ##########. . . .
. . . ####. . . . . . . . ####. . . . . . . . . . . . . . .
. . . ####. . . . . . . . ####. . . . . . . . . . . . . . .
. . . ####. . . . . . . . ####. . . . . . . . . . . . . . .
. . . ####. . . . . . . . ####. . . . . . . . . . . . . . .
. . . ####. . . . . . . . ####. . . . . . . . . . . . . . .
. . . . . . . . . . . . . ####. . . . . . . . . . . . . . .
. . . . . . . . . . . . . ####. . . . . . . . . . . . . . .
. . . . . . . . . . . . . ####. . . . . . . . . . . . . . .came_from่ฟฝ่ทกใใฆใๅน
ๅชๅ
ใฎๆค็ดขใ่กใใพใใใใ
#include "redblobgames/pathfinding/a-star/implementation.cpp" template<typename Graph> unordered_map<typename Graph::Location, typename Graph::Location> breadth_first_search(Graph graph, typename Graph::Location start) { typedef typename Graph::Location Location; queue<Location> frontier; frontier.push(start); unordered_map<Location, Location> came_from; came_from[start] = start; while (!frontier.empty()) { auto current = frontier.front(); frontier.pop(); for (auto& next : graph.neighbors(current)) { if (!came_from.count(next)) { frontier.push(next); came_from[next] = current; } } } return came_from; } int main() { SquareGrid grid = make_diagram1(); auto parents = breadth_first_search(grid, std::make_tuple(7, 8)); draw_grid(grid, 2, nullptr, &parents); }
โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ ####โ โ โ โ โ โ โ
โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ ####โ โ โ โ โ โ โ
โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ ####โ โ โ โ โ โ โ
โ โ โ ####โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ ####โ โ โ โ โ โ โ
โ โ โ ####โ โ โ โ โ โ โ โ ####โ โ โ โ โ โ ####โ โ โ โ โ โ โ
โ โ โ ####โ โ โ โ โ โ โ โ ####โ โ โ โ โ โ ##########โ โ โ โ
โ โ โ ####โ โ โ โ โ โ โ โ ####โ โ โ โ โ โ ##########โ โ โ โ
โ โ โ ####โ โ โ โ โ โ โ โ ####โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ
โ โ โ ####โ โ * โ โ โ โ โ ####โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ
โ โ โ ####โ โ โ โ โ โ โ โ ####โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ
โ โ โ ####โ โ โ โ โ โ โ โ ####โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ
โ โ โ ####โ โ โ โ โ โ โ โ ####โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ
โ โ โ โ โ โ โ โ โ โ โ โ โ ####โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ
โ โ โ โ โ โ โ โ โ โ โ โ โ ####โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ
โ โ โ โ โ โ โ โ โ โ โ โ โ ####โ โ โ โ โ โ โ โ โ โ โ โ โ โ โๅฎ่ฃ
ใซใใฃใฆใฏใ
ๅ
้จในใใฌใผใธใไฝฟ็จใใฆNodeใชใใธใงใฏใใไฝๆใใ
came_fromใใใณใฐใฉใๅ
ใฎๅใใผใใฎใใฎไปใฎๅคใไฟๅญใใพใใ
ๅค้จในใใฌใผใธใไฝฟ็จใใฆใๅไธใฎ
std::unordered_mapใไฝๆใใฆใใฐใฉใใฎใในใฆใฎใใผใใฎ
came_fromใไฟๅญใใใใจใ
came_fromใพใใใ ใใใไธใฎใใคใณใใซๆดๆฐใคใณใใใฏในใใใใใจใใใใฃใฆใใๅ ดๅใฏใๅฅใฎใชใใทใงใณใใใใพใใ1ๆฌกๅ
ใพใใฏ2ๆฌกๅ
ใฎ้
ๅ/ใใฏใใซใไฝฟ็จใใฆ
came_fromใใใณใใฎไปใฎๅคใๆ ผ็ดใใพใใ
2.1.1 TODO๏ผๆง้ ไฝใใคใณใ
ใใฎใณใผใใงใฏใPythonใณใผใใงใฟใใซใไฝฟ็จใใใใใ
std::tuple C ++ใไฝฟ็จใใพใใ ใใ ใใใฟใใซใฏใปใจใใฉใฎC ++ใใญใฐใฉใใซใฏ้ฆดๆใฟใใใใพใใใ ใณใณในใใฉใฏใฟใผใใณใใผใณใณในใใฉใฏใฟใผใไปฃๅ
ฅๆผ็ฎๅญใใใใณใใใทใฅ้ขๆฐใจใฎ็ญไพกๆฏ่ผใๅฎ็พฉใใๅฟ
่ฆใใใใใใ{xใy}ใไฝฟ็จใใฆๆง้ ไฝใๅฎ็พฉใใใฎใฏใใๅฐใ้ทใใชใใพใใใใใฎใณใผใใฏใปใจใใฉใฎC ++ใใญใฐใฉใใผใซ
ใใ็ฅใใใฆใใพใใ ๅคๆดใใๅฟ
่ฆใใใใพใใ
ใใ1ใคใฎใชใใทใงใณ๏ผใณใผใใงไฝฟ็จ๏ผใฏใ{xใy}ใ
intใจใใฆใจใณใณใผใใใใใจใงใใ T A *ใณใผใใซใไปปๆใฎ
Locationใฟใคใใงใฏใชใใๅธธใซๆดๆฐๅคใฎๅฏใชใปใใใใใๅ ดๅใใใใซใใ่ฟฝๅ ใฎๆ้ฉๅใไฝฟ็จใงใใพใใ ใใใทใฅใใผใใซใงใฏใชใใ็ฐใชใใปใใใซ้
ๅใไฝฟ็จใงใใพใใ ใใใใฎใปใจใใฉใๅๆๅใใใซๆฎใใใจใใงใใพใใ ๆฏๅๅๅๆๅใใๅฟ
่ฆใใใ้
ๅใฎๅ ดๅใA *ๅผใณๅบใใงๅฎๆฐใซใ๏ผใใใใใญใผใซใซในใฌใใในใใขใไฝฟ็จ๏ผใๅใฎๅผใณๅบใใงไฝฟ็จใใใ้
ๅใฎ้จๅใฎใฟใๅๅๆๅใงใใพใใ ใใใฏใใจใณใใชใผใฌใใซใฎใใฅใผใใชใขใซใงใฏไฝฟ็จใใใใชใใใใ่ค้ใชๆๆณใงใใ
2.2ๆฉๆ้ๅบ
Pythonใฎใใผใธใงใณใจๅๆงใซใ้ขๆฐใซใใฉใกใผใฟใผใ่ฟฝๅ ใใฆใกใคใณใซใผใใ็ขบ่ชใใใ ใใงใใ
#include "redblobgames/pathfinding/a-star/implementation.cpp" template<typename Graph> unordered_map<typename Graph::Location, typename Graph::Location> breadth_first_search(const Graph& graph, typename Graph::Location start, typename Graph::Location goal) { typedef typename Graph::Location Location; queue<Location> frontier; frontier.push(start); unordered_map<Location, Location> came_from; came_from[start] = start; while (!frontier.empty()) { auto current = frontier.front(); frontier.pop(); if (current == goal) { break; } for (auto& next : graph.neighbors(current)) { if (!came_from.count(next)) { frontier.push(next); came_from[next] = current; } } } return came_from; } int main() { SquareGrid grid = make_diagram1(); auto parents = breadth_first_search(grid, SquareGrid::Location{8, 7}, SquareGrid::Location{17, 2}); draw_grid(grid, 2, nullptr, &parents); }
. โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ . . . . ####. . . . . . .
โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ . . . ####. . . . . . .
โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ โ . . . ####. . . . . . .
โ โ โ ####โ โ โ โ โ โ โ โ โ โ โ โ โ โ . . ####. . . . . . .
. โ โ ####โ โ โ โ โ โ โ โ ####โ โ โ . . . ####. . . . . . .
. . โ ####โ โ โ โ โ โ โ โ ####โ โ . . . . ##########. . . .
. . . ####โ โ โ โ โ โ โ โ ####โ . . . . . ##########. . . .
. . . ####โ โ โ * โ โ โ โ ####. . . . . . . . . . . . . . .
. . . ####โ โ โ โ โ โ โ โ ####. . . . . . . . . . . . . . .
. . โ ####โ โ โ โ โ โ โ โ ####. . . . . . . . . . . . . . .
. โ โ ####โ โ โ โ โ โ โ โ ####. . . . . . . . . . . . . . .
โ โ โ ####โ โ โ โ โ โ โ โ ####. . . . . . . . . . . . . . .
โ โ โ โ โ โ โ โ โ โ โ โ โ ####. . . . . . . . . . . . . . .
โ โ โ โ โ โ โ โ โ โ โ โ โ ####. . . . . . . . . . . . . . .
. โ โ โ โ โ โ โ โ โ โ โ โ ####. . . . . . . . . . . . . . .2.3ใใคใฏในใใฉใฎใขใซใดใชใบใ
2.3.1้ใฟไปใใซใฆใณใ
็งปๅใฎใณในใใ5ใงใใใใฉใฌในใใฟใคใซใฎใชในใใๆใคใฐใชใใใใใใพใใใใฎใใฉใฌในใใใใใงใฏใ
to_nodeใฎใฟใซ
to_node็งปๅใๅฎ่กใใใใจใซใ
to_node ใ
ไธกๆนใฎใใผใใไฝฟ็จใใไปใฎใฟใคใใฎ็งปๅใใใใพใ ใ
struct GridWithWeights: SquareGrid { unordered_set<Location> forests; GridWithWeights(int w, int h): SquareGrid(w, h) {} double cost(Location from_node, Location to_node) const { return forests.count(to_node) ? 5 : 1; } };
2.3.2ๅชๅ
ๅบฆใญใฅใผ
ๅชๅ
ใญใฅใผใๅฟ
่ฆใงใใ C ++ใซใฏใใใคใใชใใผใใไฝฟ็จใใ
priority_queueใฏใฉในใใใใพใใใๅชๅ
ๅบฆใฎๅคๆดๆไฝใฏใใใพใใใ ใญใฅใผ่ฆ็ด ใซๆญฃใใ้ ๅบใๅๅพใใใใใซใใข๏ผๅชๅ
ๅบฆใ่ฆ็ด ๏ผใไฝฟ็จใใฆใใพใใ ใใใฉใซใใงใฏใC ++ๅชๅ
ๅบฆใญใฅใผใฏๆๅใซ
std::lessใณใณใใฌใผใฟใผใไฝฟ็จใใฆๆๅคง่ฆ็ด ใ่ฟใใพใใ ๆๅฐ้ใฎ่ฆ็ด ใๅฟ
่ฆใชใฎใงใ
std::greaterใณใณใใฌใผใฟใผใไฝฟ็จใใพใใ
template<typename T, typename priority_t> struct PriorityQueue { typedef pair<priority_t, T> PQElement; priority_queue<PQElement, vector<PQElement>, std::greater<PQElement>> elements; inline bool empty() const { return elements.empty(); } inline void put(T item, priority_t priority) { elements.emplace(priority, item); } inline T get() { T best_item = elements.top().second; elements.pop(); return best_item; } };
ใใฎใตใณใใซใณใผใใงใฏใC ++
std::priority_queueใใฉใใใใฆใใพใใใใใฎใฏใฉในใใฉใใใผใชใใงไฝฟ็จใใใฎใ่ณขๆใ ใจๆใใพใใ
2.3.3ๆค็ดข
ๅใฎ่จไบใฎๆฃฎใฎ
ๅฐๅณใใ่ฆงใใ ใใใ
template<typename Graph> void dijkstra_search (const Graph& graph, typename Graph::Location start, typename Graph::Location goal, unordered_map<typename Graph::Location, typename Graph::Location>& came_from, unordered_map<typename Graph::Location, double>& cost_so_far) { typedef typename Graph::Location Location; PriorityQueue<Location, double> frontier; frontier.put(start, 0); came_from[start] = start; cost_so_far[start] = 0; while (!frontier.empty()) { auto current = frontier.get(); if (current == goal) { break; } for (auto& next : graph.neighbors(current)) { double new_cost = cost_so_far[current] + graph.cost(current, next); if (!cost_so_far.count(next) || new_cost < cost_so_far[next]) { cost_so_far[next] = new_cost; came_from[next] = current; frontier.put(next, new_cost); } } } }
costๅคๆฐใฎใฟใคใใฏใใฐใฉใใงไฝฟ็จใใใใฟใคใใจไธ่ดใใๅฟ
่ฆใใใใพใใ
intใไฝฟ็จใใๅ ดๅใๅชๅ
ๅบฆใญใฅใผใฎๅฏๅคใณในใใจๅชๅ
ๅบฆใซ
intใไฝฟ็จใงใใพใใ
doubleใไฝฟ็จใใๅ ดๅใฏใใใใใซใ
doubleใไฝฟ็จใใๅฟ
่ฆใใใใพใใ ใใฎใณใผใใงใฏ
doubleใไฝฟ็จใใพใใใใ
intใไฝฟ็จใงใใใณใผใใฏๅใใใใซๆฉ่ฝใใพใใ ใใ ใใใฐใฉใใฎใจใใธใฎใณในใใdoubleใงๆ ผ็ดใใใฆใใๅ ดๅใใพใใฏdoubleใใใฅใผใชในใใฃใใฏใงไฝฟ็จใใใฆใใๅ ดๅใใใใงdoubleใไฝฟ็จใใๅฟ
่ฆใใใใพใใ
ๆๅพใซใๆค็ดขๅพใใในใไฝๆใใๅฟ
่ฆใใใใพใใ
template<typename Location> vector<Location> reconstruct_path( Location start, Location goal, unordered_map<Location, Location>& came_from ) { vector<Location> path; Location current = goal; path.push_back(current); while (current != start) { current = came_from[current]; path.push_back(current); } path.push_back(start);
ใในใฏใจใใธใฎใทใผใฑใณในใจใใฆๆใใใ็่งฃใใใพใใใใใผใใฎใทใผใฑใณในใจใใฆไฟๅญใใใจไพฟๅฉใงใใ ใในใไฝๆใใใซใฏใๆๅพใใๅงใใฆ
came_fromใใใใซๅพใใๅใฎใใผใใ
came_fromใพใใ ใใญใปในใฏๆๅใซๅฐ้ใใใจ็ตไบใใพใใ ใใใฏ
ๆปใใในใชใฎใงใ็ดๆฅไฟๅญใใๅ ดๅใฏใ
reconstruct_pathใฎๆๅพใซ
reverse()ใๅผใณๅบใๅฟ
่ฆใใใใพใใ ใในใ้ใซไฟๅญใใๆนใไพฟๅฉใชๅ ดๅใใใใพใใ ใพใใ้ๅงใใผใใใชในใใซไฟๅญใใใจไพฟๅฉใชๅ ดๅใใใใพใใ
่ฉฆใใฆใฟใพใใใ๏ผ
#include "redblobgames/pathfinding/a-star/implementation.cpp" int main() { GridWithWeights grid = make_diagram4(); SquareGrid::Location start{1, 4}; SquareGrid::Location goal{8, 5}; unordered_map<SquareGrid::Location, SquareGrid::Location> came_from; unordered_map<SquareGrid::Location, double> cost_so_far; dijkstra_search(grid, start, goal, came_from, cost_so_far); draw_grid(grid, 2, nullptr, &came_from); std::cout << std::endl; draw_grid(grid, 3, &cost_so_far, nullptr); std::cout << std::endl; vector<SquareGrid::Location> path = reconstruct_path(start, goal, came_from); draw_grid(grid, 3, nullptr, nullptr, &path); }
โ โ โ โ โ โ โ โ โ โ
โ โ โ โ โ โ โ โ โ โ
โ โ โ โ โ โ โ โ โ โ
โ โ โ โ โ โ โ โ โ โ
โ * โ โ โ โ โ โ โ โ
โ โ โ โ โ โ . โ โ .
โ โ โ โ โ โ โ โ โ .
โ ######โ โ โ โ โ .
โ ######โ โ โ โ โ โ
โ โ โ โ โ โ โ โ โ โ
5 4 5 6 7 8 9 10 11 12
4 3 4 5 10 13 10 11 12 13
3 2 3 4 9 14 15 12 13 14
2 1 2 3 8 13 18 17 14 15
1 0 1 6 11 16 21 20 15 16
2 1 2 7 12 17 . 21 16 .
3 2 3 4 9 14 19 16 17 .
4 #########14 19 18 15 16 .
5 #########15 16 13 14 15 16
6 7 8 9 10 11 12 13 14 15
. @ @ @ @ @ @ . . .
. @ . . . . @ @ . .
. @ . . . . . @ @ .
. @ . . . . . . @ .
. @ . . . . . . @ .
. . . . . . . . @ .
. . . . . . . . . .
. #########. . . . . .
. #########. . . . . .
. . . . . . . . . .ๅชๅ
ใญใฅใผใงใฏ็ตใฟ่พผใฟใฎใใใทใฅใใผใใซใไฝฟ็จใใใใใทใฅใใผใใซใฎๅๅพฉ้ ๅบใไธๅฎใงใฏใชใใใใ็ตๆใฏPythonใใผใธใงใณใฎ็ตๆใจๅฎๅ
จใซใฏไธ่ดใใพใใใ
2.4ๆค็ดขA *
*ใฏใ่ฟฝๅ ใใใใใฅใผใชในใใฃใใฏๆค็ดขใ้คใใใใคใฏในใใฉใฎใขใซใดใชใบใ ใใปใผๅฎๅ
จใซ็นฐใ่ฟใใพใใ ใขใซใดใชใบใ ใณใผใ
ใฏใฐใชใใใ ใใงใชใไฝฟ็จใงใใใใจใซๆณจๆใใฆใใ ใใใ ใฐใชใใใฎ็ฅ่ญใฏใใฐใฉใใฏใฉใน๏ผใใฎๅ ดๅใฏ
SquareGrids ๏ผใจ
heuristic้ขๆฐใซใใใพใใ ใใใใ็ฝฎใๆใใๅ ดๅใใขใซใดใชใบใ ใณใผใA *ใไปใฎใฐใฉใๆง้ ใงไฝฟ็จใงใใพใใ
inline double heuristic(SquareGrid::Location a, SquareGrid::Location b) { int x1, y1, x2, y2; tie (x1, y1) = a; tie (x2, y2) = b; return abs(x1 - x2) + abs(y1 - y2); } template<typename Graph> void a_star_search (const Graph& graph, typename Graph::Location start, typename Graph::Location goal, unordered_map<typename Graph::Location, typename Graph::Location>& came_from, unordered_map<typename Graph::Location, double>& cost_so_far) { typedef typename Graph::Location Location; PriorityQueue<Location, double> frontier; frontier.put(start, 0); came_from[start] = start; cost_so_far[start] = 0; while (!frontier.empty()) { auto current = frontier.get(); if (current == goal) { break; } for (auto& next : graph.neighbors(current)) { double new_cost = cost_so_far[current] + graph.cost(current, next); if (!cost_so_far.count(next) || new_cost < cost_so_far[next]) { cost_so_far[next] = new_cost; double priority = new_cost + heuristic(next, goal); frontier.put(next, priority); came_from[next] = current; } } } }
priorityๅชๅ
ๅบฆใญใฅใผใซไฝฟ็จใใใใฟใคใใๅซใๅคใฎใฟใคใใฏใใฐใฉใใฎใณในใ๏ผcost_t๏ผใจใใฅใผใชในใใฃใใฏๅคใฎไธกๆนใๅซใใใฎใซๅๅใชๅคงใใใงใใๅฟ
่ฆใใใใพใใใใจใใฐใใฐใฉใใฎๅคใintใซๆ ผ็ดใใใฆใใใใใฅใผใชในใใฃใใฏใdoubleใ่ฟใๅ ดๅใๅชๅ
ๅบฆใญใฅใผใdoubleใๅไฟกใงใใใใจใๅฟ
่ฆใงใใใใฎใณใผใไพใงใฏใdouble3ใคใฎๅค๏ผๅคใใใฅใผใชในใใฃใใฏใใใใณๅชๅ
้ ไฝ๏ผใในใฆใซไฝฟ็จใใฆใใพใใintใๅคใจใใฅใผใชในใใฃใใฏใซใฏๆดๆฐๅคใใใใใใandใไฝฟ็จใงใใพใใ็ฐกๅใชใกใข๏ผใใใฏๆธใ่พผใฟใซ่ฏใใ ใใfrontier.put(start, heuristic(start, goal))ใใจใงใฏใใใพใใfrontier.put(start, 0)ใใใ ใใ้ๅงใใผใใฎๅชๅ
้ ไฝใฏ้่ฆใงใฏใชใใใใใใใงใฏ้่ฆใงใฏใใใพใใใใใใฏๅชๅ
ๅบฆใญใฅใผใฎๅฏไธใฎใใผใใงใใใใใใซไฝใใๆธใ่พผใพใใๅใซ้ธๆใใใณๅ้คใใใพใใ #include "redblobgames/pathfinding/a-star/implementation.cpp" int main() { GridWithWeights grid = make_diagram4(); SquareGrid::Location start{1, 4}; SquareGrid::Location goal{8, 5}; unordered_map<SquareGrid::Location, SquareGrid::Location> came_from; unordered_map<SquareGrid::Location, double> cost_so_far; a_star_search(grid, start, goal, came_from, cost_so_far); draw_grid(grid, 2, nullptr, &came_from); std::cout << std::endl; draw_grid(grid, 3, &cost_so_far, nullptr); std::cout << std::endl; vector<SquareGrid::Location> path = reconstruct_path(start, goal, came_from); draw_grid(grid, 3, nullptr, nullptr, &path); }
โ โ โ โ โ โ โ โ โ โ
โ โ โ โ โ โ โ โ โ โ
โ โ โ โ โ โ โ โ โ โ
โ โ โ โ โ โ . โ โ โ
โ * โ โ โ โ . โ โ โ
โ โ โ โ โ โ . . โ .
โ โ โ โ โ โ . . . .
โ ######โ . . . . .
โ ######. . . . . .
โ . . . . . . . . .
5 4 5 6 7 8 9 10 11 12
4 3 4 5 10 13 10 11 12 13
3 2 3 4 9 14 15 12 13 14
2 1 2 3 8 13 . 17 14 15
1 0 1 6 11 16 . 20 15 16
2 1 2 7 12 17 . . 16 .
3 2 3 4 9 14 . . . .
4 #########14 . . . . .
5 #########. . . . . .
6 . . . . . . . . .
. . . @ @ @ @ . . .
. . . @ . . @ @ . .
. . . @ . . . @ @ .
. . @ @ . . . . @ .
. @ @ . . . . . @ .
. . . . . . . . @ .
. . . . . . . . . .
. #########. . . . . .
. #########. . . . . .
. . . . . . . . . .2.4.1็ด็ทๅ
ใใฎใณใผใใใใญใธใงใฏใใซๅฎ่ฃ
ใใใจใไธ้จใฎใในใๅธๆใฉใใใซใ็ดๆฅใใงใฏใชใใใจใซๆฐไปใใใใใใพใใใใใใฏๅคงไธๅคซใงใใใฐใชใใใ็นใซๅในใใใใฎ็งปๅใณในใใๅใใฐใชใใใไฝฟ็จใใๅ ดๅใ็ตๆใฏๅ็ญใฎใชใใทใงใณใซใชใใพใใๅคใใฎใในใฎใณในใใฏๅใใงใใ*ใฏๅคใใฎๆ็ญใในใฎ1ใคใ้ธๆใใพใใใ้ๅธธใซใใใใซ่ฆใใชใใใจใ้ๅธธใซๅคใใใใพใใๅ็ญใฎใชใใทใงใณใฏ็ฐกๅใชใใใฏใงๆ้คใงใใพใใใๅฎๅ
จใซ้ฉๅใจใใใใใงใฏใใใพใใใใใใใใฅใผใๅคๆดใใใใจใใๅงใใใพใใA *ใๅคงๅน
ใซๅ ้ใใใใ็ดๆฅ็ใง็พใใใในใไฝๆใใพใใใใ ใใใใใฏๅในใใใใฎ็งปๅใณในใใๅใ้็ใซใผใใงใฎใฟๆฉ่ฝใใพใใ็งใฎใใผใธใฎใใขใงใฏใใฏใคใใฏใใใฏใไฝฟ็จใใพใใใใๅชๅ
ๅบฆใฎไฝใใญใฅใผใงใฎใฟๆฉ่ฝใใพใใใใ้ซ้ใชๅชๅ
ใญใฅใผใซ็งปๅใใๅ ดๅใฏใๅฅใฎ้ซ้ใใใฏใๅฟ
่ฆใงใใ2.4.2 TODO๏ผใใฏใใซใใคใใผ๏ผ๏ผใๆธกใๅฟ
่ฆใใใใพใ
้ฃไบบใฎๆฐใใใใฏใใซใๆฏๅๅผท่ชฟ่กจ็คบใใฆ่ฟใไปฃใใใซใA *ใณใผใใฏ1ใคใฎใใฏใใซใ้ธๆใใๆฏๅใใใ้ฃไบบ้ขๆฐใซๆธกใๅฟ
่ฆใใใใพใใ็งใฎใในใใงใฏใใใใซใใใณใผใใใฏใใใซ้ซ้ใซใชใใพใใใ2.4.3 TODO๏ผใใณใใฌใผใใฎใใฉใกใผใฟใผๅใๆ้ค
ใใฎใใผใธใฎ็ฎ็ใฏใ็่งฃใใใใใณใผใใไฝๆใใใใจใงใใใใณใใฌใผใใใใฉใกใผใฟใผๅใใใจใใใณใใฌใผใใฎ่ชญใฟๅใใ่ค้ใซใชใใใใใจๆใใพใใไปฃใใใซใใใใคใใฎtypedefใไฝฟ็จใใพใใ2.4.4 TODO๏ผ่ฆไปถใฎ่ฟฝๅ
ใฐใฉใใซใฏ2ใคใฎใฟใคใ๏ผ้ใฟไปใใใใณ้ใฟใชใ๏ผใใใใใฐใฉใๆค็ดขใณใผใใงใฏใใฉใฎใฟใคใใใฉใใงๅฟ
่ฆใใฏใใใใพใใใ3 Cใงใฎๅฎ่ฃ
๏ผ
ใใใใฏ็งใฎๆๅใฎC๏ผใใญใฐใฉใ ใงใใใใใใใฎ่จ่ชใงใฏ็นๅพด็ใงใชใใใในใฟใคใซใๆญฃใใใชใๅฏ่ฝๆงใใใใพใใใใใใฎไพใฏใPythonใใใณC ++ใปใฏใทใงใณใฎไพใปใฉๅฎๅ
จใงใฏใใใพใใใใๅฝนใซ็ซใคใใจใ้กใฃใฆใใพใใไปฅไธใซใๅ็ดใชใฐใฉใใจๅน
ๅชๅ
ๆค็ดขใฎๅฎ่ฃ
ใ็คบใใพใใ using System; using System.Collections.Generic; public class Graph<Location> {
ใใใฏใ้ใฟไปใใฎใจใใธใๆใคใฐใชใใใ่กจใใฐใฉใใงใ๏ผๅใฎ่จไบใฎๆฃฎใจๅฃใฎไพ๏ผ๏ผ using System; using System.Collections.Generic;
4ๆ้ฉๅ
่จไบใฎใณใผใใไฝๆใใใจใใใใใฉใผใใณในใใใๅ็ดใใจ้ฉ็จๆงใซๆณจ็ฎใใพใใใๆๅใซใณใผใใๆฉ่ฝใใใฆใใใ้ๅบฆใๆ้ฉๅใใพใใ็งใๅฎ้ใฎใใญใธใงใฏใใงไฝฟ็จใใๅคใใฎๆ้ฉๅใฏใใญใธใงใฏใใซๅบๆใฎใใฎใงใใใใใๆ้ฉใชใณใผใใ็คบใไปฃใใใซใ็ฌ่ชใฎใใญใธใงใฏใใซๅฎ่ฃ
ใงใใใใใคใใฎใขใคใใขใๆไพใใพใใ4.1ใซใฆใณใ
ๅฏ่ฝใชๆๅคงใฎๆ้ฉๅใฏใใใผใใฎๆฐใๆธใใใใจใงใใๆจๅฅจไบ้
1๏ผใฐใชใใใฎใใใใไฝฟ็จใใๅ ดๅใใฐใชใใใซๅบใฅใใฆใใชใใในๆค็ดขใฐใฉใใ้ฉ็จใใฆใใ ใใใใใใฏๅธธใซๅฏ่ฝใจใใใใใงใฏใใใพใใใใใใฎใชใใทใงใณใฏๆค่จใใไพกๅคใใใใพใใใฐใฉใใๅ็ดใชๆง้ ๏ผใฐใชใใใชใฉ๏ผใงใใๅ ดๅใ้ขๆฐใฎ่ฟๅใ่จ็ฎใใพใใใใ่ค้ใชๆง้ ๏ผใฐใชใใใชใใใพใใฏ่ฟท่ทฏใฎใใใซๅคๆฐใฎๅฃใใใใฐใชใใ๏ผใใใๅ ดๅใฏใใใผใฟๆง้ ใซ่ฟๅใไฟๅญใใพใใ่ฟ้ฃใฎ้
ๅใๅๅฉ็จใใใใจใซใใใใณใใผๆไฝใไฟๅญใใใใจใใงใใพใใๆฏๅใชใฟใผใณใๅฎ่กใใไปฃใใใซใๆค็ดขใณใผใใงไธๅบฆ้ธๆใใฆใใฐใฉใใฎใใคใใผใกใฝใใใซๆธกใใพใใ4.2ใญใฅใผ
ๅน
ๅชๅ
ๆค็ดขใงใฏใไปใฎใขใซใดใชใบใ ใงไฝฟ็จใใใๅชๅ
ๅบฆใญใฅใผใงใฏใชใใ้ๅธธใฎใญใฅใผใไฝฟ็จใใใพใใใญใฅใผใฏใๅชๅ
ใญใฅใผใใใ้ซ้ใง็ฐกๅใงใใไปใฎใขใซใดใชใบใ ใฏใใใๅฐใชใใใผใใ่ชฟในใพใใใปใจใใฉใฎใฒใผใ ใซใผใใงใฏใ่ชฟๆปใใใใผใใฎๆฐใๆธใใใใจใฏใไปใฎใขใซใดใชใบใ ใ้
ใใใไพกๅคใใใใพใใใใ ใใใใพใ็ฏ็ดใงใใชใใซใผใใใใใใใๅน
ใฎๆค็ดขใไฝฟ็จใใใใจใใๅงใใใพใใใญใฅใผใฎๅ ดๅใฏใไปฃใใใซdeque้
ๅใไฝฟ็จใใฆใใ ใใใ dequeใฏใใฉใกใใฎๅดใใใงใใใฐใใๆฟๅ
ฅใใใณๅ้คใงใใๆฉ่ฝใๆไพใใพใใใ้
ๅใฏไธๆนใฎ็ซฏใใใฎใฟ้ซ้ใงใใ Pythonใงใฏใcollections.dequeใไฝฟ็จใใๅฟ
่ฆใใใใพใใ C ++ใงใฏใdequeใณใณใใใๆค่จใใฆใใ ใใใใใ ใใๅน
ๅชๅ
ๆค็ดขใงใฏใญใฅใผใๅฟ
่ฆใใใพใใใ2ใคใฎใใฏใฟใผใไฝฟ็จใใฆใไธๆนใ็ฉบใฎใจใใซใใใใๅใๆฟใใใใจใใงใใพใใๅชๅ
ๅบฆใญใฅใผใฎๅ ดๅใ้
ๅใพใใฏใฝใผใใใใ้
ๅใงใฏใชใใใใคใใชใใผใใไฝฟ็จใใพใใใใคใใชใใผใใฏใๆฟๅ
ฅใจๅ้คใใใฐใใ่กใๆฉ่ฝใๆไพใใพใใใ้
ๅใฏ1ใคใฎ็นใง้ซ้ใงใใ Pythonใงใฏใheapqใฎไฝฟ็จใใๅงใใใพใใ C ++ใงใฏใpriority_queueใณใณใใใ่ฉฆใใฆใใ ใใใPythonใงใฏใไธใง็คบใใQueueใใใณPriorityQueueใฏใฉในใฏ้ๅธธใซๅ็ดใชใฎใงใๆค็ดขใขใซใดใชใบใ ใซใกใฝใใใๅใ่พผใใใจใใงใใพใใใใใงใใใใๅใฆใใใฉใใใฏใใใใพใใใใใในใใใไพกๅคใฏใใใพใใ C ++ใใผใธใงใณใๅใ่พผใพใใพใใใใคใฏในใใฉใฎใขใซใดใชใบใ ใงใฏใๅชๅ
ๅบฆใญใฅใผใฎๅชๅ
ๅบฆใ2ๅไฟๅญใใใพใใ1ๅใฏๅชๅ
ๅบฆใญใฅใผใซใ2็ช็ฎใฏ2็ช็ฎใซไฟๅญใใใcost_so_farใใใใฉใใใใงใๅชๅ
ๅบฆใๅใๅใๅชๅ
ๅบฆใญใฅใผใไฝๆใงใใพใใไพกๅคใใใใใฉใใใฏใใใใพใใใๆจๆบใฎใใคใฏในใใฉใขใซใดใชใบใ ใฎๅฎ่ฃ
ใงใฏใๅชๅ
ๅบฆใญใฅใผใฎๅชๅ
ๅบฆใฎๅคๆดใไฝฟ็จใใพใใใใ ใใๅชๅ
ๅบฆใๅคๆดใใชใใจใฉใใชใใพใใ๏ผใใฎ็ตๆใใใใซ้่คใใ่ฆ็ด ใ่กจ็คบใใใพใใใใ ใใใขใซใดใชใบใ ใฏๅผใ็ถใๆฉ่ฝใใพใใๅฝผใฏๅฟ
่ฆไปฅไธใซใใใคใใฎใใคใณใใๅ่จชใใพใใๅชๅ
ๅบฆใญใฅใผใซใฏๅฟ
่ฆไปฅไธใฎ่ฆ็ด ใๅซใพใใใใใ้ๅบฆใไฝไธใใพใใใๅชๅ
ๅบฆใฎๅคๆดใใตใใผใใใใใผใฟๆง้ ใใ่ฆ็ด ใๅคใใใใซ้ๅบฆใไฝไธใใพใใChenใChaudheryใRamachandranใLan RocheใTongaใซใใใPriority Queues and Dijkstra's Algorithmใใฎ็ ็ฉถใๅ็
งใใฆใใ ใใใใใฎ็ ็ฉถใงใฏใใใผใใจใใฎไปใฎใใผใฟๆง้ ใฎใใขใชใณใฐใ่ๆ
ฎใใใใจใๆจๅฅจใใฆใใพใใใใคใใชใใผใใฎไปฃใใใซไฝใใไฝฟ็จใใใใจใ่ใใฆใใๅ ดๅใฏใๆๅใซๅข็ใฎใตใคใบใจๅชๅ
้ ไฝใๅคๆดใใใ้ ปๅบฆใๆธฌๅฎใใพใใใณใผใใฎใใญใใกใคใซใไฝๆใใๅชๅ
ๅบฆใญใฅใผใใใใซใใใฏใซใชใฃใฆใใใใฉใใใ็ขบ่ชใใพใใๆๆใชๆนๅๆงใฏใใผใฟใฎใฐใซใผใๅใใญใผใๆดๆฐๅคใงใใๅ ดๅใใใญใใฏใฝใผใใจใใใๅไฝใฝใผใใใฏใคใใฏใฝใผใใฎไพฟๅฉใชไปฃๆฟๆๆฎตใงใใใใใซใใใคใฏในใใฉใจA *ใขใซใดใชใบใ ใฎๅ ดๅใ็ถๆณใฏใใใซ่ฏใใชใใพใใใใคใฏในใใฉใฎใขใซใดใชใบใ ใฎๅชๅ
้ ไฝใฏ้ๅธธใซไฝใใงใใใญใฅใผๅ
ใฎๆๅฐ่ฆ็ด ใๅชๅ
ใใใๅ ดๅใฏfใๆฌกใซไธ็ชไธใฎ่ฆ็ด ใๅชๅ
ๆใf+eใeใจใใธใฎๆๅคง้้- ใๆฃฎใฎไพใงใฏใใใฃใณ1ใจ5ใญใฅใผๅ
ใฎใในใฆใฎๅชๅ
้ ไฝใฎ้ใซใชใใจใใใฎๆๆฎตใฎ้้ๆใคfใจใใพใf+5ใใใใใฏใในใฆๆดๆฐใงใใใใใ6ใคใฎ็ฐใชใๅชๅ
้ ไฝใใใใพใใใ6ใคใฎใใญใใฏใไฝฟ็จใใใใจใใไฝใใฝใผใใใชใใใจใใงใใพใ๏ผ*ใฏใใๅน
ๅบใๅชๅ
้ ไฝใไฝๆใใพใใใใใใงใใใฎๆนๆณใฏๆค่จใใไพกๅคใใใใพใใใพใใใใๅบ็ฏใช็ถๆณใซๅฏพๅฆใงใใใฐใซใผใๅใธใฎใใ่ๅณๆทฑใใขใใญใผใใใใใพใใๅชๅ
ใญใฅใผใฎใใผใฟๆง้ ใซ้ขใใๅฅใฎ่จไบใใใใพใใ4.3ๆค็ดข
ใใฅใผใชในใใฃใใฏใซใใใCPUใฎ่ค้ใใจๆ้ใๆถ่ฒปใใใพใใใใ ใใใใใงใฎ็ฎๆจใฏใใใๅฐใชใใใผใใ่ชฟๆปใใใใจใงใใไธ้จใฎใใใ๏ผ่ฟท่ทฏใชใฉ๏ผใงใฏใใใฅใผใชในใใฃใใฏใฏๅคใใฎๆ
ๅ ฑใ่ฟฝๅ ใใชใๅ ดๅใใใใใใฅใผใชในใใฃใใฏใไฝฟ็จใใชใๅ็ดใชใขใซใดใชใบใ ใไฝฟ็จใใๆนใ้ฉๅใชๅ ดๅใใใใพใใๆดๆฐๅคใไฝฟ็จใใฆใฎใใคใณใใจใใฆใใชใใฎใฐใฉใใฏใใใฎๅพใไฝฟ็จใฎๅฏ่ฝๆงใๆค่จใใๅ ดๅใฏcost_so_farใvisitedใcame_fromใชใฉใใใทใฅใใผใใซใงใฏใชใใๅ็ดใช้
ๅใใใvisitedใฏใใผใซ้
ๅใงใใใใใใใใใใฏใใซใไฝฟ็จใงใใพใใใในใฆใฎ่ญๅฅๅญใฎใใใใใฏใใซใๅๆๅใใพใใcost_so_farใcame_fromๅๆๅใใใชใใพใพใซใใพใ๏ผ่จ่ชใง่จฑๅฏใใใฆใใๅ ดๅ๏ผใใใฎๅพใๆๅใฎ่จชๅๆใซใฎใฟๅๆๅใใพใใไธๅบฆใซ1ใคใฎๆค็ดขใฎใฟใๅฎ่กใใๅ ดๅใๆฌกใฎๅผใณๅบใใง้็ใซใใผใฟๆง้ ใๆฝๅบใใฆๅๅฉ็จใงใใพใใๅ
ฅๅใงๅๆๅใใไปฃใใใซใๅบๅใงใชใปใใใใพใใ้
ๅใไฝฟ็จใใฆใๅคๆดใใใใคใณใใ่ฟฝ่ทกใใๅคๆดใใใ ใใงใใใใจใใฐvisited[]ใ1000ใใผใ็จใซๅๆๅใใใ้
ๅใไฝฟ็จใใฆใใใใใปใจใใฉใฎๆค็ดขใใญใปในใ100ใใผใๆชๆบใ่จชๅใใๅ ดๅใ้ขๆฐใๅ
ฅๅใใใจใใซ1000ใใผใใในใฆใๅๅๆๅใใไปฃใใใซใใคใณใใใฏใน้
ๅใๅคๆดใใ้ขๆฐใ็ตไบใใใจใใซใใใใฎ100ใใผใใฎใฟใๅคๆดใงใใพใใ็กๅนใช*ใไฝฟ็จใใไบบใใใพใ๏ผ้ๅคง่ฉไพก๏ผใใฅใผใชในใใฃใใฏใใใใฏ็ใซใใชใฃใฆใใใใใงใใใใ ใใใใใใฎๅฎ่ฃ
ใซใคใใฆใฏๆ
้ใซๆค่จใใพใใใงใใใๆขใซ่จชๅใใไธ้จใฎ่ฆ็ด ใฏใๆขใซๅฝๅขใใๅ้คใใใฆใใๅ ดๅใงใใๅๅบฆ่จชๅใใๅฟ
่ฆใใใใจๆใใพใ๏ผ็ขบใใงใฏใใใพใใ๏ผใๅฎ่ฃ
ใซใใฃใฆใฏใๆฐใใใใผใใๆขใซ้ใใฆใใใปใใใซๆขใซๆฟๅ
ฅใใใฆใใๅ ดๅใงใใๅธธใซๆฟๅ
ฅใใใพใใใใใซใใใใใผใใๆขใซใชใผใใณใปใใใซใใใใฉใใใ็ขบ่ชใใใณในใใฎใใใๅฏ่ฝๆงใฎใใในใใใใๅ้ฟใงใใพใใใใ ใใๅๆใซใ้ใใฆใใใปใใใๅคงใใ/้
ใใชใใใใฎ็ตๆใๅฟ
่ฆไปฅไธใฎใใผใใ่ฉไพกใใๅฟ
่ฆใใใใพใใใชใผใใณใปใใใฎใใงใใฏใซใณในใใใใใๅ ดๅใฏใใใใใใใฎใขใใญใผใใไฝฟ็จใใๅฟ
่ฆใใใใพใใใใ ใใๆ็คบใใใณใผใใงใฏใใใงใใฏใๅฎใใใใใฎใขใใญใผใใฏไฝฟ็จใใพใใใใใใคใใฎๅฎ่ฃ
ใงใฏๆฐใใใใผใใใชใผใใณใปใใๅ
ใฎๆขๅญใฎใใผใใใใๅชใใฆใใใใฉใใใฏใใงใใฏใใใพใใใใใใซใใใๆฝๅจ็ใซใณในใใฎใใใๆค่จผใๅ้ฟใใใพใใใใ ใใใใใซใใใจใฉใผใ็บ็ใใๅ ดๅใใใใพใใไธ้จใฎ็จฎ้กใฎใซใผใใงใฏใใใฎใใงใใฏใในใญใใใใใจๆ็ญ็ต่ทฏใ่ฆใคใใใพใใใๆ็คบใใใณใผใใงใฏใใใฎใใงใใฏใๅฎ่กใใพใ๏ผnew_cost < cost_so_far๏ผใ็งใcost_so_farๅฎใๆค็ดขใใใใฎใงใใใฎใใงใใฏใฏๅฎใใงใใ5ใใฉใใซใทใฅใผใใฃใณใฐ
5.1้้ใฃใใใน
ๆ็ญใในใๅๅพใงใใชใๅ ดๅใฏใๆฌกใฎใใงใใฏใ่ฉฆใใฆใใ ใใใ- ๅชๅ
ใญใฅใผใฏๆญฃใใๆฉ่ฝใใพใใ๏ผๆค็ดขใๅๆญขใใฆใใญใฅใผใใใในใฆใฎใขใคใใ ใๅ้คใใฆใใ ใใใๅฝผใใฏ้ ็ชใซ่กใๅฟ
่ฆใใใใพใใ
- ?
priority , ( , ). - , . , , . , , , .
5.2
ใปใจใใฉใฎๅ ดๅใใฐใชใใใงA *ใๅฎ่กใใใจใใซใๅฝผใใฏ็งใซ่ณชๅใใใพใ๏ผใชใใในใฏใพใฃใใใซ่ฆใใชใใฎใงใใ๏ผใฐใชใใใซๆฒฟใฃใใในใฆใฎๅใใฎใณในใใ็ญใใใใจใA *ใซไผใใใจใๅใ้ทใใฎๅคใใฎๆ็ญ็ต่ทฏใๅพใใใใขใซใดใชใบใ ใฏใใใใฎ1ใคใใฉใณใใ ใซ้ธๆใใพใใใในใฏ็ญใใงใใใ่ฆๆ ใใใใใใใพใใใ- 1ใคใฎ่งฃๆฑบ็ญใฏใใในใใชใณใฐใใซใใขใซใดใชใบใ ใไฝฟ็จใใฆใใขใซใดใชใบใ ใฎๅพใซใในใใพใฃใใใซใใใใจใงใใ
- ๅฅใฎ่งฃๆฑบ็ญใฏใใใฅใผใชในใใฃใใฏใ่ชฟๆดใใใใจใซใใใๆญฃใใๆนๅใซ้ใๅฐใใใจใงใใใในใฆใฎ็ถๆณใงๆฉ่ฝใใชใๅฎไพกใชใใชใใฏใใใใคใใใใพใใใใใงใใใใซใคใใฆ่ฉณใใ่ชญใใใจใใงใใพใใ
- โ . A* , , . .
- โ , . (: , , , ), ยซยป ( (x+y) % 2 == 1). .
6
- . . :
cost w or d l lengthcost_so_far g d distanceheuristic hpriority A* f , f = g + hcame_from ฯ parent previous prevfrontier OPENvisited โ OPEN CLOSED- , ,
current next u , v
- :