، کد را با ذکر جزئیات به صورت کامل توضیح بدهید. لازم است عملیات هر تابع موجود در کد را واضح و در صورت امکان با یک مثال ساده شرح بدهید.
import matplotlib.pyplot as plt
import numpy as np
from collections import deque

def is_valid_move(x, y, maze):
return 0 <= x < len(maze) and 0 <= y < len(maze[0]) and maze[x][y] == 0

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)

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)

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

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)

این کد یک الگوریتم جستجوی دوطرفه (Bidirectional Search) را برای پیدا کردن کوتاهترین مسیر در یک ماز پیاده‌سازی می‌کند. بیایید بخش‌های مختلف کد را با جزئیات بررسی کنیم:

۱. کتابخانه‌ها:

  • matplotlib.pyplot as plt: برای رسم ماز و مسیر پیدا شده استفاده می‌شود.
  • numpy as np: برای کار با آرایه‌ها (maze) استفاده می‌شود.
  • collections.deque: برای استفاده از صف دابل-اند (deque) که برای الگوریتم BFS مناسب است.

۲. تابع is_valid_move(x, y, maze):

این تابع بررسی می‌کند که آیا حرکت به خانه (x, y) در ماز معتبر است یا خیر. یک حرکت معتبر است اگر:

  • داخل مرزهای ماز باشد (x و y بزرگتر یا مساوی صفر و کوچکتر از ابعاد ماز باشند).
  • خانه (x, y) دیوار نباشد (مقدار آن در ماز صفر باشد).

مثال: اگر maze = [[0, 1], [0, 0]] باشد، is_valid_move(0, 0, maze) درست (True) و is_valid_move(0, 1, maze) نادرست (False) برمی‌گرداند زیرا (0, 1) یک دیوار است.

۳. تابع bfs(queue, visited, parent):

این تابع الگوریتم جستجوی سطح اول (Breadth-First Search یا BFS) را پیاده‌سازی می‌کند.

  • queue: صفی از خانه‌هایی که باید بررسی شوند.
  • visited: مجموعه‌ای از خانه‌هایی که قبلاً بازدید شده‌اند.
  • parent: دیکشنری که خانه والد هر خانه را ذخیره می‌کند. این برای بازسازی مسیر نهایی استفاده می‌شود.

این تابع، خانه‌ی فعلی را از صف (queue) حذف می‌کند. سپس، چهار جهت ممکن (بالا، پایین، چپ، راست) را بررسی می‌کند. اگر حرکت به خانه‌ی جدید معتبر باشد و قبلاً بازدید نشده باشد، آن را به صف اضافه می‌کند، آن را به مجموعه‌ی بازدید شده‌ها اضافه می‌کند و خانه‌ی فعلی را به عنوان والد آن در دیکشنری parent ثبت می‌کند.

۴. تابع bidirectional_search(maze, start, goal):

این تابع جستجوی دوطرفه را انجام می‌دهد. دو BFS، یکی از شروع و دیگری از هدف، همزمان اجرا می‌شوند.

  • اگر خانه شروع یا هدف دیوار باشد، None برمی‌گرداند.
  • دو صف، دو مجموعه‌ی بازدید شده و دو دیکشنری والد برای شروع و هدف ایجاد می‌کند.
  • تا زمانی که هر دو صف خالی نشده‌اند، یک مرحله BFS از هر دو طرف انجام می‌دهد.
  • در هر مرحله، بررسی می‌کند که آیا دو BFS به هم رسیده‌اند یا خیر (اشتراک در مجموعه‌های visited_start و visited_goal).
  • اگر نقطه‌ی اشتراکی پیدا شود، آن نقطه و دیکشنری‌های والد را برمی‌گرداند.
  • اگر هیچ اشتراکی پیدا نشود، None برمی‌گرداند.

۵. تابع reconstruct_path(intersect_node, parent_start, parent_goal):

این تابع با استفاده از دیکشنری‌های والد و نقطه‌ی اشتراک، مسیر کامل از شروع تا هدف را بازسازی می‌کند.

  • از نقطه‌ی اشتراک شروع می‌کند و با استفاده از parent_start به عقب برمی‌گردد تا به شروع برسد.
  • سپس از نقطه‌ی اشتراک با استفاده از parent_goal به سمت هدف حرکت می‌کند.

۶. تابع visualize(maze, path, start, goal):

این تابع ماز و مسیر پیدا شده را با استفاده از matplotlib رسم می‌کند.

  • دیوارها را سیاه، مسیر را طلایی و خانه‌های خالی را سفید نمایش می‌دهد.
  • شروع را با نقطه سبز و هدف را با نقطه قرمز نشان می‌دهد.

