روش های دقیق مربوط به حل مسئله فروشنده دوره گرد نامتقارن (TSP) Exact Methods for the Asymmetric Traveling Salesman Problem

تعریف رسمی این مسئله به صورت زیر می باشد. فرض کنید G = (V, A) گراف جهت دار کامل باشد، به این ترتیب  جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

که در این فرمول r به عنوان کمان ثابت می باشد.

چندین زیرشاخه از ATSP مد نظر قرار می گیرد، که هر کدام در ارتباط با زیرمجموعه ای از محدودیت هایی می باشد که یک فرایند خوش ساخت را ایجاد کرده که مقدار راه حل کران پایین مشخصی را برای ATSP نشان می دهد.

محدودیت های 2، 3 و 5 با تابع هدف 1، مسئله تخصیص  (AP) با مجموع حداقل را حل می کند. چنین مسئله ای همیشه دارای راه حل بهینه صحیحی بوده، و نیازمند مجموع هزینه حداقل بالاترین نقطه سیکل جهت دار گسسته تمام منحنی های مربوط به G می باشد. اگر راه حل بهینه AP تنها به تعیین یک سیکل جهت دار بپردازد، به این ترتیب به تعیین تمام محدودیت های 4 پرداخته و برای ATSP بهینه می باشد. به عبارت دیگر، هر مجموعه از راس S که منحنی آن ها تحت تاثیر این چرخه ها می باشد، به تعیین محدودیت های 4 می پردازد. ایجاد AP در زمان   حل می گردد.

محدودیت 2، 8 و 5 ، به همراه تابع هدف 1، به تعریف مولد کوتاه ترین مولد شناخته شده   می پردازد  . چنین موضوعات همیشه دارای راه حل بهینه صحیح می باشد، و منطبق با یافتن حداقل هزینه زیر گراف جهت دار  از G می باشد که i) درجه داخلی هر راس دقیقا یک بوده، و ii) هر راس از طریق راس ریشه r بدست می آید. اگر راه حل بهینه   چنین راس را با درجه خروجی برابر با یک مد نظر قرار دهد، سپس تمام محدودیت ها مد نظر قرار می گیرد 3) و از این رو برای ATSP بهینه می باشد. به عبارت دیگر هر راس دارای درجه خروجی متفاوتی از یک می باشد، که نشان دهنده محدودیت های شدیدی می باشد.  در زمان   با مد نظر قرار دادن ریشه های شاخه ای مولد در راس r حل می و با افزودن آن گردد، منحنی با حداقل هزینه وارد راس r می گردد. الگوریتم های کارآمد در ارتباط با مسئله حالت شاخه ای توسط ادموند، فالکرسون، تارجان و کامرینی، فراتا و مافیولی مطرح شده است؛ به کارگیری موثر الگوریتم تارجان در بررسی های مربوط به فیسچتی و توس یافت می شود. فیسچتی روش زمانی   را برای محاسبه کران پایین که وابسته به راس ریشه r نمی باشد، است.

زیرساخت سوم، مرتبط به محدودیت 3، 9 و 5 با تابع هدف 1 بوده، که به تعریف مسئله مولد غیرشاخه ای می پردازد. چنین مسئله ای به آسانی به    منتقل شده و به سادگی منجر به ترانهادن ماتریکس ورودی گشته، بنابراین در زمان   حل می گردد.

برای بدست آوردن کران پایین تر، دو فرایند بازسازی   و  معرفی می گردد.

بازسازی   توسط   با افزودن محدودیت 3 برای   بدست می آید، که درجه خروجی برابر با 1 را برای راس ریشه r مد نظر قرار می دهد. چنین مسئله ای با مد نظر قرار دادن ماتریکس هزینه مشخص شده به   انتقال می یابد، که از طریق افزودن مقدار مثبت M به   بدست می آید و در ارتباط با تمام  ، مقدار بهینه   برابر با   می باشد.

بازسازی  همانند   با افزودن محدودیت 2  به   بدست می آید که درجه ورودی برابر با 1 را برای راس ریشه r می باشد. چنین مسئله ای در زمان  با انتقال آن به   از طریق جا به جایی ماتریکس هزینه ورودی حل می گردد.

2. روش شاخه و کران بر مبنای AP

در این بخش ما به بررسی الگوریتم های شاخه و کران بر مبنای AP می پردازیم که از زمان بررسی های انجام شده توسط بالاس و توس مطرح شده است. تمام این الگوریتم ها از رویکرد شاخه و کران درجه اول  که در بررسی های توس و کارپانتو نشان داده شده است، حاصل شده که در زیر نشان داده می شود.

در هر گره h از مسیر تصمیم گیری، روش TSPI به حل مسائل جایگزینی   که توسط 1،2،3، 5 تعریف می گردد پرداخته و محدودیت های ثابت متغیرهای دیگر در ارتباط با زیرمجموعه های کمان زیر می باشند:

 جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

به آسانی تبدیل به استاندارد AP با تغییر ماتریکس هزینه می گردد تا محدودیت های دیگر را مد نظر قرار دهد.

اگر راه حل بهینه  به تعریف سیکل جهت دار هامیلتون نپردازد و مقدار   ( که نشان دهنده کران پایین تر مرتبط به گره h می باشد) کوچکتر از مقدار راه حل بهینه کنونی برای مثال UB باشد، به این ترتیب، گره های نزولی m از گره h بر طبق به طرح شاخه ای زیر ایجاد می گردد ( که بر مبنای تغییر قوانین حذفی مطرح شده توسط بلمور و مالون می باشد).

فرض کنید  به عنوان زیرشاخه ای در   بوده که دارای حداقل تعداد مورد نظر منحنی ها نبوده، یعنی به گونه ای که   بر مبنای حداقل موارد می باشد و فرض کنید  بر مبنای منحنی غیر مشخص AP به روشی می باشد که در محدوده زیرشاخه ها می باشد. زیرمجموعه های منحنی ها شامل شده و غیر مشمول در ارتباط با گره نزولی   از گره های شاخه ای h، برای نمونه   می باشد که به شکل زیر تعریف می گردد    . ( شکل 4.1 را برای توضیح بیشتر مشاهده کنید):

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

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

شکل 4.1 شاخه گزینی زیرمجموعه ها  ، به ترتیبی که   و    .

2.1 الگوریتم کارپانتو، دل آمیکو و تروس

روش های کارپانتو، دل آمیکو و تروس متفاوت از مواردی می باشد که در بخش 166 در موارد اصلی زیر نشان داده شده است.

a) در گره مربوط به مسیر تصمیم گیری انشعابی، رویکردهای مربوط به کاهشی برای حذف از منحنی G نشان داده شده که متعلق به مسیرهای بهینه نمی باشد؛ به این ترتیب گراف جهت دار G به بخش 1 انتقال می یابد، برای مثال  ، که امکان استفاده از رویکردها مشخص را برای نمودار پراکنش نشان می دهد.

b) استفاده از تکنیک پارامتری کارآمد برای راه حل  ، این امکان را برای   ایجاد می کند تا در زمان   حل گردد؛

c) کاربرد، در هر گره شاخه ای h، در ارتباط با رویکرد ادغام شده زیرشاخه ها برای کاهش تعداد این موارد توسط راه حل بهینه   مد نظر قرار می گیرد.

2.1.1 رویکرد کاهشی.

در گره ریشه مسیر تصمیم گیری شاخه ای، AP منطبق با ماتریکس هزینه کامل اصلی بوده، c توسط روش دوگانه   با رویکرد CTCS که بر طبق به نظریه کارپانتو توس نشان داده می شود، حل می گردد. فرض کنید   و  بر مبنای راه حل بهینه مرتبط به AP بوده و فرض کنید   به عنوان مقدار بهینه مورد نظر باشد. مشخص می باشد که برای هر منحنی  ، هزینه کاهش  نشان دهنده کران پایین بر روی افزایش راه حل AP بهینه مربوط به ادغام منحنی   می باشد. اگر میزان احتمالی ATZP از UB شناخته شده باشد، به این ترتیب هر منحنی   بوده به گونه ای که  از بخش A کنار گذاشته شده، از این رو مد نظر قرار دادن آن در راه حل ATSP منجر به مقادیر پایین تر از UB نمی گردد. گراف جهت دار اصلی G می تواند به میزان یک کاهش یابد  ،  به صورتی که  .

