پیاده سازی الگوریتم BFS

[mreram]

سلام
میخوام الگوریتم جستجوی عرضی رو پیاده سازی کنم ... لطفا کمک کنید چجوری این الگوریتم رو پیاده سازی کنم ؟؟
از نظر گرافیکی چطوری درخت رو از کاربر بگیرم؟
اگر تجربه ای دارید لطفا کمک کنید

[pedram.11]

سلام یه نمونه bfs در مورد سطل آب توی این تاپیک (http://barnamenevis.org/showthread.php?473831-%D9%85%D8%B3%D8%A6%D9%84%D9%87-%D8%B8%D8%B1%D9%81-%D8%A2%D8%A8-%D8%AF%D8%B1-%D9%87%D9%88%D8%B4-%D9%85%D8%B5%D9%86%D9%88%D8%B9%DB%8C) بود اگه سوالی بود در خدمتم :تشویق:

[mreram]

چجوری باید به این مقدار دهی کرد؟؟ کلا KeyValuePairچجوری مقدار میگیره؟؟
Queue<KeyValuePair<int, string>>
خیلی بهم کمک کرد مرسی

[pedram.11]

KeyValuePair مثه همون pair توی c++ یا truple هست. مثلا برای نوع int با مقدار 1 برای Key و نوع string با مقدار "x" برای Value:
KeyValuePair<int, string> pair = new KeyValuePair<int, string>(1, "x");



و برای دسترسی به مقادیر:
int key = pair.Key;
string value = pair.Value;

[mreram]

مثلا واسه وارد کردن یک مجموعه تو list اینکارو میکنم ولی واسه این نمیشه ...


List<int> nodes =new List<int> { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
این اررور میده:

List<KeyValuePair<int,string>> nodes =new List<KeyValuePair<int,string>> { { 1, 2},{"d","v" }};

[pedram.11]

اینطوری بنویسید:
List<KeyValuePair<int, string>> nodes = new List<KeyValuePair<int, string>> { new KeyValuePair<int, string>(1, "d"), new KeyValuePair<int, string>(2, "v") };
یا اینطوری:
List<KeyValuePair<int, string>> nodes = new List<KeyValuePair<int, string>>();
nodes.Add(new KeyValuePair<int, string>(1, "d"));
nodes.Add(new KeyValuePair<int, string>(2, "v"));

[mreram]

اون قسمت مسیر جوابو نفهمیدم:عصبانی++:
میشه بیشتر مسیر جواب رو توضیح بدی توضیح بدی ؟؟

[pedram.11]

چراااااا :عصبانی++: :لبخند:
مسیر جواب یعنی از کجا شروع کردیم و چه مسیری رو طی کردیم که به جواب رسیدیم. در bfs برای پیدا کردن مسیر راه های زیادی هست. یکی شماره گذاری نود ها یکی ثبت نود قبلی که از طریق اون به نود فعلی رسیدیم و ... . من حالت دوم رو انتخاب کردم. چون در حالت اول با شماره گذاری مجبور میشیم ازای هر شماره یکبار نود هارو پیمایش کنیم که این باعث کندی برنامه میشه و چون پیچیدگی زمانی دریافت آیتم از دیکشنری 1 هست اینو انتخاب کردم و به ازای هر نود، اون نود رو به عنوان کلید و نود قبلی رو بعنوان مقدار در دیکشنری ثبت کردم. در آخر که به جواب رسیدیم به ازای هر نود، نود قبلی رو که ازش به جواب رسیدیم رو به یه لیست(way) اضافه میکنیم. اینطوری به ترتیب از جواب تا نقطه شروع در لیست ثبت میشه و در یک حلقه معکوس میتونیم به جواب سوال برسیم

[mreram]

الان مسیر جوابو چجوری بنویسم اینجا؟

class BFS {


public static List<KeyValuePair<int, string>> src;
public static string answer;
Queue<KeyValuePair<int, string>> q = new Queue<KeyValuePair<int, string>>(src);
Dictionary<int, string> pathtrue = new Dictionary<int, string>();

Dictionary<KeyValuePair<int, string>, bool> visited = new Dictionary<KeyValuePair<int, string>, bool>();
List<KeyValuePair<int, string>> answers = new List<KeyValuePair<int, string>>();


public BFS()
{

while (q.Count > 0)
{
KeyValuePair<int, string> p = q.Dequeue();


visited[p] = true;
if (answer == p.Value)
{

answers.Add(p);

}
}

}
public void pathshow()
{
for (int j = 0; j < q.Count; j++)
MessageBox.Show(q.ToList()[j].Value);
}
public void answershow()
{
for (int i = answers.Count - 1; i >= 0; i--)
MessageBox.Show(answer);
}
}
private void Form1_Load(object sender, EventArgs e)
{
List<KeyValuePair<int, string>> lst =
new List<KeyValuePair<int, string>>{
new KeyValuePair<int,string>(1,"A"),
new KeyValuePair<int,string>(2,"B"),
new KeyValuePair<int,string>(3,"C"),
new KeyValuePair<int,string>(4,"D")};
BFS.src = lst;
BFS.answer="C";
BFS test = new BFS();
test.answershow();

[pedram.11]

اول اینکه کدها یکم مورد دارن
1. برای مسئله نباید از همون اول تمام نود ها توی صف باشن. در مرحله اول فقط باید نود شروع درون صف قرار بگیره.
2. نباید به هر نودی که رسیدید در صف قرارش بدید. فقط باید نود های مجاور اون نود و البته نودی که قبلا مشاهده نشده رو در صف قرار بدید. یعنی تنها نود هایی که از اون نود میشه دسترسی داشت و اینکه قبلا بهش نرسیدید!
3. pair انتخابی برای این مدل بنظر درست نمیاد. منظورتون از 1 و A چیه؟ اگه منظور وزن یال هست و اگه تمامی نودها(از A تا D) با هم مرتبط هستن که هیچ ولی باید نام دو نود مرتبط روی یال رو معرفی کنید، اما اگه هردو نام نود هستن باید از یک نوع باشن و این pair به این معنی میشه که key و value دو نود هستن که به هم راه دارن.

صورت سوال و همچنین نقطه شروع رو مشخص کنید بعد میشینیم پاش :لبخند: :تشویق:

[mreram]

درست میفرمایید :لبخند:
a,1 تو pair باید اصلاح بشه اول یه قصد دیگه داشتم ولی الان لازم ندارم
مسئله پیاده سازی الگوریتمه ..مسئله ی خاصی نیست فقط میخوام از یک نود مثلا A شروع کنه و یه هدف بهش داده بشه ... مسیر جواب رو نشون بده

[pedram.11]

پیاده سازی هم باشه باید یه نمونه در نظر داشته باشید چون با الگوریتم bfs چندین نمونه مسئله متفاوت میشه ساخت.
در هر صورت من نمونه رو اینطور در نظر گرفتم:
یک گراف جهت دار با وزن ثابت. سوال: پیدا کردن مسیر از نود A به نود C طبق کد زیر:
class BFS
{
public static List<KeyValuePair<string, string>> src;
public static string answer;
public static string Start;
Queue<string> q = new Queue<string>();
Dictionary<string, string> pathtrue = new Dictionary<string, string>();


Dictionary<string, bool> visited = new Dictionary<string, bool>();
List<string> answers = new List<string>();




public BFS()
{
q.Enqueue(Start);
pathtrue[Start] = null;
visited[Start] = true;
while (q.Count > 0)
{
string p = q.Dequeue();
if (answer == p)
{
answers.Add(answer);
while (pathtrue[p] != null)
answers.Add((p = pathtrue[p]));
return;
}
foreach (var itm in src)
{
if (itm.Key == p && !visited.ContainsKey(itm.Value))
{
q.Enqueue(itm.Value);
pathtrue[itm.Value] = p;
visited[itm.Value] = true;
}
}
}
}
public void pathshow()
{
string p = "";
for (int j = answers.Count - 1; j >= 0; j--)
p += answers[j] + " -> ";
if (p.Length > 0)
p = p.Remove(p.Length - 4);
MessageBox.Show(p);
}
public void answershow()
{
for (int i = answers.Count - 1; i >= 0; i--)
MessageBox.Show(answers[i]);
}
}
private void Form1_Load(object sender, EventArgs e)
{
List<KeyValuePair<string, string>> lst =
new List<KeyValuePair<string, string>>{
new KeyValuePair<string,string>("A","B"),
new KeyValuePair<string,string>("A","D"),
new KeyValuePair<string,string>("B","E"),
new KeyValuePair<string,string>("E","F"),
new KeyValuePair<string,string>("F","K"),
new KeyValuePair<string,string>("K","J"),
new KeyValuePair<string,string>("C","A"),
new KeyValuePair<string,string>("J","I"),
new KeyValuePair<string,string>("G","I"),
new KeyValuePair<string,string>("I","C"),
};
BFS.src = lst;
BFS.Start = "A";
BFS.answer = "C";
BFS test = new BFS();
test.pathshow();
}



طبق کد src داده های گراف هست و pairهای عضو لیست، یال های جهت دار هستن که از Key به Value راه دارن. توی الگوریتم به ازای هر نود، نودهای مجاور اون نود که قبلا پردازش نشده به صف اضافه میشه و والد اون نود(نودی که ازش به نود فعلی رسیدیم یعنی p) به pathtrue اضافه میشه. وقتی به جواب رسیدیم توی pathtrue میگردیم به ترتیب از نود پایانی، نود های والد رو به لیست جواب(answers) اضافه میکنیم :لبخندساده:

[nadianadia]

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