Question

الگوریتم bfs چیست؟لطفا توضیح کامل بدید

+مر30

Comments

فارسی را پاس بدارید (انگلیسی را زاپاس بدارید)
قبلا بچه ها فارسیش رو پرسیدن :د
http://www.7khatcode.com/index.php?qa=3163&qa_1=%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85-%D8%AC%D8%B3%D8%AA%D8%AC%D9%88%DB%8C-%D9%BE%D9%87%D9%86%D8%A7-%D9%86%D8%AE%D8%B3%D8%AA

---

مر29+1= مر28+2 = ........= مر1+29 = مر0+30 = ........ = مر-30+60 = ........ = مر30 = mrc = مرسی
چقدر کلمه مترادف  پیدا میشه تو این دنیا

Answer 1

سلام

ما چند مدل الگوریتم جستجو داریم برای BFS یه مثال میزنم متوجه شی.

فرض کن از تهران بخوای بری مشهد. برای رفتن به مشهد میتونی اول به همه استانای همجوار تهران بری بعد از اونجا راهتو ادامه بدی. تو این الگوریتم میاد فاصله همه محل های همجواری که میتونه به اونا بره رو با هم مقایسه میکنه هرکدوم کمتر بود میره اونجا که امکان داره این مسئله اومو از هدفش دورتر هم بکنه. فرض کن همجوارای تهران فقط قزوین و سمنانن و فرض کن از تهران تا قزوین 80 و از تهران تا سمنان 90 کیلومتره الگوریتم قزوینو واسه حرکت انتخاب میکنه.

Answer 2

ما یک الگوریتم bfs بیشتر نداریم ،

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

اینجا کامل تر توشیح داده شده 

 

Answer 3

یکی از الگوریتم های جست و جو  و پیمایش گراف BFS هستش .

BFS کاربرد های خیلی زیادی داره مثلا

• موتور جست و جوی گوگل رو در نظر بگیرید  برای  index کردن یک سایت از BFS استفاده میکنه تمام لینک های صفحه اول سایت رو پیدا می کنه بعد لینک ها رو یک طبقه میره جلوتر پیمایش می کنه  و همین طور ادامه میده
• یا مثلا شبکه های اجتماعی مثل linkedin قسمت هایی که مربوط به پیشنهاد دادن Friend هستن به همین شکل عمل می کنن( گراف از روابط بین افراد تشکیل میدیم برای پیدا کردن دوستای یک نفر  شروع به پیمایش گراف بصورت لایه به لایه  بوسیله BFS می کنیم )
• یا در  پردازش تصویر برای عملیات هایی مثل erode , skeleton  تا اون جایی که من اطلاع دارم یکی از روش هایی که استفاده میشه BFS هست
• garbage collection هایی که زبون هایی مثل جاوا و سی شارپ دارن هم از گراف استفاده می کنن (تعداد دفعات استفاده از یک متغیر در توابع و متد های مختلف رو داخل graph ذخیره می کنیم و برای چک کردن این که دیگه بهش نیاز نداریم از BFS یا DFS استفاده میشه ) http://cecs.wright.edu/~tkprasad/courses/ceg860/L9GC.ppt
• حل کردن پازل ها و سوال های معمایی ! مثلا یکی از سوالایی که من خیلی خوشم امد ازش  http://stackoverflow.com/questions/22342854/what-is-the-optimal-algorithm-for-the-game-2048  , http://ov3y.github.io/2048-AI/اگر سورس کدشو پاسخ اولشو ببینین از bfs وdfs هم داخلش استفاده شده
• داخل expert system ها که نیاز به رسیدن به goal از روی گراف داریم هم بعضی وقت ها از BFS استفاده میشه
• برای چک کردن همبند بودن گراف - پیدا کردن کوتاه ترین مسیر داخل گراف و ... که داخل برنامه هایی مثل google maps استفاده شدن هم  از BFS استفاده میشه
• و خیلی از مسایل دیگه که میشه با در نظر گرفتن به شکل گراف حلشون کرد .....

داخل  این 2تا سوال هم الگوریتم BFS گذاشته شده

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

الگوریتم جست وجوی پهنا نخست