منو
 صفحه های تصادفی
رشته الکترونیک هواپیما
تولید انبوه
بازرگانی و کشاورزی
تیره هیدروکارتیاسه
اسپوروفیت
نقش قابلیت نفوذ اوربیتال ها در ایجاد اثر پوششی
بریستول مایرز سکوئیب
مهندسی نرم افزار
اثبات قضیه دزارگ در صفحه
نمایشگاه
 کاربر Online
398 کاربر online

مسئله فروشنده دوره گرد

تازه کردن چاپ
علوم ریاضی > ریاضی
علوم ریاضی > ریاضی > شاخه های ریاضی > ریاضیات کاربردی > نظریه گراف
(cached)

فرض کنید نمودار شکل زیر نقشه چهار شهر و فاصله بین آنها برحسب کیلومتر باشد.


img/daneshnameh_up/7/74/dore.jpg


فرض کنید یک فروشنده بخواهد از هر شهر تنها یک بار عبور کند که نقطه شروع و پایان شهر باشد. کمترین مسافتی که فروشنده می تواند همه مسیر را بپیماید، کدام است؟

حل مسئله

این مساله را می توان با نوشتن همه دورهای همیلتونی ممکن با نقطه شروع و پایان از راس و محاسبه کل مسافت پیموده شده برای هر دور حل کرد.


مسیر
مسافت (کیلومتر)

ABCDA

ABDCA

ACBDA

ACDBA

ADBCA

ADCBA

30+30+25+40=125

30+35+25+50=140

50+30+35+40=155

140

155

125




بنابراین مسیر یا حداقل مسافت کل یعنی، 125 کیلومتر را به دست می دهد. حالت کلی مساله فروشنده دوره گرد شامل یافتن یک دور همیلتونی برای یک گراف دلخواه راسی با حداقل مسافت پیموده شده است، که هر یال در آن مسافت بین دو راس را نشان می دهد. یک راه برای حل مساله، حالت کلی استفاده از روش مثال بالا است. برای این منظور،همه دورهای همیلتونی را که از یک راس خاص شروع شده و به همان راس پایان می یابد می نویسیم و مسافت کل هر دور را حساب می کنیم و از میان آنها، آن دوری را انتخاب می کنیم، که مسافت کل آن حداقل است، با این حال حتی برای مقادیر متوسط این روش غیر عملی است. مثلاً برای یک گراف کامل با 30 راس تعداد دور همیلتونی مختلف با شروع و پایان از یک راس خاص وجود دارد، که باید بررسی شود. حتی اگر برای هر دور پیدا شده در محاسبه مسافت کل به یک میکروثانیه زمان احتیاج باشد، برای 30 راس تقریباً سال نیاز داریم درحال حاضر، برای حل حالت کلی مساله فروشنده دوره گرد هیچ الگوریتم شناخته شده ای وجود ندارد، تا از کارایی کافی برخوردار باشد.






تعداد بازدید ها: 57646


ارسال توضیح جدید
الزامی
big grin confused جالب cry eek evil فریاد اخم خبر lol عصبانی mr green خنثی سوال razz redface rolleyes غمگین smile surprised twisted چشمک arrow



از پیوند [http://www.foo.com] یا [http://www.foo.com|شرح] برای پیوندها.
برچسب های HTML در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..