0
ответов
Предложите алгоритм (график -возможно NP -Завершено)
Имеется сеть городов, соединенных дорогами различной целочисленной длины. Путешественник хочет поехать на своей машине из одного города в другой. Однако он не хочет минимизировать пройденное расстояние;...
вопрос задан: 11 November 2015 23:39
0
ответов
Как 2-CNF SAT находится в P, а 3-CNF SAT находится в NPC?
Я действительно не понимаю, почему 2-CNF SAT находится в P, а 3-CNF SAT находится в NPC. Я читал CLRS, и я понимаю, как они доказывают, что 3-CNF SAT находится в NPC. Разве я не могу использовать ту же сводимость от SAT к 2-CNF-SAT к ...
вопрос задан: 7 April 2015 11:22
0
ответов
How to tell if greedy algorithm suffices for finding minimum coin change?
The minimum coin change problem is an NP-complete problem but for certain sets of coins the greedy algorithm (choose largest denominations first) works. Given a set of integers denoting coin-values, ...
вопрос задан: 1 February 2015 00:01
0
ответов
NP-полный рюкзак
Я видел это решение ECLiPSe для проблемы, упомянутой в этом комиксе XKCD. Я попытался преобразовать это в чистый Пролог. go: - Всего = 1505, Цены = [215, 275, 335, 355, 420, 580], длина (Цены, ...
вопрос задан: 14 June 2014 10:24
0
ответов
найти максимальное количество вершин -непересекающихся путей в графе с ограничением
В неориентированном графе G = (V,E )каждому ребру соответствует не -отрицательное значение. Как найти максимальное число вершинных -непересекающихся путей из s в t на графе G с ограничением, что сумма...
вопрос задан: 11 July 2012 19:50
0
ответов
минимальные умножения против проблемы покрытия множества
У меня есть множество I = {P1, P2, ..., Pm} и n конечных подмножеств I, обозначаемый через R1,R2,...,Rn следующим образом: R1 = {P1, P2} R2 = {P2, P4} R3 = {P2, P3, P4} R4 = {P1, P2, P4}.. .. где Pi обозначает ...
вопрос задан: 30 May 2012 16:54
0
ответов
Proof that Dominating Set is NP-Complete
here is the question. I am wondering if there is a clear and efficient proof: Vertex Cover: input undirected G, integer k > 0. Is there a subset of
vertices S, |S|<=k, that covers all edges? ...
вопрос задан: 25 May 2012 10:22
0
ответов
Вывод подмножества NP-полный?
Рассмотрим следующую задачу: есть N монет с номерами от 1 до N. Вы не можете их видеть, но вам дано M фактов о них в виде: struct Fact
{ set position int num_heads
} ...
вопрос задан: 17 May 2012 15:33
0
ответов
Компиляторы, которые переводят алгоритмы проверки в задачи SAT
Доказательство того, что SAT является NP-полным, является конструктивным доказательством, поэтому должно быть возможно реализовать его в виде программы. Кто-нибудь это делал? Я ищу программу (компилятор), которая принимает в качестве входных данных ...
вопрос задан: 12 December 2011 08:02
0
ответов
np-полнота в остовном дереве с ограниченной степенью
Я понимаю, почему остовное дерево с ограниченной степенью считается NP-полным со степенью или 2 (это пример гамильтониана Проблема пути), но я не понимаю, почему это относится к степеням> ...
вопрос задан: 21 October 2011 10:22
0
ответов
Список проблем, которые в целом являются NP-трудными, но есть ли решение за полиномиальное время в плоских графах?
Я столкнулся со многими проблемами, которые можно сформулировать как задачу графа.
В целом это NP-сложно, но иногда можно доказать, что граф плоский.
Следовательно, я заинтересован в изучении этих проблем и ...
вопрос задан: 13 October 2011 09:51
0
ответов
Минимальная экспоненция цепи дополнения
Я знаю, что это было доказано NP-полное, и это нормально. В настоящее время я решаю его с филиалом и связанным, где я устанавливаю начальный верхний предел на количество умножений, это примет нормальный ...
вопрос задан: 7 September 2011 08:15
0
ответов
Факторно-временные алгоритмы и P / NP
Нетрудно заметить, что n! растет медленнее, чем что-либо, до степени N (скажем, 100 ^ N), и поэтому, если проблема считается NP-полной и одна из них возникла при n! алгоритм, аппроксимирующий ...
вопрос задан: 4 June 2011 05:32
0
ответов
Алгоритмы для нахождения числа гамильтоновых путей в графе
Я пытаюсь решить слегка измененную версию проблемы гамильтонова пути. Он изменен тем, что нам дается начальная и конечная точки, и вместо того, чтобы определять, существует ли решение, ...
вопрос задан: 18 March 2011 20:51
0
ответов
как найти наименьшее количество операций для вычисления x ^ n
вот проблема из ACM International Collegiate Programming Contest Asia Regional Contest, Yokohama, 2006-11-05 Начиная с x и многократно умножая на x, мы можем вычислить x ^ 31 с помощью ...
вопрос задан: 28 December 2010 20:21
0
ответов
Докажите, что клика NP-полноты + граф независимого множества
"Докажите, что NP-Complete определяет данные входные G и k, имеет ли G клику размера k и независимое множество. размера k. Обратите внимание, что это 1 проблема, а не 2; ответ будет положительным, если и только ...
вопрос задан: 14 December 2010 15:57