3-опционный код оптимизации для TSP
У меня есть этот код (проблема TSP), который работает для оптимизации с 2 опциями, и я хотел бы изменить его для оптимизации с 3 опциями. Я знаю, что должен добавить для, но на самом деле не понимаю диапазон третьего для. Вы можете мне помочь?
double bestDecrement = tsp.infinite;
// intial and final position are fixed (initial/final node remains 0)
for ( uint a = 1 ; a < currSol.sequence.size() - 2 ; a++ )
{
int h = currSol.sequence[a-1];
int i = currSol.sequence[a];
for ( uint b = a + 1 ; b < currSol.sequence.size() - 1 ; b++ )
{
int j = currSol.sequence[b];
int l = currSol.sequence[b+1];
double neighDecrement = - tsp.cost[h][i] - tsp.cost[j][l] + tsp.cost[h][j] + tsp.cost[i][l] ;
if ( neighDecrement < bestDecrement )
{
bestDecrement = neighDecrement;
move.from = a;
move.to = b;
}
}
}
Решение
В основном вы ищете 3 края, чтобы удалить, а затем снова вставить. Так, например:
for ( uint a = 1 ; a < currSol.sequence.size() - 3 ; a++ )
...
for ( uint b = a + 1 ; b < currSol.sequence.size() - 2 ; b++ )
...
for ( unit c = b + 1 ; c < currSol.sequence.size() - 1 ; c++)
...
Более сложная часть заключается в определении новых затрат, поскольку существует несколько выполнимых повторных вставок (в отличие от одной из двух опций).
Другие решения