شنبه 27 آبان 1396 | Saturday 18 th of November 2017 صفحه اصلی گروه الکترونیکی کامپیوتر
الگوریتم فروشنده دوره گرد

در محدوده جغرافیایی یک فروشنده دوره گرد تعدادی شهر وجود دارد که فاصله بین هر زوج از شهر ها ، مشخص و عددی مثبت است  قرار است فروشده  از یکی  از شهرها شروع کند و  کلیه شهر ها را  ، هر یک فقط یک بار ، ملاقات کند و در به نقطه شروع برگردد . برای به حداقل رساندن زمان سفر فروشنده باید کوتاهترین مسیر را با شروع از موطن فروشنده تعیین کنیم این مسئله کوتاهترین مسیر را مسئله فروشنده دوره گرد می نامند.

در مسئله فروشنده دوره گرد ، شبکه بین شهری را می توان به وسیله یک گراف جهت دار و وزن دار نمایش داد و با توجه به این که برخی از مسیرها ممکن است یک طرفه باشد گراف بدون جهت توصیه نمی شود. همچنین فرض می کنیم، وزن ها مقادیری غیر منفی هستند . یک تور که مدار هامیلتون هم گفته می شود در یک گراف جهت دار از مسیری از یک رأس به خودش است که از هر کدام از رئوس دیگر دقیقا یک بار عبور می کند. یک تور بهینه در گراف جهت دار موزون ،چنین مسیری با طول حداقل است. هدف مسأله فروشنده دوره گرد یافتن یک تور بهینه در گرافی موزون و جهت  دار است.

چون نقطه شروع تأثیری در تور بهینه ندارد.  V1را رأس اغازی در نظر می گیریم. در حالت کلی ممکن است گراف یک گراف کامل باشد و از هر رأس به رئوس دیگر یک یال وجود داشته باشد.در این صورت تعداد کل تورها عبارتست از :

(n-1) (n-2) …. 1 =(n-1)!

هدف مسئله فروشنده دوره گرد یافتن یک طور بهینه در گرافی موزون و جهت دار است

Compatability by:
آخرین به روز رسانی سایت: سه شنبه, 22 اسفند 1391 - 00:26