الگوریتمی ارائه کنید که طولانی ترین مسیر بین دو نقطه از گراف را ارائه دهد(بدون ایجاد حلقه)
Printable View
الگوریتمی ارائه کنید که طولانی ترین مسیر بین دو نقطه از گراف را ارائه دهد(بدون ایجاد حلقه)
آیا زیارت دوباره نقطه هایه گراف قابله قبوله یا نه، اگر که نه :
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
بین دو نقطه
میگردم که بتونم یک سایته بدرد بخور پید کنم.
در ضمن در مورد سوال تابع شما هم دارم فکر میکن، سواله ساده ولی جالبیه،
به محضه اینکه چیزی پیدا کردم میفرستم اینجا.
این مسئله جزو مسائل NP-complete پس بهتره از الگوریتم *A با هیوریستیک و greedy کمینه ساز حلش کنی .
بر چه اساسی میگید که این مسئله جزو NP-complete هست؟نقل قول:
نوشته شده توسط k.robot
سلام
اگر بتونید این مقاله رو ترجمه کنید شاید کمکی باشه :
ضمیمه 3194
دوست عزیز شما می تونید از الگوریتم دایکسترا که در زمینه کوتاهترین مسیر بین دو نقطه می باشد استفاده کنید که البته باید کمی تغییرات بدهید که واسه مسأله شما جواب دهد البته الگوریتمهای پیچیده ای نیز در این زمینه می باشد که اگر ملیل باشید به من mail بزنید تا برایتان بفرستم
نمیشه این کار را کرد، بر عکسِ الگریتمه کوتاهترین مسیر، الگریتم طولانیترین مسیر همونطوری که K.Robotگفتند،NP-Complete هست.نقل قول:
نوشته شده توسط mohandese_hiclass
همینطوری نمیشه که یک الگریتم را تغییر داد.
http://en.wikipedia.org/wiki/NP-completeنقل قول:
نوشته شده توسط Mega7000
دوست عزیز من تا حالا تو هیچ مرجعی ندیدم که نوشته باشه مسئله مطرح شده NP-COMPLETE
هست اگه مرجعی دارید خوشحال می شم بخونم باز من کمی مطالعه می کنم شاید راه حلی پیدا کردم
http://www.tcs.hut.fi/Studies/T-79.2...solutions_5.psنقل قول:
نوشته شده توسط mohandese_hiclass
میشه خواهش کنم خودمون راجع بهش فکر کنیم تا اینکه همش دنبال جواب سوال توی منابع دیگه باشیم؟؟
دوست عزیز تو این مقاله صراحتا اعلام نشده طولانی ترین مسیر بین دو نقطه مسئله np-copmlete هست
مگا جان باید برای جواب دادن به یه سوال کمی مطالعه بشه یا نه روی مسائلی میشه بدون مطالعه فکر کرد که مقدماتشو دونست و همچنین مسئله تا حالا حل نشده باشه من یه بار بدون مطالعه این کارو کردم و سه ماه رو یه موضوع وقت گذاشتم بعد دیدم این مسئله ساله 1995 حل شده بود
مگا جان، من دو بار از بالا تا پائین این بحث را نگاه کردم و ندیدم کی داره رو کم کنی میکنه،نقل قول:
نوشته شده توسط Mega7000
من دارم به نکاتی که اساتید اشکال گرفتن بررسی میکنم که ببینم مشکل از کجاست،
والا من تا جایی که میبینم این بحث داره خوب پیش میره و من یکچندا چیزه جدیدی پیدا کردم که وقتی که کاملتر
بفهمم به دنبالهئ این بحث پست میکنم.
در ضمن مسایل مربوط به گراف چیزی نیست که هرکی بتونه پیشنهاد بکنه، این مسایل خیلی آنالایز شدن و همونطوری که اشاره شده بهتره که ما یک نگاهی به چیزهایی که در این زمینه موجوده بیندازیم تا اینکه کور کورانه فکر پیشنهاد کنیم.
حرف شما کاملا منطقی منم نمی گم اشتباه می گید من میگم کمی مطالعه بعد فکرنقل قول:
نوشته شده توسط Mega7000
من معتقدم اگه کمی با الگوریتم دایکسترا یا فلوید ور بریم می تونیم به یه جایی برسیم دوست عزیزمون هم که گفته بودن مسئله np-copmlete هست من هیج جایی ندیدم شما فکر می کنید مسئله واقعا np-complete هست؟؟؟؟؟؟؟؟؟؟
در مورد اینکه این مساله np-complete است ، شک نکنید چون قبلا ثابت شده فقط تنها کاری که میشه کرد بهینه کردن اونه .نقل قول:
حرف شما کاملا منطقی منم نمی گم اشتباه می گید من میگم کمی مطالعه بعد فکر
من معتقدم اگه کمی با الگوریتم دایکسترا یا فلوید ور بریم می تونیم به یه جایی برسیم دوست عزیزمون هم که گفته بودن مسئله np-copmlete هست من هیج جایی ندیدم شما فکر می کنید مسئله واقعا np-complete هست؟؟؟؟؟؟؟؟؟؟
میشه اثباتشو بکید کجاست ما هم بخونیمنقل قول:
نوشته شده توسط Mehrafrooz
اثباتش رو من تو یکی از پایان نامه های کارشناسی ارشد دانشگاه تهران خوندم . تو اینترنت چند تا از این پایان نامه ها به صورت مختصر وجود داره ، ولی اگه می خواید کامل بخونید باید به دانشگاه تهران سر بزنید .
لینکهاش رو می گردم بهتون اطلاع می دم .
برید به سایت مرکز اطلاعات و مدارک علمی ایران :نقل قول:
میشه اثباتشو بکید کجاست ما هم بخونیم
http://database.irandoc.ac.ir
و "صالحی‌فتح‌آبادی، حسن" رو جستجو کنید . بین پایان نامه های که ایشون استاد راهنما بودند ، پیدا می کنید .
البته کامل نیستند .
دوست عزیز من حتما این موضوع رو پی گیری می کنم و حتما اگه به نتیجهای رسیدم حتما همه رو در جریان می گذارم چون تا حالا روی این مسئله کامل فکر نکرده بودم و نمی دونستم مسئله np-complete هست پس بهتره به جای جوابای کوتاه مدتی روش فکر کنیم تا بعد روش کامل بحث کنیم امیدوارم مگا جان هم موافق باشهنقل قول:
نوشته شده توسط Mehrafrooz
می تونیم مبنای الگوریتم رو بر این مبنا بگذاریم که همه گره ها رو چک کنه؟(اما خودم فکر می کنم اصلا بهینه نیست)
دوست عزیز درباره NP-complete بودن این مسئله بیشتر به مورد پیدا کردن بیشترین فاصله بین دو راس گراف به طوری که تعداد یال مشاهده شده از یه مقداری که ورودی مسئله است بیشتر یا مساوی باشه صدق میکنه.به این لینک سری بزن
http://www.csc.liv.ac.uk/~ped/teacha...otated_np.html
k.robot جان منم با شما موافقم اتفاقا امروز داشتم در این مورد مطالبی می خوندمنقل قول:
نوشته شده توسط k.robot
لطفا طراح این سوال دز مورد سوال بیشتر توضیح بده
به لینک زیرم سری بزنید
citeseer.ifi.unizh.ch
مگا جان حرف شما کاملا درسته تمام گرهها باید چک شوند حتی شاید با یک الگوریتم بهینه هم مجبور به این کار بشیم ولی به نظر من اینجا مهمتر از گرها یالها هستن که تعدادشون هم بیشتره من دو سه روزه روش کار می کنم به یه نتایجی هم رسیدم و موفق شدم یه الگوریتم در بیارم که تا حالا واسه 20 -30 تا مثال درست جواب داده سعی می کنم تو ورد تایپ کنم بزارم تو سایت فقط یه ایراد داره اونم زمان اجراشه که n^4 هست که n هم تعداد گرههاست نه تعداد یالهانقل قول:
نوشته شده توسط Mega7000
به نظر شما زمان اجراش قابل قبوله به نظره من بد نیست
یه الگوریتم پیشنهادی
1-مثل الگوریتم دایکسترا می ریم فقط به جای اینکه هر دفعه مینمم را انتخاب کنیم ماکزیمم را انتخاب می کنیم
2-اگر گرهی در آخر باقی ماند که بررسی نشده آن را هم تا آخر بررسی می کنیم سپس در سطر مربوط به هدف ما جستجو می کنیم و بیشترین عدد را انتخاب می کنیم
3-نحوه حلقه ایجاد نشدن را هم از روی حروف چک می کنیم مثلا اگه از a به b مسیری داشته باشیم مثلا 20asd اگه باز d انتخاب شود یا هر گرهی از سه گره ایجاد شده نشان دهنده حلقه هست
4-هزینه الگوریتم هم میشه یکی تشکیل ماتریس مجاورت که n^2 هست +تشکیل آرایه همانند الگوریتم دایکسترا که می شود kn^2 چون در هر مرحله یک جستجو هم تو ماتریس مجاورت داریم کلا میشه kn^2*n^2 که در کل میشه o(n^4)
سعی می کنم دفعه بعد یه مثال کامل هم بزارم تو سایت لطفا معایب الگوریتم و حتما بگید