UCS

البته! در ادامه، هر بخش و هر خط از کد ارائه شده را به تفصیل توضیح می‌دهم:

۱. وارد کردن کتابخانه‌ها

import networkx as nx
import matplotlib.pyplot as plt
import heapq

• import networkx as nx:

  • NetworkX یک کتابخانه پایتون برای ایجاد، مدیریت و مطالعه ساختار، دینامیک و عملکرد شبکه‌های پیچیده است. این خط کتابخانه NetworkX را با نام مستعار nx وارد می‌کند تا در طول کد به راحتی از آن استفاده شود.

• import matplotlib.pyplot as plt:

  • Matplotlib یک کتابخانه قدرتمند برای ایجاد نمودار و ترسیم‌های دو بعدی در پایتون است. ماژول pyplot آن، که با نام مستعار plt وارد شده، رابطی شبیه به MATLAB برای ایجاد نمودارها فراهم می‌کند.

• import heapq:

  • heapq یک ماژول استاندارد پایتون است که عملکرد‌های مربوط به صف‌های اولویت‌دار (heaps) را فراهم می‌کند. این ماژول برای پیاده‌سازی صف اولویت در الگوریتم‌های جستجو مانند جستجوی هزینه یکنواخت (Uniform Cost Search) استفاده می‌شود.

۲. تعریف کلاس Node

class Node:
    def __init__(self, state, parent=None, action=None, path_cost=0):
        self.state = state
        self.parent = parent
        self.action = action
        self.path_cost = path_cost

    def __lt__(self, other):
        return self.path_cost < other.path_cost

• class Node::

  • تعریف یک کلاس به نام Node که برای نمایش هر گره (Node) در گراف یا درخت جستجو استفاده می‌شود.

• def __init__(self, state, parent=None, action=None, path_cost=0)::

  • متد سازنده (Constructor) کلاس Node است که هنگام ایجاد شیء جدید این کلاس فراخوانی می‌شود.

  • پارامترها:

    • state: وضعیت یا وضعیت فعلی گره.

    • parent: گره والد (گره قبلی در مسیر).

    • action: عملی که از گره والد به این گره انجام شده است.

    • path_cost: هزینه مسیر از گره شروع تا این گره.

• self.state = state:

  • ذخیره وضعیت گره در ویژگی state شیء.

• self.parent = parent:

  • ذخیره گره والد در ویژگی parent شیء.

• self.action = action:

  • ذخیره عملی که از گره والد به این گره انجام شده است.

• self.path_cost = path_cost:

  • ذخیره هزینه مسیر در ویژگی path_cost شیء.

• def __lt__(self, other)::

  • تعریف متد مقایسه‌ای کمتر (<) برای اشیاء کلاس Node. این متد برای مقایسه گره‌ها بر اساس هزینه مسیرشان استفاده می‌شود، که برای اولویت‌بندی در صف اولویت‌دار ضروری است.

• return self.path_cost < other.path_cost:

  • بازگرداندن نتیجه مقایسه هزینه مسیر این گره با هزینه مسیر گره دیگر.

۳. تعریف تابع جستجوی هزینه یکنواخت (Uniform Cost Search)

def uniform_cost_search(graph, start, goal):
    frontier = []
    heapq.heappush(frontier, Node(start))
    explored = set()
    path = []

    while frontier:
        node = heapq.heappop(frontier)

        if node.state == goal:
            path = reconstruct_path(node)
            break

        explored.add(node.state)

        for (cost, result_state) in graph[node.state]:
            if result_state not in explored:
                child_cost = node.path_cost + cost
                child_node = Node(result_state, node, None, child_cost)
                if not any(frontier_node.state == result_state and
                           frontier_node.path_cost <= child_cost for frontier_node in frontier):
                    heapq.heappush(frontier, child_node)

    return path

این تابع برای پیدا کردن کمترین هزینه مسیر از نقطه شروع (start) تا مقصد (goal) در یک گراف استفاده می‌شود.

• def uniform_cost_search(graph, start, goal)::

  • تعریف تابع uniform_cost_search با پارامترهای:

    • graph: گراف ورودی که به صورت یک دیکشنری پیاده‌سازی شده است.

    • start: گره شروع جستجو.

    • goal: گره هدف یا مقصد جستجو.

• frontier = []:

  • ایجاد یک لیست خالی به نام frontier که نقش صف اولویت‌دار را بازی می‌کند. این لیست برای نگهداری گره‌هایی است که باید بررسی شوند.

• heapq.heappush(frontier, Node(start)):

  • ایجاد یک شیء Node با وضعیت اولیه start و افزودن آن به frontier با استفاده از تابع heappush از ماژول heapq. ابتدا، هزینه مسیر این گره صفر است.

