مسئله ظرف آب در هوش مصنوعی

[fati71]

با سلام
یه سوال دارم خواهشا جواب بدید
مسئله ظرف آب در هوش مصنوعی
یه ظرف با ظرفیت3 لیتری و یه ظرف با ظرفیت 4 لیتری داریمx=4 ,y=3
از مقدار 0و0 می خواهیم برسیم به مقدار درخواستی کاربر مثلا 2و0(x=2, y=0)
در هر مرحله یک کار باید انجام شود(یعنی مثلا یا x پر شود یا خالی شود و یا y پر شود یا خالی شود و یا مقادیر با هم جابه جا می شوند ..)
مراحل زیر طی می شود
x=0 ,y=0
x=0,y=3
x=3 , y=0
x=3,y=3
x=4,y=2
x=0,y=2
x=2,y=0
این برنامه رو به زبان سی شارپ می خواستم
تقریبا حل کردم و از الگوریتم bf استفاده کردم ولی خیلی مشکل دارم چون تازه برنامه نویسی رو آغاز کردم
آیا کسی می تونه راهنمایی کنه ؟

[pedram.11]

سلام و عرض احترام
منو بسی به تفکر واداشت :متفکر: گردو غبار اون قسمت از حافظه برداشته شد :لبخند:
بلی با bfs حل میشه. من به اینصورت نوشتمش:
void bfs(int x, int y)
{
int maxX = 4, maxY = 3;
Dictionary<KeyValuePair<int, int>, bool> visited = new Dictionary<KeyValuePair<int, int>, bool>();
Dictionary<KeyValuePair<int, int>, KeyValuePair<int, int>> steps = new Dictionary<KeyValuePair<int, int>, KeyValuePair<int, int>>();
visited[new KeyValuePair<int, int>(0, 0)] = true;
steps[new KeyValuePair<int, int>(0, 0)] = new KeyValuePair<int, int>(0, 0);
Queue<KeyValuePair<int, int>> q = new Queue<KeyValuePair<int, int>>();
q.Enqueue(new KeyValuePair<int, int>(0, 0));
List<KeyValuePair<int, int>> Way = new List<KeyValuePair<int, int>>();
while (q.Count > 0)
{
KeyValuePair<int, int> p = q.Dequeue();
visited[p] = true;
if (p.Key == x && p.Value == y)
{
KeyValuePair<int, int> v = p;
Way.Add(p);
while ((v = steps[v]).Key != 0 || v.Value != 0)
Way.Add(v);
Way.Add(new KeyValuePair<int,int>(0,0));
}
if (p.Key == maxX)
{
KeyValuePair<int, int> EmptyX = new KeyValuePair<int, int>(0, p.Value);
if (!visited.ContainsKey(EmptyX))
{
q.Enqueue(EmptyX);
visited[EmptyX] = true;
steps[EmptyX] = p;
}
}
if (p.Value == maxY)
{
KeyValuePair<int, int> EmptyY = new KeyValuePair<int, int>(p.Key, 0);
if (!visited.ContainsKey(EmptyY))
{
q.Enqueue(EmptyY);
visited[EmptyY] = true;
steps[EmptyY] = p;
}
}
if (p.Key == 0)
{
KeyValuePair<int, int> fullX = new KeyValuePair<int, int>(maxX, p.Value);
if (!visited.ContainsKey(fullX))
{
q.Enqueue(fullX);
visited[fullX] = true;
steps[fullX] = p;
}
}
if (p.Value == 0)
{
KeyValuePair<int, int> fullY = new KeyValuePair<int, int>(p.Key, maxY);
if (!visited.ContainsKey(fullY))
{
q.Enqueue(fullY);
visited[fullY] = true;
steps[fullY] = p;
}
}
for (int i = 1; i <= p.Key; i++)
{
if (p.Value + i > maxY)
break;
KeyValuePair<int, int> n = new KeyValuePair<int, int>(p.Key - i, p.Value + i);
if (!visited.ContainsKey(n))
{
q.Enqueue(n);
visited[n] = true;
steps[n] = p;
}
}
for (int i = 1; i <= p.Value; i++)
{
if (p.Key + i > maxX)
break;
KeyValuePair<int, int> n = new KeyValuePair<int, int>(p.Key + i, p.Value - i);
if (!visited.ContainsKey(n))
{
q.Enqueue(n);
visited[n] = true;
steps[n] = p;
}
}
}
for (int i = Way.Count-1; i >= 0; i--)
Console.WriteLine(string.Format("x={0}, y={1}", Way[i].Key, Way[i].Value));
}

موفق باشید :تشویق:

[fati71]

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

[pedram.11]

بله چشم :لبخندساده:
همونطور که میدونیم الگوریتم bfs برای پیدا کردن کوتاهترین مسیر از صف یا queue استفاده میکنه.
و الگوریتم اون به اینصورت هست:

Visited[v]:=1
CreateQueue(q)
AddQueue(q, v)
While (not EmptyQueue(q))
DeleteQueue(q,v)
For (all vertex w adjacent to v)
If (not visited[w]) then
AddQueue(q,w)
Visited[w]:=1
End if
End For
End while
visited برای بررسی اینه که اون node از گراف پردازش شده یا نه. node شروع رو در queue قرار میدیم و تا وقتی که صف خالی نشده یا به جواب نرسیدیم به ازای هر نودی که از صف برمیداریم تمام نودهای مجاور اون نود که قبلا پردازش نشده رو در صف قرار داده و همینکارو ادامه میدیم...

