الگوریتم پیدا کردن مسیر

[armita]

فرض کنید یک جدول دارین و بعضی از خونه های اون صفرن و بعضی ها یک.
شما فقط اجازه ی حرکت روی خونه های یک رو دارین.
خونه های یک ،یک مسیر رو ایجاد می کنن.
مسیر از یک خونه به عنوان شروع ، شروع میشه و تا خونه ی پایان ادامه پیدا می کنه.
ممکنه که مسیر بعضی جاها خودش رو قطع کنه و مثلا یک مسیر مربعی در مسیر اصلی به وجود بیاد.
به نظر شما بهترین روش برای این که سریعا به خونه ی پایان برسیم چیه ؟ توجه داشته باشین که مجبور نیستیم از همه ی خونه های یک رد بشیم.

 

[trustme]

پاسخ : الگوریتم پیدا کردن مسیر

بنده پیشنهاد استفاده از ساختار مورچه ها رو می دم
انتخاب ها در هر جا رو به عنوان یه بردار در نظر بگیریم تا بدونیم به جای اول برگشتیم یا نه!

 

[fzgm]

پاسخ : الگوریتم پیدا کردن مسیر

بنده پیشنهاد استفاده از ساختار مورچه ها رو می دم

راه حل بسیار بدیعی است!!

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

 

[Sylar]

پاسخ : الگوریتم پیدا کردن مسیر

کلنی مورچه ها؟ خیلی آسون تر از اون تئوری میشه حلش کرد.
دوستان یک مبحث هست به اسم نظریه گراف بهترین کتاب براش Introduction to graph theory نوشته D.B.West اه.
نسخه فارسیش هم هست نظریه گراف که البته به مفت نمیارزه. اگر میتونی انگلیسی بخونی اصلش را بخون.

توی اون در بخش Tree یک سری الگوریتم گفته. یکیش BFS اه. این با BFS حل میشه.
اگر میخوایید دقیق بدونید بگید با ساختارش براتون توضیح بدم چیه.

 

[trustme]

پاسخ : الگوریتم پیدا کردن مسیر

توضیح بده BFS رو

 

[Sylar]

پاسخ : الگوریتم پیدا کردن مسیر

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

فرض کن یک جایی وایسادی که هزارتا کوچه جلوته.
شما دنبال یک خونه میگردی. میدونی که این خونه ای که دنبالشی مثلا ماکسیموم فاصله اش از شما ۴ تا خونه است.(یعنی جزء چهار خونه ی اول هر کوچس)
حالا چطوری میخوایی دنبال خونه ی مورد نظرت بگردی؟
یک کاری که آدم به ذهنش میرسه اینه که اول بیایی اولین خونه ی هر کوچه را چک کنی. اگر پیداش نکردی بعد بری دومین خونه ی
هر کوچه را تست کنی و به همین ترتیب ادامه بدی تا پیداش کنی.
به این روش جستجو میگن Breadth First Search یا BFS.

ما میاییم این مسئله را با یک سری نقطه و خط نظیر میکنیم وروی اونا بحث میکنیم(بش میگن گراف)

اعداد روی شکل بیان کننده ترتیب چک کردن ماست. یعنی ما اول ۱ را چک میکنیم اگر نبود ۲ بعد ۳ بعد ۴ ...
همونطور که میبینید شکل ما طبقه طبقه میشه.
طبقه دوم فاصله شون از نقطه ی ابتدا ۱ اه. طبقه ۳ فاصله شون از نقطه ی ابتدا ۲ ست و ...
یک خورده با این مفهوم سعی کنید مسئله را حلش کنید تا متوجه نکاتش بشید.
من ادامه اش را بعدا براتون توضیح میدم.

 

[ariaie]

پاسخ : الگوریتم پیدا کردن مسیر

سلام

خوب یکیم دیر دارم جواب میدم ولی امیدوارم بدرد بخوره!
BFS خوبه ولی راحتتر هم میشه حلش کرد اگه روی هر خونه که هستی خونه های مجورش که 1 هستنو نگاه میکنی اولویت حرکت هم با حرکت به سمت بایین یا سمت راست باشه !البته بستگی به مسیر داره ولی ÷یش میاد که از BFS بهتر جواب بده بد یه STACK یا آرایه نگه میداری که مسیرت توشه که هر وقت به بنبست خوردی بتونی برگردی!

موفق باشید.

 

[ariaie]

پاسخ : الگوریتم پیدا کردن مسیر

راستی این مساله بیدا کردن مسیر نیست ولی با بیدا کردن مسیر میشه حلش کرد!
بیشتر به این ماز (MAZE )میگن! اگه کسی دوس داره میتونه کتاب CLRS- introduction to algorithms چاپ MIT مراجعه کنه !

 

[سروش ربیعی]

پاسخ : الگوریتم پیدا کردن مسیر

بردار و سو و این جور چیزا نمی‌خواد. اگه منظورتون از کلنی مورچه‌ها اونی باشه که من فکر می‌کنم، باید بگم برای این مسأله خیلی قلمبه‌ست! تئوری کلنی مورچه‌ها برای پردازش داده‌های فازی و آنالیز مجموعه‌های آماری بزرگ به کار میره.

