سوال در مورد الگوریتم BFS در درس هوش مصنوعی

[s4lish]

سلام دوستان...حتما خیلی از شما الگوریتم BFS رو می شناسید...

من آخرش هر کاری کردم نتونستم پیاده سازیش کنم....:عصبانی++:

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

مشکل اصلی من تو پیمایش گراف نیست...
مشکل اینجاست یال های این گراف اندازه دارن و جهت هم ندارن و باید یه محدوده تعیین کنیم براش..مثلا تا عمق 12 پیش بره..حالا من تو پیاده سازیش موندم....یعنی کسی نیست بگه چطور می شه اینو نوشت؟!

[s4lish]

اینو که گفتید گفتنش ساده بووود....من خودم بسیار الگوریتم نوشتم....ولی این دیگه واقعا خیلی باسم سنگینه...
در ضمن من هنوز تو اینش موندم..تازه استاد گفته باید با DFS بنویسیم و همینطور پازل 8 رو با A* ...
حالا که فکرشو می کنم مخم سووت می کشه.:عصبانی++:

[قله بلند]

سلام
من یه توضیحاتی می دم. امیدوارم مفید باشه.

در الگوریتم ادموندز-کارپ، قراره مسیر منبع تا چاه در کمترین یال پیدا بشه یعنی دیگه مسیرهای گمراه کننده و زیاد شونده و بی خودی باید حذف بشه. یکی از طرقش استفاده از BFS هست. در این الگوریتم(ادموندز-کارپ) ما هم جهت داریم و هم اندازه یال ولی برای پیدا کردن کوتاهترین مسیر دیگه در BFS نه به اندازه یال ها نگاه می کنیم و نه به جهت اونها بلکه بدون جهت و با اندازه 1. حالا مسیری پیدا شد ولی ممکنه اون مسیری نباشه که ما را به چاه برسونه، خوب از یه مسیر دیگه می ریم. یعنی چون جهت رو از بین بردیم اینجوری شد. اینقدر این حلقه می چرخه تا بالاخره مسیر کوتاهی پیدا بشه که ما رو به چاه برسونه.
حالا برای الگوریتم شما هم همینه، قراره از آراد به بخارست برسید. با این الگوریتم با کوتاهترین مسیر می رسید.
اینی که گفته شده تا عمق 12، به نظرم درست نباشه چون شاید شما مجبور باشید تا آخرین عمق درخت یا گراف رو پیمایش کنید تا به بخارست برسید.
اگر هم واقعاً این منظور باشه، که هر سطحی که توسط این الگوریتم پیمایش می شه یعنی یک عمق شما پیش رفته اید، البته به غیر از ریشه که در سطح صفر قرار دارد.
شما باید کل حلقه while رو بنویسید که کل درخت یا گراف رو پیمایش بکنه و شرط if قرار بدید که اگر به سطح 12 رسید از برنامه خارج بشه. در این حالت یا به بخارست رسیده یا نرسیده. یه متغیر تعریف کنید و مقدار اون رو صفر بگذارید و هر بار که گره ای ملاقات شد و همسایه های اون وارد صف شد، یکی به شمارنده اضافه کنید و هر بار با شرطی که در if می گذارید چک کنید تا از عمق 12 خارج نشود.

[s4lish]

دوستان ..من یه چیزایی گرفتم ولی اینکه نمی تونم بنویسم شاید به خاطر اطلاعات ناکافی از برنامه نویسی باشه.......خودم الان چن روزه دپرس شدم..استاد هم سخت گیریاشو بیشتر کرده..5 تا برنامه داده بنویسیم هر کدوم یه نمره امتحان آخر هم از 10 نمره می خواد بگیره..یه دونه هم ارائه می خواد که من شناسایی از طریق کف دست رو انتخاب کردم..بعدشم تمرینات کتاب راسل رو هم می خواد..حالا این همه دغدغه ی فکری دارم..اصلا مغزم خوب کار نمی کنه...خیلی ناامید شدم به این درس تو این ترم...خواستم با سی پلاس بنوسیم که پیاده سازی صف و اینچیزا بساط داره...تو سی شارپ می خوام بنویسم نمی دونم این صف رو صورت آبجکت می شناسه..نمی تونم داده ای رو ازش بردارم و تو یه Int ذخیره کنم...اخطار می ده ..
can not convert Object to int .....
دیگه حوصلمو سر برده..نخواستیم اصلا..حالم بد شد.

[faezeh_r]

میشه کد این الگوریتمو رو سایت بذارید. ممنون

[s4lish]

میشه کد این الگوریتمو رو سایت بذارید. ممنون

دوست عزیز اگه کد رو بلد بودم که دیگه نمی اومدم که تو سایت سوال بپرسم...
من هنوز نمی تونم شبیه سازیش کنم که چطوری عمل می کنه ..
اصلا مدیریت حافظه ی این چطوری خواهد بود که اون همه اطلاعات رو ذخیره کنه..

جدا مدیریت حافظش چه شکلیه صورت می گیره؟!؟

[qwerty11]

خواستم با سی پلاس بنوسیم که پیاده سازی صف و اینچیزا بساط داره...تو سی شارپ می خوام بنویسم نمی دونم این صف رو صورت آبجکت می شناسه..نمی تونم داده ای رو ازش بردارم و تو یه Int ذخیره کنم...اخطار می ده ..
can not convert Object to int .....
دیگه حوصلمو سر برده..نخواستیم اصلا..حالم بد شد.
سلام. خدا بد نده :متفکر: cast کردن میدونی چیه !؟ شما با سی پلاس آشنایی خوبی نداری چون سی پلاس خودش صف و این چیزا رو پیاده سازی کرده برات. با یه سرچ ساده میتونی پیداش کنی !

