Вопросы по теме 'np'
Что делает NP-сложную задачу не NP-полной?
У меня возникла путаница по поводу NP-сложных проблем. Некоторые NP-сложные проблемы находятся в NP, которые называются NP-Complete, а некоторые - не в NP. Например: проблема с остановкой является NP-сложной, а не NP -полный. Но почему он не...
1833 просмотров
schedule
20.11.2021
Планирование классов для логической выполнимости [сокращение за полиномиальное время], часть 2
Несколько дней назад я задал вопрос о том, как преобразовать проблему планирования занятий в университете в проблему логической выполнимости.
( Планирование классов до логической выполнимости [сокращение за полиномиальное время] )
Я получил...
815 просмотров
schedule
29.09.2021
SQL-запрос для поиска строк с наиболее подходящими ключевыми словами
Я действительно плохо разбираюсь в SQL, и я хотел бы знать, какой SQL я могу запустить, чтобы решить проблему, ниже которой я подозреваю, что это проблема NP-Complete, но я согласен с тем, что запрос занимает много времени для обработки больших...
1476 просмотров
schedule
31.10.2021
Алгоритм макс. 3 цветов
В этой задаче мне дан граф G = (V,E) , цель состоит в том, чтобы найти раскраску вершин графа тремя возможными цветами, которые максимизируют функцию качества.
q(c) = количество ребер, концы которых окрашены по-разному .
Дайте вероятностное...
791 просмотров
schedule
12.05.2022
Упаковка вершин на двудольном графе
Свяжите каждый узел неориентированного графа с положительным весом. Задача упаковки вершин состоит в том, чтобы найти подмножество узлов с наибольшей суммой весов, так что никакие два узла с ребром между ними не выбраны.
Каков наиболее...
556 просмотров
schedule
13.06.2022
Какой приблизительный алгоритм TSP использует Google OR-Tools?
Я наткнулся на Google OR-Tools , который вычисляет TSP с разумными приближениями, как описано в эту ссылку . Мне любопытно узнать, какой конкретный алгоритм использует этот инструмент для TSP. Есть ли у него какие-то особые оптимизации (кода),...
348 просмотров
schedule
11.07.2022
Связующие деревья с минимальным количеством листьев
Итак, моя проблема заключается в следующем:
У меня есть неориентированный (полный) взвешенный граф G=(V,E), и я хотел бы сгенерировать все возможные остовные деревья с минимальным количеством листьев , т.е. с минимальным количеством вершин степени...
2471 просмотров
schedule
31.08.2022
Сложность старой загадки Top Coder: составить число, вставив +
Это продолжение моего предыдущего вопроса ( о старой загадке топового кодера).
Учитывая строку цифр, найдите минимальное количество сложений, необходимых для того, чтобы строка равнялась некоторому целевому числу. Каждое добавление эквивалентно...
399 просмотров
schedule
27.09.2022
Если проблема A ≤p B, то B ≤p A, докажите или опровергните
Как формально доказать или опровергнуть, что если задача A ≤p B, то следует, что B ≤p A
Я интуитивно думаю, что это должно быть опровергнуто, но я не уверен, как это сделать.
338 просмотров
schedule
30.09.2022
Какой из этих языков является NP-полным?
Я искал разницу между NP и NP-полными проблемами. Я наткнулся на этот замечательный ответ Джейсона в StackOverflow. О NP-полных задачах он сказал
NP-задача X, для которой можно свести любую другую NP-задачу Y к X за полиномиальное время....
3021 просмотров
schedule
04.12.2022
Несколько TSP с изюминкой
Пару недель назад я столкнулся с проблемой, которую фактически разбил на вариант задачи о коммивояжере. Повороты такие:
Есть несколько продавцов. Список городов динамически увеличивается (например, ввод в реальном времени). Каждый город полностью...
205 просмотров
schedule
09.06.2023
Алгоритм с полиномиальным временем для разбиения множества по степеням двойки?
Это гораздо больше вопрос алгоритма / доказательства, чем программирования / реализации, поэтому извиняюсь, если StackOverflow не подходит для этого.
Что касается проблемы:
предположим, что у нас есть набор чисел, и каждое число должно быть...
766 просмотров
schedule
29.07.2023
Понимание временной сложности k-клики фиксированного размера
Определите временную сложность задачи (например, нижнюю или верхнюю границу). Входные данные: график. Выходные данные: «да», если граф содержит клику размером 100. В противном случае выведите «нет».
Определите нижнюю границу временной сложности для...
1408 просмотров
schedule
11.12.2022
np.where для нескольких переменных
У меня есть кадр данных с:
customer_id [1,2,3,4,5,6,7,8,9,10]
feature1 [0,0,1,1,0,0,1,1,0,0]
feature2 [1,0,1,0,1,0,1,0,1,0]
feature3 [0,0,1,0,0,0,1,0,0,0]
Используя это, я хочу создать новую переменную (скажем, new_var), чтобы сказать, когда...
1562 просмотров
schedule
19.11.2022
Путаница с NP-трудным и NP-полным в задачах коммивояжера
Оптимизация коммивояжера (TSP-OPT) является NP-сложной задачей, а поиск коммивояжера (TSP) является NP-полной. Однако TSP-OPT можно свести к TSP, поскольку, если TSP можно решить за полиномиальное время, то и TSP-OPT(1) тоже. Я думал, что для того,...
8236 просмотров
schedule
31.07.2023
Все возможные пути в графе
Для заданного графа G(V, E) , исходной вершины s и конечной вершины d проблема состоит в том, чтобы найти все возможные пути из s до d , где G может содержать петли и циклы. Я хочу получить все простые пути, цикл не разрешен.
Какова...
151 просмотров
schedule
11.12.2022
Является ли кратчайший гамильтонов путь NP-трудным?
Гамильтонов путь - это путь, который соединяет все узлы без повторов, и это NP-полная проблема.
Является ли кратчайший гамильтонов путь (SHP) NP-трудным?
Чем отличается проблема коммивояжера с ШП?
74 просмотров
schedule
19.12.2022
Нахождение всех возможных простых путей в неориентированном графе является NP трудным / NP полным
Доказательства нужны:
Нахождение всех возможных простых путей в неориентированном графе является NP трудным / NP полным. Граф может содержать несколько ребер между одной и той же парой узлов и петель.
Я искал, у меня возникла идея или обсуждение....
276 просмотров
schedule
15.07.2023
Отключить два узла в неориентированном взвешенном графе с минимальной стоимостью
Предположим, у нас есть неориентированный взвешенный граф, а также исходный и конечный узлы, и нам нужно отключить исходный и конечный узлы, удалив ребра, а стоимость удаления ребра — это вес ребра. Нам нужно минимизировать стоимость отключения двух...
72 просмотров
schedule
10.03.2023
Реализация покрытия вершин на Прологе
Я пытаюсь реализовать покрытие вершин в прологе. Я думал сделать следующее:
Используйте граф в следующем формате [(VertexSouce/VertexDest), ...] и передайте общее количество вершин в графе. Таким образом, предикат будет выглядеть так:...
702 просмотров
schedule
06.12.2023
