سوال: دور همیلتونی [بایگانی]

Parsa_2006

جمعه 15 خرداد 1388, 01:15 صبح

سلام
اگه امکان داره در مورد بدست آوردن دور همیلتونی یک گذاف به من توضیح بدید
با تشکر

pesar irooni

شنبه 16 خرداد 1388, 02:40 صبح

میتونی راجع به مساله فروشنده دوره گرد تحقیق کنی. چون اینا هر دو یکی هستند و جز مسائل NP-Compelete هستند و راه حل آنها برنامه سازی پویاست. شما اگه هر مساله بهینه سازی (برنامه سازی پوویا) که ببینی راه حلش تقریبا یکیه. مثلا تو همین تالار تاپیکی بنام "برش طولی 1 بعدی" از همین نوع مساله هاست.

qwerty11

پنج شنبه 21 خرداد 1388, 20:42 عصر

میتونی راجع به مساله فروشنده دوره گرد تحقیق کنی. چون اینا هر دو یکی هستند و جز مسائل NP-Compelete هستند و راه حل آنها برنامه سازی پویاست. شما اگه هر مساله بهینه سازی (برنامه سازی پوویا) که ببینی راه حلش تقریبا یکیه. مثلا تو همین تالار تاپیکی بنام "برش طولی 1 بعدی" از همین نوع مساله هاست.

دوست عزيز اشتباه ميكني. در واقع راه حل اصلي اين سوال روش backtrack يا پسگرد ميباشد.

xxxxx_xxxxx

پنج شنبه 21 خرداد 1388, 21:06 عصر

دوست عزيز اشتباه ميكني. در واقع راه حل اصلي اين سوال روش backtrack يا پسگرد ميباشد.
خب فروشنده دوره گرد هم يك نوع دور هميلتوني هست ديگه. مگه نه؟

درواقع مسئله فروشنده دوره گرد همون دور هميلتوني‌ست با مسيرهاي هزينه دار

pesar irooni

جمعه 22 خرداد 1388, 03:14 صبح

راه حل اصلي اين سوال روش backtrack يا پسگرد ميباشد
دور همیلتونی رو به روشهای پسگرد و انشعاب و تحدید هم میشه حل کرد. نه تنها دور همیلتونی بلکه بسیاری از مسائل دیگه برنامه سازی پویا رو میشه با این روشها هم حل کرد (مثل کوله پشتی 0 و 1) ولی نمیشه گفت که راه حلش حتما همونه..........