۷. بخش اصلی کد:

  • ماز، شروع و هدف تعریف می‌شوند.
  • تابع bidirectional_search برای پیدا کردن مسیر فراخوانی می‌شود.
  • تابع reconstruct_path برای ساخت مسیر کامل فراخوانی می‌شود.
  • تابع visualize برای نمایش ماز و مسیر فراخوانی می‌شود.

به طور خلاصه، این کد با استفاده از جستجوی دوطرفه، کوتاهترین مسیر بین دو نقطه در یک ماز را پیدا کرده و آن را نمایش می‌دهد. استفاده از BFS از دو طرف، به طور قابل توجهی سرعت جستجو را در مقایسه با BFS معمولی افزایش می‌دهد.

، کد را با ذکر جزئیات به صورت کامل توضیح بدهید. لازم است عملیات هر تابع موجود در کد را واضح و در صورت امکان با یک مثال ساده شرح بدهید.
import matplotlib.pyplot as plt
import numpy as np
from collections import deque

def is_valid_move(x, y, maze):
return 0 <= x < len(maze) and 0 <= y < len(maze[0]) and maze[x][y] == 0

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)

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)

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

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)

این کد یک الگوریتم جستجوی دوطرفه (Bidirectional Search) را برای یافتن کوتاه‌ترین مسیر در یک ماز پیاده‌سازی می‌کند و سپس مسیر پیدا شده را به صورت گرافیکی نمایش می‌دهد. بیایید هر تابع را به تفصیل بررسی کنیم:

1. is_valid_move(x, y, maze):

این تابع بررسی می‌کند که آیا حرکت به مختصات (x, y) در ماز مجاز است یا خیر. شرط‌های مجاز بودن حرکت عبارتند از:

  • 0 <= x < len(maze): مختصات x باید درون محدوده‌ی سطرهای ماز باشد.
  • 0 <= y < len(maze[0]): مختصات y باید درون محدوده‌ی ستون‌های ماز باشد.
  • maze[x][y] == 0: خانه‌ی مربوطه در ماز باید 0 باشد (یعنی دیوار نباشد).

مثال: برای ماز [[0, 1, 0], [0, 0, 1], [1, 0, 0]], is_valid_move(1, 1, maze) True برمی‌گرداند (چون خانه (1,1) 0 است و در محدوده‌ی ماز قرار دارد)، اما is_valid_move(0, 1, maze) False برمی‌گرداند (چون خانه (0,1) 1 است، یعنی دیوار است).

2. bfs(queue, visited, parent):

این تابع الگوریتم جستجوی عرضی (Breadth-First Search – BFS) را اجرا می‌کند.

  • queue: یک صف (از نوع deque) حاوی مختصات خانه‌هایی است که باید بررسی شوند.
  • visited: یک مجموعه برای ذخیره‌ی مختصات خانه‌هایی که قبلاً بازدید شده‌اند.
  • parent: یک دیکشنری که برای هر خانه، مختصات خانه‌ی والد آن را ذخیره می‌کند. این برای بازسازی مسیر استفاده می‌شود.

تابع، خانه‌ی اول را از صف خارج می‌کند (queue.popleft()). سپس، چهار جهت مجاور (بالا، پایین، چپ، راست) را بررسی می‌کند. اگر حرکت به یک خانه‌ی مجاور مجاز باشد (is_valid_move) و آن خانه قبلاً بازدید نشده باشد، آن را به صف اضافه می‌کند، به visited اضافه می‌کند و خانه‌ی فعلی را به عنوان والد آن در parent ثبت می‌کند.

3. bidirectional_search(maze, start, goal):

این تابع هسته‌ی اصلی الگوریتم جستجوی دوطرفه است. دو جستجوی BFS، یکی از نقطه‌ی شروع و دیگری از نقطه‌ی هدف، همزمان انجام می‌شوند.

  • ابتدا بررسی می‌کند که آیا نقطه‌ی شروع یا هدف روی یک دیوار قرار دارند یا خیر. اگر اینطور باشد، None برمی‌گرداند.
  • دو صف، دو مجموعه visited و دو دیکشنری parent (برای شروع و هدف) ایجاد می‌کند.
  • تا زمانی که هر دو صف خالی نشده‌اند، یک دور BFS از هر دو طرف انجام می‌دهد.
  • پس از هر دور، بررسی می‌کند که آیا دو جستجو به یک نقطه‌ی مشترک رسیده‌اند یا خیر (یعنی اشتراک بین دو مجموعه visited).
  • اگر نقطه‌ی اشتراک (intersect_node) پیدا شود، آن نقطه و دو دیکشنری parent را برمی‌گرداند.
  • در غیر این صورت، None, None, None برمی‌گرداند.

