Вопросы по теме 'np'
Докажите, что задача факторизации α находится в NP
Пытаюсь освежить теорию вычислений, но не уверен в решении этой проблемы:
Prove that the problem of factoring α is in NP.
У меня есть ощущение, что это может быть связано с поиском проблемы NP и поиском сведения к проблеме факторизации α.
395 просмотров
schedule
08.06.2023
Все ли NP-задачи тоже NP-полны?
Определение NP-полной
Задача является NP-полной, если
принадлежит к классу NP
все остальные задачи в NP полиномиально переходят в него
Итак, если все другие проблемы в NP трансформируются в NP-полную проблему, то не означает ли это, что...
3546 просмотров
schedule
07.04.2022
Максимально независимый алгоритм набора
Я не верю, что существует алгоритм для поиска максимального независимого набора вершин в двудольном графе, кроме метода грубой силы нахождения максимума среди всех возможных независимых наборов.
Меня интересует псевдокод, чтобы найти все возможные...
5813 просмотров
schedule
25.07.2022
Как установить раздел за полиномиальное время?
Я только что прочитал о возможности решить задачу установить раздел наполовину за полиномиальное время. Но я не мог найти алгоритм, чтобы сделать это.
У меня есть два вопроса:
Где взять этот алгоритм?
Как возможно, что задача NP может быть...
1259 просмотров
schedule
07.06.2022
Полнота Np - нужно некоторое разъяснение в сокращении
Я хотел некоторые разъяснения в концепции. Для доказательства NP-полноты задачи используем редукции.
Теперь предположим, что у меня есть L‹=L'. должно ли сокращение быть от L до L 'или я могу сделать это и в обратном порядке? т. е. Могу ли я...
275 просмотров
schedule
05.09.2022
Когда NP завершено, становится NP сложно
Как правило, если у нас есть проблема с NPC. Добавляя к нему больше ограничений (усложняя), возможно ли, что проблема станет NPH? Я знаю разницу между NPC и NPH, но я не знаю, как показать, что добавление новых ограничений к существующей проблеме...
244 просмотров
schedule
18.01.2024
Bin Packing относительно версий оптимизации и решения
Я готовлюсь к экзамену, и нам дали набор практических задач. Вот один, с которым я борюсь, и я надеюсь, что кто-то может помочь пролить свет на правильный подход к этой проблеме:
Вот мой первоначальный подход к проблеме:
Версия решения: Чтобы...
552 просмотров
schedule
25.04.2022
Полный взвешенный график G, нахождение весов и одна машина
Я много читал о темах Complete Weighted Graph и Hamiltonian Tour на этом сайте, которые спросил один из пользователей, я спросил много сотрудников в моем университете, но не смог получить хороший ответ, я изменил важную часть этого вопроса...
267 просмотров
schedule
10.07.2023
Как распределить количество элементов в ведре так, чтобы оно было в пределах диапазона — алгоритм
Я решал проблему, где, скажем, у меня есть 50 элементов n1, n2, n3, ... , n50 .
Теперь у меня есть ограниченное количество ведер, скажем, 5 ведер, и ведро может содержать диапазон, скажем, только от 100 до 150 (что есть не что иное, как сумма...
909 просмотров
schedule
19.09.2022
оптимизация решения Brute-force TSP
Я работаю над небольшим проектом по решению TSP, но у меня возникла проблема. Идея состоит в том, чтобы оптимизировать локальную часть неоптимального пути, просто найдя лучшую комбинацию. Это достигается с помощью простой рекурсивной функции...
691 просмотров
schedule
24.04.2023
матрицы не выровнены сообщение об ошибке
У меня есть следующий фрейм данных возврата
ret
Out[3]:
Symbol FX OGDC PIB WTI
Date
2010-03-02 0.000443 0.006928 0.000000 0.012375
2010-03-03 -0.000690 -0.007873...
8242 просмотров
schedule
25.05.2023
Симметричные (или ненаправленные) наборы данных гамильтонового цикла
Я хотел бы протестировать свой недавно созданный алгоритм на больших (50+ узлов) графах. Желательно, чтобы они были сложными графами, и существовали бы известные туры (по крайней мере, для большинства из них).
Наборы задач для этой задачи найти не...
95 просмотров
schedule
20.10.2022
Теорема Кука и NP полные редукции
На основании теоремы Кука
Любая задача NP может быть преобразована в SAT за полиномиальное время.
Я знаю, что SAT — это NP-полная задача. Следовательно, правильно ли сказать: если мы можем свести задачу поиска A (находящуюся в NP) к...
70 просмотров
schedule
06.09.2022
Пожалуйста, объясните, как правильна логика определения новой проблемы как NP-Complete
Используемая логика выглядит следующим образом - у нас есть существующий класс проблем, которые являются NP-Complete. Теперь возникает новая проблема "Q".
Шаг 1 - Мы доказываем, что Q находится в NP, хорошо и хорошо.
Шаг 2 - Мы показываем, что...
40 просмотров
schedule
09.11.2022
Учитывая набор целых чисел и пороговое значение T, разделите набор на как можно больше групп, сумма которых ›= T
Учитывая набор целых чисел и пороговое значение T, разделите набор на как можно больше групп, сумма которых >= T.
Оставшиеся целые числа (сумма которых ‹ T, поэтому нельзя составить другую группу) должны быть оставлены вне групп.
Ограничения:...
63 просмотров
schedule
26.07.2023
Как использовать np.where с несколькими условиями
Как указать более одного условия при использовании np.where() для получения индексов элементов массива, которые удовлетворяют всем этим условиям?
a = np.array([1, 2, 3, 4, 5, 6])
print(np.where(a > 2 and a < 5))
Когда я сказал...
155 просмотров
schedule
30.09.2022
