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

Актуальность и цели. В задачах дискретной оптимизации мы рассматриваем алгоритмы решения, основанные на расширениях метода ветвей и границ. Сами эти расширения заключаются в совместной работе нескольких вспомогательных эвристических алгоритмов, и они могут быть отнесены к разным, причем независимым друг от друга, областям искусственного интеллекта. Поэтому актуальность исследования обеспечивается как предметными областями, так и алгоритмами - исследованием совместной работы разных вспомогательных алгоритмов, относящихся к различным областям искусственного интеллекта. Целью работы является дальнейшее описание применения кластеризации ситуаций в методе ветвей и границ на примере задачи коммивояжера. Материалы и методы. Применены эвристические алгоритмы искусственного интеллекта и дискретной оптимизации, объединенные в единый программный пакет, а также статистические методы анализа алгоритмов. Результаты. Результатами являются закономерности, полученные при применении кластеризации ситуаций и некоторых других эвристик в методе ветвей и границ при решении задачи коммивояжера. Выводы. Было предложено улучшение алгоритма ветвей и границ с помощью подключения к нему эвристики для кластеризации ситуаций. Кроме того, получены конкретные значения для относительного улучшения среднего времени работы этого алгоритма в рассмотренной нами прикладной задаче, являющейся вариантом задачи коммивояжера, близким к псевдогеометрическому.