مقدار UB، از طریق روش ذهنی برای ATSP بدست می آید؛ در بخش صفحه 164، الگوریتم پیوسته ای که توسط کارپ مطرح شده است، مورد استفاده قرار می گیرد. روش دیگر بر مبنای محاسبه کران بالا با مد نظر قرار دادن   بدست می آید، به ترتیبی که  به عنوان پارامتر مشخص می باشد. به هر حال اگر در پایان الگوریتم شاخه و کران ، هیچ میزان احتمالی از مقدار کمتر از UB مد نظر قرار نگیرد، این ترتیب  ، به عنوان کران بالای مشخصی نبوده، بنابراین   می بایست افزایش یافته و جریانات جدید می بایست به اجرا در بیاید.

2.1.2 راه حل   پارامتری. کارایی الگوریتم ATSP کل بستگی به بازدهی الگوریتم MAP مورد استفاده دارد. در هر گره h از مسیر تصمیم، به جای حل کردن   از همان ابتدا، یک تکنیک پارامتری مورد استفاده قرار می گیرد، که تنها یک مسیر افزوده را مد نظر قرار می دهد. در واقع زمانی که یک گره نزولی h از گره اصلی k ایجاد می گردد، تنها یک منحنی، برای مثال  از راه حل   مستثنی می گردد. بنابراین، برای رسیدن به راه حل بهینه   از   ، تنها ضروری است تا به تامین محدودیت 2 برای   و محدودیت 3 برای   بپردازیم. بنابراین تنها نیاز داریم تا مسیر افزوده ای از راس s تا راس t را در یک گراف دو بخشی منطبق با   با توجه به ماتریکس هزینه کاهشی   مد نظر قرار دهیم.  توجه داشته باشید که مد نظر قرار دادن منحنی های جدید که در  قرار دارند، پارامتربندی را تحت تاثیر قرار نداده، به گونه ای که این منحنی ها متعلق به راه حل بهینه ای از   می باشند. زمانی که طرح G پراکنده می شود، کوتاه ترین مسیر افزوده از طریق روش های حاصل شده از الگوریتم متصل شده مطرح شده از طرف جانسون برای محاسبه کوتاه ترین مسیر در نمودار پراکنش یافت می گردد، که از ردیف های گروهی ایجاد می گردد. بنابراین پیچیدگی زمانی مورد نظربرای حل هر   برابر با   می باشد.

محاسبه کوتاه ترین مسیر افزوده در هر گره h،  به محض اینکه هزینه های رو به کاهش کنونی، بیشتر و یا برابر فاصله بین مقدار UB کران بالای موجود و میزان بهینه   می گردد، متوقف می شود.

2.1.3 ادغام زیرشاخه ها

گره h از مسیر تصمیم گیری را مد نظر قرار دهید که در آن چندین راه حل MAP بهینه وجود دارد. بررسی های محاسباتی نشان می دهد که راه حل بهینه ای که معمولا منجر به کمترین تعداد گره ها در زیرشاخه هایی که کمتر از h می باشد، دارای حداقل تعداد مسیرهای فرعی می باشد. یک روش ابتکاری که سعی در کاهش تعداد این مسیرهای فرعی دارد، از طریق به کارگیری قوانین زیر بدست می آید.

با مد نظر قرار دادن دو زیرشاخه   و  ، اگر یک جفت از منحنی   و   وجود داشته باشد، به این ترتیب منحنی   و  دارای مقدار کاهشی صفر می باشند ( یعنی  )، به این ترتیب راه حل بهینه   از طریق ارتباط   و  از زیرشاخه مجزای    بدست می آید. به صورتی که در پایان روش، سیکل جهت دار هامیلتون مد نظر قرار گرفته، بنابراین راه حل بهینه ای در ارتباط با ATSP در ارتباط با گره h مد نظر قرار گرفته و هیچ گره نزولی ایجاد نمی گردد.

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

2.2. الگوریتم های میلر و پکنی

روش های موثری برای راه حل ATSP توسط میلر و پنکی در اوایل قرن نوزدهم مطرح شده است. این روش ها معمولا بر مبنای رویکرد کلی می باشد که توسط کارپانتو و توس بیان شده است، تفاوت و شباهت های اصلی بین آن ها در بخش زیر مورد بحث قرار داده می شود.

در صفحه 596، میلر و پکنی الگوریتم مقدماتی را نشان می دهند که بر مبنای موازی سازی رویکرد کارپنتو و تروس می باشد، که از طریق بکارگیری روش های ابتکاری در گره ریشه مد نظر قرار می گیرد.

الگوریتمی که در صفحه 664 نشان داده شده است، بهبود روش موازی اصلی را نشان می دهد. MAP در گره ها از طریق رویکرد پارامتری  مد نظر قرار می گیرد که مسیر افزوده مجزایی را با استفاده از   محاسبه می کند. علاوه بر این الگوریتم پیوندی در گره ریشه به کار گرفته می شود، و در ارتباط ا گره های دیگر، به همراه بسامد کاهشی می باشد به ترتیبی که جستجو همچنان ادامه می یابد. علاوه بر این مرحله شاخه و کران از طریق کنار گذاشتن تمام موارد ورودی با هزینه بیش از حد آستانه مورد نظر  بدست می آید.

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

الگوریتمی که در صفحه 665 نشان داده شد، به عنوان الگوریتم اصلاح شده صفحه 664 است، که با در نظر گرفتن کاربردهای آن در هر گره حاصل می گردد، و به عنوان رویکرد دقیقی برای مد نظر قرار دادن سیکل جهت دار هامیلتون بر روی زیرگراف جهت دار می باشد که توسط منحنی هایی ارزش کاهشی صفر تعریف می گردد. پیچیده ترین نسخه های مربوط به کدهای میلر و پکنی در صفحه 597 نشان داده می شود، که شامل موارد اصلاح شده ای می باشد که قبلا توسط محققان مطرح شده است.

شباهت بین روش های کارپانتو، دل آمیکو، و توس و الگوریتم میلر و پنکی به صورت زیر می باشد: a) قوانین شاخه گزینی مواردی می باشد که در صحه 166 نشان داده شده است، b) MAP در گره های شاخه گزینی مختلف از طریق روش   حل می گردد؛ C) الگوریتم سرهم بندی در گره ریشه بکار برده می شود. این دو روش در جنبه های زیر متفاوت می باشند: a) در ارتباط با مرحله پراکنش، صفحه 164 معیاری را بر مبنای مقایسه بین کاهش هزینه مورد نظر توسط AP اولیه و فاصله بین کران بالا و پایین نشان می دهد؛ b) تکنیک موثر برای ذخیره و بازیابی مشکلات فرعی در صفحه 164 مطرح می گردد به صورتی که بررسی مسیر تصمیم گیری شاخه ای شدید تر می گردد؛ و c) الگوریتم تجربی سریعتربرای مد نظر قرار دادن سیکل جهت دار هامیلتون بر روی زیرگراف جهت دار توسط منحنی با ارزش کاهشی صفر در صفحه 164 نشان داده شده است.

با مقایسه نتایج محاسبه شده که توسط میلر و پنکی بدست آمده و مواردی که در صفحه 164 نشان داده شده است، مشخص می شود که کد دوم کندتر از الگوریتم های نشان داده شده در صفحه 597 برای محدوده ارزشی کوچکتر ( و نمونه های تصادفی) می باشد اما به نظر می رسد که در محدوده ارزشی بزرگتر سریعتر می باشد. در مجموع، این دو روش عملکرد قابل مقایسه ای را نشان می دهد.

3. روش افزوده شاخه و کران

این بخش به توصیف روش های مطرح شده توسط فیس چتی و توس می پردازد، که به جاسازی روش های پیچیده تر پیوندی در روش استاندارد شاخه و کران کارپانتو و تورس می پردازد. مشاهده کنید که AP,،   و  (که در بخش 1 تعریف شده اند) مکمل یکدیگر می باشند. در واقع، AP محدودیت درجات را برای تمام راس ها تحمیل کرده، در حالی که محدودیت های مربوط به این ارتباط به طور کامل نادیده گرفته می شود. بازسازی  ، در عوض، قابلیت دسترسی را از راس r برای تمام رئوس تحمیل کرده، در حالی که محدودیت های درجه خروجی برای تمام راس های متفاوت از r نادیده گرفته می شود. در نهایت   قابلیت دسترسی را از تمام رئوس برای راس r تحمیل کرده، در حالی که محدودیت های درجه ورودی برای تمام رئوس متفاوت از r نادیده گرفته می شود. روش احتمالی برای ترکیب این سه بازسازی بکارگیری روش افزوده نشان داده شده توسط فیس چتی و توس می باشد.

