BS

کد ارائه‌شده یک الگوریتم جستجوی دو جهتی (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: دیکشنری برای ردیابی مسیر (پدر هر نقطه).

• منطق:

  1. نقطه فعلی (x, y) از صف استخراج می‌شود.

  2. تمامی جهات ممکن (بالا، پایین، چپ، راست) بررسی می‌شوند.

  3. برای هر جهت، مختصات جدید (nx, ny) محاسبه می‌شود.

  4. اگر حرکت معتبر باشد و نقطه قبلاً بازدید نشده باشد:

     • نقطه به صف اضافه می‌شود.

     • به مجموعه بازدید شده اضافه می‌شود.

     • والد نقطه جدید به نقطه فعلی تنظیم می‌شود.

مثال ساده:

فرض کنید در حال حاضر نقطه (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)

توضیح:

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

• پارامترها:

  • maze: ماتریس نمایانگر مسیرها و موانع.

  • start: مختصات نقطه شروع.

  • goal: مختصات نقطه هدف.

• منطق:

  1. بررسی می‌شود که نقطه شروع یا هدف دیوار نباشند.

  2. دو صف جداگانه برای شروع و هدف ایجاد می‌شود.

  3. دو مجموعه برای پیگیری بازدیدهای از هر طرف ایجاد می‌شود.

  4. دیکشنری والد برای هر طرف ایجاد می‌شود.

  5. تا زمانی که هر دو صف خالی نشوند:

     • از هر دو صف (queue_start و queue_goal) یک گام BFS انجام می‌شود.

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

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

  6. اگر جستجو به پایان برسد بدون یافتن مسیر، نتیجه 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. اگر نقطه تقاطعی وجود نداشته باشد، مسیر خالی برگردانده می‌شود.

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

  3. لیست مسیر معکوس شده تا ترتیب از شروع به تقاطع باشد.

  4. سپس از نقطه تقاطعی به سمت هدف حرکت کرده و نقاط را اضافه می‌کند.

  5. مسیر کامل بازگردانده می‌شود.

مثال ساده:

با استفاده از مثال قبلی:

• نقطه تقاطعی (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()

توضیح:

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

• پارامترها:

  • maze: ماتریس نمایانگر مسیرها و موانع.

  • path: لیستی از نقاط مسیر یافته شده.

  • start: نقطه شروع.

  • goal: نقطه هدف.

• منطق:

  1. ایجاد یک نقشه نقشه‌بندی از ماتریس با استفاده از رنگ‌های سفید (مسیر آزاد) و سیاه (دیوار).

  2. اگر مسیر وجود داشته باشد، نقاط مسیر با رنگ طلایی برجسته می‌شوند.

  3. نقطه شروع با رنگ سبز و نقطه هدف با رنگ قرمز مشخص می‌شوند.

  4. تنظیمات گرافیکی مانند محدوده محور، شبکه، و وارونه کردن محور y انجام می‌شود.

  5. نمایش نمودار با استفاده از 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)

توضیح:

1. تعریف ماتریس:

   • ماتریس 5×5 با مقادیر 0 (مسیر آزاد) و 1 (دیوار) تعریف شده است.

   • به عنوان مثال، maze[0][1] = 1 به معنی وجود یک دیوار در ردیف اول و ستون دوم است.

2. تعریف نقطه شروع و هدف:

   • start = (0, 0): نقطه شروع در گوشه بالایی سمت چپ ماتریس.

   • goal = (4, 4): نقطه هدف در گوشه پایینی سمت راست ماتریس.

3. اجرای الگوریتم جستجوی دو جهتی:

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

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

4. نمایش گرافیکی:

   • visualize ماتریس و مسیر یافته شده را نمایش می‌دهد.

نتیجه:

با اجرای این کد، یک نمودار گرافیکی از ماتریس نمایش داده می‌شود که در آن:

• دیوارها به رنگ سیاه، مسیر آزاد به رنگ سفید.

• مسیر از نقطه شروع به هدف با رنگ طلایی نشان داده شده است.

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

خلاصه عملکرد کلی کد:

1. بررسی صحت نقاط شروع و هدف: اطمینان از اینکه هر دو نقطه روی مسیر آزاد قرار دارند.

2. شروع جستجوی دو جهتی: از هر دو طرف (شروع و هدف) به طور همزمان BFS انجام می‌شود.

3. پیدا کردن نقطه تقاطع: وقتی دو جستجو به یک نقطه مشترک می‌رسند، جستجو متوقف می‌شود.

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

5. نمایش گرافیکی: مسیر پیدا شده به همراه ماتریس به صورت گرافیکی ترسیم می‌شود.

این الگوریتم به دلیل جستجوی همزمان از دو جهت، در بسیاری از موارد کارآمدتر از جستجوی یک‌طرفه BFS است، به ویژه در محیط‌های بزرگ.