طولانی ترین مسیر بین دو نقطه

[Mega7000]

الگوریتمی ارائه کنید که طولانی ترین مسیر بین دو نقطه از گراف را ارائه دهد(بدون ایجاد حلقه)

[اَرژنگ]

آیا زیارت دوباره نقطه هایه گراف قابله قبوله یا نه، اگر که نه :
The worst case length of a tour for the traveling salesman

http://epubs.siam.org/fulltext/SIDMA...e-10/27824.pdf

[Mega7000]

خب قطعا معلومه که نه!!!
نباید تکراری باشه یا تولید حلقه کنه

[اَرژنگ]

خب من خودم جواب رو نمی دونم،واسه همین اینجا مطرح کردم تا افرادی مثل شما کمکم کنن

دوست عزیز.
ما میدونیم که شما دنبال جواب میگردید، ولی برایه ما سوال هنوز مشخص نیست،
بر طبقه اطلاعاتی که پیدا کردم، به برگترین فاصله بین دو نقطه بر رویه گراف میگن،
قطر گراف (diameter of a graph).
ولی اگر منظور از حلقه، یک مدار بسته در گراف باشه، در آن حالت بله، از یک نقطه
دوبار نمیتونه رد بشه (و شرایط کامل داده شده). و جواب بدترین حالته فروشنده دوره گرده که مسیرش
از نقطه اولی شروع میشه و در نقطه دومی پایان میاهبد.
اگر از یک نقطه چند بار رد شدن قابل قبول هست اصلاً سوال یک چیزی دیگه میشه.
اگر منظور از حلقه اینه که از مسیرها دوباره رد نشه، باز این میشه یک سوال دیگر،
قصد من از پرسیدن این همه سوال این بود که بدونیم بر رویه کدام سوال داریم کار میکنیم.
اگر تمام اطلاعاتی که در اختیار شما قرار دادن همینهایه که گفتید، اعتراض کنید که سوال مبهمه
و برایه یک جواب معنی دار اطلاعات بیشتری باید دار اختیارتان بزارند.

[Mega7000]

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

[اَرژنگ]

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

در این صورت جواب سوال میشه:
The worst case length of a tour for the traveling salesman
بین دو نقطه
میگردم که بتونم یک سایته بدرد بخور پید کنم.
در ضمن در مورد سوال تابع شما هم دارم فکر میکن، سواله ساده ولی جالبیه،
به محضه اینکه چیزی پیدا کردم میفرستم اینجا.

[k.robot]

این مسئله جزو مسائل NP-complete پس بهتره از الگوریتم *A با هیوریستیک و greedy کمینه ساز حلش کنی .

[اَرژنگ]

این مسئله جزو مسائل NP-complete پس بهتره از الگوریتم *A با هیوریستیک و greedy کمینه ساز حلش کنی .

بر چه اساسی میگید که این مسئله جزو NP-complete هست؟

[Mehrafrooz]

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

Epp-SJC-98.rar

[mohandese_hiclass]

دوست عزیز شما می تونید از الگوریتم دایکسترا که در زمینه کوتاهترین مسیر بین دو نقطه می باشد استفاده کنید که البته باید کمی تغییرات بدهید که واسه مسأله شما جواب دهد البته الگوریتمهای پیچیده ای نیز در این زمینه می باشد که اگر ملیل باشید به من mail بزنید تا برایتان بفرستم

[اَرژنگ]

دوست عزیز شما می تونید از الگوریتم دایکسترا که در زمینه کوتاهترین مسیر بین دو نقطه می باشد استفاده کنید که البته باید کمی تغییرات بدهید که واسه مسأله شما جواب دهد البته الگوریتمهای پیچیده ای نیز در این زمینه می باشد که اگر ملیل باشید به من mail بزنید تا برایتان بفرستم

نمیشه این کار را کرد، بر عکسِ الگریتمه کوتاهترین مسیر، الگریتم طولانیترین مسیر همونطوری که K.Robotگفتند،NP-Complete هست.
همینطوری نمیشه که یک الگریتم را تغییر داد.

[اَرژنگ]

سلام k.robot
بابا زیر دیپلم حرف بزنید،ما هم بفهمیم

http://en.wikipedia.org/wiki/NP-complete

[mohandese_hiclass]

