این کد الگوریتمی برای جستجوی دوطرفه در یک ماز پیادهسازی میکند که به منظور پیدا کردن کوتاهترین مسیر از یک نقطه به نقطه دیگر طراحی شده است. همچنین، مسیر پیدا شده را به صورت گرافیکی نمایش میدهد. بیایید هر بخش از کد را به تفصیل بررسی کنیم:
۱. کتابخانهها
import matplotlib.pyplot as plt
import numpy as np
from collections import deque
matplotlib.pyplot: برای ترسیم و نمایش گرافیکی ماز و مسیر استفاده میشود.
numpy: برای کار با آرایهها و دادهها.
collections.deque: برای استفاده از صف دابل-اند (deque) که برای الگوریتم BFS (جستجوی عرضی) مناسب است.
۲. تابع is_valid_move(x, y, maze)
این تابع بررسی میکند که آیا حرکت به مختصات (x, y) در ماز مجاز است یا خیر.
def is_valid_move(x, y, maze):
return 0 <= x < len(maze) and 0 <= y < len(maze[0]) and maze[x][y] == 0
- شرطها:
0 <= x < len(maze): مختصات x باید در محدودهی سطرهای ماز باشد.
0 <= y < len(maze[0]): مختصات y باید در محدودهی ستونهای ماز باشد.
maze[x][y] == 0: خانهی مربوطه در ماز باید 0 باشد (یعنی دیوار نباشد).
مثال: برای ماز زیر:
maze = [[0, 1], [0, 0]]
is_valid_move(0, 0, maze) → True (چون خانه آزاد است)
is_valid_move(0, 1, maze) → False (چون دیوار است)
۳. تابع bfs(queue, visited, parent)
این تابع الگوریتم جستجوی عرضی (BFS) را برای یک طرف اجرا میکند.
def bfs(queue, visited, parent):
(x, y) = queue.popleft()
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] # Up, Down, Left, Right moves
for dx, dy in directions:
nx, ny = x + dx, y + dy
if is_valid_move(nx, ny, maze) and (nx, ny) not in visited:
queue.append((nx, ny))
visited.add((nx, ny))
parent[(nx, ny)] = (x, y)
- متغیرها:
queue: صفی از خانههایی که باید بررسی شوند.
visited: مجموعهای از خانههایی که قبلاً بازدید شدهاند.
parent: دیکشنری که برای هر خانه، مختصات خانهی والد آن را ذخیره میکند.
عملیات:
- خانهی اول را از صف حذف میکند.
- چهار جهت مجاور (بالا، پایین، چپ، راست) را بررسی میکند.
- اگر حرکت به خانهی مجاور مجاز باشد و آن خانه قبلاً بازدید نشده باشد، آن را به صف اضافه میکند و به مجموعهی
visited اضافه میکند.
۴. تابع bidirectional_search(maze, start, goal)
این تابع هستهی اصلی الگوریتم جستجوی دوطرفه است.
def bidirectional_search(maze, start, goal):
if maze[start[0]][start[1]] == 1 or maze[goal[0]][goal[1]] == 1:
return None, None, None
queue_start = deque([start])
queue_goal = deque([goal])
visited_start = set([start])
visited_goal = set([goal])
parent_start = {start: None}
parent_goal = {goal: None}
while queue_start and queue_goal:
bfs(queue_start, visited_start, parent_start)
bfs(queue_goal, visited_goal, parent_goal)
# Check for intersection
intersect_node = None
for node in visited_start:
if node in visited_goal:
intersect_node = node
break
if intersect_node is not None:
return (intersect_node, parent_start, parent_goal)
return (None, None, None)
- عملیات:
- بررسی میکند که آیا نقطهی شروع یا هدف دیوار هستند.
- دو صف برای شروع و هدف، دو مجموعهی
visited و دو دیکشنری parent ایجاد میکند.
- در هر دور، یک BFS از سمت شروع و یک BFS از سمت هدف انجام میدهد.
- بررسی میکند که آیا دو جستجو به یک نقطهی مشترک رسیدهاند (اشتراک در مجموعهها).
مثال: اگر ماز به صورت زیر باشد و هدف پیدا شود:
maze = [
[0, 1, 0],
[0, 0, 0],
[1, 0, 0]
]
جستجو به سمت پایین و راست ادامه مییابد تا به نقطهی مشترک برسد.
۵. تابع reconstruct_path(intersect_node, parent_start, parent_goal)
این تابع مسیر پیدا شده را بازسازی میکند.
def reconstruct_path(intersect_node, parent_start, parent_goal):
if intersect_node is None:
return []
path = []
# from start to intersection
step = intersect_node
while step is not None:
path.append(step)
step = parent_start[step]
path.reverse()
# from intersection to goal
step = parent_goal[intersect_node]
while step is not None:
path.append(step)
step = parent_goal[step]
return path
- عملیات:
- از نقطهی مشترک به سمت شروع حرکت میکند و مسیر را ثبت میکند.
- مسیر را معکوس میکند.
- سپس از نقطهی مشترک به سمت هدف حرکت میکند و مسیر را اضافه میکند.
۶. تابع visualize(maze, path, start, goal)
این تابع ماز و مسیر را به صورت گرافیکی نمایش میدهد.
def visualize(maze, path, start, goal):
maze_copy = np.array(maze)
fig, ax = plt.subplots(figsize=(10, 10))
# Coloring the maze
cmap = plt.cm.Dark2
colors = {'empty': 0, 'wall': 1, 'path': 2}
for y in range(len(maze)):
for x in range(len(maze[0])):
color = 'white' if maze[y][x] == 0 else 'black'
ax.fill_between([x, x+1], y, y+1, color=color)
# Drawing the path
if path:
for (y, x) in path:
ax.fill_between([x, x+1], y, y+1, color='gold', alpha=0.5)
# Mark start and goal
sy, sx = start
gy, gx = goal
ax.plot(sx+0.5, sy+0.5, 'go') # green dot at start
ax.plot(gx+0.5, gy+0.5, 'ro') # red dot at goal
# Set limits and grid
ax.set_xlim(0, len(maze[0]))
ax.set_ylim(0, len(maze))
ax.set_xticks(range(len(maze[0])))
ax.set_yticks(range(len(maze)))
ax.grid(which='both')
ax.invert_yaxis() # Invert the y-axis so the first row is at the top
ax.xaxis.tick_top() # and the x-axis is on the top
plt.show()
- عملیات:
- ماز را با رنگهای سفید (خانههای خالی) و سیاه (دیوارها) رنگآمیزی میکند.
- مسیر پیدا شده را با رنگ طلایی نمایش میدهد.
- نقاط شروع و هدف را با دایرههای سبز و قرمز مشخص میکند.
- تنظیمات محورهای گرافیکی را انجام میدهد.
۷. اجرای کد
در انتهای کد، یک ماز تعریف شده و مختصات شروع و هدف مشخص میشوند. سپس، الگوریتم جستجوی دوطرفه و بازسازی مسیر و در نهایت نمایش گرافیکی ماز و مسیر اجرا میشود.
# Define the maze
maze = [
[0, 1, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 0, 0, 1, 0],
[0, 1, 0, 0, 0],
[0, 0, 0, 1, 0]
]
start = (0, 0)
goal = (4, 4)
intersect_node, parent_start, parent_goal = bidirectional_search(maze, start, goal)
path = reconstruct_path(intersect_node, parent_start, parent_goal)
visualize(maze, path, start, goal)
نتیجهگیری
این کد پیادهسازی کارآمدی از الگوریتم جستجوی دوطرفه برای پیدا کردن کوتاهترین مسیر در یک ماز است و از matplotlib برای نمایش بصری نتایج استفاده میکند. با استفاده از این روش، میتوان به راحتی مسیرهای مختلف را در مازهای پیچیده پیدا کرد و آنها را به صورت گرافیکی نمایش داد.