Amaliy matematika va informatika” yo’nalishi 18. 08-guruh talabasi Topvoldiyev Muslimjon Muxtorjom o’g’lining

II BOB AMALIY QISM

2.1 Krestofides algoritmi kelib chiqishi

Krestofides algoritmi 1976 – yili Nekos Chrestofides tomonidanfanga kiritilgan, bu algoritm yordamida komivoyajer va TSP (Traveling Salesman Problem - sayyohlik muammosi) masalasiga yechim topishga yordam beradi. Kristofidlar algoritmining taxminiy nisbati 3/2 ga yaqin bo'lgan o'z echimini topishga olib keladigan sayohatchilar muammosiga kirishlar mavjud. Kirishlar biri bunday sinf bir tomonidan tashkil qilingan yo'lda bir n og'irligiga ega yo'l qirralarning bilan, uchlari 1 birgalikda og'irligi yo'lida ikki qadam-biridan burchaklar bog'lovchi tomonlarining majmui bilan, 1 + ε bir qator uchun e nolga yaqin tanlagan, lekin ijobiy. To'liq grafikning qolgan barcha qirralari ushbu subgrafdagi eng qisqa yo'llar bilan berilgan masofalarga ega . Bu holda n - 1 uzunligi bo'yicha daraxtning minimal uzunligi yo'l orqali beriladi, va ikkita ikkita tog 'cho'qqisi - bu yo'lning so'nggi nuqtalari, ularning mukammal mos kelishi taxminan n / 2 ga teng bo'lgan bitta qirradan iborat . Daraxt va mos keladigan birlashma - bu sikl, unda hech qanday yorliqlar bo'lmaydi va og'irligi taxminan 3 n / 2 . Biroq, optimal yechim og'irligi qirralarning foydalanadi 1 + ε ikki weight- bilan birga 1 yo'lining so'nggi nuqta chekka voqea va umumiy og'irligi (+ 1 ε () n - 2) + 2 , yaqin n kichik ε qiymatlari . Shunday qilib, biz 3/2 ga yaqinlashamiz.