Задача коммивояжера ("двойной выбор") Простейшее преобразование, которым можно воспользоваться в симметричной задаче коммивояжера, является так называемый "двойной выбор". Он заключается в том, что мы выбираем любые два ребра (например (a, b) и (c, d)), удаляем их и "перекоммутируем" соединявшиеся ими точки так, чтобы образовался новый маршрут. Если сумма стоимостей двух новых ребер оказалась меньше, чем двух старых, то мы нашли улучшенный маршрут.
