Изменения
→Задачи
Формулируется задача следующим образом:
Задано <math>C=\{c_1,c_2,\dots,c_N\} </math>- множество городов и для каждой пары <math>\{c_i,c_j\}</math> задано расстояние. Наша цель - – найти цепь из городов, минимизирующую величину:
:<math>\sum^{N-1}_{i=1} d(C_{\pi(i)},C_{\pi(i+1)})+d(C_{\pi(N)},C_{\pi(1)})</math>
Для того, чтобы объектизировать эту задачу, нам необходимо определить подзадачи. TSP - – является <math>NP</math>-сложной именно потому, что нет хорошего разложения этой задачи.
Разобьём задачу таким образом:
::'''and''' <math>f_2(\pi,a,b)=\sum^{N-1}_{i=\pi^{-1}(b)} d(C_{\pi(i)},C_{\pi(i+1)}) + \sum^{\pi^{-1}(a)-1}_{i=1} d(C_{\pi(i)},C_{\pi(i+1)}) </math> <math>+ d(C_{\pi(N)},C_{\pi(1)})</math>,
где <math>a</math> и <math>b</math> - – два города, указанных ''априори''.
Предполагается, что <math>a</math> и <math>b</math> выбраны произвольно.