3.1 روش حد و مرز افزوده

روش حد و مرزی افزوده برای ATSP به صورت زیر مد نظر قرار می گیرد. فرض کنید  به صورت روش مرزی موجد برای ATSP باشد. فرض کنید   و در ارتباط با ماتریکس ارزش  ، رویکرد به صورت   بوده، و زمانی که برای نمونه ATSP بکار گرفته می شود دارای ماتریکس ارزش  بوده که کران پایین آن   و همچنین ماتریکس هزینه  به صورت زیر باشد

روش افزوده نمونه هایی از توالی ATSP را ایجاد کرده، که هر کدام از آن ها با ماتریکس ارزشی باقیمانده نسبت به نمونه های قبلی با توجه به روش های مختلف حد و مرزی مد نظر قرار می گیرند. طرح پاسکالی این روش به صورت زیر می باشد.

الگوریتم افزوده:

1. ورودی: ماتریکس ارزش C

2. خروجی: کران پایین   و ماتریکس هزینه باقیمانده   

3. آغازگر  

4.  

5. کاربرد  ، و کسب ارزش  

6.   

استدلال استقرایی نشان می دهد که مقدار   که در مرحله 6 محاسبه شده است، توالی غیرکاهشی مشخصی را از کران پایین برای ATSP نشان می دهد. علاوه بر این ماتریکس هزینه باقیمانده   به هدف کاهش مورد استفاده قرار می گیرد.

روش های مرتبط، با استفاده از هزینه کاهشی برای بهبود کران پایین ATSP بر مبنای یافته های کریستوفید و بالاس  می باشد. برای مقایسه رویکرد افزایشی با روش محدود لاگرانژی  کریستوفید و بالاس، خواننده به صفحه 304 ارجاع داده می شود.

توجه کنید که، به دلیل شرط ii، هر یک از رویکردهای  یک شکاف افزایشی را ایجاد می کند.

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

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

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

هزینه های کاهشی مرتبط به بازسازی AP به آسانی بدون محاسبات اضافی بدست می آید. به منظور کاهش هزینه برای  ، موارد مرتبط به منحنی ها که وارد راس ریشه r نمی گردند، بر مبنای هزینه های کاهشی مشکلات شاخه ای این مولدها بوده ( که در زمان   از طریق روش های بیان شده در صفحه 305 محاسبه می گردند). در حالی که مواردی که در ارتباط با منحنی های ورودی r می باشند، از طریق کم کردن موارد حداقل از هزینه های ورودی بدست می آید. کاهش هزینه در ارتباط با مشکلات   و  به روش مشابه به دست می آید.

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

الگوریتم افزوده ATSP

1. ورودی: ماتریکس ارزش C

2. خروجی: کران پایین   و ماتریکس هزینه باقیمانده C

مرحله 1:

3. حل مشکلات AP بر روی ماتریکس هزینه اصلی C. فرض کنید C بر مبنای ماتریکس هزینه کاهشی می باشد  

مرحله2:

4. حل مشکل   بر روی ماتریکس هزینه   و بروزرسانی   برای تبدیل شدن به ماتریکس هزینه کاهشی  

5. حل مشکل   بر روی ماتریکس هزینه   و بروزرسانی   برای تبدیل شدن به ماتریکس هزینه کاهشی 

مرحله 3:

6.  

7. حل مشکل   بر روی ماتریکس هزینه   و بروزرسانی   برای تبدیل شدن به ماتریکس هزینه کاهشی  

مرحله 4

8.  

9. حل مشکل   بر روی ماتریکس هزینه   و بروزرسانی   برای تبدیل شدن به ماتریکس هزینه کاهشی  

فرض کنید  نشان دهنده زیرگراف جهت دار G بوده که توسط منحنی هایی تعریف می گردد که هزینه کاهشی آن ها برابر با صفر می باشد.

فرض کنید  معرف زیرگراف جهت دار G باشد که توسط منحنی تعریف می گردد که هزینه کاهشی آن برابر با صفر می باشد.

در مرحله 1، رویکرد مرزی بر مبنای AP بکار گرفته می شود. بعد از این مراحل، هر راس در  

حداقل دارای یک منحنی ورودی و خروجی می باشد؛ به هر حال،   برای پیوند قوی تضمین شده نمی باشد.

در مرحله2، اجبار برای پیوند شدید  با بکارگیری روش حد و مرزی بر مبنای   و  به کار گرفته می شود. در واقع بعد از مرحله 4، هر راس از بالاترین نقطه 1 در   حاصل شده، که بعد از مرحله 5 هر راس به بالاترین نقطه 1 می رسد.

گراف جهت دار مولد کنونی   در این نقاط شامل منحنی هایی می باشد، که در این مورد کران پایین  دیگر از طریق رویکرد افزایشی توسعه نمی یابد. اگر چنین منحنی هایی آشکار گردد، منطبق با راه حل ذهنی ATSP می باشد، که بهینه سازی ان از طریق مقایسه هزینه های اصلی با کران پایین تر   بدست می آید. اغلب موارد، به هر حال زیرگراف جهت دار مولد   به صورت غیر هامیلتون می باشد.

فرض کنید گره های پیش رونده و پس رونده h در گراف جهت دار   به ترتیب به صورت   و   باشد، ما این مورد را مطرح می کنیم که راس  بر مبنای نقطه   بوده به صورتی که هیچ یک از رئوس بخش های پیش رونده نمی تواند به رئوس دیگر   بدون گذر از راس r برسد. به طور مشابه راس   بر مبنای نقطه مشترک   می باشد، به صورتی که هیچ یک از این رئوس برگشتی نمی تواند از رئوس دیگر در  بدون گذر از راس r برسد.

مشخصا وجود نقاط پیش رو پس رو بر مبنای شرایط مناسبی برای   بوده که بر مبنای موارد غیر هامیلتون می باشد.

مفهوم مورد نظر بر مبنای نقاط مشترک می باشد: راس r به عنوان نقطه پیوندی   بوده اگر گراف غیرمستقیم   توسط زیر مجموعه های راس  مد نظر قرار داده شود. توجه داشته باشید که مفهوم پیوندهای رو به جلو بدوره گرد قوی تر از پیوندهای غیر مستقیم می باشد. در واقع اگر راس r بر مبنای نقاط پیوندی   باشد به این ترتیب بر مبنای نقطه پیوندی   بوده در حالی که شرایط متضاد آن هرگز برقرار نمی شود.

وجود نقاط پیوندی رو  به جلو از r در مورد   به کار گرفته می شود تا کران پایین   را با حل کردن   افزایش دهد. در واقع در چنین مواردی هیچ هزینه شاخه ای که در آن r دارای درجه خارجی برابر با 1 باشد، با توجه به هزینه کاهشی   وجود ندارد. بر این مبنا، در ارتباط با هر راس r می توان به ایجاد روش هایی در ارتباط با   و  پرداخت، به گونه ای که کران پایین تر   در مواردی که ریشه راس r بر مبنای نقطه پیوندی پیشرو و پسرو باشد افزایش می یابد. بعد از اجرا مراحل 7 و 9 ، راس کنونی r بر مبنای نقطه پیوندی گراف کنونی   می باشد.

پیچیدگی  کل زمان الگوریتم   برابر با   می باشد. بیشترین مرحله وقت گیر مرحله 3  ، و مرحله 7 و 9   بوده که به اندازه n زمان به اجرا در می آید. استحکام کران پایینی نهایی   به شدت بستگی به کاهش هزینه ها  حاصل از محاسبه کران پایینی می باشد. به طور خاص،   مرتبط به AP را مد نظر قرار دهید، که توسط فرمول زیر تعریف می گردد.

 جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

و فرض کنید  به عنوان راه حل بهینه دوگانه مورد نظر در مرحله 3 می باشد. در ارتباط با هر راس  ، فرض کنید   بر مبنای هزینه کوتاه ترین مسیر از راس I تا h باشد که با توجه به هزینه های کاهشی     محاسبه می گردد. مشخص است که راه حل بهینه دیگر توسط   و   برای هر   داده می شود. ( در واقع داریم  در حالی که در مورد  ،   به دنبال تعریف   بر مبنای کوتاه ترین مسیر می باشد).  اکنون فرض کنید  ، که به عنوان هزینه کاهشی بر مبنای راه حل بهینه دو گانه می باشد.

