Полный взвешенный граф и гамильтонов тур

Я столкнулся с вопросом на промежуточном экзамене.Может кто уточнить ответ?Задача A: Для полного взвешенного графа G найти гамильтонов тур с минимальным весом.Проблема B: Имеет ли G полный взвешенный граф G и действительное число R гамильтонов тур с весом не более R?Предположим, существует машина, которая решает B. Сколько раз мы можем вызвать B (каждый раз, когда даны G и вещественное число R), чтобы решить задачу A с этой машиной?Предположим, что сумма ребер в G до M.1) Мы не можем этого сделать, потому что есть бесчисленное состояние.2) O (| E |) раз3) O (lg m) раз4) поскольку A NP-Hard, этого сделать нельзя.
7 голосов | спросил nini 20 FebruaryEurope/MoscowbFri, 20 Feb 2015 18:55:22 +0300000000pmFri, 20 Feb 2015 18:55:22 +030015 2015, 18:55:22

0 ответов


Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132