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

Я столкнулся с вопросом на промежуточном экзамене. Кто-нибудь может уточнить ответ?

Задача A: по заданному весовому графу G найти гамильтоново тур с минимальным весом.

Задача B: Учитывая полный взвешенный граф G и действительное число R, имеет ли G гамильтоново тур с весом не более R?

Предположим, есть машина, которая решает B. Сколько раз мы можем позвонить B (каждый раз, когда задаются G и действительное число R), чтобы решить проблему A с этой машиной? Пусть сумма ребер в G с точностью до M.

1) Мы не можем этого сделать, потому что существует неисчислимое состояние.

2) O (| E |) раз

3) O(LG м) раз

4) потому что A NP-Hard, это не может быть сделано.

Источник

3 ответа

Первый алгоритм

Ответ (3) O(lg m) times, Вам просто нужно выполнить бинарный поиск минимального гамильтонова тура по взвешенному графику. Обратите внимание, что если гамильтониан тур по длине L на графике нет смысла проверять, является ли гамильтонов тур по длине L', где L' > L, существует, так как вы заинтересованы в гамильтоновом туре с минимальным весом. Таким образом, на каждом шаге вашего алгоритма вы можете исключить половину оставшихся возможных тур-весов. Следовательно, вам придется позвонить B в твоей машине O(lg m) раз, где m обозначает общий вес всех ребер в полном графе.

Редактировать:

Второй алгоритм

У меня есть небольшая модификация вышеуказанного алгоритма, который использует машину O(|E|) время, так как некоторые люди говорили, что мы не можем применить бинарный поиск в бесчисленном множестве возможных значений (и они, возможно, правы): взять каждое возможное подмножество ребер из графа, и для каждого подмножества сохранить значение, которое является суммой весов всех ребер из подмножества. Позволяет сохранить значения для всех подмножеств в массиве с именем Val, Размер этого массива 2^|E|, Сортировать Val в возрастающем порядке, а затем примените бинарный поиск для минимального гамильтонова пути, но на этот раз вызовите машину, которая решает проблему B только со значениями из Val массив. Поскольку каждое подмножество ребер включено в отсортированный массив, гарантируется, что решение будет найдено. Общее количество звонков машины составляет O(lg(2^|E|)), который O(|E|), Итак, правильный выбор (2) O(|E|) times,

Замечания:

Первый предложенный мной алгоритм, вероятно, неверен, так как некоторые люди отмечали, что нельзя применять бинарный поиск в несчетном множестве. Поскольку мы говорим о действительных числах, мы не можем применить бинарный поиск в диапазоне [0-M]

Источник

Предположим, что при кодировании графов веса кодируются в виде двоичных строк, представляющих неотрицательные целые числа, и что Problem B на самом деле может быть алгоритмически решен путем ввода действительного числа и выполнения вычислений, основанных на том, что, по-видимому, все выглядит следующим образом.

Возможно выполнить первый бинарный поиск по целому интервалу {0,...,M} чтобы получить минимальный вес гамильтонова тура в O(log M) вызывает алгоритм для Problem B, Как впоследствии известен оптимальный, мы можем исключить отдельные ребра в G и использовать полученный график в качестве входных данных для алгоритма Problem B проверить, изменяется ли оптимальное или нет. Этот процесс использует O(|E|) вызывает алгоритм для Problem B определить ребра, которые встречаются в оптимальном гамильтоновом туре. Общее время выполнения этого подхода O( (|E| + log M ) * r(G)), где r(G) обозначает время работы алгоритма для Problem B принимая график G в качестве входа. Я предполагаю, что r является многочленом, хотя вопрос прямо не указывает на это; в целом, общее время выполнения будет полиномиально ограничено длиной кодирования ввода, так как M может быть вычислено за полиномиальное время (и, следовательно, псевдополиномиально ограничено длиной кодирования входного G).

При этом предполагаемые ответы можно прокомментировать следующим образом.

  1. Ответ неверный, так как множество необходимых состояний конечно.
  2. Может быть правдой, но не следует из алгоритма, рассмотренного выше.
  3. Может быть правдой, но не следует из алгоритма, рассмотренного выше.
  4. Ответ неверный. Строго говоря, NP- твердость Problem A не исключает алгоритм полиномиального времени; кроме того, алгоритм для Problem B не считается полиномиальным, поэтому даже P=NP не следует, если Problem A может быть решено полиномиальным числом обращений к алгоритму для Problem B (что имеет место по алгоритму, описанному выше).
Источник

Я полагаю, что выбор, который должен был быть ответом, - 1- вы не можете этого сделать. Причина в том, что вы можете выполнять бинарный поиск только по счетным множествам.

Обратите внимание, что ребра графа могут даже иметь отрицательные веса, и, кроме того, они могут иметь дробные или даже иррациональные веса. В этом случае пространством поиска ответа будет множество всех реальных значений, меньших m.

Тем не менее, вы можете быть как можно ближе к ответу A в Log(n) времени, но вы не можете найти точный ответ. (n - размер счетного пространства).

Источник
Другие вопросы по тегам