Вопросы по теме 'np-complete'
Алгоритм поиска, какие числа из списка размера n суммируются с другим числом
У меня есть десятичное число (назовем его цель ) и массив других десятичных чисел (назовем массив элементами ), и мне нужно найти все комбинации чисел из элементы , которые в сумме соответствуют цели.
Я предпочитаю решение на C # (.Net 2.0), но...
24876 просмотров
schedule
20.03.2024
Что P = NP? И почему это такой известный вопрос?
Вопрос о том, P = NP, пожалуй, самый известный во всей компьютерной науке. Что это означает? А почему это так интересно?
О, и для дополнительной поддержки, пожалуйста, опубликуйте доказательство истинности или лжи утверждения. :)
122172 просмотров
schedule
20.04.2023
Каков хороший алгоритм сжатия записей в заблокированном файле?
Предположим, у вас есть большой файл, состоящий из группы блоков фиксированного размера. Каждый из этих блоков содержит некоторое количество записей переменного размера. Каждая запись должна полностью помещаться в один блок, и тогда такие записи по...
1004 просмотров
schedule
20.11.2022
Проблема суммы подмножеств и разрешимость NP-полных задач
Я читал о проблеме подмножества сумм, когда придумал, как представляется, универсальный алгоритм для ее решения:
(defun subset-contains-sum (set sum)
(let ((subsets) (new-subset) (new-sum))
(dolist (element set)
(dolist...
1734 просмотров
schedule
30.09.2022
3-cnf-sat с неожиданным вопросом
Если вы измените задачу 3-cnf-sat следующим образом: Для каждого c i , c i = -x i1 ИЛИ -x i2 ИЛИ x i3 означает, что ровно одна из переменных появляется без отрицания. Вам также присваиваются значения (0 или 1) для некоторых (или всех ) из x. Вы...
371 просмотров
schedule
13.09.2022
NP-сложна ли эта комбинаторная задача оптимизации?
Я работаю над проблемой комбинаторной оптимизации, которая, как я подозреваю, является NP-сложной, и генетический алгоритм хорошо работает с нашим набором данных. Мы исследовательская группа и планируем опубликовать наши результаты в нашей области...
2538 просмотров
schedule
25.08.2022
Если известно, что проблема X (проблема принятия решения) является NP-полной и доказано, что она сводится к проблеме Y, можете ли вы тогда сказать, что проблема Y является NP-полной?
Если известно, что проблема X (проблема принятия решения) является NP-полной и доказано, что она сводится к проблеме Y за полиномиальное время, можете ли вы тогда сказать, что проблема Y является NP-полной?
Моей первой мыслью было: нет, нужно...
623 просмотров
schedule
30.04.2022
Алгоритм редукции - преобразование любой проблемы SGI в сумму подмножества
Можно ли представить любую проблему изоморфизма подграфов как проблему суммы подмножества, чтобы можно было использовать методы динамического программирования, доступные для решения проблемы суммы подмножества, для решения проблемы SGI?
355 просмотров
schedule
16.02.2023
Минимальное возведение в степень аддитивной цепи
Я знаю, что это было доказано NP-полным, и это нормально. В настоящее время я решаю это с ветвью и границей, где я установил начальный верхний предел на количество умножений, которое потребовало бы обычный алгоритм двоичного квадрата/умножения, и он...
2350 просмотров
schedule
22.04.2022
Решение для упаковки в мусорные ведра: что с этим происходит?
Я попытался реализовать решение для bin-packing- проблема с типом , в основном так, как описано Дитрихом Эппом . Я пока не использую Haskell, поэтому написал что-то на C++.
Для ширины стены меньше определенного числа (36) моя программа и...
215 просмотров
schedule
22.03.2023
NP-полный, нет эффективного алгоритма?
Я мало что знаю об NP-complete, но читал об этом тут и там. В книге «Введение в алгоритм», которую я изучаю (самостоятельно), говорится: «Хотя никогда не было найдено эффективного алгоритма для NP-полной задачи, никто никогда не доказывал, что...
479 просмотров
schedule
02.10.2022
Вариант PartitionProblem - фиксированный размер подмножеств
У меня есть проблема, которая является разновидностью проблемы с разделами, которая является NP-полной. Это проблема оптимизации, а не проблема принятия решения.
Задача : разбить список чисел на два подмножества так, чтобы разница их сумм была...
257 просмотров
schedule
08.04.2023
Коммивояжер TSP: Улучшение грубого алгоритма
Согласно wiki , потребуется (N-1)! для расчета тура с N городами. Я нашел лучший способ сделать это, но я не могу подсчитать, насколько я его улучшил. Могу сказать вам, что на моем домашнем компьютере я смог собрать карту 20 городов менее чем за 1...
736 просмотров
schedule
12.02.2023
Минимальные деревья Штейнера и NP-полнота
В чем разница между следующими деревьями Штейнера: (не) метрическим минимальным деревом Штейнера, евклидовым минимальным деревом Штейнера, графовым минимальным деревом Штейнера и т. д.? Какие из них NP-полные, а какие NP-сложные? Некоторые из...
363 просмотров
schedule
15.06.2023
Теорема Кука (на простом английском языке)
Я прочитал книгу Гэри и Джонсона Computers and Intractability — A Guide to the Theory of NP-Completeness для курса по алгоритмам; однако, просматривая материал год спустя, я понял, что никогда по-настоящему не понимал теорему Кука.
Что касается...
451 просмотров
schedule
06.11.2022
Установить уменьшение обложки
Допустим, у нас есть множество U = {x1, x2, x3} и множество S = {{x1}, {x1, x2}, {x1, x3}, {x1,x1,x3}}. Это чисто пример и проблема для общей проблемы. Это похоже на обычную задачу покрытия набора, поэтому я полагаю, что сведение ее к настоящей...
364 просмотров
schedule
21.07.2022
NP Hardest Longest Path Ациклический модифицированный
Я застрял с этой проблемой на целый день.
Когда мы находим самый длинный путь в графе, мы сначала выполняем топологическую сортировку, а затем проверяем путь соседних вершин и продолжаем обновлять, выбирая максимум веса ребра или альтернативный...
247 просмотров
schedule
15.09.2022
Можно ли уменьшить набор, независимый от K, до 2-SAT
Это вопрос домашнего задания для начала. Перед тем, как я начну, у меня есть несколько вопросов.
Наша проблема:
«Сократите k-независимое множество до 2-SAT следующим образом. Для графа G с n вершинами формируется n предложений, по одному на...
1218 просмотров
schedule
12.05.2022
Определение завершения NP
Я пытаюсь понять формальное определение NP Complete и у меня есть несколько вопросов. Мне было интересно, может ли кто-нибудь дать больше информации.
В книге по алгоритмам Джона Клейнберга говорится, что если каждый NP проблема может быть...
477 просмотров
schedule
22.03.2023
Доказательство NP-полноты оптимального покрытия пути
Эта статья решает задачу оптимального покрытия пути для блок-графов или двудольный граф перестановок. В третьей строке его введения написано, что проблема оптимального покрытия пути является NP-полной, и дана ссылка на «Компьютер и неразрешимость:...
302 просмотров
schedule
04.05.2023