من هنوز نمی تونم شبیه سازیش کنم که چطوری عمل می کنه ..
اصلا مدیریت حافظه ی این چطوری خواهد بود که اون همه اطلاعات رو ذخیره کنه..

جدا مدیریت حافظش چه شکلیه صورت می گیره؟!؟
2 تا راه میتونم بهت پیشنهاد بدم :

1- کلاً 9! حالت داری و هر حالت هم 9 کاراکتر. پس کلاً سه و نیم میلیون بایت حافظه میخوای که ram هم در اختیارت میزاره و مشکلی نیست.

2- کلاً 9! حالت داری. پس هر حالت رو میشه تو یه int ذخیره کرد. که کلاً 4*9! بایت خونه ی حافظه میشه. (تو این روش مثلاً باید به حالت 123456789 عدد 0، به حالت 123456798 عدد 1 و ... نسبت بدی)

[faezeh_r]

سلام لازم نیست که شما بذاریدش رو سایت خودم پیداش کردم می ذارمش تا شما هم فیض ببرید!!


#include <iostream>
using namespace std;
struct node {
int info;
node *next;
};
class Queue {
public:
Queue();
~Queue();
bool isEmpty();
void add(int);
int get();
private:
node *first, *last;
};
class Graph {
public:
Graph(int size = 2);
~Graph();
bool isConnected(int, int);
// adds the (x, y) pair to the edge set
void addEdge(int x, int y);
// performs a Breadth First Search starting with node x
void BFS(int x);
// searches for the minimum length path
// between the start and target vertices
void minPath(int start, int target);
private :
int n;
int **A;
};
Queue::Queue() {
first = new node;
first->next = NULL;
last = first;
}
Queue::~Queue() {
delete first;
}
bool Queue::isEmpty() {
return (first->next == NULL);
}
void Queue::add(int x) {
node *aux = new node;
aux->info = x;
aux->next = NULL;
last->next = aux;
last = aux;
}
int Queue::get() {
node *aux = first->next;
int value = aux->info;
first->next = aux->next;
if (last == aux) last = first;
delete aux;
return value;
}
Graph::Graph(int size) {
int i, j;
if (size < 2) n = 2;
else n = size;
A = new int*[n];
for (i = 0; i < n; ++i)
A[i] = new int[n];
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j)
A[i][j] = 0;
}
Graph::~Graph() {
for (int i = 0; i < n; ++i)
delete [] A[i];
delete [] A;
}
bool Graph::isConnected(int x, int y) {
return (A[x-1][y-1] == 1);
}
void Graph::addEdge(int x, int y) {
A[x-1][y-1] = A[y-1][x-1] = 1;
}
void Graph::BFS(int x) {
Queue Q;
bool *visited = new bool[n+1];
int i;
for (i = 1; i <= n; ++i)
visited[i] = false;
Q.add(x);
visited[x] = true;
cout << "Breadth First Search starting from vertex ";
cout << x << " : " << endl;
while (!Q.isEmpty()) {
int k = Q.get();
cout << k << " ";
for (i = 1; i <= n; ++i)
if (isConnected(k, i) && !visited[i]) {
Q.add(i);
visited[i] = true;
}
}
cout << endl;
delete [] visited;
}
void Graph::minPath(int start, int target) {
Queue Q;
int i, p, q;
bool found;
struct aux { int current, prev; };
aux *X = new aux[n+1];
int *Y = new int[n+1];
bool *visited = new bool[n+1];
for (i = 1; i <= n; ++i)
visited[i] = false;
Q.add(start);
visited[start] = true;
found = false;
p = q = 0;
X[0].current = start;
X[0].prev = 0;
while (!Q.isEmpty() && !found) {
int k = Q.get();
for (i = 1; i <= n && !found; ++i)
if (isConnected(k, i) && !visited[i]) {
Q.add(i);
++q;
X[q].current = i;
X[q].prev = p;
visited[i] = true;
if (i == target) found = true;
}
++p;
}
cout << "The minimum length path from " << start;
cout << " to " << target << " is : " << endl;
p = 0;
while (q) {
Y[p] = X[q].current;
q = X[q].prev;
++p;
}
Y[p] = X[0].current;
for (q = 0; q <= p/2; ++q) {
int temp = Y[q];
Y[q] = Y[p-q];
Y[p-q] = temp;
}
for (q = 0; q <= p; ++q)
cout << Y[q] << " ";
cout << endl;
cout << "Length = " << q-1 << endl;
delete [] visited;
delete [] X;
delete [] Y;
}

[motanro]

هوش مصنوعی خیلی رشته خوبیه، مخصوصا رشته پردازش تصویرش
در کل کاربرد هوش مصنوعی کلا گستردس و مثل یک ابزار هست که هر شخصی می تونه ازش استفاده خوب یا بد کنه
در رابطه با هوش مصنوعی (https://hamrah.academy/blog/artificial-intelligence/) آکادمی همراه اول یک مقاله خوب نوشته که واقعا عالی بود
بهتون پیشنهاد میدم که بخونید ...
اینم لینکش:
https://hamrah.academy/blog/artificial-intelligence/