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

  • شروع کننده موضوع
  • #1

armita

کاربر خاک‌انجمن‌خورده
ارسال‌ها
2,204
امتیاز
686
نام مرکز سمپاد
دبیرستان فرزانگان ۱
شهر
تهران
دانشگاه
شریف
رشته دانشگاه
‫علوم کامپیوتر‬‎
فرض کنید یک جدول دارین و بعضی از خونه های اون صفرن و بعضی ها یک.
شما فقط اجازه ی حرکت روی خونه های یک رو دارین.
خونه های یک ،یک مسیر رو ایجاد می کنن.
مسیر از یک خونه به عنوان شروع ، شروع میشه و تا خونه ی پایان ادامه پیدا می کنه.
ممکنه که مسیر بعضی جاها خودش رو قطع کنه و مثلا یک مسیر مربعی در مسیر اصلی به وجود بیاد.
به نظر شما بهترین روش برای این که سریعا به خونه ی پایان برسیم چیه ؟ توجه داشته باشین که مجبور نیستیم از همه ی خونه های یک رد بشیم.
 

trustme

لنگر انداخته
ارسال‌ها
2,810
امتیاز
900
نام مرکز سمپاد
شهید بهشتی
شهر
کاشان
سال فارغ التحصیلی
1387
دانشگاه
دانشگاه خواجه نصیر طوسی
رشته دانشگاه
مهندسی مکانیک
پاسخ : الگوریتم پیدا کردن مسیر

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

fzgm

کاربر فوق‌حرفه‌ای
ارسال‌ها
782
امتیاز
82
نام مرکز سمپاد
فرزانگان 1 تهران
شهر
تهران
مدال المپیاد
ریاضی،کامپیوتر(کوتاه)،ادبیات،شیمی(تنوع؟!)
دانشگاه
دانشگاه تهران
رشته دانشگاه
علوم مهندسی
پاسخ : الگوریتم پیدا کردن مسیر

به نقل از مـ‌‍‌‌همّد بذرکار :
بنده پیشنهاد استفاده از ساختار مورچه ها رو می دم :D
راه حل بسیار بدیعی است!:D!

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

Sylar

کاربر حرفه‌ای
ارسال‌ها
454
امتیاز
60
نام مرکز سمپاد
شهید اژه ای
شهر
اصفهان
پاسخ : الگوریتم پیدا کردن مسیر

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

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

trustme

لنگر انداخته
ارسال‌ها
2,810
امتیاز
900
نام مرکز سمپاد
شهید بهشتی
شهر
کاشان
سال فارغ التحصیلی
1387
دانشگاه
دانشگاه خواجه نصیر طوسی
رشته دانشگاه
مهندسی مکانیک
پاسخ : الگوریتم پیدا کردن مسیر

توضیح بده BFS رو :D
 

Sylar

کاربر حرفه‌ای
ارسال‌ها
454
امتیاز
60
نام مرکز سمپاد
شهید اژه ای
شهر
اصفهان
پاسخ : الگوریتم پیدا کردن مسیر

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

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

ما میاییم این مسئله را با یک سری نقطه و خط نظیر میکنیم وروی اونا بحث میکنیم(بش میگن گراف)
390px-Breadth-first-tree.svg.png


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

ariaie

کاربر نیمه‌فعال
ارسال‌ها
15
امتیاز
0
نام مرکز سمپاد
شيخ انصاري دزفول
شهر
دزفول
مدال المپیاد
المپیادکامپیوتر شرکت کردم یه بار ولی خو چیزی درباره سوالاش نمیدونسم کمیم برا المپیاد فیزیک خوندم
دانشگاه
شهید جمران اهواز
رشته دانشگاه
مهندسی کامپیوتر-نرم افزار
پاسخ : الگوریتم پیدا کردن مسیر

سلام

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

موفق باشید.
 

ariaie

کاربر نیمه‌فعال
ارسال‌ها
15
امتیاز
0
نام مرکز سمپاد
شيخ انصاري دزفول
شهر
دزفول
مدال المپیاد
المپیادکامپیوتر شرکت کردم یه بار ولی خو چیزی درباره سوالاش نمیدونسم کمیم برا المپیاد فیزیک خوندم
دانشگاه
شهید جمران اهواز
رشته دانشگاه
مهندسی کامپیوتر-نرم افزار
پاسخ : الگوریتم پیدا کردن مسیر

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

سروش ربیعی

کاربر نیمه‌فعال
ارسال‌ها
19
امتیاز
3
نام مرکز سمپاد
اورمیه
شهر
اورمیه
دانشگاه
اورمیه
رشته دانشگاه
مهندسی کامپیوتر / نرم‌افزار
پاسخ : الگوریتم پیدا کردن مسیر

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

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

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

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

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

narenjak

کاربر فوق‌حرفه‌ای
ارسال‌ها
863
امتیاز
836
نام مرکز سمپاد
علامه حلی
پاسخ : الگوریتم پیدا کردن مسیر

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

BLACK HOLE

کاربر فوق‌حرفه‌ای
ارسال‌ها
826
امتیاز
2,199
نام مرکز سمپاد
فرزانگان امين
شهر
اصفهان
سال فارغ التحصیلی
1392
مدال المپیاد
نجوم
دانشگاه
University of Alberta
رشته دانشگاه
Computer Science
پاسخ : الگوریتم پیدا کردن مسیر

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

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

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

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

اگر مایل باشید می‌تونم فایل‌های الگوریتم پروژه (++C) و فلوچارت‌هاش رو براتون ارسال کنم.
میشه dfs رو توضیح بدید لطفا؟فرقش با bfs چیه؟ :D
 

princess

کاربر نیمه‌فعال
ارسال‌ها
11
امتیاز
7
نام مرکز سمپاد
فرزانگان تهران
شهر
تهران
مدال المپیاد
کامپیوتر ریاضی
دانشگاه
امیرکبیر
رشته دانشگاه
علوم کامپیوتر
پاسخ : الگوریتم پیدا کردن مسیر

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

hashemt4

کاربر جدید
ارسال‌ها
1
امتیاز
0
نام مرکز سمپاد
دانشگاه جهرم
شهر
شیراز
پاسخ : الگوریتم پیدا کردن مسیر

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

sjazayeri

کاربر حرفه‌ای
ارسال‌ها
472
امتیاز
590
نام مرکز سمپاد
شهید دستغیب ۱
شهر
شیراز
مدال المپیاد
برنز کامپیوتر
پاسخ : الگوریتم پیدا کردن مسیر

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

maziar

مازیمون
ارسال‌ها
1,962
امتیاز
6,833
نام مرکز سمپاد
علامه حلی
شهر
تهران، استانبول، کوالالامپور، اُسلو!
دانشگاه
Universitetet i Oslo
رشته دانشگاه
ریاضی، CS، نانو الکترونیک
پاسخ : الگوریتم پیدا کردن مسیر

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