کد ارائه‌شده یک الگوریتم جستجوی دو جهتی (Bidirectional Search) برای پیدا کردن مسیر از نقطه شروع به نقطه هدف در یک ماتریس (Maze) با موانع است. این الگوریتم از روش جستجوی اول‌عمق اول‌عرض (BFS) دو طرفه استفاده می‌کند تا بهبود قابل توجهی در کارایی در مقایسه با جستجوی یک‌طرفه داشته باشد.
در ادامه، هر بخش از کد به تفصیل توضیح داده شده و عملکرد آن با مثال‌های ساده توضیح داده می‌شود.
1. وارد کردن کتابخانه‌ها
import matplotlib.pyplot as plt
import numpy as np
from collections import deque
توضیح:
-
matplotlib.pyplot: برای ترسیم و نمایش گرافیکی ماتریس و مسیر استفاده می‌شود.
-
numpy: برای مدیریت و پردازش داده‌های عددی و آرایه‌ای به کار می‌رود.
-
collections.deque: برای پیاده‌سازی صف‌ها (Queue) که در الگوریتم BFS استفاده می‌شود.
2. بررسی معتبر بودن حرکت
def is_valid_move(x, y, maze):
return 0 <= x < len(maze) and 0 <= y < len(maze[0]) and maze[x][y] == 0
توضیح:
این تابع بررسی می‌کند که آیا حرکت به مختصات (x, y) در ماتریس امکان‌پذیر است یا خیر.
-
پارامترها:
-
x, y: مختصات فعلی که قصد دارید به آن حرکت کنید.
-
maze: ماتریس نمایانگر ساختار محیط (0: مسیر آزاد، 1: دیوار).
-
منطق:
-
0 <= x < len(maze): بررسی اینکه x خارج از محدوده ماتریس نیست.
-
0 <= y < len(maze[0]): بررسی اینکه y خارج از محدوده ماتریس نیست.
-
maze[x][y] == 0: بررسی اینکه مختصه مقصد دیوار نیست و مسیر آزاد است.
مثال ساده:
فرض کنید ماتریسی به صورت زیر داریم:
maze = [
[0, 1],
[0, 0]
]
-
is_valid_move(0, 0, maze) ➔ True (مسیر آزاد)
-
is_valid_move(0, 1, maze) ➔ False (دیوار)
3. تابع BFS برای گسترش جستجو
def bfs(queue, visited, parent):
(x, y) = queue.popleft()
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] # حرکت به بالا، پایین، چپ، راست
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)
توضیح:
این تابع یک گام از جستجوی BFS را از جهت مشخص شده انجام می‌دهد.
-
پارامترها:
-
queue: صف حاصله از نقاط برای گسترش.
-
visited: مجموعه‌ای از نقاطی که تاکنون بازدید شده‌اند.
-
parent: دیکشنری برای ردیابی مسیر (پدر هر نقطه).
-
منطق:
-
نقطه فعلی (x, y) از صف استخراج می‌شود.
-
تمامی جهات ممکن (بالا، پایین، چپ، راست) بررسی می‌شوند.
-
برای هر جهت، مختصات جدید (nx, ny) محاسبه می‌شود.
-
اگر حرکت معتبر باشد و نقطه قبلاً بازدید نشده باشد:
مثال ساده:
فرض کنید در حال حاضر نقطه (0, 0) در صف قرار دارد و جهت‌ها قابل جابجایی به سمت پایین و راست هستند:
-
از (0, 0) به (1, 0) قابل حرکت است.
-
(1, 1) نیز قابل حرکت است (بعداً).
4. جستجوی دو جهتی
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)
# بررسی تقاطع
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)
توضیح:
این تابع پیاده‌سازی الگوریتم جستجوی دو جهتی را انجام می‌دهد که هم از نقطه شروع و هم از نقطه هدف به سمت همدیگر گسترش می‌یابند تا در نقطه‌ای مشترک برخورد کنند.
-
پارامترها:
-
منطق:
-
بررسی می‌شود که نقطه شروع یا هدف دیوار نباشند.
-
دو صف جداگانه برای شروع و هدف ایجاد می‌شود.
-
دو مجموعه برای پیگیری بازدیدهای از هر طرف ایجاد می‌شود.
-
دیکشنری والد برای هر طرف ایجاد می‌شود.
-
تا زمانی که هر دو صف خالی نشوند:
-
از هر دو صف (queue_start و queue_goal) یک گام BFS انجام می‌شود.
-
بررسی می‌شود که آیا نقاط بازدید شده از هر دو طرف با هم تداخل دارند.
-
اگر نقطه مشترکی یافت شد، نتایج بازگردانده می‌شود.
-
اگر جستجو به پایان برسد بدون یافتن مسیر، نتیجه None برگردانده می‌شود.
مثال ساده:
فرض کنید ماتریسی ساده داریم:
maze = [
[0, 1],
[0, 0]
]
start = (0, 0)
goal = (1, 1)
در این حالت:
-
جستجو از (0, 0) و از (1, 1) به سمت هم گسترش می‌یابد.
-
نقطه مشترک (1, 0) یافت شده و مسیر بازگردانده می‌شود.
5. بازسازی مسیر
def reconstruct_path(intersect_node, parent_start, parent_goal):
if intersect_node is None:
return []
path = []
# از شروع تا نقطه تقاطع
step = intersect_node
while step is not None:
path.append(step)
step = parent_start[step]
path.reverse()
# از نقطه تقاطع تا هدف
step = parent_goal[intersect_node]
while step is not None:
path.append(step)
step = parent_goal[step]
return path
توضیح:
این تابع مسیر کامل از نقطه شروع به هدف را با استفاده از نقطه تقاطع و دیکشنری والد‌ها بازسازی می‌کند.
-
پارامترها:
-
intersect_node: نقطه تقاطعی بین جستجوی دو جهته.
-
parent_start: دیکشنری والد‌ها از طرف شروع.
-
parent_goal: دیکشنری والد‌ها از طرف هدف.
-
منطق:
-
اگر نقطه تقاطعی وجود نداشته باشد، مسیر خالی برگردانده می‌شود.
-
از نقطه تقاطعی به نقطه شروع حرکت کرده و نقاط را به لیست مسیر اضافه می‌کند.
-
لیست مسیر معکوس شده تا ترتیب از شروع به تقاطع باشد.
-
سپس از نقطه تقاطعی به سمت هدف حرکت کرده و نقاط را اضافه می‌کند.
-
مسیر کامل بازگردانده می‌شود.
مثال ساده:
با استفاده از مثال قبلی:
-
نقطه تقاطعی (1, 0) است.
-
از (1, 0) به (0, 0) و سپس از (1, 0) به (1, 1) حرکت می‌کنیم.
-
مسیر نهایی: [(0, 0), (1, 0), (1, 1)]
6. نمایش گرافیکی ماتریس و مسیر
def visualize(maze, path, start, goal):
maze_copy = np.array(maze)
fig, ax = plt.subplots(figsize=(10, 10))
# رنگ‌آمیزی ماتریس
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)
# رسم مسیر
if path:
for (y, x) in path:
ax.fill_between([x, x+1], y, y+1, color='gold', alpha=0.5)
# علامت‌گذاری شروع و هدف
sy, sx = start
gy, gx = goal
ax.plot(sx+0.5, sy+0.5, 'go') # نقطه سبز در شروع
ax.plot(gx+0.5, gy+0.5, 'ro') # نقطه قرمز در هدف
# تنظیمات گرافیکی
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() # وارونه کردن محور y به طوری که ردیف اول در بالا باشد
ax.xaxis.tick_top() # قرار دادن محور x در بالا
plt.show()
توضیح:
این تابع ماتریس و مسیر پیدا شده را به صورت گرافیکی نمایش می‌دهد.
-
پارامترها:
-
منطق:
-
ایجاد یک نقشه نقشه‌بندی از ماتریس با استفاده از رنگ‌های سفید (مسیر آزاد) و سیاه (دیوار).
-
اگر مسیر وجود داشته باشد، نقاط مسیر با رنگ طلایی برجسته می‌شوند.
-
نقطه شروع با رنگ سبز و نقطه هدف با رنگ قرمز مشخص می‌شوند.
-
تنظیمات گرافیکی مانند محدوده محور، شبکه، و وارونه کردن محور y انجام می‌شود.
-
نمایش نمودار با استفاده از plt.show().
مثال ساده:
با استفاده از مسیر [(0, 0), (1, 0), (1, 1)] و ماتریس زیر:
maze = [
[0, 1],
[0, 0]
]
نمودار به این صورت نمایش داده می‌شود:
-
خانه (0, 0) به رنگ سفید، (0, 1) به رنگ سیاه.
-
مسیر از (0, 0) به (1, 0) و سپس به (1, 1) با رنگ طلایی برجسته می‌شود.
-
نقطه شروع با رنگ سبز و نقطه هدف با رنگ قرمز نشان داده می‌شود.
7. تعریف ماتریس، نقطه شروع و هدف؛ اجرای الگوریتم و نمایش نتایج
# تعریف ماتریس
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)
توضیح:
-
تعریف ماتریس:
-
تعریف نقطه شروع و هدف:
-
start = (0, 0): نقطه شروع در گوشه بالایی سمت چپ ماتریس.
-
goal = (4, 4): نقطه هدف در گوشه پایینی سمت راست ماتریس.
-
اجرای الگوریتم جستجوی دو جهتی:
-
نمایش گرافیکی:
نتیجه:
با اجرای این کد، یک نمودار گرافیکی از ماتریس نمایش داده می‌شود که در آن:
-
دیوارها به رنگ سیاه، مسیر آزاد به رنگ سفید.
-
مسیر از نقطه شروع به هدف با رنگ طلایی نشان داده شده است.
-
نقطه شروع با نقطه سبز و نقطه هدف با نقطه قرمز مشخص شده‌اند.
خلاصه عملکرد کلی کد:
-
بررسی صحت نقاط شروع و هدف: اطمینان از اینکه هر دو نقطه روی مسیر آزاد قرار دارند.
-
شروع جستجوی دو جهتی: از هر دو طرف (شروع و هدف) به طور همزمان BFS انجام می‌شود.
-
پیدا کردن نقطه تقاطع: وقتی دو جستجو به یک نقطه مشترک می‌رسند، جستجو متوقف می‌شود.
-
بازسازی مسیر کامل: با استفاده از دیکشنری والد‌ها مسیر از نقطه شروع به هدف تشکیل می‌شود.
-
نمایش گرافیکی: مسیر پیدا شده به همراه ماتریس به صورت گرافیکی ترسیم می‌شود.
این الگوریتم به دلیل جستجوی همزمان از دو جهت، در بسیاری از موارد کارآمدتر از جستجوی یک‌طرفه BFS است، به ویژه در محیط‌های بزرگ.