دوست عزیز من تا حالا تو هیچ مرجعی ندیدم که نوشته باشه مسئله مطرح شده NP-COMPLETE
هست اگه مرجعی دارید خوشحال می شم بخونم باز من کمی مطالعه می کنم شاید راه حلی پیدا کردم

[اَرژنگ]

دوست عزیز من تا حالا تو هیچ مرجعی ندیدم که نوشته باشه مسئله مطرح شده NP-COMPLETE
هست اگه مرجعی دارید خوشحال می شم بخونم باز من کمی مطالعه می کنم شاید راه حلی پیدا کردم

http://www.tcs.hut.fi/Studies/T-79.2...solutions_5.ps

[Mega7000]

میشه خواهش کنم خودمون راجع بهش فکر کنیم تا اینکه همش دنبال جواب سوال توی منابع دیگه باشیم؟؟

[mohandese_hiclass]

دوست عزیز تو این مقاله صراحتا اعلام نشده طولانی ترین مسیر بین دو نقطه مسئله np-copmlete هست

[mohandese_hiclass]

مگا جان باید برای جواب دادن به یه سوال کمی مطالعه بشه یا نه روی مسائلی میشه بدون مطالعه فکر کرد که مقدماتشو دونست و همچنین مسئله تا حالا حل نشده باشه من یه بار بدون مطالعه این کارو کردم و سه ماه رو یه موضوع وقت گذاشتم بعد دیدم این مسئله ساله 1995 حل شده بود

[اَرژنگ]

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

مگا جان، من دو بار از بالا تا پائین این بحث را نگاه کردم و ندیدم کی داره رو کم کنی میکنه،
من دارم به نکاتی که اساتید اشکال گرفتن بررسی میکنم که ببینم مشکل از کجاست،
والا من تا جایی که میبینم این بحث داره خوب پیش میره و من یکچندا چیزه جدیدی پیدا کردم که وقتی که کاملتر
بفهمم به دنبالهئ این بحث پست میکنم.
در ضمن مسایل مربوط به گراف چیزی نیست که هرکی بتونه پیشنهاد بکنه، این مسایل خیلی آنالایز شدن و همونطوری که اشاره شده بهتره که ما یک نگاهی به چیزهایی که در این زمینه موجوده بیندازیم تا اینکه کور کورانه فکر پیشنهاد کنیم.

[mohandese_hiclass]

دوست خوبم
مطمئنن اون مسئله ای که آدم خودش حل می کنه،خیلی چیزهای دیگه هم به موازاتش یاد می گیره.
اگه ایده ای دارین پیشنهاد بدین تا خودمون حلش کنیم

حرف شما کاملا منطقی منم نمی گم اشتباه می گید من میگم کمی مطالعه بعد فکر
من معتقدم اگه کمی با الگوریتم دایکسترا یا فلوید ور بریم می تونیم به یه جایی برسیم دوست عزیزمون هم که گفته بودن مسئله np-copmlete هست من هیج جایی ندیدم شما فکر می کنید مسئله واقعا np-complete هست؟؟؟؟؟؟؟؟؟؟

[Mehrafrooz]

حرف شما کاملا منطقی منم نمی گم اشتباه می گید من میگم کمی مطالعه بعد فکر
من معتقدم اگه کمی با الگوریتم دایکسترا یا فلوید ور بریم می تونیم به یه جایی برسیم دوست عزیزمون هم که گفته بودن مسئله np-copmlete هست من هیج جایی ندیدم شما فکر می کنید مسئله واقعا np-complete هست؟؟؟؟؟؟؟؟؟؟

در مورد اینکه این مساله np-complete است ، شک نکنید چون قبلا ثابت شده فقط تنها کاری که میشه کرد بهینه کردن اونه .

[mohandese_hiclass]

در مورد اینکه این مساله np-complete است ، شک نکنید چون قبلا ثابت شده فقط تنها کاری که میشه کرد بهینه کردن اونه .

میشه اثباتشو بکید کجاست ما هم بخونیم

[Mehrafrooz]

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

[Mehrafrooz]

میشه اثباتشو بکید کجاست ما هم بخونیم

برید به سایت مرکز اطلاعات و مدارک علمی ایران :
http://database.irandoc.ac.ir
و "صالحی‌فتح‌آبادی، حسن" رو جستجو کنید . بین پایان نامه های که ایشون استاد راهنما بودند ، پیدا می کنید .
البته کامل نیستند .

