تفاوت الگوریتم uniform cost search یا UCS با BFS

Question

دوستان خسته نباشید  UCS با BFS چه تفاوتی داره ؟  و به چه شکل پیاده سازی میشه ؟

Answer 1

در UCS  هر بار راسی  که کمترین فاصله رو داره انتخاب می کنیم و چک می کنیم که آیا راس هدف هست یا نه اگر راس هدف نبود گسترش داده میشه  و تا رسیدن به هدف این کار رو ادامه میدیم

در BFS ما اول همه ی راس های متصل به یک Node رو گسترش میدادیم بعد از گسترش دادن چک می کنیم که به هدف رسیدیم یا نه واین کارو تا رسیدن به هدف ادامه میدیم.

 

پس تفاوت BFS و UCS دو مورد هست :

•  در UCS راسی که گسترش داده میشه  راس با کمترین cost هست در حالی که در BFS بترتیب ورود گسترش داده میشن
• در BFS ما بعد از گسترش این که به هدف رسیدیم چک میشه ولی در UFS قبل از گسترش 

 

این گراف رو در نظر بگیرید :

 

 

فرض کنید که از راس A شروع کردیم و می خواهیم به G برسیم 

الگوریتم UCS به این شکل عمل می کنه :

 

مرحله 1 : 2 مسیر A_B , A_D رو  به عنوان مسیر اولیه به راس های پیموده شده اضافه می کنیم :

A_B 

A_D

 

مرحله 2 : این جا ما 2 مسیر A_B داریم و A_D  چون مسیر A_D طولش از A_B کمتر هست اونو گسترش میدیم

A_B

A_D_F

A_D_E

 

مرحله 3 : این جا طول مسیر A_B از 2 مسیر A_D_E , A_D_F کمتر هست پس مسیر A_B گسترش داده میشه

A_B_C

A_D_F

A_D_E

 

مرحله 4 :این جا مسیر A_D_F کمترین طول روداره (طول از A_D که 3 هست + D_F که 2 هست یعنی در مجموع 5 

A_B_C

A_D_F_G

A_D_E

 

مرحله 5 :  در این مرحله چون A_D_E کمترین طول رو داره گسترش داده میشه (دقت کنید با این که حتی به Goal رسیدیم ولی جست و جو ادامه داره)

A_B_C

A_D_F_G

A_D_E_B  چون قبلا به B رفتیم و این مسیر از A_B بلند تر هست اضافه نمیشه 

 

مرحله 6 :  در این مرحله چون A_B_C کمترین طول رو داره گسترش داده میشه

A_B_C_G

A_D_F_G

 

مرحله 7 :  در این مرحله چون A_D_F_G کمترین طول رو داره گسترش داده میشه ولی چون داخل مسیر G هم وجود داره یعنی به goal رسیدیم و مسیر مورد نظر برگشت داده میشه .

 

شَبه کد الگوریتم به این شکل میشه :

 

 

 

Answer 2

UCS (جستجوی هزینه یکنواخت) یک الگوریتم جستجو است که برای پیمایش یا جستجوی یک درخت یا نمودار وزن دار استفاده می شود. این شبیه به الگوریتم شناخته شده Dijkstra است و برای یافتن کوتاه ترین مسیر بین دو گره در یک گراف استفاده می شود. تفاوت کلیدی بین UCS و Dijkstra در این است که الگوریتم Dijkstra فقط زمانی قابل استفاده است که تمام وزن های لبه غیر منفی باشند، در حالی که UCS می تواند زمانی استفاده شود که وزن های منفی وجود داشته باشد، اما چرخه های منفی وجود نداشته باشد. الگوریتم تمام مسیرها را به ترتیب افزایش هزینه بررسی می کند و تضمین می شود که در صورت وجود راه حل بهینه را پیدا کند.

#include <iostream>
#include <queue>
#include <vector>
#include <utility>
using namespace std;

#define INF 0x3f3f3f3f

vector<pair<int,int>> adj[100]; // Adjacency list to store edges and weights
int dist[100]; // Array to store the minimum distance from the source to each node
bool visited[100]; // Array to keep track of visited nodes

void UCS(int start, int goal) {
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; // Priority queue to sort nodes by increasing distance
    pq.push({0, start}); // Push the starting node into the queue
    for (int i = 0; i < 100; i++) {
        dist[i] = INF; // Initialize all distances as infinite
    }
    dist[start] = 0; // Distance to the starting node is 0

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (visited[u]) continue; // Skip if the node has already been visited
        visited[u] = true;
        for (int i = 0; i < adj[u].size(); i++) {
            int v = adj[u][i].first;
            int weight = adj[u][i].second;
            if (dist[v] > dist[u] + weight) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
    cout << "Shortest distance from node " << start << " to node " << goal << " is " << dist[goal] `oaicite:{"index":0,"invalid_reason":"Malformed citation << endl;\n}\n\nint main() {\n    int n, m; // n = number of nodes, m = number of edges\n    cin >> n >>"}` m;
    for (int i = 0; i < m; i++) {
        int u, v, w; // u and v are the nodes, w is the weight of the edge
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }
    int start, goal;
    cin >> start >> goal;
    UCS(start, goal);
    return 0;
}

 

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

لطفاً توجه داشته باشید که این یک پیاده سازی ساده است و ممکن است بخواهید آن را با استفاده خاص خود تنظیم کنید.

Answer 3

تفاوت بین UCS (جستجوی هزینه یکنواخت) و BFS (جستجوی گسترده-اول) عبارتند از:

 

1- UCS نوعی الگوریتم جستجو است که برای یافتن مسیر با حداقل هزینه از گره شروع به گره هدف در یک نمودار وزنی استفاده می شود. این الگوریتم بدین گونه کار می کند که ابتدا گره را با کمترین هزینه گسترش می دهد و سپس همسایگان آن را تا رسیدن به گره هدف کاوش می کند.

 

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

 

از نظر پیاده سازی، هر دو الگوریتم را می توان با استفاده از ساختار داده صف پیاده سازی کرد. برای UCS، از صف اولویت برای ذخیره گره های مورد بررسی استفاده می شود، جایی که گره ها بر اساس هزینه آنها اولویت بندی می شوند. برای BFS، یک صف استاندارد برای ذخیره گره های مورد بررسی استفاده می شود، جایی که گره ها به ترتیبی که به صف اضافه می شوند، گسترش می یابند.

 

توجه به این نکته مهم است که BFS تضمینی برای یافتن راه حل بهینه در یک نمودار وزنی ندارد، زیرا هزینه یال ها را در نظر نمی گیرد. در چنین مواردی، UCS الگوریتم ترجیحی است.