Табу поиска пример вопроса

Question

Не могли бы вы помочь мне понять этот пример поиска на странице Табу 7:

TS - метод математической оптимизации, относящийся к классу траекторных методов. Поиск по Tabu повышает производительность метода локального поиска за счет использования структур памяти, которые описывают посещаемые решения: после определения потенциального решения оно помечается как "taboo" ("tabu" - это другое написание одного и того же слова), так что алгоритм не посещает эту возможность повторно. Табу поиска приписывают Фреду У. Гловеру

Я не понимаю, почему верхний треугольник используется, и почему это:

Структура табу теперь показывает, что изменение позиций модулей 4 и 5 запрещено в течение 3 итераций. Самый лучший ход на этом шаге - поменять местами 3 и 1 для усиления 2.

Не могли бы вы объяснить, почему треугольник и почему это вышеупомянутое утверждение?

???

Answer 1

Заявление

В примере с PowerPoint они выбрали продолжительность 3. Каждый раз, когда делается один своп, это будет табу на следующие 3 хода.

Вот почему на шаге 1 (примечание: я начинаю с шага 0) у вас есть следующее утверждение:

Структура табу теперь показывает, что изменение позиций модулей 4 и 5 запрещено в течение 3 итераций. Самый лучший ход на этом шаге - поменять местами 3 и 1 для усиления 2.

Поменять местами 3 и 1 на этом шаге - лучший ход для увеличения стоимости.

После вашего последнего шага (шаг 3) они фактически меняются местами 4 и 5, даже если это табу из-за критерия стремления. (20 > 18, что является лучшим значением на данный момент).

Треугольник

Представление представляет собой треугольник, потому что манипуляция с обменом является симметричной. Таким образом, вам не нужно больше, чем верхний треугольник для представления вашей структуры табу.

В каждой ячейке структуры табу у вас есть оставшийся срок владения (длительность, оставшаяся для перехода, который будет табу) пары (x,y) = (y,x).

Я не знаю много о поиске табу, но я надеюсь, что это поможет.