می توان به آسانی مشخص کرد که هزینه    از رای h تا k ( با محاسبه c ) برابر با   می باشد، به صورتی که   هزینه مسیرهای مشابهی می باشد که با در نظر گرفتن  محاسبه می گردد. بنابراین   ه عنوان ماتریکس هزینه می باشد که در نتیجه   با کاهش هزینه مسیرحاصل از راس 1 می باشد، در حالی که باعث افزایش هزینه مسیرها به سمت راس 1 می گردد.

الگوریتم جدید حد و مرز افزوده،  ، با افزودن مراحل زیر به دنبال مرحله 3 بدست می آید.

3. به محاسبه هزینه  ( بر مبنای ماتریکس کاهشی c) از راس 1 تا راس  ؛

 جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

توجه داشته باشید که بعد از مرحله 3، زیرگراف جهت دار  شامل یک حالت شاخه ای بوده، از این رو مرحله 4 در   حذف می گردد.

در نگاه اول الگوریتم   ضعیف تر از   بوده و از این رو مراحلی که شرایط احتمالی را بر روی کران پایین تر ایجاد می کند، جایگزین مراحلی می شود و که هیچ بهبودی را ایجاد نمی کند. به هر حال سوگیری هزینه در مرحله 3 باعث می شود که مرحله 5 بعدی سهم خود را نسبت به کران پایین تر افزایش دهد. بررسی های محاسباتی نشان داده است که  معمولا فراتر از عملکرد   می باشد، از این رو الگوریتم   در صفحه 304 مد نظر قرار می گیرد.

بر مبنای زمان محاسباتی الگوریتم آزمایشی  ، این موارد از طریق موارد به کار گرفته شده در صفحه 304 کاهش می یابد.

4. روش شاخه و برش

در مرحله بعد ما روش چندوجهی فیسچتی و توس در صفحه 3.6 را طرح می کنیم. روش شاخه و برش ATSP با توجه به محدودیت های آن اخیرا توسط اسور، جانگر و رینلت و فیسچتی و گراتچل و افراد دیگر مطرح شده است. روش فیسچتی و توس بر مبنای مدل –6 بوده و از طبقه های دیگر روش های القایی نابرابر برای انواع ATSP استفاده کرده که دارای اهمیت خاصی برای راه حل های نمونه های حقیقی می باشد. در ارتباط با هر دسته، .ما موضوعات تفکیک شده مربوطه را مد نظر قرار می دهیم که به صورت زیر تعریف می گردد. با مد نظر قرار دادن نقطه  که به ارزیابی برابری می پردازد و در نهایت   از نابرابری ATSP، می توان اعضای مربوط به   یافت، یعنی نابرابری   متعلق به   بوده و به این ترتیب باعث به حداکثر رسیدن میزان خطای  می گردد. خواننده به فصل 3 از کتاب کنونی برای تجزیه و تحلیل چندوجهی ATSP ، و همچنین فصل 2 برای طرح روش شاخه و برش برای مسئله فروشنده دوره گرد نامتقارن ارجاع داده می شود.

برای ساده سازی نشانه گذاری،   و   ، می نویسیم   برای  ؛ علاوه بر این ما می نویسیم   یا   به ترتیبی که   یا  .

4.1 تفکیک نابرابری متقارن

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

انطباق بالا نشان می دهد که هر الگوریتم تفکیک شده برای STSP مورد استفاده قرار گرفته به صورت جعبه سیاهی برای ATSP باشد.  به این منظور، با مد نظر قرار دادن نقطه  ، در ابتدا می توانیم به تعریف   از   از طریق تغییرات بپردازیم

و به این ترتیب می توانیم الگوریتم تفکیک STSP را نسبت به   مد نظر قرار دهیم. بلعکس، نابرابری مشخص شده STSP نسبت به موارد مشابه ATSP انتقال می یابد، هر دو این نابرابری ها دارای درجه یکسانی از تخلفات می باشند.

چندین الگوریتم تفکیک شده دقیق و جامع برای STSP در سال های اخیر مطرح شده است، که تمام آن ها برای ATSP مورد استفاده قرار می گیرد؛ فصل 2 از کتاب کنونی را برای جزییات بیشتر مشاهده کنید. در صفحه 306 تنها دو ابزار تفکیک شده مورد استفاده قرار می گیرد.

i) الگوریتم دقیق صفحه 646 برای SECs و

ii) ساده ترین طرح جامع در ارتباط با محدودیت های جستجو که در آن بخش های مربوط به گراف بر مبنای   با در نظر گرفتن   بر مبنای شرایط بلقوه مد نظر قرار داده می شود.

4.2 تفکیک نابرابری    و  

نابرابری  توسط گراتسچل و پادبرگ مطرح شده است.

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

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

بر مبنای تمدید تعاریف اصلی، ما در نهایت   را در نظر می گیریم، که در هر مورد به ترتیب محدودیت های مشخص   و   را مد نظر قرار می دهد.

مشکل مربوط به توالی دسته نابرابر   نشان دهنده توالی بالاترین نقطه بوده  ،  ، که در آن میزان تخلف در حداکثر ممکن می باشد.

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

این بر مبنای مشکلات بهینه سازی ترکیبی می باشد که می تواند توسط طرح شمارشی نامشخص ساده حل گردد.

ما کار خود را با توالی گره تهی آغاز می کنیم. به این ترتیب به شکل مکرر، ما توالی موجود را به روش ممکن توسعه داده و به ارزیابی میزان خطا نابرابری   می پردازیم. این مراحل توسط درخت تصمیم شاخه ای نشان داده می شوند. گره ریشه درخت نشان دهنده توالی تهی می باشد. هر گره در  منطبق با توالی نوع   می باشد؛ به صورتی که   بوده، که هر یک از این گره ها گره رو به کاهش   را ایجاد کرده، که هر کدام نشان دهنده توالی توسعه یافته می باشند  . فراگیر شدن تمام این گره های درختی به طور مشخص ، حتی در ارتباط با مقادیر کوچک n غیرعملی می باشد. از طرف دیگر، تعداد زیادی از این گره ها توسط محاسبه ساده کران بالایی ( در مسیر زیرشاخه های مربوطه) کاهش می یابند.

فرض کنید  به عنوان توالی مرتبط به گره های شاخه ای کنونی، برای مثال   باشد، و فرض کنید  حداکثر میزان خطا را که در طی شمارش مد نظر قرار می گیرد، نشان می دهد. هر یک از گره های بلقوه رو به پایین را   را مد نظر قرار دهید که مرتبط به توالی نوع  می باشد. به این ترتیب به طور مستقیم از تعریف 11 داریم

 جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

که صورتی که ما موارد زیر را تعریف می کنیم

  جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

مشاهده کنید که  نمی تواند فراتر از میزان خطای SEC مرتبط با   حرکت کند؛ از این رو ما داریم   به صورتی که تمام SEC  توسط   مد نظر قرار می گیرد.

بر طبق فرمول 12، تنها گره نزولی  که می بایست ایجاد گردد در ارتباط با توالی   به صورت زیر می باشد.

  جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

توجه داشته باشید که هر دو کمیت   و  می تواند به صورت دوره ای بر مبنای درخت شاخه ای محاسبه گردد:

 

و

  جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

که در این فرمول  در ارتباط با مجموعه های تک عضوی   می باشد.

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

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

در صفحه 306، یکی از بیشترین نابرابری های  مرتبط به توالی گره که به وسیله   آغاز می گردد برای هر   ایجاد می گردد. این مورد از طریق جستجوی مسیر تصمیم گیری به صورت عمقی حاصل شده، و مقدار   بهترین توالی مورد نظر را به صفر بازنشانی می کند به صورتی که برگشت به عقب برای گره سطح 1 وجود دارد.

ما این بخش را با مد نظر قرار دادن نامعادله   زیر به پایان می رسانیم

 جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

که در این فرمول  به عنوان توالی گره مجزای   بوده، نامعادله  به صورت مشخص بوده و برای P تحریک کنند می باشد؛ آن توسط مد نظر قرار دادن نامعادله سیکل  مرتبط به سیکل جهت دار   بدست می آید.

نامعادله  از نامعادله   با مبادله ضریب دو منحنی   و   برای تمام  ،  حاصل می گردد. این به عنوان یک عملیات کلی به نام جابه جایی می باشد که به صورت زیر کار می کند.

در ارتباط با  ، فرض کنید  توسط مورد زیر تعریف گردد:  برای تمام  . مشخصا نامعادله   برای ATSP نوع P معتبر می باشد اگر نسخه ترانهاد به صورت   باشد. این به دنبال این شرایط می آید  ، به ترتیبی که   اگر  . علاوه بر این هر رویکرد مجزای   می تواند مورد استفاده قرار گیرد و به صورت جعبه سیاهی می باشد که در ارتباط با   می باشد. در این مورد فرد بخش های ترانهاد را  در مورد خروجی های مرتبط به رویکرد نشان داده، و به این ترتیب نامعادله برگشتی را جا به جا می کند.