ما ترم قبل پروژه‌مون پیاده‌سازی بازی سوکوبان با بهترین راه حل بود. دقیقاً همین الگوریتم مورد نظر شما رو براش نوشتم. البته صورت سؤال شما یه ایراد داره: اگه یه مسیر خودشو قطع کنه مسلماً کوتاه‌ترین نیست. ولی شما گفتین که دنبال سریع‌ترین راه برای رسیدن به مقصد هستین. (منظورتون از سرعت، کوتاه‌ترین مسیر بود یا سریع‌ترین پردازش؟)

تجربه نشون داده که در این مورد خاص الگوریتم DFS بهتر از BFS جواب می‌ده. (البته اثبات آنالیزی هم داره ولی براساس روش‌های آماریه. یعنی فقط برای مسیرهایی که زیاد «خلوت» نباشن.)

بهترین الگوریتم ترکیبی‌ای که ما براش تونستیم بنویسیم از دو تا DFS و یک حدس آماری استفاده می‌کنه.

اگر مایل باشید می‌تونم فایل‌های الگوریتم پروژه (++C) و فلوچارت‌هاش رو براتون ارسال کنم.

 

[narenjak]

پاسخ : الگوریتم پیدا کردن مسیر

بستگی به شرایط داره
یه جا حافظه زیاده bfs توصیه میشه
یه جا زمان زیاده dfs توصیه میشه
یه جا نه می خواهیم یه چیز خوبی باشه A* توصیه میشه
مسئله رو باید ریز تر کنی

 

[BLACK HOLE]

پاسخ : الگوریتم پیدا کردن مسیر

بردار و سو و این جور چیزا نمی‌خواد. اگه منظورتون از کلنی مورچه‌ها اونی باشه که من فکر می‌کنم، باید بگم برای این مسأله خیلی قلمبه‌ست! تئوری کلنی مورچه‌ها برای پردازش داده‌های فازی و آنالیز مجموعه‌های آماری بزرگ به کار میره.

ما ترم قبل پروژه‌مون پیاده‌سازی بازی سوکوبان با بهترین راه حل بود. دقیقاً همین الگوریتم مورد نظر شما رو براش نوشتم. البته صورت سؤال شما یه ایراد داره: اگه یه مسیر خودشو قطع کنه مسلماً کوتاه‌ترین نیست. ولی شما گفتین که دنبال سریع‌ترین راه برای رسیدن به مقصد هستین. (منظورتون از سرعت، کوتاه‌ترین مسیر بود یا سریع‌ترین پردازش؟)

تجربه نشون داده که در این مورد خاص الگوریتم DFS بهتر از BFS جواب می‌ده. (البته اثبات آنالیزی هم داره ولی براساس روش‌های آماریه. یعنی فقط برای مسیرهایی که زیاد «خلوت» نباشن.)

بهترین الگوریتم ترکیبی‌ای که ما براش تونستیم بنویسیم از دو تا DFS و یک حدس آماری استفاده می‌کنه.

اگر مایل باشید می‌تونم فایل‌های الگوریتم پروژه (++C) و فلوچارت‌هاش رو براتون ارسال کنم.

میشه dfs رو توضیح بدید لطفا؟فرقش با bfs چیه؟

 

[princess]

پاسخ : الگوریتم پیدا کردن مسیر

dfs یعنی depth first search یعنی این که ما تو گراف یه جوری می ریم که به ته خط برسیم بعد بر می گردیم و راه های دیگه رو می ریم. ( یعنی اول عمق گراف رو پیمایش می کنیم. ) اما bfs یعنی breadth first search و ما تو هر مرحله همه ی جاهایی رو که می تونیم بریم در نظر می گیریم و هر کدوم رو یه دونه می ریم جلو تر ( به سمت عمق ). مثل این که ما یه لشکر آدم هستیم که صرفا می خواهیم کل گراف رو تو کمترین زمان ممکن تصرف کنیم!

 

[hashemt4]

پاسخ : الگوریتم پیدا کردن مسیر

دوستان کسی هست که سورس سی پلاس پلاس این بازی بوسیله اگوریتم های bfs , dfs , A Star رو داشته باشه؟؟؟

 

[sjazayeri]

پاسخ : الگوریتم پیدا کردن مسیر

A* رو این مساله نمیشه چون در مورد خونه ها اطلاعات اضافه نداریم.
میشه فاصله هر خونه از خونه انتهایی رو در نظر گرفت ولی خب, خوب نیست.
کار جالبی که میشه کرد اینه که از دو طرف BFS بزنیم, اینجوری تعداد راس هایی که روی لبه جستجو قرار دارن کمترن و با یه ضریب ثابت الگوریتم سریع تره.

 

[maziar]

پاسخ : الگوریتم پیدا کردن مسیر

خب خيلي راه داره ولي ايده ي من يه راهه قديمي هست اين مساله رو اولين بار وقتي حل كردم كه داشتم يك ساله پيش برايه يك روبات مسيرياب كد ميزدم
ببينيد شما كي تونيد زمين رو يك و صفر در نظر بگيريد
بعد اگر ما بدونيم كه از هر نقطه چطور ميشه به مقصد رسيد پس كوتاه ترين راه رو داريم
پس ايده ي اوليه و غيره گرافي يه الگوريتم بگشتي كنده
ايده ي دوم اينه اگه يه مستطيل با همون ابعاد در نظر بگيري و فاصله ي هر نقطه از مقصد رو توش بنويسي حاله مينمم فاصله ي هر نقطه رو مي دوني و مي توني مسير اپتيمال رو پيدا كني