4. reconstruct_path(intersect_node, parent_start, parent_goal):

این تابع مسیر پیدا شده را با استفاده از دیکشنری‌های parent بازسازی می‌کند.

  • اگر intersect_node None باشد (یعنی مسیری پیدا نشده است)، لیست خالی برمی‌گرداند.
  • از intersect_node شروع می‌کند و با استفاده از parent_start به سمت نقطه‌ی شروع حرکت می‌کند تا به None برسد (خانه‌ی والد شروع None است). این مسیر را معکوس می‌کند.
  • سپس از intersect_node شروع می‌کند و با استفاده از parent_goal به سمت نقطه‌ی هدف حرکت می‌کند.
  • دو مسیر را به هم متصل می‌کند و مسیر کامل را برمی‌گرداند.

5. visualize(maze, path, start, goal):

این تابع ماز و مسیر پیدا شده را به صورت گرافیکی نمایش می‌دهد. از matplotlib استفاده می‌کند.

  • ماز را با رنگ‌های سیاه (دیوار) و سفید (خانه‌های خالی) نمایش می‌دهد.
  • مسیر پیدا شده را با رنگ طلایی نمایش می‌دهد.
  • نقطه‌ی شروع را با دایره‌ی سبز و نقطه‌ی هدف را با دایره‌ی قرمز نمایش می‌دهد.

بخش اصلی کد:

  • یک ماز نمونه تعریف می‌شود.
  • مختصات شروع و هدف مشخص می‌شوند.
  • bidirectional_search فراخوانی می‌شود تا مسیر پیدا شود.
  • reconstruct_path فراخوانی می‌شود تا مسیر کامل بازسازی شود.
  • visualize فراخوانی می‌شود تا ماز و مسیر نمایش داده شوند.

در مجموع، این کد یک پیاده‌سازی کارآمد از الگوریتم جستجوی دوطرفه برای پیدا کردن کوتاه‌ترین مسیر در یک ماز است و از matplotlib برای نمایش بصری نتایج استفاده می‌کند. جستجوی دوطرفه به طور کلی نسبت به جستجوی BFS معمولی در ماز‌های بزرگ‌تر کارایی بیشتری دارد.

، کد را با ذکر جزئیات به صورت کامل توضیح بدهید. لازم است عملیات هر تابع موجود در کد را واضح و در صورت امکان با یک مثال ساده شرح بدهید.
import matplotlib.pyplot as plt
import numpy as np
from collections import deque

def is_valid_move(x, y, maze):
return 0 <= x < len(maze) and 0 <= y < len(maze[0]) and maze[x][y] == 0

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)

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)

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

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)

این کد پیاده‌سازی یک الگوریتم جستجوی دوطرفه برای پیدا کردن کوتاه‌ترین مسیر در یک ماز و سپس نمایش گرافیکی آن است. بیایید هر بخش از کد را با جزئیات بررسی کنیم:

۱. کتابخانه‌ها

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: دیکشنری که برای هر خانه، مختصات خانه‌ی والد آن را ذخیره می‌کند.

عملیات:

  1. خانه‌ی اول را از صف خارج می‌کند.
  2. چهار جهت مجاور (بالا، پایین، چپ، راست) را بررسی می‌کند.
  3. اگر حرکت به خانه‌ی مجاور مجاز باشد و آن خانه قبلاً بازدید نشده باشد، آن را به صف اضافه می‌کند و به مجموعه‌ی 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)
  • ورودی‌ها: ماز، مختصات شروع و هدف.
  • عملیات:
    1. بررسی می‌کند که آیا نقطه‌ی شروع یا هدف دیوار هستند.
    2. دو صف برای شروع و هدف، دو مجموعه‌ی visited و دو دیکشنری parent ایجاد می‌کند.
    3. در هر دور، یک BFS از هر دو طرف انجام می‌دهد.
    4. بررسی می‌کند که آیا دو جستجو به یک نقطه‌ی مشترک رسیده‌اند (اشتراک در مجموعه‌ها).

مثال: اگر ماز به صورت زیر باشد و هدف پیدا شود:

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
  • عملیات:
    1. از نقطه‌ی مشترک به سمت شروع حرکت می‌کند و مسیر را ثبت می‌کند.
    2. مسیر را معکوس می‌کند.
    3. سپس از نقطه‌ی مشترک به سمت هدف حرکت می‌کند و مسیر را اضافه می‌کند.

