Вопросы по теме 'np-complete'
Как спроектировать функцию вероятности приемлемости для моделируемого отжига с несколькими различными затратами?
Я использую симулированный отжиг для решения NP-полной задачи планирования ресурсов. Для каждого варианта порядка задач я вычисляю несколько различных затрат (или значений энергии). Некоторые примеры (хотя подробности, вероятно, не имеют отношения...
7501 просмотров
schedule
21.12.2022
Простая редукция (полнота NP)
Я ищу средство, чтобы доказать, что проблема кратчайшего пути бикритерии np завершена. То есть, учитывая граф с длинами и весами, мне нужно знать, существует ли путь в графе из s в t с общей длиной ‹= L и весом ‹= W.
Я знаю, что должен взять...
1195 просмотров
schedule
14.05.2022
Сложная проблема программирования, с которой я не могу справиться
Во-первых, позвольте мне сказать, что это не домашнее задание (я студент A-Level, это не то, что мы решаем задачи (это намного сложнее)), а скорее проблема, которую я Я пытаюсь выяснить, чтобы улучшить мою логику программирования.
Я подумал о...
2473 просмотров
schedule
04.01.2023
Это проблема НП?
во-первых, я собираюсь сказать, что я не очень много знаю о теории и тому подобном. Но мне было интересно, была ли это NP или NP-полная проблема. Это звучит как частный случай проблемы суммы подмножества.
Во всяком случае, есть игра, в которую я...
132 просмотров
schedule
25.03.2023
Измерение сложности NP-complete
Например, известно, что задача решения множества-покрытия является NP-полной задачей. Входными данными этой задачи являются вселенная U, семейство S подмножеств U и целое число k ().
Одна вещь, которая меня смущает, заключается в том, что если мы...
165 просмотров
schedule
19.11.2023
пример приведения полиномиального решения к NP-полному
Я знаю, что если я сведу NP-полную проблему к неизвестной проблеме P , тогда я уверен, что P сам по себе NP-завершен. И я знаю, что если я сведу Проблему P к NP-полной проблеме, вывода не будет. Итак, я хочу привести пример, чтобы показать, что...
800 просмотров
schedule
22.10.2022
NP-полнота и сводимость
Я новичок на этом веб-сайте, поэтому прошу прощения, если этот вопрос не в том разделе. Я беру класс анализа алгоритмов и застрял на одной из моих домашних задач, и был бы признателен, если бы я мог получить некоторые рекомендации.
Проблема, на...
954 просмотров
schedule
18.06.2022
Эффективное планирование заданий с уменьшением прибыли на нескольких машинах
Задача: Рассмотрим задачу планирования n заданий на M машинах, где каждое задание i имеет время обработки p i и приносит прибыль g i ( t), если завершено к моменту времени t. Все задания освобождаются в момент времени 0. Все g i (t) являются...
303 просмотров
schedule
09.05.2022
как судоку np-complete?
как судоку является np-полной проблемой? согласно вики, чтобы быть классифицированной как np-полная проблема, она должна удовлетворять 2 условиям
проблема должна быть в np
любая другая проблема в np должна быть сведена к данной задаче за...
3333 просмотров
schedule
09.11.2022
Сведение по Карпу с РАЗДЕЛЕНИЯ на ПОДСТАВНУЮ СУММУ
РАЗДЕЛЕНИЕ: Для данного набора натуральных чисел A = {a_1, ..., a_n} существует ли подмножество A с суммой, равной сумме его дополнения?
SUBSET SUM: Учитывая набор положительных целых чисел A = {a_1, ..., a_n} и другое положительное целое число B,...
3381 просмотров
schedule
25.09.2023
Алгоритм планирования заданий на процессорах
Согласно комментарию Эрлиха (кстати, спасибо), термин "планирование" может вводить в заблуждение, и это может быть более подходящим описанием: учитывая матрицу N*N, найдите перестановку строк, которая даст наибольшую диагональную сумму.
У меня...
233 просмотров
schedule
03.11.2022
NP-Complete vs NP-hard (почему они неравны?)
Почему NP-хард не равен NP-полному?
Мое неформальное понимание используемых определений:
NP - все задачи, которые можно проверить за полиномиальное время
NP-complete - все задачи NP и NP-сложные
NP-сложный - по крайней мере, такой же...
2762 просмотров
schedule
04.02.2022
Можно ли найти все простые числа, меньшие n, за полиномиальное время?
Имейте в виду, что я почти полный нуб в теории сложности.
Я читал о том, как AKS Primality показывает, что числа размера n могут быть простыми или составными за полиномиальное время. Учитывая это, означает ли это, что поиск всех простых чисел,...
138 просмотров
schedule
11.08.2023
Какие из следующих утверждений верны для данных частных случаев задачи коммивояжера?
Я изучаю Алгоритмы: разработка и анализ II класс, один из вопросов задает:
Какие из следующих утверждений верно?
Рассмотрим экземпляр TSP, в котором стоимость каждого ребра равна 1 или 2. Тогда оптимальный маршрут можно вычислить...
357 просмотров
schedule
04.02.2023
Когда L2 является NP полным, а L1 может быть уменьшен до L2
Если L2 является NP-полным и L1 ≤p L2, я могу видеть, что L1 является NP в любой момент времени. И я считаю, что L1 может быть сложным для NP (хотя и не всегда). Теперь мой вопрос: кажется, что в некоторых случаях NP hard можно свести к NP. Я...
158 просмотров
schedule
13.08.2023
SAT является NP-полным, так почему бы нам не k-SAT является NP-полным для произвольного значения k?
k-SAT — это частный случай SAT. Поскольку SAT является NP-полным, я не понимаю, почему у нас нет k-SAT, являющегося NP-полным для любых значений k. На занятии мой профессор использовал полиномиальную редукцию из SAT, чтобы доказать, что 3-SAT...
120 просмотров
schedule
09.11.2022
Проблема алгоритма выбора подграфа (динамическое программирование или NP)
У нас есть проблема с алгоритмом, не могли бы вы написать свои идеи по этому поводу, спасибо!
Имеется N узлов с K разными цветами. Некоторые из узлов имеют прямое соединение друг с другом, а некоторые нет. Мы хотим выбрать M узлов из этих N узлов,...
107 просмотров
schedule
17.12.2023
