Вопросы по теме 'np'
Оптимизация NP-Complete Graph: минимальный выбор узла?
Предположим, у вас есть график G = (V, E) , представляющий план этажа одноэтажного торгового центра. Отдельные хранилища представлены вершинами, а ребра между вершинами представляют собой произвольное определение хранилищ, близких друг к другу.
В...
124 просмотров
schedule
26.09.2022
Коммивояжер TSP: Улучшение грубого алгоритма
Согласно wiki , потребуется (N-1)! для расчета тура с N городами. Я нашел лучший способ сделать это, но я не могу подсчитать, насколько я его улучшил. Могу сказать вам, что на моем домашнем компьютере я смог собрать карту 20 городов менее чем за 1...
736 просмотров
schedule
12.02.2023
Оптимизация размещения произвольных фигур на плоскости
Я пытаюсь создать алгоритм, который может брать набор объектов и организовывать их в заданной области таким образом, чтобы прямоугольник, ограничивающий все фигуры, был оптимизирован (либо по используемой области, либо путем максимизации диапазона по...
143 просмотров
schedule
26.06.2022
Алгоритм поиска уникального набора элементов, по одному элементу из каждого набора наборов
Предположим, у вас есть набор людей J , и вам нужно сфотографировать каждого человека. У них есть только один фотограф, и у фотографа есть конечное количество раз T ( |T| > |J| ), доступных для каждой фотографии. В любой момент времени t из...
287 просмотров
schedule
22.05.2023
Кратчайший путь затрат
Мне нужно найти кратчайший путь из точки D в R. Это фиксированные точки. Это пример ситуации:
В ящике также есть стены, через которые вы не сможете пройти, если не сломаете их. Каждое разрушение стены стоит вам, скажем, «а» очков, где «а» —...
727 просмотров
schedule
05.06.2023
Этот язык есть в NP?
L={[G, K] | G is a simple undirected graph with no simple path longer than k}
(Далее, это Со-НП)?
Я считаю, что это НП. Я мог бы предоставить верификатор, который делал следующее:
V(G,E, k) — верификатор, где G — граф, E — список...
241 просмотров
schedule
09.10.2022
Недетерминизм против проверяемости за полиномиальное время
Я читал, что проблема NP поддается проверке за полиномиальное время или, что то же самое, решается за полиномиальное время с помощью недетерминированной машины Тьюринга. Почему эти определения эквивалентны?
374 просмотров
schedule
18.07.2022
Доказательство неприближимости покрытия минимального цикла
Рассмотрим проблему покрытия циклов: для данного графа G мы ищем множество циклов C, такое что все вершины V (G) находятся по крайней мере в одном цикле C, а количество циклов в C минимально.
Моя задача — показать, что эта задача не допускает...
147 просмотров
schedule
06.04.2024
Как оптимизировать назначение задач агентам с этими ограничениями?
У меня есть проблема с назначением как часть моей магистерской диссертации, и я ищу общее направление в ее решении.
Итак, есть список агентов и список задач, причем количество задач больше, чем количество агентов.
Агенты представляют...
738 просмотров
schedule
22.06.2022
Полиномиальная аппроксимация рюкзака по времени
задачу о рюкзаке можно решить за O(n²V) время, где V = max(v[i], i = 1,..,n) обозначает максимальное значение любого предмета. Если мы «изменим единицы измерения» с помощью параметра округления θ = ε/n * V и рассмотрим измененные значения...
227 просмотров
schedule
25.04.2022
Теорема Кука (на простом английском языке)
Я прочитал книгу Гэри и Джонсона 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
Отображение NP, NP-полноты или NP-жесткости
Правильно ли я понимаю эти три категории?
Чтобы показать, что проблема X является NP:
Покажите, что X можно проверить детерминистически за полиномиальное время (или X разрешимо с помощью НТМ)
Чтобы показать, что проблема X является...
115 просмотров
schedule
10.02.2023
Определение завершения NP
Я пытаюсь понять формальное определение NP Complete и у меня есть несколько вопросов. Мне было интересно, может ли кто-нибудь дать больше информации.
В книге по алгоритмам Джона Клейнберга говорится, что если каждый NP проблема может быть...
477 просмотров
schedule
22.03.2023
Это лучший способ решить сумму подмножества?
Я пробовал базовый способ быстрее решить проблему суммы подмножества, и я придумал это
Наивным способом является функция oldSS , которая проверяет все 2^n комбинаций. Но потом я заметил, что перед проверкой каждого случая вычисляю минимальное и...
74 просмотров
schedule
25.05.2023
Что такое естественная NP-полная задача?
Я думаю, что у меня довольно приличное понимание NP-Complete, NP-Hard и т. д. в целом, но внезапно, наткнувшись на какую-то литературу, я обнаружил, что кто-то говорит о «естественной» NP-полной задаче — явно с этими цитаты. Я не понял, что они...
170 просмотров
schedule
01.09.2023
Почему самая длинная общая подпоследовательность для нескольких строк является NP-Hard?
Мне сложно понять, почему самая длинная общая проблема подпоследовательности для нескольких строк (k> 2) - это NP-Hard. Я знаю, что проблема LCS для двух строк длиной l1, l2 может быть решена за время O (l1 * l2). У меня вопрос, почему мы не можем...
742 просмотров
schedule
30.03.2022
Np.concatenate ValueError: все входные массивы должны иметь одинаковое количество измерений
Я пытаюсь объединить, но в итоге получил указанную ошибку. Я также новичок в python.
def cving(x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, ind1, ind2, ind3, ind4, ind5, num):
if num == 0:
xwhole = np.concatenate((x2, x3, x4, x5), axis=0)...
3180 просмотров
schedule
17.12.2022
Доказательство NP-полноты оптимального покрытия пути
Эта статья решает задачу оптимального покрытия пути для блок-графов или двудольный граф перестановок. В третьей строке его введения написано, что проблема оптимального покрытия пути является NP-полной, и дана ссылка на «Компьютер и неразрешимость:...
302 просмотров
schedule
04.05.2023
