Вопросы по теме 'np'
Нахождение подмножества, удовлетворяющего определенному условию
У меня есть несколько массивов чисел (каждый элемент массива может принимать значение только 0 или 1), как это
v1: 1; 0; 0; 1; 1;
v2: 0; 1; 0; 0; 1;
v3: 1; 1; 0; 1; 0;
v4: 1; 0; 0; 1; 0;
v5: 1; 1; 0; 1; 1;
v6: 1; 1; 0; 1; 1;
Я хочу...
595 просмотров
schedule
02.01.2023
Np-снижение твердости
Если я хочу показать, что проблема является np-сложной, можно ли использовать существующую np-сложную задачу несколько раз? Например, используйте гамильтоновский цикл n раз в графе, где n - количество вершин? Или мне нужно преобразовать граф во...
316 просмотров
schedule
01.08.2023
Разрешимо ли это за полиномиальное (или псевдополиномиальное) время?
Я пытаюсь придумать разумный алгоритм для этой проблемы:
Допустим, у вас есть куча мячей. Каждый шар имеет как минимум один цвет, но может быть и разноцветным. Каждый шар имеет вес и связанную с ним ценность. Есть также куча коробок, каждая из...
782 просмотров
schedule
20.03.2023
Минимизация цветов: вариант алгоритма рюкзака?
Работая над проектом, я столкнулся с этой проблемой, которую я переформулирую здесь в терминах, выходящих за пределы реальной области проблемы (полагаю, я мог бы говорить о калибрах фейерверков и формах, но это еще больше усложнило бы понимание). Я...
494 просмотров
schedule
26.12.2022
Класс NP: почему выводится полиномиальная длина?
Чтобы задача соответствовала классу NP:
Решение задачи должно иметь полиномиальную выходную длину и
Решение должно быть верифицируемым за полиномиальное время.
Каково значение полиномиальной выходной длины?
PS: я думаю, что длина...
295 просмотров
schedule
07.12.2023
класс NP, проверка полиномиального времени CLIQUE
Проблема CLIQUE — задача нахождения максимальной клики в графе является NP-полной. То есть CLIQUE
a.) в NP и b.) существует NP-полная задача, 3-SAT для одной, которая сводится к CLIQUE за полиномиальное время.
Часть (b) выше в порядке - повсюду...
1197 просмотров
schedule
12.10.2023
Является ли интеграция np, np полной, np сложной или ни одной из вышеперечисленных?
Иногда очень сложно вычислить интеграл, но достаточно легко проверить правильность решения. Мне кажется, что это должно быть как минимум np, но мое понимание концепции ограничено, и я могу что-то упустить
Изменить: просто для ясности: мне...
743 просмотров
schedule
17.06.2023
Изоморфизм подграфов в SAT
Проблема изоморфизма подграфов (SI) - это вычислительная задача, в которой два графа G и H заданы в качестве входных данных, и нужно определить, содержит ли G подграф, изоморфный H.
Это проблема NP-Complete .
Я хочу знать его связь с проблемой...
1495 просмотров
schedule
29.06.2022
Алгоритм суммирования подмножества немного быстрее, чем 2 ^ (n/2) в худшее время?
Проанализировав самый быстрый алгоритм суммирования подмножеств, который выполняется за время 2^(n/2), я заметил небольшую оптимизацию, которую можно выполнить. Я не уверен, действительно ли это считается оптимизацией, и если это так, мне интересно,...
307 просмотров
schedule
06.04.2023
Мне нужно решить NP-сложную задачу. Есть надежда?
Есть много реальных проблем, которые оказываются NP - тяжело . Если предположить, что P NP , для этих проблем не существует алгоритмов с полиномиальным временем.
Если вам нужно решить одну из этих проблем, есть ли надежда, что вы сможете...
5836 просмотров
schedule
04.03.2022
NP-Complete и некоторые решения задач на графе?
Мы знаем об NP-Complete, NP-Hard и NP Class. Я хочу подытожить несколько советов по следующей задаче, взятой из середины экзамена MIT в 2008 году.
Решение Вариант какой из следующих задач для связного неориентированного взвешенного графа G...
186 просмотров
schedule
17.09.2022
Сложность некоторых задач в NP?
Я хочу обобщить некоторые проблемы на сложности. Какие из них можно решить в поливремени?
I) поиск максимального подполного графа данного графа = проблема клики
II) выбрать некоторые элементы среди n объектов, в которых заданы...
100 просмотров
schedule
12.10.2023
Есть ли способ использовать np.array в коде
Я хотел знать, есть ли способ преобразовать этот код в код np.array. затем добавьте его в ссылку . Я хотел добавить угол, с которого мяч вылетает.
import numpy as np
import scipy as sp
from scipy.integrate import ode
import matplotlib.pylab as...
59 просмотров
schedule
25.06.2023
Почему мы говорим, что полные проблемы NP - это NP?
Я просмотрел все ссылки по этой теме, но все еще не понимаю, почему мы считаем NP Complete NP. Только ли мы можем проверить это за полиномиальное время, когда мы говорим, что NP-полные проблемы являются NP, но у нас есть некоторые NP-проблемы,...
415 просмотров
schedule
04.06.2022
Tile Trial NP-сложная сложность
В игре Final Fantasy XIII-3 игроку предлагается пара головоломок. Первая представленная головоломка называется Tile Trial . Она представляет игроку сетку плиток, на некоторых из которых есть кристаллы. Цель состоит в том, чтобы собрать все...
99 просмотров
schedule
06.05.2022
Обновление матрицы путей в графе
У меня есть эта матрица, которая содержит путь между вершинами. Например, для 4 вершин у нас есть такая матрица:
0 0 1 1
1 0 1 1
0 0 0 1
0 0 0 0
Это показывает нам, что у нас есть путь между (1,3) и (1,4) и (2,1) и (2,3) и (2,4) и...
40 просмотров
schedule
19.03.2023
Как вы узнаете, является ли k постоянным для O (n ^ k) в сумме подмножества?
Проблема суммы подмножества: задан набор чисел S и целевое число, скажем, 0 . Цель состоит в том, чтобы найти подмножество S’ из S такое, что элементы в нем составляют в сумме 0 . Я слышал, что эта задача становится полиномиальной, если...
146 просмотров
schedule
01.04.2022
Рюкзак или что-то подобное без стоимости и с ограничениями на то, какие предметы могут быть назначены куда?
Скажем, у меня есть некоторое количество грузов, которые мне нужно распределить по конечному числу рюкзаков так, чтобы в каждом рюкзаке было как можно более равномерное распределение веса. Загвоздка в том, что разные веса можно поместить только в...
639 просмотров
schedule
21.07.2023
Упаковка прямоугольников в прямолинейный многоугольник
Учитывая набор прямоугольников, выровненных по оси (поворот на 90 градусов) и прямолинейный многоугольник, я хотел бы определить, могут ли все прямоугольники быть упакованы в этот многоугольник, и, если возможно, найти произвольную упаковку.
Это...
409 просмотров
schedule
22.02.2022
Как *оптимально* решить планирование N заданий с заранее известными (arrival_time, временем выполнения), чтобы среднее время ожидания для N заданий было минимальным?
Может кто-нибудь объяснить, как можно оптимально решить эту проблему?
Понятно, что жадный подход не даст оптимального решения, хотя эти две ссылки говорят, что SJF является оптимальным (я не думаю, что они учитывают среднее время ожидания, а вместо...
1452 просмотров
schedule
22.04.2022