شرایط بالا نشان می دهد که الگوریتم مجزای دقیق و غیرمستدل همچنین برای نامعادله   مورد استفاده قرار می گیرد.

4.3 تفکیک نامعادله CAT

مجموعه نامعادلات زیر توسط بالاس نشان داده شده است. دو منحنی مجزا   و   به صورت ناسازگار می باشند اگر   . مسیر تناوبی محصور شده CAT)) بر مبنای توالی  از منحنی مجزای t بوده به گونه ای که   ناسازگار با منحنی   و   می باشد و همچنین سازگار با منحنی های دیگر در T ( به همراه   و  ) می باشد. فرض کنید   و   مرتبط به مجموعه منحنی G بوده و باعث ورود و خروج راس   می باشد. با مد نظر قرار دادن  ، گره v به نام منبع می باشد اگر  ، در حالی که به نام نفوذی می باشد اگر  . توجه داشته باشید کمی تواند نقش نفوذی و منبع را داشته باشد. فرض کنید  به صورت مجموعه ای از منحنی ها باشد   به صورتی که i به عنوان منبع بوده و j به صورت گره نفوذی می باشد.

در ارتباط با CAT از طول t، نامعادله CAT بصورت زیر

به صورت معتبر و مشخص برای نوع ATSP می باشد.

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

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

فرض کنید  شامل حاشیه   با گره مورد نظر  باشد. سیکل   و  به عنوان زیرمجموعه حاشیه   بوده که نشان دهنده زیرگراف جهت دار  می باشد و به ترتیبی که   در ارتباط با تمام  می باشد. سیکل C به صورت بی قاعده می باشد اگر   به صورت بی قاعده باشد. ii)   برای تمام موارد به صورت  ؛ و iii) به صورت نامشخص می باشد اگر زیرگراف جهت دار G تحت تاثیر گره هایی قرار گیرد که تحت پوشش C دارای پوشش دیگری به غیر از C باشد.

بر مبنای این ساختار، سیکل ساده بی قاعده C در G منطبق با   می باشد، که   بوده اگر   تحت تاثیر C بوده و به این ترتیب کل وزن C عبارتست از

از این رو  کران پایین تر نامعادله مورد نظر   را نشان می دهد ، که بر مبنای زیر محاسبه می گردد

الگوریتم تفکیک شده غیرمستدل ، سیکل وزنی حداقل  از حاشیه e استفاده می کند. اگر   به شکل ساده باشد، به این ترتیب منطبق با  ، برای مثال T می باشد. علاوه بر این اگر، کران پایین  فراتر از حد آستانه    ،

به این ترتیب نامعادله مورد نظر به طور مشخصی نادیده گرفته می شود؛ از این رو به ارزیابی میزان حقیقی   پرداخته، و این نامعادلات را مد نظر قرار می دهیم به صورتی که  . به منظور اجتناب از مشخص کردن نامعادلات یکسان، حاشیه e از G بعد از محاسبه هر  برداشته می شود.

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

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

4.4 کاهش و افزایش دسته ها

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

و  گراف جهت دار   را ایجاد می کند که توسط  با جایگزین کردن هر گره   با دسته   بدست می آید، که حداقل شامل یک گره می باشد ( از این رو،  ). به عبارت دیگر   به عنوان بخش مناسبی از V می باشد، که در آن مجموعه  منطبق با گره   در  می باشد.

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

در صفحه 73 نشان داده شده است که نامعادله جدید همیشه برای  معتبر می باشد؛ علاوه بر این، اگر نامعادله آغازین  به تعریف   بپردازد، به این ترتیب   بر مبنای جنبه  می باشد.

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

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

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

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

ساده ترین شرایط مربوط به کاهش منحنی I ( یعنی منحنی   با  ) بوده و نیازمند  برای زوج گره   به همراه   می باشد. برای مشاهده صحت این شرایط، فرض کنید  . این نشان می دهد که  ، به نرتیبی که  به عنوان بردار خصوصیات منحنی   بوده، و   به عنوان مضروب اعداد غیرمنفی با   می باشد. در ارتباط با هر  ، ما به تعریف  به عنوان بردار مشخص منحنی   حاصل از   با جایگزین کردن گره   با منحنی   می باشد. به این ترتیب، بر مبنای ساختار،    می باشد، که بر خلاف فرضیه   می باشد.

مشخص شده است که حاشیه 1 با در نظر گرفتن STSP کاهش نمی یابد. به این ترتیب، ATSP دارای ظرافت بیشتری نسبت به STSP می باشد، به این صورت که اطلاعات مرتبط به جهت گیری منحنی منجر به کاهش بیشتر می گردد. در اینجا تفسیر چندوجهی از این عملکردها وجود دارد.

در مشکلات مربوط به جداسازی، نقطه  برای ما مد نظر قرار داده می شود که نامعادله   را با در نظر گرفتن برابری مد نظر قرار داده و آن را از انواع ATSP تفکیک می کند. بحث بالا نشان می دهد که این زمانی امکان پذیر می باشد که  از   جدا شده از این رو F می تواند جایگزین P گردد تا آن جایی که مربوط به   می شود. این ویژگی کلی بوده و در ارتباط با جنبه های غیرتهی F از نوع P به کار گرفته می شود. در واقع فرض کنید  بر مبنای جنبه P بوده که توسط نامعادله   برای P مد نظر قرار داده می شود، و فرض کنید   باشد. اگر   نتواند از F جدا شود، به این ترتیب  ، به این ترتیب همچنین نمی تواند از P جدا شود. بلعکس، فرض کنید نامعادله مشخصی برای  وجود داشته باشد، که F توسط   نقص شده با مقدار   نقص شود. به این ترتیب در ارتباط با مقدار بالای M نامعادله   برای P معتبر بوده، اما توسط   به اندازه   نقص می گردد.

عملکردهای مختلف بین TSP متقارن و نامتقارن دارای ریشه ثابتی از   برای بعضی از منحنی های ATSP بوده که به بازتاب   و نمونه ATSP می پردازد که از طریق پیوند   در راس مجزای حاصل می گردد- به ترتیبی که ساختارهای مشابه عمل نمی کند تا زمانی که ثابت  برای بعضی از STSP های نامشخص مد نظر قرار گیرد. در ارتباط با شرایط چندوجهی ، این بدین معنی می باشد که جنبه F از نوع ATSP تحت تاثیر   قرار گرفته که دارای انطباق 1-1 با گره n-1 می باشد. از این رو در موارد نامتقارن، جنبه F بار دیگر بر مبنای ATSP در گراف کاهشی تفسیر شده ، در حالی که برای STSP تفسیر مشابه امکان پذیر نمی باشد.

در صفحه 306، منحنی 1، این کاهش به شکل تکراری مد نظر قرار می گیرد، به گونه ای که هر مسیر را با یک منحنی توسط یک گره مجزا جایگزین می کند. در نتیجه این فرایند پیش پردازش بر روی  ، تمام متغیرهای غیرصفر به صورت کسری می باشد. توجه داشته باشید که نتایج مشابه در ارتباط با TSP متقارن ایجاد نمی گردد، به صورتی که هر زنجیره توسط یک بخش و نه گره مجزا جایگزین می گردد. روش های کاهشی پیچیده تر در صفحه 306 نشان داده نشده است. بحث های بالا به هر حال موارد دیگری را نیز نشان می دهد که مجموعه S اشباع شده مد نظر قرار می گیرد. برای نمونه فرض کنید سه گره مجزای   و K وجود دارد، به صورتی که   و   و   وجود دارد که  . ادعای ما این است که، در این مورد، مجموعه اشباع شده   می تواند کاهش یابد. در واقع نقطه   نامعادله ATSP یعنی   را مد نظر قرار می دهد، بنابراین از بحث بالا، می توانیم P را با بخش   جایگزین کنیم. اکنون هر نقطه حدی F منطبق با منحنی با استفاده از مسیر  یا  می باشد. این ویژگی باعث ایجاد انطباق 1-1 بین نقاط حدی از F و انواع مربوط به ATSP می گردد که i و j به یک گره مجزا کاهش می یابند.

4.5 قیمت گذاری با توجه به کاهش

