- 深さ優先探索 (DFS): 深さ優先探索は、スタックを使用して地図上を移動する方法です。現在の位置から隣接する場所を探索し、目的地が見つかるまで最も深い位置に進みます。以下は、PythonでのDFSの基本的なコード例です。
def dfs(map, start, goal):
stack = [start]
visited = set()
while stack:
current = stack.pop()
if current == goal:
return True
visited.add(current)
neighbors = get_neighbors(current, map)
for neighbor in neighbors:
if neighbor not in visited:
stack.append(neighbor)
return False- 幅優先探索 (BFS): 幅優先探索は、キューを使用して地図上を移動する方法です。現在の位置から隣接する場所を探索し、目的地が見つかるまで同じ距離の位置に進みます。以下は、PythonでのBFSの基本的なコード例です。
from collections import deque
def bfs(map, start, goal):
queue = deque([start])
visited = set()
while queue:
current = queue.popleft()
if current == goal:
return True
visited.add(current)
neighbors = get_neighbors(current, map)
for neighbor in neighbors:
if neighbor not in visited:
queue.append(neighbor)
return False- Aアルゴリズム: Aアルゴリズムは、最適な経路を見つけるための効率的な探索アルゴリズムです。このアルゴリズムはヒューリスティック関数を使用して、現在の位置から目的地までの推定コストを計算します。以下は、PythonでのA*アルゴリズムの基本的なコード例です。
import heapq
def astar(map, start, goal):
heap = [(0, start)]
cost_so_far = {start: 0}
while heap:
_, current = heapq.heappop(heap)
if current == goal:
return True
neighbors = get_neighbors(current, map)
for neighbor in neighbors:
new_cost = cost_so_far[current] + get_cost(current, neighbor)
if neighbor not in cost_so_far or new_cost < cost_so_far[neighbor]:
cost_so_far[neighbor] = new_cost
priority = new_cost + heuristic(neighbor, goal)
heapq.heappush(heap, (priority, neighbor))
return False以上が、地図の探索における一般的なアルゴリズムのコード例です。これらのアルゴリズムは、地図上の位置を効率的に探索するための強力なツールです。必要に応じて、これらのアルゴリズムをカスタマイズして、特定の要件に合わせることもできます。