۶. تابع 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()
  • عملیات:
    1. ماز را با رنگ‌های سفید (خانه‌های خالی) و سیاه (دیوارها) رنگ‌آمیزی می‌کند.
    2. مسیر پیدا شده را با رنگ طلایی نمایش می‌دهد.
    3. نقاط شروع و هدف را با دایره‌های سبز و قرمز مشخص می‌کند.
    4. تنظیمات محورهای گرافیکی را انجام می‌دهد.

۷. اجرای کد

در انتهای کد، یک ماز تعریف شده و مختصات شروع و هدف مشخص می‌شوند. سپس، الگوریتم جستجوی دوطرفه و بازسازی مسیر و در نهایت نمایش گرافیکی ماز و مسیر اجرا می‌شود.

# 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 برای نمایش بصری نتایج استفاده می‌کند. با استفاده از این روش، می‌توان به راحتی مسیرهای مختلف را در مازهای پیچیده پیدا کرد و آنها را به صورت گرافیکی نمایش داد.

، کد را با ذکر جزئیات به صورت کامل توضیح بدهید. لازم است عملیات هر تابع موجود در کد را واضح و در صورت امکان با یک مثال ساده شرح بدهید.
import matplotlib.pyplot as plt
import numpy as np
from collections import deque

def is_valid_move(x, y, maze):
return 0 <= x < len(maze) and 0 <= y < len(maze[0]) and maze[x][y] == 0

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)

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)

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

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)

این کد الگوریتمی برای جستجوی دوطرفه در یک ماز پیاده‌سازی می‌کند که به منظور پیدا کردن کوتاه‌ترین مسیر از یک نقطه به نقطه دیگر طراحی شده است. همچنین، مسیر پیدا شده را به صورت گرافیکی نمایش می‌دهد. بیایید هر بخش از کد را به تفصیل بررسی کنیم:

۱. کتابخانه‌ها

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: دیکشنری که برای هر خانه، مختصات خانه‌ی والد آن را ذخیره می‌کند.

عملیات:

  1. خانه‌ی اول را از صف حذف می‌کند.
  2. چهار جهت مجاور (بالا، پایین، چپ، راست) را بررسی می‌کند.
  3. اگر حرکت به خانه‌ی مجاور مجاز باشد و آن خانه قبلاً بازدید نشده باشد، آن را به صف اضافه می‌کند و به مجموعه‌ی 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)
  • عملیات:
    1. بررسی می‌کند که آیا نقطه‌ی شروع یا هدف دیوار هستند.
    2. دو صف برای شروع و هدف، دو مجموعه‌ی visited و دو دیکشنری parent ایجاد می‌کند.
    3. در هر دور، یک BFS از سمت شروع و یک BFS از سمت هدف انجام می‌دهد.
    4. بررسی می‌کند که آیا دو جستجو به یک نقطه‌ی مشترک رسیده‌اند (اشتراک در مجموعه‌ها).

مثال: اگر ماز به صورت زیر باشد و هدف پیدا شود:

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
  • عملیات:
    1. از نقطه‌ی مشترک به سمت شروع حرکت می‌کند و مسیر را ثبت می‌کند.
    2. مسیر را معکوس می‌کند.
    3. سپس از نقطه‌ی مشترک به سمت هدف حرکت می‌کند و مسیر را اضافه می‌کند.

۶. تابع 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()
  • عملیات:
    1. ماز را با رنگ‌های سفید (خانه‌های خالی) و سیاه (دیوارها) رنگ‌آمیزی می‌کند.
    2. مسیر پیدا شده را با رنگ طلایی نمایش می‌دهد.
    3. نقاط شروع و هدف را با دایره‌های سبز و قرمز مشخص می‌کند.
    4. تنظیمات محورهای گرافیکی را انجام می‌دهد.

۷. اجرای کد

در انتهای کد، یک ماز تعریف شده و مختصات شروع و هدف مشخص می‌شوند. سپس، الگوریتم جستجوی دوطرفه و بازسازی مسیر و در نهایت نمایش گرافیکی ماز و مسیر اجرا می‌شود.

# 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 برای نمایش بصری نتایج استفاده می‌کند. با استفاده از این روش، می‌توان به راحتی مسیرهای مختلف را در مازهای پیچیده پیدا کرد و آنها را به صورت گرافیکی نمایش داد.