Публикации по теме 'np-complete'
Этот алгоритм решает NP-полные задачи за время P.
Проблема булевой выполнимости состоит в том, чтобы написать алгоритм, определяющий, может ли данное логическое выражение в N переменных когда-либо принимать значение истина для некоторого выбора этих N переменных.
Эта задача относится к классу NP-Complete . Это означает, что если бы можно было написать алгоритм, который завершается за время P, то существует процедура модификации этого алгоритма для решения любой другой задачи класса NP также за полиномиальное время.
Я только что..
Вопросы по теме 'np-complete'
Алгоритм разделения списка чисел на 2 списка равных сумм
Есть список номеров.
Список должен быть разделен на 2 списка одинакового размера с минимальной разницей в сумме. Суммы должны быть напечатаны.
#Example:
>>>que = [2,3,10,5,8,9,7,3,5,2]
>>>make_teams(que)
27 27
Есть ли...
15669 просмотров
schedule
22.03.2023
В чем разница между «комбинаторным алгоритмом» и «линейным алгоритмом»?
Или, точнее, каково определение комбинаторного алгоритма и линейного алгоритма, соответственно?
Чтобы было ясно, потому что очевидно, что первые ответившие неправильно поняли вопрос: я не ищу определение алгоритма, работающего в линейном времени по...
4958 просмотров
schedule
10.05.2022
Лучшее время выполнения для решения проблемы NP-Complete?
Какой самый быстрый алгоритм существует для решения конкретной NP-полной задачи? Например, наивная реализация коммивояжера — это O(n!), но при динамическом программировании это можно сделать за O(n^2 * 2^n). Есть ли какая-нибудь, возможно, «более...
1020 просмотров
schedule
03.01.2023
Алгоритм/аппроксимация для комбинированного независимого набора/расстояния Хэмминга
Вход: граф G. Выход: несколько независимых множеств, так что принадлежность узла ко всем независимым множествам уникальна. Таким образом, узел не имеет соединений ни с одним узлом в своем наборе. Вот пример пути.
Поскольку здесь потребовалось...
735 просмотров
schedule
09.05.2022
Все ли NP-задачи тоже NP-полны?
Определение NP-полной
Задача является NP-полной, если
принадлежит к классу NP
все остальные задачи в NP полиномиально переходят в него
Итак, если все другие проблемы в NP трансформируются в NP-полную проблему, то не означает ли это, что...
3546 просмотров
schedule
07.04.2022
минимальное умножение против проблемы с набором покрытия
У меня есть набор I = {P1, P2, ..., Pm} и n конечных подмножеств I, обозначаемых R1, R2,..., Rn следующим образом:
R1 = {P1, P2}
R2 = {P2, P4}
R3 = {P2, P3, P4}
R4 = {P1, P2, P4}
....
где Pi обозначает целое число.
Для каждого Ri...
233 просмотров
schedule
30.05.2024
Алгоритм разделения списка на две равные части
Связанные вопросы:
Алгоритм разделения списка чисел на 2 списка с равной суммой
разделите список на две части, чтобы их сумма самые близкие друг к другу
Предположим, у меня есть список, который содержит ровно 2k элементов....
1546 просмотров
schedule
28.05.2024
Полнота Np - нужно некоторое разъяснение в сокращении
Я хотел некоторые разъяснения в концепции. Для доказательства NP-полноты задачи используем редукции.
Теперь предположим, что у меня есть L‹=L'. должно ли сокращение быть от L до L 'или я могу сделать это и в обратном порядке? т. е. Могу ли я...
275 просмотров
schedule
05.09.2022
Когда NP завершено, становится NP сложно
Как правило, если у нас есть проблема с NPC. Добавляя к нему больше ограничений (усложняя), возможно ли, что проблема станет NPH? Я знаю разницу между NPC и NPH, но я не знаю, как показать, что добавление новых ограничений к существующей проблеме...
244 просмотров
schedule
18.01.2024
Java: коммивояжер - найден полиномиальный алгоритм
Изменить : улучшение этого алгоритма. был найден. Добро пожаловать, чтобы увидеть это.
Этот вопрос является улучшением моего старого вопроса. Теперь я хочу показать вам пример кода Java и более подробно объяснить мой алгоритм. Детали....
5552 просмотров
schedule
31.08.2022
Разбиение списка целых чисел на разделы, чтобы минимизировать разницу их сумм
Учитывая список целых чисел l , как я могу разделить его на 2 списка a и b так, чтобы d(a,b) = abs(sum(a) - sum(b)) было минимальным. Я знаю, что проблема является NP-полной, поэтому я ищу алгоритм псевдополиномиального времени, т.е. O(c*n) ,...
2262 просмотров
schedule
30.03.2023
Bin Packing относительно версий оптимизации и решения
Я готовлюсь к экзамену, и нам дали набор практических задач. Вот один, с которым я борюсь, и я надеюсь, что кто-то может помочь пролить свет на правильный подход к этой проблеме:
Вот мой первоначальный подход к проблеме:
Версия решения: Чтобы...
552 просмотров
schedule
25.04.2022
Уменьшите сумму подмножества до полимино-упаковки
Это домашнее задание, поэтому любая помощь приветствуется.
Мне нужно доказать, что следующая задача является NP-полной. Подсказка говорит, что вы должны свести задачу суммы подмножества к этой задаче.
Имея набор фигур, как показано ниже, и...
683 просмотров
schedule
17.01.2023
SAT с двумя пунктами является полиномиальным
Какова сложность экземпляра SAT с k унарными предложениями и только двумя предложениями?
Я хотел бы найти статью с этим результатом .. Я нашел одну статью, в которой проблема немного другая. Все переменные появляются не более двух раз...
81 просмотров
schedule
06.08.2023
Зачем использовать линейное целочисленное программирование (ILP), хотя оно NP-Complete?
Вопрос может и глупый но он реально меня давно смущает.
Я прочитал много статей о беспроводных сенсорных сетях. Многие исследователи моделируют свои проблемы в форме ПИЖ. Однако ILP является NP-полным, поэтому он неэффективен для решения...
811 просмотров
schedule
08.02.2023
Является ли эта задача оптимизации двудольного графа NP-полной?
Я пытался найти алгоритм полиномиального времени для решения этой проблемы, но тщетно. Я не знаком с NP-полностью. Просто интересно, является ли эта проблема на самом деле NP-полной, и мне не следует тратить дальнейшие усилия на попытки придумать...
1228 просмотров
schedule
23.06.2022
алгоритм цветового кодирования самого длинного пути
прежде всего я хотел бы прояснить, да, это для задания колледжа, и я ищу помощь в понимании алгоритма, чтобы иметь возможность реализовать его. Итак, у меня есть это задание, которое можно найти здесь:...
888 просмотров
schedule
06.04.2023
Доказательство NP-полноты задачи о множестве-разбиении
Я сократил задачу о сумме подмножества до задачи о разделе, но не знаю, правильно ли это, поэтому мне нужна ваша помощь. МОЙ МЕТОД : В задаче о сумме подмножества мы должны найти подмножество S1 множества S так, чтобы оно суммировалось с числом t, и...
569 просмотров
schedule
13.03.2023
Пожалуйста, объясните, как правильна логика определения новой проблемы как NP-Complete
Используемая логика выглядит следующим образом - у нас есть существующий класс проблем, которые являются NP-Complete. Теперь возникает новая проблема "Q".
Шаг 1 - Мы доказываем, что Q находится в NP, хорошо и хорошо.
Шаг 2 - Мы показываем, что...
40 просмотров
schedule
09.11.2022
Задача о точном покрытии, но с ограничением на точное количество подмножеств в решении
Я относительно новичок в точном покрытии и подобных проблемах, поэтому, пожалуйста, потерпите меня. Предположим, у меня есть типичная задача точного покрытия, т.е. учитывая набор X и набор подмножеств X S , я хочу найти S * (a подмножество S...
264 просмотров
schedule
02.08.2023
