Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Саудагердің саяхаттау мәселесіне жуықтау Кристофид алгоритмі немесе Кристофид–Сердюков алгоритмі – саяхатшы сатушы мәселесіне шамамен шешімдер табуға арналған алгоритм, қашықтықтар метрикалық кеңістік құрайтын жағдайларда (олар симметриялық және үшбұрыш теңсіздігін қанағаттандырады). Бұл алгоритм оның шешімдері оңтайлы шешім ұзындығының 3/2 есесінен аспайтынын кепілдейді және Никос Кристофид пен Анатолий И. Сердюковтың есімімен аталады; соңғысы оны 1976 жылы тәуелсіз түрде ашқан (бірақ жарияланым 1978 жылы жарық көрген).
Approximation for the travelling salesman problem
The Christofides algorithm or Christofides–Serdyukov algorithm is an algorithm for finding approximate solutions to the travelling salesman problem, on instances where the distances form a metric space (they are symmetric and obey the triangle inequality). It is an approximation algorithm that guarantees that its solutions will be within a factor of 3/2 of the optimal solution length, and is named after Nicos Christofides and Anatoliy I. Serdyukov (Анатолий Иванович Сердюков); the latter discovered it independently in 1976 (but the publication is dated 1978).
Алгоритм
1=G = (V,w) – саяхатшы сатушы мәселесінің мысалы. Яғни, G – V нүктелері жиынтығындағы толық граф, ал w функциясы G графының әрбір қабырғасына теріс емес нақты салмақ тағайындайды. Үшбұрыш теңсіздігіне сәйкес, кез келген үш u, v және x нүктесі үшін w(uv) + w(vx) ≥ w(ux) орындалуы керек. Ал алгоритмді псевдокод түрінде келесідей сипаттауға болады.
Let 1=G = (V,w) be an instance of the travelling salesman problem. That is, G is a complete graph on the set V of vertices, and the function w assigns a nonnegative real weight to every edge of G.
According to the triangle inequality, for every three vertices u, v, and x, it should be the case that w(uv) + w(vx) ≥ w(ux). Then the algorithm can be described in pseudocode as follows.
Мысал
Берілген: шеттері үшбұрыш теңсіздігіне бағынатын толық граф.
Минималды жайылма ағашты (T) есептеу.
T-де тақ дәрежелі төбелердің (O) жиынын есептеу.
O төбелерін ғана пайдаланып G графигінің кіші графигін құру.
Бұл кіші графикте минималды салмақты толық сәйкестікті (M) құру.
Сәйкестік M және жайылма ағаш T ∪ M біріктіріліп, Эйлер мультиграфы құрылады.
Эйлер айналысын есептеу.
Мысалы, айналыс A > B > C > A > D > E > A болуы мүмкін. Сондай-ақ A > B > C > A > E > D > A да жарамды.
Қайталама төбелерді жойып, алгоритмнің нәтижесін алу.
Егер балама айналыс қолданылса, C-ден E-ге дейінгі қысқа жол пайда болар еді. Егер бұл Эвклид графигі болса, онда бұл (A > B > C > E > D > A) қысқарақ болар еді, себебі A > B > C > D > E > A жолының кесісетін түзулері бар, және осының нәтижесінде бұл ең қысқа жол емес екені дәлелденген.
Given: complete graph whose edge weights obey the triangle inequality Calculate minimum spanning tree T Calculate the set of vertices O with odd degree in T Form the subgraph of G using only the vertices of O Construct a minimum weight perfect matching M in this subgraph Unite matching and spanning tree T ∪ M to form an Eulerian multigraph Calculate Euler tourHere the tour goes A >B >C >A >D >E >A. Equally valid is A >B >C >A >E >D >A. Remove repeated vertices, giving the algorithm's output. If the alternate tour would have been used, the shortcut would be going from C to E which results in a shorter route (A >B >C >E >D >A) if this is an euclidean graph as the route A >B >C >D >E >A has intersecting lines which is proven not to be the shortest route.