مسیر همیلتونی !

[redflight]

سلام من یه الگوریتم دور همیلتونی توی اینترنت بود از روی اون مسیر همیلتنی رو نوشتم وروی داده های کوچیک جواب می ده اما من می خوام روی 500 تا داده تست کنم ولی جواب نمی ده! یعنی بهتره بگم روی 50 تا هم جواب نمی ده چ برسه به 500 تا!
می دونم NP-C هست اما روی 50 تا غیر عادی نیست که جواب نمی ده؟
کسی برنامه مسیر همیلتونی رو داره؟ یا بهترین الگوریتمش رو داره من پیاده سازی کنم؟
مسیر همیلتی موازی شده؟

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

پیدا کردن فقط یه دور منظورتونه یا همه؟
اگه گراف کامل از درجه ۵۰ باشه با شروع از یه راس خاص !۴۹ دور مختلف می‌شه نوشت. این فاکتوریل یه عدد شصت وچند رقمیه!
در کل حتی اگه فقط پیدا کردن یه دور مد نظرتون باشه اگه بخواید کل فضا رو بدون الگوریتم هوشمند خاصی به صورت کورکورانه بگردید بازم الگوریتم از مرتبه‌ی !(n-1) هستش در بدترین حالت.

[redflight]

پیدا کردن فقط یه دور منظورتونه یا همه؟
اگه گراف کامل از درجه ۵۰ باشه با شروع از یه راس خاص !۴۹ دور مختلف می‌شه نوشت. این فاکتوریل یه عدد شصت وچند رقمیه!
در کل حتی اگه فقط پیدا کردن یه دور مد نظرتون باشه اگه بخواید کل فضا رو بدون الگوریتم هوشمند خاصی به صورت کورکورانه بگردید بازم الگوریتم از مرتبه‌ی !(n-1) هستش در بدترین حالت.

همه ی مسیر ها مد نظرم هست
اصلا امکان پذیر نیست؟؟؟
بعد یه سوال، الگوریتم موازیش پیاده سازی شده؟ اون چی؟ قابل انجامه؟

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

همه ی مسیر ها مد نظرم هست
اصلا امکان پذیر نیست؟؟؟
بعد یه سوال، الگوریتم موازیش پیاده سازی شده؟ اون چی؟ قابل انجامه؟

یه برنامه‌ی خیلی ساده رو در نظر بگیرید که فقط اعداد یک تا !۴۹ رو چاپ کنه. با فرض استفاده از کلاسای مخصوص کار با اعداد خیلی بزرگ، کل برنامه بیشتر از ده خط نمی‌شه. ولی عمرمون قد نمی‌ده تموم شدنش رو ببینیم! حالا فرض کنید به جای چاپ عدد لیست مسیر رو چاپ کنه و تازه برای محاسبه‌ی این لیست محاسبات پیچیده‌تری هم لازم باشه. یا مثلا تصور کنید واسه هر مسیر حدود صد بایت متن لازم باشه که نشونش بدیم. اگه بخوایم نتیجه رو توی فایل بریزیم کلی ترا بایت فضا لازم داریم. کافیه ۴۹ فاکتوریل رو ضرب در صد و تقسیم بر یک میلیارذ کنید تا عدد تخمینی به ترا بایت به دست بیاد. یه عدد پنجاه و چند رقمی!
وقتی می‌گید همه رو می‌خوام، یعنی هیچ راه میانبری جز بررسی تک تک موارد وجود نداره. مگه اثبات ریاضی وجود داشت که تعدادشون خیلی کمتر از این عدد هست و می‌شه سریعتر بهشون رسید، که خب اثبات ریاضی وجود داره که تعدادشون دقیقا !۴۹ تاست! پس نباید دنبال الگوریتم برای کم کردن زمان به صورت پایین اومدن مرتبه باشید. ولی خب می‌شه موازی برنامه‌نویسی کرد. اونم خودش بحث می‌خواد که چقدر می‌ارزه.
در مورد همیلتونی بودن بیشتر پیدا کردن یه دور یا یه مسیر مد نظر هست تا پیدا کردن همشون. مشابه همین مساله در مورد اعداد اول خیلی بزرگ هست که در رمزنگاری کاربرد داره. اگه بگن کل اعداد اول پونصد رقمی رو چاپ کنید ... اما اونجا برای ما صرفا پیدا کردن یه عدد اول مهم هست و نه همشون. بررسی اول بودن یه عدد پونصد رقمی خودش مکافاتی داره. چه برسه بخوای کل اعداد پونصد رقمی رو بررسی کنی!

البته این صحبتایی که من کردم بحث بدترین حالت برای لیست کردن همه‌ی دورها بود که اگه گراف کامل باشه اتفاق می‌افته. اما اگه صرفا پیدا کردن یه دور مد نظر باشه ممکنه بحث متفاوت باشه. اتفاقا گراف کامل برای پیدا کردن دور از مرتبه‌ی n هست و خیلی ساده!

[redflight]

من هر چی می گردم مقاله هایی ک برای موازی کردنش پیدا می کنم با PRAM هست
شما نمی دونین تا حالا پیاده سازی شده یانه؟