Участница:Maria Akimenkova/Задача3

Материал из DISCOPAL
Перейти к: навигация, поиск

Решение задачи Приближенный алгоритм для метрической задачи коммивояжера/Задачи/MTSP NP-полна


StasFomin 18:22, 15 мая 2019 (MSK):«все отсутствующие ребра можно провести, но сопоставить им очень большие веса, так чтобы оптимальный путь через них заведомо не проходил» — так ведь это нарушит неравенство треугольника.

StasFomin 04:25, 16 мая 2019 (MSK): После правок сильно лучше не стало. Не знаю, откуда вы списывате эти «многобукв» (безумные определения невнятных языков). Тут нужно только одно, парой строчек — как вы собираетесь решить обычного NP-полного коммивояжера через решения задачи о метрическом коммивояжере. Все. Как вы делаете полиномиальное сведение, и почему оно корректно.