Как работает линейный поиск с 2,5 оптами для TSP?

Я понимаю логику выполнения попарного обмена с двумя вариантами, чтобы два ребра не пересекались:

Просто выньте два края и замените их двумя другими. Если у вас есть список городов:

A, B, C, D, E, A, и AB и DE выбраны... тогда просто измените порядок городов между B и D так:

A, E, B, C, D, A

Для 3-opt аналогично, я тоже понимаю, что учитывая A,B,C,D,E,F,A, возможны два изменения. Например, если выбраны AB, CD и EF, то:

A,C,B,E,D,F,A и A,E,D,B,C,F,A — это варианты туров с тремя вариантами выбора.

Однако что такое 2.5 opt и как его реализовать? Я пытался найти информацию об этом, но я не понимаю большую часть того, что я нашел...


algorithm traveling-salesman
person u3l    schedule 18.01.2014    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Документ на http://www.staff.uni-mainz.de/schneidj/papers/gestatten.pdf кажется достаточно ясным.

В разделе 2.2 описывается вставка узла, которая вырезает узел из тура и вставляет его обратно между двумя другими узлами, которые ранее шли один за другим (есть также изображение этого).

Раздел 2.3 описывает 2-opt, который, я думаю, вы понимаете.

Раздел 2.5 описывает 3-opt и приводит некоторые статистические данные о нем. В самом конце этого раздела показано, что вставку узла можно рассматривать как частный случай этого, с несколько иной статистикой, и что по этой причине вставку узла иногда называют 2.5-opt. Как и 3-opt, он обрезает три ссылки, но, как и 2-opt, таких ходов может быть около O(N^2).

В случае, если ссылка снова не работает, ссылка будет следующей:

О структуре соседства задачи коммивояжера, порожденной локальными поисковыми ходами Гюнтер Штаттенбергер · Маркус Данкесрайтер · Флориан Баумгартнер · Йоханнес Дж. Шнайдер

person mcdowella    schedule 18.01.2014
comment
Запрещен доступ к этой бумаге. - person nbro; 01.11.2016
comment
У меня тоже ссылка не работает - поиск в Интернете подсказывает, что вы можете получить копию с сайта local-search-moves" rel="nofollow noreferrer"> Thirdworld.nl/ - person mcdowella; 01.11.2016