[mohandese_hiclass]

برید به سایت مرکز اطلاعات و مدارک علمی ایران :
http://database.irandoc.ac.ir
و "صالحی‌فتح‌آبادی، حسن" رو جستجو کنید . بین پایان نامه های که ایشون استاد راهنما بودند ، پیدا می کنید .
البته کامل نیستند .

دوست عزیز من حتما این موضوع رو پی گیری می کنم و حتما اگه به نتیجهای رسیدم حتما همه رو در جریان می گذارم چون تا حالا روی این مسئله کامل فکر نکرده بودم و نمی دونستم مسئله np-complete هست پس بهتره به جای جوابای کوتاه مدتی روش فکر کنیم تا بعد روش کامل بحث کنیم امیدوارم مگا جان هم موافق باشه

[Mega7000]

می تونیم مبنای الگوریتم رو بر این مبنا بگذاریم که همه گره ها رو چک کنه؟(اما خودم فکر می کنم اصلا بهینه نیست)

[k.robot]

دوست عزیز درباره NP-complete بودن این مسئله بیشتر به مورد پیدا کردن بیشترین فاصله بین دو راس گراف به طوری که تعداد یال مشاهده شده از یه مقداری که ورودی مسئله است بیشتر یا مساوی باشه صدق میکنه.به این لینک سری بزن
http://www.csc.liv.ac.uk/~ped/teacha...otated_np.html

[mohandese_hiclass]

دوست عزیز درباره NP-complete بودن این مسئله بیشتر به مورد پیدا کردن بیشترین فاصله بین دو راس گراف به طوری که تعداد یال مشاهده شده از یه مقداری که ورودی مسئله است بیشتر یا مساوی باشه صدق میکنه.به این لینک سری بزن
http://www.csc.liv.ac.uk/~ped/teacha...otated_np.html

k.robot جان منم با شما موافقم اتفاقا امروز داشتم در این مورد مطالبی می خوندم
لطفا طراح این سوال دز مورد سوال بیشتر توضیح بده
به لینک زیرم سری بزنید
citeseer.ifi.unizh.ch

[mohandese_hiclass]

می تونیم مبنای الگوریتم رو بر این مبنا بگذاریم که همه گره ها رو چک کنه؟(اما خودم فکر می کنم اصلا بهینه نیست)

مگا جان حرف شما کاملا درسته تمام گرهها باید چک شوند حتی شاید با یک الگوریتم بهینه هم مجبور به این کار بشیم ولی به نظر من اینجا مهمتر از گرها یالها هستن که تعدادشون هم بیشتره من دو سه روزه روش کار می کنم به یه نتایجی هم رسیدم و موفق شدم یه الگوریتم در بیارم که تا حالا واسه 20 -30 تا مثال درست جواب داده سعی می کنم تو ورد تایپ کنم بزارم تو سایت فقط یه ایراد داره اونم زمان اجراشه که n^4 هست که n هم تعداد گرههاست نه تعداد یالها
به نظر شما زمان اجراش قابل قبوله به نظره من بد نیست

[mohandese_hiclass]

یه الگوریتم پیشنهادی
1-مثل الگوریتم دایکسترا می ریم فقط به جای اینکه هر دفعه مینمم را انتخاب کنیم ماکزیمم را انتخاب می کنیم
2-اگر گرهی در آخر باقی ماند که بررسی نشده آن را هم تا آخر بررسی می کنیم سپس در سطر مربوط به هدف ما جستجو می کنیم و بیشترین عدد را انتخاب می کنیم
3-نحوه حلقه ایجاد نشدن را هم از روی حروف چک می کنیم مثلا اگه از a به b مسیری داشته باشیم مثلا 20asd اگه باز d انتخاب شود یا هر گرهی از سه گره ایجاد شده نشان دهنده حلقه هست
4-هزینه الگوریتم هم میشه یکی تشکیل ماتریس مجاورت که n^2 هست +تشکیل آرایه همانند الگوریتم دایکسترا که می شود kn^2 چون در هر مرحله یک جستجو هم تو ماتریس مجاورت داریم کلا میشه kn^2*n^2 که در کل میشه o(n^4)
سعی می کنم دفعه بعد یه مثال کامل هم بزارم تو سایت لطفا معایب الگوریتم و حتما بگید