عنوان پایان‌نامه
مسئله فروشنده دوره گرد چند گانه در متریک نامتقارن
- رشته تحصیلی
- مهندسی کامپیوتر- آلگوریتم ها و محاسبات
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس یک فنی شماره ثبت: 81..;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 69434
- تاریخ دفاع
- ۱۷ مرداد ۱۳۹۴
- دانشجو
- سپیده پیامنی
- استاد راهنما
- دارا معظمی
- چکیده
- ما تعمیمی از مسئله فروشنده دوره گرد در فضای نامتقارن را بررسی می کنیم. در این نوع، چندین فروشنده داریم که در فضای متریک حرکت می کنند و هدف این است که هر راس حداقل توسط یک فروشنده ملاقات شود، به طوری که کل فاصله طی شده توسط تمام فروشنده ها مینیمم باشد. در نوع اول، دو راس s، t و یک عدد صحیح k داریم و هدف پیدا کردن k مسیر از s به t است به طوری که اجتماع این مسیرها همه رئوس را شامل شوند. ما برای این مسئله یک الگوریتم دو معیاره که حداکثر از k+k/b مسیر استفاده می کند، ارائه می دهیم. در نوع دوم، k جفت از راس های {(s_i,t_i ) }_(i=1)^k را در نظر می گیریم. هدف پیدا کردن یک مسیر s_i-t_i برای هر جفت است به طوری که هر راس حداقل در یکی از مسیرها ظاهر شود. ما نشان می دهیم که می توان هزینه کل مسئله را وقتی که k=2 است، تقریب بزنیم. در فصل پنجم این الگوریتم ها را ارائه می دهیم.
- Abstract
- In the classic form of the Traveling Salesman Problem (TSP), the goal is to find the shortest Hamiltonian cycle in a symmetric metric. The idea is that this describes the fastest way a salesman can visit a given set of clients and then return to their starting position. We consider some generalizations of the Asymmetric Traveling Salesman Path Problem. In the first variant, we are given two nodes s, t and an integer k and the goal is to find k paths from s to t whose union covers all nodes. Next, we consider the case where we have k pairs of nodes{(s_i,t_i ) }_(i=1)^k. The goal is to find an s_i-t_i path for every pair such that each node of G lies on at least one of these paths.
