Коварный p43. (Именно так остается думать)
Задача сама по себе малой размерности - 43 пункта. Однако несколько часов работы метода Литтла не находят решение, включая метод с модификациями.
Рассмотрев данные, углядел, что p43 получена из задачи размерности 22 пункта путем дублирования некоторых пунктов 2, 3, а то и 4 раза. Между такими клонами пунктов нулевая стоимость, а стоимость до других пунктов копируются.
Такая простая модификация задачи вводит в ступор метод Литтла просто потому, что в дереве решений появляется очень много клонов маршрута, в которых просто переставлены порядок подряд идущих пунктов-клонов. В итоге, каждый набор клонов увеличивает просматриваемое дерево решения в число пересатоновок пунктов клонов - экспоненциальный рост.
При схлопывании пунктов-клонов задача p43 решается за секунду.
Получается, нужен какой-то метод предварительного анализа и выявления таких групп пунктов клонов, не обязательно полных дубликатов (достаточно явная группировка). Потом эти группы представить как один пункт и составить новую задачу.
Пока есть следующие трудности:
- каким способом разбить пункты на группы?
- как обеспечить корректность такой модификации задачи, чтобы оптимальное решение в новой задаче был оптимальным в исходной?
Для полных клонов, когда между клонами нулевая стоимость и строки стоимостей просто продублированы, это легко. А как быть со "слабыми клонами"? Например, пункты внутри города можно рассматривать как "слабые клоны" в объемах всего земного шара.