قیمت گذاری به عنوان عامل مهمی در کدهای شاخه و برش می باشد، و این امکان را به وجود می آورد تا به شکل موثری به مدیریت مشکلات LP شامل چندین ستون پرداخته شود. فرض کنید

بر مبنای موضوعات LP قابل حل باشد. M بر مبنای ماتریکس   می باشد که ستون های آن توسط منحنی  مد نظر قرار می گیرد. اولین ردیف  از M منطبق با معادله درجه 2-3 می باشد ( با مد نظر قرار دادن منحنی تکراری     می باشد. در حالی که ردیف های باقیمانده، به هر صورتی که باشد، منطبق با بعضی از برش ها ایجاد شده از طریق فرایند تفکیک می باشد. علامت   نشان دهنده   بوده که در ارتباط با اولین ردیف   از M ، و  در ارتباط با ردیف های باقیمانده می باشد. فرض کنید   نشان دهنده مدخل M با ردیف h و ستون   می باشد.

برای پایین نگه داشتن اندازه LP ، طرح قیمت گذاری زیر معمولا مورد استفاده قرار می گیرد. ما چندین مجموعه از منحنی برای مثال   را مد نظر قرار می دهیم و موقتا ثابت  را برای تمام   مد نظر قرار می دهیم. سپس به حل مسئله LP محدود شده می پردازیم

که در این فرمول   و   حاصل   و M می باشد که تمام این مدخل ها توسط   کنار گذاشته می شوند.

فرض کنید که فرمول 17 محتمل بوده، و فرض کنید که   و  ، بر مبنای شرایط اصلی و راه حل های دوگانه مبنا باشد. مشخصا  و به این ترتیب ما در یک شرایط قابل قبول قرار می گیریم که باعث تضمین   شده، بنابراین، اثبات می شود که  ( به همراه   برای تمام   به عنوان راه حل بهینه برای فرمول 16 می باشد، و اینکه مقدار   به عنوان کران پایین تر  می باشد. در مورد این هدف ما به محاسبه هزینه کاهشی LP با در نظر گرفتن   می پردازیم، برای مثال   و نشان می دهیم که آیا  به صورت   می باشد. اگر مورد به همین شکل باشد، داریم   و کار به این شکل انجام می گیرد. به عبارت دیگر، مجموعه کنونی   با افزودن منحنی با هزینه های کاهشی منفی مد نظر قرار گرفته و کل روش ها تکرار می گردد. این راه حل تکراری 17، به دنبال بروزرسانی   مد نظر قرار گرفته، که معمولا به نام گردش قیمت می باشد.

بر طبق به تجارب محاسباتی معمول، اولین تکرار گردش قیمت تعداد زیادی از ستون های جدید را نسبت به LP مد نظر قرار داده به صورتی که ف و این به دلیل  کاهش اولیه (17) می باشد.

برای توضیح این عملکرد، شرایطی را در نظر بگیرید که LP اول در گره ریشه درخت شاخه ای حل می گردد. در این مورد (16) شامل معادله درجه   می باشد، از این رو راه حل بهینه   به طور کارآمدی از طریق کد AP محاسبه می شود. اکنون فرض کنید که ما مجموعه مرکزی   را برای مد نظر قرار دادن منحنی n که در راه حل های بهینه AP انتخاب می شود کار خود را آغاز می کنیم. برای مد نظر قرار دادن مبنای LP، ما منحنی دیگر   را برای A مد نظر قرار می دهیم، که برای تعیین ماتریکس غیرمجزای    از M انتخاب می گردد. بر مبنای ساخت، مسئله 17 دارای راه احتمالی منحصر به فردی می باشد- برای مثال، بردار راه حل AP بهینه مد نظر قرار می گیرد- از این رو می دانیم که  در این موارد مد نظر قرار می گیرد. به این ترتیب در مورد انتخاب های اشتباه منحنی  در مجموعه اصلی، راه حل  برای فرمول 16 امکان پذیر می باشد، یعنی تعداد زیادی از هزینه های   به صورت منفی می باشد. تکرار این روش قیمت گذاری معمولا قبل از قیمت گذاری صحیح منحنی ها مورد نیاز می باشد.

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

در مرحله بعد ما به شرح تکنیک های مختلف که به نانم قیمت گذاری AP در صفحه 306 می باشد، می پردازیم، که این شرایط قیمت گذاری با کاربرد این فرایند تقویت می گردد که هر راه حل احتمالی برای فرمول 16 نمی تواند به انتخاب منحنی با مد نظر قرار دادن کاهش هزینه به روش دلخواه بر مبنای معادله مدرج- در بین محدودیت های دیگر انتخاب شده و به اجرا در آید. این تکنیک به نام قیمت گذاری لاگرانژی می باشد که به طور مستقل توسط لوبل به عنوان یک روش قدرتمند برای حل مسئله زمان بندی مسیر در مقیاس بالا معرفی می شود.

روش دو گانه   در ارتباط با فرمول 17 را به عنوان بردار چندگانه لاگرانژی در نظر بگیرید، و کاهش هزینه LP ،   بر مبنای هزینه منطبق با لاگرانژی می باشد. به این ترتیب قیمت گذاری استاندارد شامل حل فرمول زیر می باشد.

که در این فرمول   بر مبنای دوگانگی LP می باشد. بنابراین داریم   که در این مورد   عبارتست از   یعنی  . این روش تقویتی شامل جایگزینی شرط    در فرمول 18 توسط

  می باشد

به این ترتیب ما به محاسبه کران پایین  می پردازیم.

که در این فرمول  با حل کردن   بر مبنای هزینه لاگرانژی   بدست می آید. به این ترتیب  ، از این رو  نشان می دهد  . به ترتیبی که   می باشد، می بایست این مراحل را تکرار کرد، بعد از اینکه به مجموعه   اضافه شد، منحنی  در روش های AP بهینه انتخاب می گردند.

روش جدید دارای دو مزیت می باشد، که عبارتند از 1) بررسی های بهبود یافته برای  ، و 2) قوانین بهتر برای انتخاب منحنی که به مجموعه منحنی اصلی افزوده می گردد. علاوه بر این   همیشه کران پایین تری را در مورد Z ایجاد می کند که در بعضی از موارد در درک گره های شاخه ای موجود مد نظر قرار می گیرند حتی زمانی که  . در نهایت، هزینه های AP منفی بردار هزینه   را بعد از حل  کاهش داده و برای ثابت   استفاده می گردد به این ترتیب   به گونه ای که  حداقل بزرگتر از میزان راه حل شناخته شده ATSP می باشد.

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

قیمت گذاری AP نیازمند محاسبه تمام هزینه های کاهشی، برای مثال، از طریق طرح ردیفی می باشد. ما   را برای تمام   مد نظر قرار داده، و سپس در این توالی ردیف های h از M به همراه  مد نظر قرار داده می شود. در ارتباط با هر یک از این ردیف های h ما به تعیین مجموعه    پرداخته، و   را به روز می کنیم. بر مبنای ساختارهای ترکیبی ساده اکثر برش ها، ساختار نامشخص   معمولا در زمان   به اجرا در آمده، از این رو کل زمان سپری شده برای محاسبه هزینه های کاهشی برابر با   برای ارزش دهی بوده، به علاوه   در ارتباط با کاهش هزینه واقعی مد نظر قرار می گیرد.

یکی از موانع قیمت گذاری AP زمان سپری شده محاسبه برای راه حل AP می باشد، که به طور قابل توجهی از طریق استراتژی زیر کاهش می یابد. بعد از هر راه حل LP ما به محاسبه هزینه کاهشی   پرداخته و به تعیین پیوستگی   می پردازیم. اگر   باشد، ما از این چرخه قیمت گذاری استفاده می کنیم. اگر  ، ما از قیمت گذاری استاندارد استفاده می کنیم.  یعنی، ما  را بروز کرده و آن را تکرار می کنیم. اگر   باشد، ما به سمت قیمت گذاری AP بر می گردیم، و به حل مسئله AP بر مبنای هزینه کاهشی می پردازیم. ما همچنین به تعیین مجموعه منحنی Q که شامل منحنی   می باشد پرداخته و مبنای LP را برای این مشکلات AP تعیین می کنیم، و همچنین به محاسبه هزینه های کاهشی   برای تمام   می پردازیم.