• explored = set():

  • ایجاد یک مجموعه خالی به نام explored برای ذخیره وضعیت گره‌هایی که قبلاً بررسی شده‌اند تا از بازبینی مجدد آنها جلوگیری شود.

• path = []:

  • ایجاد یک لیست خالی به نام path که مسیر نهایی از start به goal در آن ذخیره می‌شود.

• while frontier::

  • آغاز یک حلقه while که تا زمانی که frontier خالی نباشد اجرا می‌شود.

• node = heapq.heappop(frontier):

  • خارج کردن گره با کمترین هزینه مسیر از frontier با استفاده از heappop و ذخیره آن در متغیر node.

• if node.state == goal::

  • بررسی اینکه آیا وضعیت گره فعلی (node.state) برابر با وضعیت هدف (goal) است.

• path = reconstruct_path(node):

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

• break:

  • خروج از حلقه while چون مسیر به مقصد پیدا شده است.

• explored.add(node.state):

  • افزودن وضعیت گره فعلی به مجموعه explored برای نشان دادن این که این گره بررسی شده است.

• for (cost, result_state) in graph[node.state]::

  • مرور تمام همسایگان (شامل هزینه و وضعیت) گره فعلی در گراف.

• if result_state not in explored::

  • بررسی اینکه وضعیت همسایه قبلاً بررسی نشده باشد.

• child_cost = node.path_cost + cost:

  • محاسبه هزینه مسیر به همسایه با افزودن هزینه یال جاری (cost) به هزینه مسیر جاری (node.path_cost).

• child_node = Node(result_state, node, None, child_cost):

  • ایجاد یک شیء Node جدید برای همسایه با وضعیت result_state, والد آن node, عملی مشخص نشده (None)، و هزینه مسیر محاسبه شده child_cost.

• if not any(frontier_node.state == result_state and frontier_node.path_cost <= child_cost for frontier_node in frontier)::

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

• heapq.heappush(frontier, child_node):

  • افزودن همسایه جدید به frontier با استفاده از heappush تا در صف اولویت قرار گیرد.

• return path:

  • بازگرداندن مسیر نهایی پیدا شده پس از پایان حلقه while.

۴. تعریف تابع بازسازی مسیر (Reconstruct Path)

def reconstruct_path(node):
    path = []
    while node:
        path.append(node.state)
        node = node.parent
    return path[::-1]

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

• def reconstruct_path(node)::

  • تعریف تابع reconstruct_path که یک شیء Node (فرضاً گره هدف) را به عنوان ورودی می‌گیرد.

• path = []:

  • ایجاد یک لیست خالی به نام path برای ذخیره مسیر.

• while node::

  • آغاز یک حلقه while تا زمانی که node برابر با None نباشد.

• path.append(node.state):

  • افزودن وضعیت گره فعلی به لیست path.

• node = node.parent:

  • حرکت به گره والد برای ادامه بازسازی مسیر به سمت گره شروع.

• return path[::-1]:

  • بازگرداندن مسیر به صورت معکوس ([::-1])، زیرا مسیر از گره هدف به گره شروع ساخته شده است و نیاز به ترتیب از شروع به هدف دارد.

۵. تعریف تابع ترسیم گراف (Visualize Graph)

def visualize_graph(graph, path=None):
    G = nx.DiGraph()
    labels = {}
    for node, edges in graph.items():
        for cost, child_node in edges:
            G.add_edge(node, child_node, weight=cost)
            labels[(node, child_node)] = cost

    pos = nx.spring_layout(G)
    nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=2000)
    nx.draw_networkx_edge_labels(G, pos, edge_labels=labels)

    if path:
        path_edges = list(zip(path[:-1], path[1:]))
        nx.draw_networkx_edges(G, pos, edgelist=path_edges, edge_color='r', width=2)

    plt.show()

این تابع برای ترسیم گراف و مسیر یافت شده (در صورت وجود) استفاده می‌شود.

• def visualize_graph(graph, path=None)::

  • تعریف تابع visualize_graph با پارامترهای:

    • graph: گراف ورودی به صورت دیکشنری.

    • path: مسیر پیدا شده توسط الگوریتم جستجو (اختیاری).

• G = nx.DiGraph():

  • ایجاد یک گراف جهت‌دار خالی با استفاده از NetworkX.

• labels = {}:

  • ایجاد یک دیکشنری خالی برای ذخیره برچسب‌های یال‌ها (هزینه‌ها).

• for node, edges in graph.items()::

  • مرور هر گره و یال‌های متصل به آن در گراف ورودی.

• for cost, child_node in edges::

  • مرور هر یال متصل به گره جاری شامل هزینه یال و گره مقصد.

