پیمایش مسیر در یک گراف وزن دار

[i-nostalgic]

چگونه می شود در یک گراف وزن دار از یک گره خاص شروع کرد و با پیمایش حداقل مسیر از تمام گره ها بگذرد و مسیر را ذخیره کند (گره پایانی مشخص نیست)

[مسعود اقدسی فام]

حداقل مسیر یعنی مجموع وزن کم باشه؟ تکرار یال یا گره مهم نیست؟

[i-nostalgic]

تو تعریف مسیر داریم که از هر گره یک بار میگذرد دیگه.فقط راس شروع مشخص است و باید از تمام راس های دیگر بگذرد با کمترین وزن.

[مسعود اقدسی فام]

تو تعریف مسیر داریم که از هر گره یک بار میگذرد دیگه.فقط راس شروع مشخص است و باید از تمام راس های دیگر بگذرد با کمترین وزن.

مسیر هیچ شرط خاصی نداره. ممکنه تکرار هم داشته باشه.

این چیزی که می گید در واقع همون TSP یا فروشنده دوره گرد می شه. فقط اینکه از راس آخر به راس اول بر نمی گردید.

[i-nostalgic]

فروشنده دوره گرد رو نمی دونم چیه.
مخواهیم از یک راس خاص شروع کنیم و از راس های دگر عبور کنیم به طوری که کمترین مسیر را طی کنیم و به راس اول بر نگردیم
به نظرم kruskal ,prim جواب میده با کمی تغییر الگوریتم.

[مسعود اقدسی فام]

فروشنده دوره گرد رو نمی دونم چیه.
مخواهیم از یک راس خاص شروع کنیم و از راس های دگر عبور کنیم به طوری که کمترین مسیر را طی کنیم و به راس اول بر نگردیم
به نظرم kruskal ,prim جواب میده با کمی تغییر الگوریتم.

پریم و کروسکال کوجکترین مجموع یال رو می‌دن، نه کوتاهترین مسیر. تغییراتش اگه خیلی باشه می‌شه همون فروشنده دوره‌گرد. مطالعه کنید بعد نظر بدید که به درد نمی‌خوره و برید سراغ روش‌های دیگه. نه بدون مطالعه.

[i-nostalgic]

پریم و کروسکال کوجکترین مجموع یال رو می‌دن، نه کوتاهترین مسیر. تغییراتش اگه خیلی باشه می‌شه همون فروشنده دوره‌گرد. مطالعه کنید بعد نظر بدید که به درد نمی‌خوره و برید سراغ روش‌های دیگه. نه بدون مطالعه.
من کجا گفتم به درد نمی خوره ؟ :متفکر:
الگوریتمی که نوشتم شبیه کروسکاله نه خودش
پیچیدگی برنامه با دوره گرد میشه n^2*2^n که اگر برد یازی 20 * 20 باشه مشه 400 خانه یعنی 400 گره
در صورتی که با ترکیب چند الگوریتم حداکثر پیچیدگی n^2میشود
حال کدام یکی بهتره؟
تو دوه گرد بر میگرده میاد خونه شرو در صورتی که اینجا خونه پایان مشخص نیست

[مسعود اقدسی فام]

با همون کروسکال و پریم بنویسید. :)

[i-nostalgic]

با همون کروسکال و پریم بنویسید. :)
فکر کنم فارسی صحبت کردم این طور نیست؟
با اونا هم جواب نمیده:D
یه چیزی شبیه اون رو پیاده سازی کردم
چون اگر تعداد راس های گرافت زیاد باشه کلی طول میده
بهتر نیست به جای حفظ یک الگوریتم به کاربرد اون فکر بشه یک مساله هزار راه داره
که با توجه به شرایط مختلف باید یکی انتخاب بشه نه اینکه فقط با فلان روش حل میشه
سعی میکنم تا شنبه تمومش کنم exe شو بزارم

[مسعود اقدسی فام]

من راه حل رو پیشنهاد دادم که چیزی شبیه TSP می‌تونه باشه. شما اصرار کردید چیزی شبیه پریم و کروسکال. من دیگه اصراری نکردم و گفتم هر طور راحتید انجام بدید.
متاسفانه فرصت کافی برای فکر روی حل مساله ندارم. اما اگه قرار می‌شد هر گره آخری که به دست می‌یاد (مهم نیست چه گرهی) به گره اول وصل بشه، تبدیل می‌شد به فروشنده دوره‌گرد. همین.

[i-nostalgic]

آره اگر اونجوری میشد کار ساده تر میشد
ولی تقریبا با کمی گول زدن برنامه مشکل حل شد

[اوبالیت به بو]

چگونه می شود در یک گراف وزن دار از یک گره خاص شروع کرد و با پیمایش حداقل مسیر از تمام گره ها بگذرد و مسیر را ذخیره کند (گره پایانی مشخص نیست)

الگوریتم شما یک الگوریتم Greedy است (حریصانه). حتما می دونید این الگوریتم ها همیشه و همه جا جواب صحیح را نمی دهند و بستگی به شرایط مساله دارد (مثلا در مثال شما بستگی به هزینه مسیر هر یال یا تعداد گره های موجود در گراف و یا ... دارد) پس یعنی نمیشه گفت این راه حل صد در صد است.

الگوریتم S3P دکسترا فکر کنم کارساز باشه. اجازه بدید بقیه الگوریتم ها رو هم مطالعه کنم تا بگم بهتون.


پریم و کروسکال کوجکترین مجموع یال رو می‌دن، نه کوتاهترین مسیر.

دقیقا درسته. اصلا هدف مساله جناب i-nostalgic (http://barnamenevis.org/member.php?260025-i-nostalgic) چیزه دیگه ای هست. پریم و کراسکال یک Minimum spanning tree رو ارائه می دن و این درخت سبب میشه که شما از یک مسیر بیش از یکبار عبور کنید (اگر هدف پیمایش همه گره ها باشد چون مسیر برگشتی به جز همان مسیری که آمدی وجود ندارد). در این مساله استفاده از پریم و کراسکال اشتباه است چون این الگوریتم ها در پیمایش استفاده نمی شوند.


آره اگر اونجوری میشد کار ساده تر میشد
ولی تقریبا با کمی گول زدن برنامه مشکل حل شد

گول زدن!!!!! یعنی چی؟؟؟

[ladymehrnosh]

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

[Coraal]

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