Изменения

Перейти к: навигация, поиск
Задачи
:<math>\sum^{N-1}_{i=1} d(C_{\pi(i)},C_{\pi(i+1)})+d(C_{\pi(N)},C_{\pi(1)})</math>
Для того, чтобы объектизировать эту задачуПрименяя к этой задаче мультиобъктивизацию, нам необходимо определить нужно разбить её на подзадачи. TSP &ndash; является <math>NP</math>-сложной именно потому, что нет хорошего разложения этой задачи.Тем не менее задачу можно разбить на две или больше подтуров, каждый из которых мы можем минимизировать. Представим подтуры в виде двух городов. Тогда наша задача примет вид:
Разобьём задачу таким образом:
:<math>minimize\{f(\pi,a,b) = (f_1(\pi,a,b),f_2(\pi,a,b))\}</math>
::'''where'''<math>f_1(\pi,a,b)=\sum^{\pi^{-1}(b)-1}_{i=\pi^{-1}(a)} d(C_{\pi(i)},C_{\pi(i+1)})</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> &ndash; два города, указанных ''априори''. Если <math>\pi (a) < \pi (b)</math>, меняем их местами.
Предполагается, что <math>a</math> и <math>b</math> выбраны произвольно.
Анонимный участник

Навигация