سوال در مورد پیدا کردن کوتاه ترین دور و توضیح الگوریتمی(ضمیمه شده)

[miladna]

سلام دوستان
خسته نباشید
یه سوال در مورد پیدا کردن کوتاه ترین دور همیلتونی داشتم.
می خواستم بدونم چه طوری میشه یه دور همیلتونی رو پیدا کرد؟
منظورم اینه که پس از دریافت باید چه طوری تمام حالات ممکن رو بررسی کنم؟یعنی مثلا:
می خوام وقتی ماتریس درجات یک گراف رو دریافت می کنه :
ABCD
A0111
B1011
C1101
D1110
پس از این که مثلا به AB رسید به سطر B بیاد و تمام حالات رو در B بررسی کنه و پس از برررسی تمام حالات در مورد B به C بره و تمام حالات رو در مورد C هم بررسی کنه و ... .
ضمنا کسی می تونه این الگوریتم زیر رو توضیح بده.



http://www.up.vatandownload.com/images/c4q4b33ailuwm14g7pxu.jpg

http://www.up.vatandownload.com/images/8ra9h661e5qppv709et3.jpg
الگوریتم بالا اول یه مسیر پیدا می کنه و وزن اون هم پیدا می کنه ، پس از اون این مسیر و وزن رو به عنوان بهترین وزن و مسیر قرار می ده پس از این به i یکی , به j دو تا اضافه می کنه (البته یکی هم اضافه کنه موردی پیش نمیاد و فقط یک بار بیهوده حلقه رو دور می زنه ، ؟؟؟!!!) ، حالا وزن رو مقایسه می کنه اگه کمتر بود با وزن و مسیر قبلی جایگزین میشه ، حالا به j یکی اضافه می کنه اگه j در مقایسه با تعداد راس ها کوچکتر-مساوی بود. به i هم یکی اضافه می کنه ، اگه i از n-2 راس ها کوچکتر-مساوی بود (چرا؟)
برداشت بالا درست هست؟
با تشکر از شما

[vistacali]

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

لینک: الگوریتم همیلتونی (http://fa.wikipedia.org/wiki/%DA%AF%D8%B1%D8%A7%D9%81_%D9%87%D9%85%DB%8C%D9%84% D8%AA%D9%88%D9%86%DB%8C)
لینک:فروشنده دوره گرد (http://fa.wikipedia.org/wiki/%D9%85%D8%B3%D8%A6%D9%84%D9%87_%D9%81%D8%B1%D9%88% D8%B4%D9%86%D8%AF%D9%87_%D8%AF%D9%88%D8%B1%D9%87%E 2%80%8C%DA%AF%D8%B1%D8%AF)
کد برنامه فروشنده دروه گرد (http://www.codeproject.com/Articles/9372/Solution-to-Travelling-Salesman-Problem)
فیلم اموزشی فروشنده دوره گرد بخش اول (http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=0CCMQtwIwAA&url=http%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DRv5 6SvbrU8M&ei=X_aGT6-4KsaUswbUoMXSBg&usg=AFQjCNEmtnDEzKSXUaP--iIAFsC8ZTs3kw&sig2=WZXWc40QMc-ltek3iPcTOA)
فیلم اموزشی فروشنده دوره گرد بخش دوم (http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&ved=0CCoQtwIwAQ&url=http%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DX9M X_ZJOyes&ei=X_aGT6-4KsaUswbUoMXSBg&usg=AFQjCNEyPDvt7bB8eGid5nb5FHoxN16skw&sig2=P4IV02gM9DE5zqKBtwF3-Q)
فیلم امروزشی فروشنده دوره گرد بخش سوم (http://www.youtube.com/watch?v=9VyD7MlntS4)
فیلم اموزشی فروشنده دوره گرد بخش چهارم (http://www.youtube.com/watch?v=5vf7kScUcl8)
سایت اصلی فیلم ها فروشنده دوره گرد بدون فیلتر (http://www.matlabsite.com/270/mvfor101-solution-representation-techniques-for-tsp.html)
دانلود برنامه با الگوریتم های مختلف (http://forum.matlabsite.com/thread-157.html?highlight=%D9%81%DB%8C%D9%84%D9%85+%D8%A2 %D9%85%D9%88%D8%B2%D8%B4%DB%8C+%D8%B1%D9%88%D8%B4+ %D9%87%D8%A7%DB%8C+%D8%AD%D9%84+%D9%85%D8%B3%D8%A3 %D9%84%D9%87+%D9%81%D8%B1%D9%88%D8%B4%D9%86%D8%AF% D9%87+%D8%AF%D9%88%D8%B1%D9%87+%DA%AF%D8%B1%D8%AF)

[miladna]

ممنون از vistacali عزیز من این لینک ها دیده بودم ، به غیر از فیلم ها ، یه چیز دیگه ای که خواستم بگم ما تا قبل از اشاره گرها خوندیم و همین دیگه.
یه چیز دیگه روش greedy رو چه طوری استفاده می کنن؟
در مورد این مسئله روش های دیگه ای هم هست ، مثل backtraking یا Dijkstra یا Bellman-Ford یا Floyd-Warshall یا ... هست ولی نوع استفاده رو من متاسفانه ... .
در مورد الگوریتم کسی می تونه راهنمایی کنه؟؟؟؟

[shahmohammadi]

سلام.

در مورد این مسئله روش های دیگه ای هم هست ، مثل backtraking یا Dijkstra یا Bellman-Ford یا Floyd-Warshall یا ... هست ولی نوع استفاده رو من متاسفانه ... .
baktrack
لينك (http://barnamenevis.org/showthread.php?334761-backtracking-search)
توي همين سايت چند لينك ديگر هم هست كه يادم رفته. بگرديد پيدا مي كنيد.

[miladna]

ضمن تشکز از شاه محمودی عزیز ، از دوستان کسی می تونه عکس های ضمیمه رو توضیح بده؟

[vistacali]

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

[miladna]

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


الگوریتم بالا اول یه مسیر پیدا می کنه و وزن اون هم پیدا می کنه ، پس از اون این مسیر و وزن رو به عنوان بهترین وزن و مسیر قرار می ده پس از این به i یکی , به j دو تا اضافه می کنه (البته یکی هم اضافه کنه موردی پیش نمیاد و فقط یک بار بیهوده حلقه رو دور می زنه ، ؟؟؟!!!) ، حالا وزن رو مقایسه می کنه اگه کمتر بود با وزن و مسیر قبلی جایگزین میشه ، حالا به j یکی اضافه می کنه اگه j در مقایسه با تعداد راس ها کوچکتر-مساوی بود. به i هم یکی اضافه می کنه ، اگه i از n-2 راس ها کوچکتر-مساوی بود (چرا؟)
برداشت بالا درست هست؟
با تشکر از شما