Участница:Maria Akimenkova/Задача3 — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
 
Строка 20: Строка 20:
 
[[Участник:StasFomin|StasFomin]] 18:22, 15 мая 2019 (MSK):«все отсутствующие ребра можно провести, но сопоставить им очень большие веса, так чтобы оптимальный путь через них заведомо не проходил»  — так ведь это нарушит неравенство треугольника.
 
[[Участник:StasFomin|StasFomin]] 18:22, 15 мая 2019 (MSK):«все отсутствующие ребра можно провести, но сопоставить им очень большие веса, так чтобы оптимальный путь через них заведомо не проходил»  — так ведь это нарушит неравенство треугольника.
  
[[Категория:На проверку]]
+
[[Участник:StasFomin|StasFomin]] 04:25, 16 мая 2019 (MSK): После правок сильно лучше не стало. Не знаю, откуда вы списывате эти «многобукв» (безумные определения невнятных языков). Тут нужно только одно, парой строчек — как вы собираетесь решить обычного NP-полного коммивояжера через решения задачи о метрическом коммивояжере. Все. Как вы делаете полиномиальное сведение, и почему оно корректно.
 +
 
 +
[[Категория:Проблемы в решении]]

Текущая версия на 04:25, 16 мая 2019

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


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

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