• G.add_edge(node, child_node, weight=cost):

  • افزودن یال به گراف NetworkX با وزن (هزینه) مشخص.

• labels[(node, child_node)] = cost:

  • ذخیره هزینه یال به عنوان برچسب در دیکشنری labels.

• pos = nx.spring_layout(G):

  • محاسبه موقعیت هر گره در فضای دو بعدی با استفاده از الگوریتم نمایش فنری (Spring Layout) برای جذابیت بصری.

• nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=2000):

  • ترسیم گراف با موقعیت‌های تعیین‌شده، نمایش برچسب‌ها، رنگ دهی گره‌ها به رنگ آبی روشن و تنظیم اندازه گره‌ها.

• nx.draw_networkx_edge_labels(G, pos, edge_labels=labels):

  • ترسیم برچسب‌های یال‌ها (هزینه‌ها) در موقعیت‌های تعیین‌شده.

• if path::

  • بررسی اینکه آیا مسیر پیدا شده (path) وجود دارد یا خیر.

• path_edges = list(zip(path[:-1], path[1:])):

  • ایجاد لیستی از یال‌های مسیر به صورت جفت‌های پشت سر هم.

• nx.draw_networkx_edges(G, pos, edgelist=path_edges, edge_color='r', width=2):

  • ترسیم یال‌های مسیر با رنگ قرمز و عرض دو برابر برای برجسته کردن مسیر.

• plt.show():

  • نمایش نمودار ترسیم‌شده با استفاده از Matplotlib.

۶. تعریف گراف، نقطه شروع و هدف، اجرای جستجو و نمایش نتایج

# Define the graph
graph = {
    'A': [(1, 'B'), (3, 'C')],
    'B': [(2, 'D')],
    'C': [(5, 'D'), (2, 'B')],
    'D': []
}

start = 'A'
goal = 'D'
path = uniform_cost_search(graph, start, goal)

visualize_graph(graph, path)
print("Path from", start, "to", goal, ":", path)

• تعریف گراف:

  graph = {
      'A': [(1, 'B'), (3, 'C')],
      'B': [(2, 'D')],
      'C': [(5, 'D'), (2, 'B')],
      'D': []
  }
  

  • گراف به صورت یک دیکشنری تعریف شده است که کلیدها گره‌ها ('A', 'B', 'C', 'D') و مقادیر لیستی از تاپل‌ها هستند. هر تاپل شامل یک هزینه یال و گره مقصد است.

  • به عنوان مثال، از گره 'A' به 'B' با هزینه 1 و به 'C' با هزینه 3 ارتباط وجود دارد.

  • گره 'D' هیچ یالی خروجی ندارد (لیست خالی).

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

  start = 'A'
  goal = 'D'
  

  • نقطه شروع جستجو گره 'A' و هدف جستجو گره 'D' است.

• اجرای جستجوی هزینه یکنواخت:

  path = uniform_cost_search(graph, start, goal)
  

  • فراخوانی تابع uniform_cost_search با گراف تعریف‌شده، نقطه شروع 'A' و هدف 'D'. نتیجه مسیر پیدا شده در متغیر path ذخیره می‌شود.

• ترسیم گراف و مسیر:

  visualize_graph(graph, path)
  

  • فراخوانی تابع visualize_graph با گراف ورودی و مسیر پیدا شده. این تابع گراف را ترسیم کرده و مسیر پیدا شده را برجسته می‌کند.

• چاپ مسیر پیدا شده:

  print("Path from", start, "to", goal, ":", path)
  

  • نمایش مسیر پیدا شده از نقطه 'A' به 'D' به صورت متنی در کنسول. برای مثال:

    Path from A to D : ['A', 'B', 'D']
    

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

1. ایمپورت کتابخانه‌های لازم: برای مدیریت گراف، ترسیم و استفاده از صف اولویت.

2. تعریف کلاس Node: برای نمایش هر گره در روند جستجو با ویژگی‌هایی مانند وضعیت، والد، عمل و هزینه مسیر.

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

4. تعریف تابع reconstruct_path: بازسازی مسیر پیدا شده از گره هدف به گره شروع.

5. تعریف تابع visualize_graph: ترسیم گراف و مسیر پیدا شده به صورت بصری.

6. تعریف گراف نمونه: یک گراف ساده با چهار گره و هزینه‌های مشخص برای یال‌ها.

7. اجرای جستجو: پیدا کردن مسیر از 'A' به 'D' با استفاده از الگوریتم.

8. نمایش نتایج: ترسیم گراف با مسیر پیدا شده و چاپ مسیر در کنسول.

با اجرای این کد، شما می‌توانید مسیر با کمترین هزینه از گره 'A' به گره 'D' را پیدا کرده و آن را به صورت تصویری مشاهده کنید.