چگونه می شود در یک گراف وزن دار از یک گره خاص شروع کرد و با پیمایش حداقل مسیر از تمام گره ها بگذرد و مسیر را ذخیره کند (گره پایانی مشخص نیست)
چگونه می شود در یک گراف وزن دار از یک گره خاص شروع کرد و با پیمایش حداقل مسیر از تمام گره ها بگذرد و مسیر را ذخیره کند (گره پایانی مشخص نیست)
حداقل مسیر یعنی مجموع وزن کم باشه؟ تکرار یال یا گره مهم نیست؟
تو تعریف مسیر داریم که از هر گره یک بار میگذرد دیگه.فقط راس شروع مشخص است و باید از تمام راس های دیگر بگذرد با کمترین وزن.
فروشنده دوره گرد رو نمی دونم چیه.
مخواهیم از یک راس خاص شروع کنیم و از راس های دگر عبور کنیم به طوری که کمترین مسیر را طی کنیم و به راس اول بر نگردیم
به نظرم kruskal ,prim جواب میده با کمی تغییر الگوریتم.
من کجا گفتم به درد نمی خوره ؟
الگوریتمی که نوشتم شبیه کروسکاله نه خودش
پیچیدگی برنامه با دوره گرد میشه n^2*2^n که اگر برد یازی 20 * 20 باشه مشه 400 خانه یعنی 400 گره
در صورتی که با ترکیب چند الگوریتم حداکثر پیچیدگی n^2میشود
حال کدام یکی بهتره؟
تو دوه گرد بر میگرده میاد خونه شرو در صورتی که اینجا خونه پایان مشخص نیست
آخرین ویرایش به وسیله i-nostalgic : چهارشنبه 03 آبان 1391 در 09:25 صبح
با همون کروسکال و پریم بنویسید. :)
فکر کنم فارسی صحبت کردم این طور نیست؟
با اونا هم جواب نمیده:D
یه چیزی شبیه اون رو پیاده سازی کردم
چون اگر تعداد راس های گرافت زیاد باشه کلی طول میده
بهتر نیست به جای حفظ یک الگوریتم به کاربرد اون فکر بشه یک مساله هزار راه داره
که با توجه به شرایط مختلف باید یکی انتخاب بشه نه اینکه فقط با فلان روش حل میشه
سعی میکنم تا شنبه تمومش کنم exe شو بزارم
آخرین ویرایش به وسیله i-nostalgic : پنج شنبه 04 آبان 1391 در 10:25 صبح
من راه حل رو پیشنهاد دادم که چیزی شبیه TSP میتونه باشه. شما اصرار کردید چیزی شبیه پریم و کروسکال. من دیگه اصراری نکردم و گفتم هر طور راحتید انجام بدید.
متاسفانه فرصت کافی برای فکر روی حل مساله ندارم. اما اگه قرار میشد هر گره آخری که به دست مییاد (مهم نیست چه گرهی) به گره اول وصل بشه، تبدیل میشد به فروشنده دورهگرد. همین.
آره اگر اونجوری میشد کار ساده تر میشد
ولی تقریبا با کمی گول زدن برنامه مشکل حل شد
الگوریتم شما یک الگوریتم Greedy است (حریصانه). حتما می دونید این الگوریتم ها همیشه و همه جا جواب صحیح را نمی دهند و بستگی به شرایط مساله دارد (مثلا در مثال شما بستگی به هزینه مسیر هر یال یا تعداد گره های موجود در گراف و یا ... دارد) پس یعنی نمیشه گفت این راه حل صد در صد است.
الگوریتم S3P دکسترا فکر کنم کارساز باشه. اجازه بدید بقیه الگوریتم ها رو هم مطالعه کنم تا بگم بهتون.
دقیقا درسته. اصلا هدف مساله جناب i-nostalgic چیزه دیگه ای هست. پریم و کراسکال یک Minimum spanning tree رو ارائه می دن و این درخت سبب میشه که شما از یک مسیر بیش از یکبار عبور کنید (اگر هدف پیمایش همه گره ها باشد چون مسیر برگشتی به جز همان مسیری که آمدی وجود ندارد). در این مساله استفاده از پریم و کراسکال اشتباه است چون این الگوریتم ها در پیمایش استفاده نمی شوند.
گول زدن!!!!! یعنی چی؟؟؟
سلام
چه شکلی در یک گراف وزن دار تمام مسیرهای ممکن بین دو نقطه چاپ بشه و بعدم طولانی ترین و سنگین ترینش رو پیدا کنه چاپ شه ؟؟؟
خوهشا سریع جواب بدین ...
سلام.
توی الگوریتم کراسکال، اوجا که چک میکنه اگه یال جدید اضافه کنیم دور ایجاد میکنه یا نه..
به این صورت چک میکنه که اگه دو راس یالی که اضافه میشه، عضو یک درخت باشن، پس دور درست میشه.
اما من دلیل اینکه اگه عضو یک درخت باشن، دور ایجاد میشه رو متوجه نمیشم.
میشه توضیح بدین لطفن..مرسی