سپس ما از Q تمام منحنی هایی که قبلا در   وجود داشته حذف کرده و Q را با افزودن تکرار منحنی در  مد نظر قرار می دهیم که   بوده، تا زمانی که هیچ منحنی وجود نداشته، یا   باشد. به این ترتیب Q شامل تعداد قابل توجهی از منحنی هایی می باشد که احتمالا در فرمول 16 مد نظر قرار می گیرند. ما در نهایت   را بروز کرده، و  را تکرار کرده یا   را از چرخه قیمت خارج می کنیم.

4.6 الگوریتم کلی

الگوریتم به عنوان روش شاخه و برش درجه پایین می باشد. که در هر گره از این شاخه ها، بازسازی LP با مد نظر قرار دادن تمام محدودیت های موجود در LP نهایی که در گره اصلی حل می گردد، شروع به کار می کند. در ارتباط با این متغیرها، مواردی از فایل های مخدوش شده در ارتباط با مبنای بهینه با مد نظر قرار دادن LP در گره اصلی بوده و مجموعه متغیرهای اصلی را مشخص می کند.   با مد نظر قرار دادن تمام منحنی ها متعلق به این مبنا می باشد ( در ارتباط با گره ریشه،  شامل متغیرهای   در مبنای بهینه AP بوده که با حل AP در ارتباط با هزینه اصلی  ایجاد می گردد). علاوه بر این   شامل تمام منحنی های شناخته شده راه حل ATSP می باشد. با مد نظر قرار دادن مبانی پیشرفته بالا، یک تکرار به حل LP موجود پرداخته، و از روش قیمت گذاری AP استفاده می کند که در بخش 4.5 نشان داده شده و در صورت نیاز تکرار می شود. توجه داشته باشید که روش قیمت گذاری و تثبیت بعد از هر راه حل LP مد نظر قرار گرفته می شود.

در مورد خروج چرخه قیمت گذاری، برش هایی که مرتبط به این شرایط می باشند فراتر از 0.01 بوده و از LP کنونی کنار گذاشته شده، و بر این اساس مبنای LP بروز می گردد. علاوه بر این الگوریتم جدا کننده برای یافتن نامعادله ATSP که باعث کاهش راه حل بهینه LP کنونی می گردد، برای مثال   به کار گرفته می شود. بر مبنای قوانین ذهنی برش های مورد نظر با توجه به میزان خطا کمتر از 0.1 کنار گذاشته می شوند، و مرحله جداسازی به محض اینکه   برش مد نظر قرار می گیرد، قطع می شود.

یکی از موارد در ارتباط با خطای برش در زمان پردازش گره های قبلی یا کنونی ایجاد می گردد، که تمام آن ها در ساختار اطلاعات جهانی به نام مجموعه محدودیت ها ذخیره می شوند. اگر بعضی از این برش ها توسط  مد نظر قرار نگیرد، فاز جداسازی پایان می یابد. علاوه بر این الگوریتم  پادبرگ- رینالدی برای جداسازی SEC به کار گرفته می شود. و فاز جداسازی قطع می گردد اگر SEC های خطا ایجاد گردند. زمانی که به این صورت نباشد، کاهش مسیر منحنی 1 از   مد نظر قرار می گیرد، و الگوریتم جداسازی را برای جستجو،   و   و نامعادله CAT بکار گرفته می شود. به منظور اجتناب از نامعادلات ، نامعادله   هرکز تفکیک نمی گردد و جداسازی CAT زمانی متوقف می شود که جستجوی خطا مد نظر قرار گیرد. زمانی که این برش ها مد نظر قرار گیرند، مواردی در ارتباط با LP افزوده شده و تکرار می گردد.

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

بر مبنای قانون کاهشی غیرمستدل، این شاخه بندی ها انجام می گیرد زمانی که   به صورت کسری از این موارد بوده و کران پایینی در تکرار 5 LP/ قیمت گذاری/ جداسازی افزایش نمی یابد.

الگوریتم ذهنی ساده برای بروز کردن بهترین راه حل ATSP بهینه بکار گرفته می شود. این الگوریتم بر مبنای اطلاعات مربوط به LP کنونی بوده، و شامل برشماری کاملی از سیکل جهت دار هامیلتون در گراف پشتیبانی شده   می باشد، که به صورت   تعریف می گردد. به این منظور الگوریتم شمارشی HC مارتلو در صفحه 585 ، با توجه به  مرحله برگشتی نشان داده می شود.  چون  معمولا پراکنده می باشد، این کرت بالا بر مبنای برگشتی به سختی بدست آمده و HC اغلب موارد در تکمیل این شمارش ها در زمان محاسبه کوتاه مد نظر قرار می گیرد. این موارد ذهنی زمانی به کار گرفته می شود که تفکیک SEC مد نظر نبوده، به این ترتیب  به شدت مرتبط می باشد.

5.  بررسی های محاسباتی

الگوریتمی که در بخش قبلی توصیف شده است بر مبنای محاسباتی در مجموعه بزرگی از نمونه های ATSP مد نظر قرار می گیرد:

- 42 نمونه توسط سراسلا، جانسون، مک گوچ و ژانگ؛ نمونه ها در این مجموعه به صورت تصادفی برای مد نظر قرار دادن کاربردهای واقعی که در زمینه های مختلفی می باشد، ایجاد می گردد.

- 5 نمونه زمان بندی شده توسط بالاس مد نظر قرار می گیرد

- 2 نمونه حقیقی دیگر عبارتند از (  و  )؛

- 10 نمونه تصادفی که هزینه های واقعی آن در محدوده یکپارچه مد نظر قرار می گیرد.

- تمام 27 نمونه ATSP در   نشان داده می شود.

برای توضیح مفصل 42 نمونه اول خواننده به صفحه 200 ارجاع داده می شود، در حالی که جزییات مربوط به   در صفحه وب مربوطه نشان داده می شود.

5 نمونه مورد نظر بالاس توسط ویدجت مد نظر قرار داده می شود، که مولدهای مربوط به نمونه های واقعی توسط صنعت شیمی توسط دونالد میلر ایجاد می گردد. نمونه   نشان دهنده تحویل محصولات دارویی در بخش تجاری بلونیا بوده و از نمونه   حاصل می گردد  با مد نظر قرار دادن 10 راس اضافی در نموداری که نشان دهنده مرکز بلونیا می باشد، حاصل می گردد. سرانجام اینکه نمونه   بر مبنای مشکلات واقعی می باشد که در کاربردهای مسیریابی مد نظر بوده که توسط کاسگارد مد نظر قرار می گیرد.

تمام نمونه ها دارای هزینه های غیرمنفی یکپارچه ای بوده، و بر مبنای درخواست محقق در دسترس قرار می گیرند. در ارتباط با هر نمونه ما در جدول 4.1 مواردی را همچون، نانم، اندازه، راه حل بهینه، و منبع نمونه مد نظر قرار می گیرد.

کدهای ATSP خاص تست می گردند: 1) کد CDT شاخه و کران بر مبنای AP که در بخش 2.1 نشان داده می شود؛ 2) کد FT-ADD که منطبق با رویکرد افزوده توصیف شده در بخش 3 بوده؛ و 3) کد  ، که منطبق با الگوریتم شاخه و برش توصیف شده در بخش 4 می باشد.

علاوه بر این، کدهای شاخه و برش مورد قبول اپل گیت، بیکس بای، چاتال و کوک مد نظر قرار می گیرد، که در فصل 2 توصیف شده است. این کد برای TSP متقارن مشخص بوده، به این ترتیب، نمونه های متقارن از طریق یکی از روش های برگشتی زیر ایجاد می گردند:

-  تغییرات مربوط به 3 گره توسط کارپ مد نظر قرار گرفته است. گراف غیر جهت دار کامل با راس 3n حاصل گراف جهت دار کامل می باشد که دو کپی به ان اضافه می گردد،   و   از راس  ، و توسط i) تعیین هزینه   و   در ارتباط با هر  به اندازه 0. Ii) تعیین ارزش   به   و iii) تعیین هزینه موارد باقیمانده به  .

- تغییرات دو گره که توسط جانکر و ولگنانت مطرح شده ( همچنین نظرات جانگر، رینلت، و رینالدی را مشاهده کنید). یک نمودار غیر جهت دار کامل با راس 2n حاصل موارد کامل مستقیم با افزودن یک کپی  از هر راس  بوده و i) ارزش این حاشیه ها   برای هر  به صفر می رسد، ii) هزینه هر یک از بخش های  به  می رسد، به ترتیبی که M بر مبنای ارزش مثبت می باشد. ارزش رو به تغییر   از هزینه مطلوب STSP کم می گردد.