حالا توی کدایی که گذاشتم:



void bfs(int x, int y)
{
int maxX = 4, maxY = 3;
Dictionary<KeyValuePair<int, int>, bool> visited = new Dictionary<KeyValuePair<int, int>, bool>();
Dictionary<KeyValuePair<int, int>, KeyValuePair<int, int>> steps = new Dictionary<KeyValuePair<int, int>, KeyValuePair<int, int>>();
visited[new KeyValuePair<int, int>(0, 0)] = true;
steps[new KeyValuePair<int, int>(0, 0)] = new KeyValuePair<int, int>(0, 0);
Queue<KeyValuePair<int, int>> q = new Queue<KeyValuePair<int, int>>();
q.Enqueue(new KeyValuePair<int, int>(0, 0));
List<KeyValuePair<int, int>> Way = new List<KeyValuePair<int, int>>();

visited برای ثبت نود های پردازش شدست. steps که اسمشو اشتباهی نوشتم :اشتباه: نود قبلیو که به نود فعلی رسیدیم رو ثبت میکنه(برای ثبت کل مسیر شروع تا پایان جواب)
چون ما از نود 0و0 شروع میکنیم visited رو true و اونو در صف q قرار میدیم(خط 9).

while (q.Count > 0)
{
KeyValuePair<int, int> p = q.Dequeue();
visited[p] = true;

بعد از هربار که یه نود رو از صف برمیداریم اون رو پردازش شده در نظر میگیریم که دوبازه اشتباهی در صف ثبت نشه.

اگه به جواب رسیدیم از نود پایانی نود قبلی رو که در steps ذخیره شده بود رو بدست میاریم و توی لیست جواب Way میریزیم:

if (p.Key == x && p.Value == y)
{
KeyValuePair<int, int> v = p;
Way.Add(p);
while ((v = steps[v]).Key != 0 || v.Value != 0)
Way.Add(v);
Way.Add(new KeyValuePair<int,int>(0,0));
}
طبق محدودیت های سوال که گفتید یا ظرف کامل پر شه یا خالی و یا از یکی به یکی دیگه ریخته بشه، همه حالت هارو چک میکنیم و در صورتی که قبلا چک نشدن در صف قرار میدیم.



وقتی که ظرف X پر باشه میشه کلا خالیش کرد:
if (p.Key == maxX)
{
KeyValuePair<int, int> EmptyX = new KeyValuePair<int, int>(0, p.Value);
if (!visited.ContainsKey(EmptyX))
{
q.Enqueue(EmptyX);
visited[EmptyX] = true;
steps[EmptyX] = p;
}
}
اگه هم ظرف Y پر باشه میشه خالیش کرد:

if (p.Value == maxY)
{
KeyValuePair<int, int> EmptyY = new KeyValuePair<int, int>(p.Key, 0);
if (!visited.ContainsKey(EmptyY))
{
q.Enqueue(EmptyY);
visited[EmptyY] = true;
steps[EmptyY] = p;
}
}
اگه ظرف X خالی باشه میشه پرش کرد:


if (p.Key == 0)
{
KeyValuePair<int, int> fullX = new KeyValuePair<int, int>(maxX, p.Value);
if (!visited.ContainsKey(fullX))
{
q.Enqueue(fullX);
visited[fullX] = true;
steps[fullX] = p;
}
}
اگه ظرف Y خالی باشه میشه پرش کرد:
if (p.Value == 0)
{
KeyValuePair<int, int> fullY = new KeyValuePair<int, int>(p.Key, maxY);
if (!visited.ContainsKey(fullY))
{
q.Enqueue(fullY);
visited[fullY] = true;
steps[fullY] = p;
}
}

در آخر تمام حالاتی که از ظرف X بشه به ظرف Y و ریخت عکسش رو با 2 حلقه جداگونه بررسی میکنیم و در صف قرار میدیم:



for (int i = 1; i <= p.Key; i++)
{
if (p.Value + i > maxY)
break;
KeyValuePair<int, int> n = new KeyValuePair<int, int>(p.Key - i, p.Value + i);
if (!visited.ContainsKey(n))
{
q.Enqueue(n);
visited[n] = true;
steps[n] = p;
}
}
for (int i = 1; i <= p.Value; i++)
{
if (p.Key + i > maxX)
break;
KeyValuePair<int, int> n = new KeyValuePair<int, int>(p.Key + i, p.Value - i);
if (!visited.ContainsKey(n))
{
q.Enqueue(n);
visited[n] = true;
steps[n] = p;
}
}
و آخر کار جوابو چاپ میکنیم


for (int i = Way.Count-1; i >= 0; i--)
Console.WriteLine(string.Format("x={0}, y={1}", Way[i].Key, Way[i].Value));


اگه خوب توضیح ندادم بگید تا بگم :لبخند: :لبخندساده:

[fati71]

آقای پدرام خیلی متشکرم

[nadianadia]

سلام خسته نباشید میتونید بگین چجوری میشه الگوریتم BFS رو برای بازی هشت توی سی شارپ یا matlab نوشت؟؟