تمام این تست ها بر مبنای آلفای دیجیتال 533MHZ با 512 مگابایت حافظه RAM بر مبنای سیستم عامل یونیکس با6.5.3  بر مبنای حل کننده LP می باشد. در تمام این جداول، ما درصدهایی را نشان می دهیم که منطبق با کران پایینی در گره ریشه، کران پایین نهایی، و کران بالای نهایی می باشد که تمام آن ها با توجه به مقدار راه حل بهینه محاسبه می شود.

جدول 4.1 نمونه های ATSP

علاوه بر این تعداد گره های درخت جستجو، و زمان محاسبه به ثانیه داده می شود.

5.1 تنظیم کد

در این بخش ما به تجزیه و تحلیل کدها به هدف تصمیم گیری می پردازیم، برای هر کد، بهترین عملکرد میانگین وجود دارد.

کد CDT.

هیچ تغییر خاصی در ارتباط با این کد به اجرا گذاشته نمی شود.

کد  . اجرای موارد اصلی رویکرد کران پایین را مد نظر قرار می دهد. به گونه ای که در کد CDT، عملکرد بهبود یافته الگوریتم کلی با استفاده از ارتباط ذهنی کارپ بدست آمده، و عملیات ادغام زیرشاخه ها در بخش 2.1.3 توضیح داده می شود. این منحر به کاهش گره های شاخه یا و کل زمان محاسبه می گردد؛ به طور خاص، نمونه های  و   توسط کد اصلی در محدوده زمانی 1000 CPU ثانیه حل نمی گردد.

کد  . یک معیار جدید شاخه بندی، به نام پایداری به شکل کسری (FP) مورد آزمایش قرار می گیرد. به طور کلی، معیار FP اولویتی را برای شاخه بندی برای متغیرهایی می دهد که به طور مشخص در راه حل بهینه LP در گره شاخه بندی کنونی مد نظر قرار می گیرند. این استراتژی کلی مطرح شده و در صفحه 298 به طور محاسباتی مورد تجزیه و تحلیل قرار گرفته است. جدول 4.2 به مقایسه کدهای تغییر یافته و اصلی بر روی مجموعه مرتبط با نمونه ها می پردازد به صورتی که محدودیت زمانی 10000 CPU در ثانیه را شامل می گردد. بر طبق به این نتایج، معیار FP از موقعیت های آسیب شناختی به دلیل شاخه بندی اجتناب کرده و کدهای قوی تری را مد نظر قرار می دهد.

کد تطبیقی. این کدها با پارامتر پیش فرض از طریق تنظیم پارامتر تصادفی   مد نظر قرار می گیرد به گونه ای که هر یک از دستورات را به اجرا در می آورد. هر دو مورد   از طریق تحمیل کردن محدوده زمانی 1000 CPU در ثانیه مد نظر قرار می گیرد. در ارتباط با دو گره انتقالی، پارامتر M به اندازه 1000000 می باشد ( اما برای نمونه هایی با n= 1000 و برای نمونه  ، که ما از  استفاده می کنیم تا از مشکلات عددی استفاده کنیم). مقایسه نتایج حاصله از این انطباق گشتار در جدول 4.3 داده شده است، به ترتیبی که نمونه های یکسان از جدول 4.2 مد نظر قرار می گیرد. بر طبق به این نتایج هیچ برتری بین این دو گشتار بدون توجه به کیفیت کران پایین در گره ریشه و نه زمان محاسبه وجود ندارد.

جدول 4.8  با در نظر گرفتن و بدون در نظر گرفتن ثبات ( 10000 ثانیه محدودیت زمانی)

به هر حال با مد نظر قرار دادن عملکرد میانگین، دو گره متغیر قابل قبول می باشد.

اگرچه تنظیم این پارامترهای انطباقی خارج از محدوده این بخش می باشد، جدول 4.3 به تجزیه و تحلیل حساسیت کد نسبت به پارامترهای با اندازه کمتر می پردازد، که به کنترل اجرای الگوهای برش محلی به منظور جداسازی می پردازد. به طور خاص، تنظیم این اندازه به صفر  ایجاد برش های محلی را از بین برده و این امکان را به وجود می آورد که بر مبنای کد STSP عمل کنند، به صورتی که گزینه   و  امکان ایجاد برش های دیگر را بر مبنای راه حل های خاص بر روی زیرمجموعه رئوس به اندازه های بالاتر از 16 و 24 به ترتیب به وجود می آورد.

حدول 4.3  حساسیت تغییر انطباق گره 3 و 2 به نسبت پارامترهای مشخص.

به این ترتیب، ما به تجزیه و تحلیل قابلیت روش برش محلی برای ایجاد اتوماتیک برش ها می پردازیم، که نقش مهمی را برای حل نمونه ATSP ایفا می کند. نتایج مربوط به جدول 4.3 نشان می دهد که برش های محلی نقش مهمی را ایفا کرده، و این امکان را ایجاد می کنند تا به صورت بهینه نمونه های مشکل حل گردند ( برای مثال نمونه های  ،   و   توسط مقادیر برابر با 16 حل می گردند، و موارد باقیمانده بدون برش های محلی حل نمی گردند). جای تعجب نیست که نگرانی اصلی در ارتباط با نمونه های تصادفی یکپارچه می باشند. در بین این اندازه ها، حتی بعد از تغییر دو گره، بهترین انتخاب به صورت پیش فرض می باشد، که انطباقی را بین موارد بالاسری تفکیک شده و فرایندهای کران پایین ایجاد می کند. ما همچنین به تست اندازه قطعات 8 و 32 بدون کسب نتایج بهتر می پردازیم. . ( تغییر سه گره، عملکردهای مشابه را نشان می دهد.)

5.2 مقایسه کد

مقایسه چهار الگوریتم، به نام های  ،   و موارد منطبق، در جدول   و  در ارتباط با مجموعه کاملی از 86 نمونه داده می شود. در ارتباط با محدودیت زمانی، ما 1000CPU ثانیه را برای CDT و  ، و 1000CPU ثانیه را برای   و   در نظر می گیریم. محدودیت زمانی کوچکتر که به دو الگوریتم اول داده می شود انتخاب می گردد تا شاخه های جستجوی مورد نظر را به شکل قابل قبول مد نظر قرار داده، اما مقایسه را با الگوریتم های دیگر تحت تاثیر قرار نمی دهد: بر طبق به بررسی های مقدماتی در ارتباط با بعضی از نمونه ها، روش شاخه و کران نمونه هایی را با 1000CPU ثانیه حل کرده و فاصله نهایی آنقدر زیاد می باشد تا همگرایی در 10000 ثانیه ایجاد گردد.

در ارتباط با کران پایین تر در گره ریشه، جداول نشان می دهند که روش افزوده به طور قابل توجه نتایج بهتری را نسبت به کران پایین AP نشان می دهند، اما این دو مورد توسط روش برش صفحات مد نظر قرار می گیرند. در نسخه STSP کنونی، کدهای  گره ریشه کران پایین را بدست می آورند که توسط  حاصل می گردد، و به این ترتیب کارایی مورد نظر ATSP را در نسخه اصلی نشان می دهد. البته، می توان انتظار بهبود عملکرد   را با به کارگیری رده های اضافی برش های خاص ATSP همانند نامعادلات سیکل  که در فصل 3 توصیف شده است بپردازیم.  در ارتباط با  ، مشاهده می کنیم که استفاده از برش های محلی، منجر به بهبود قابل توجه کران پایین گره ریشه می گردد. جای تعجب نیست که این موارد بهبود یافته بدوره گرد مهمتر از موارد مربوط به نمونه های   می باشد. طبق نظر ما، این مورد نشان دهنده اهمیت بکارگیری ساختار مشکلات عدم تقارن اصلی بوده، که منجر به ساخت موارد مشابه STSP می گردد که معمولا توسط برش های دسته   مد نظر قرار نمی گیرد.

جدول 4.4 مقایسه کدهای شاخه و کران. محدودیت زمانی 1000 ثانیه

به موجب زمان محاسبه کلی، در ارتباط با بیشتر نمونه های تصادفی، کارآمدترین کد CDT می باشد که به خوبی بر روی نمونه های   و   کار می کند.   به طور متوسط دارای عملکرد بهتری از CDT می باشد ( باعث بهینه سازی در 1000 CPU در ثانیه، 8 نمونه دیگر) می گردد، ولی به هر حال به عنوان 4 کد برتر بر روی نمونه ها نمی باشد.

کدهای  و   به طور کلی، به عنوان بهترین روش بوده، که کد اول همیشه سریعتر از کد دوم می باشد، بنابراین  جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.