10
ответов

Как NP-Hard отличается от NP? [Дубликат]

Я понимаю множество определений NP, NP-complete и NP-hard. Я понимаю, что если мы сможем решить NP-полную проблему, мы сможем решить все проблемы NP. Я также знаю, что проблема классифицируется как NP -...
вопрос задан: 23 July 2015 13:15
10
ответов

Алгоритм для создания школьного расписания

Я задавался вопросом, существуют ли известные решения для алгоритма создания школьного расписания. В основном это об оптимизации "дисперсии часа" (и в случае учителей и классов) для данного класса-...
вопрос задан: 22 April 2015 13:46
3
ответа

Чем отличаются NP, NP-Complete и NP-Hard?

Чем отличаются NP, NP-Complete и NP-Hard? Я знаю о многих ресурсах по всему Интернету. Я хотел бы прочитать ваши объяснения, и причина в том, что они могут отличаться от того, что ...
вопрос задан: 7 January 2019 09:20
1
ответ

проверить наличие значения на другом Датафрейме

У меня есть два кадра данных F1 и F2, содержащие оба столбца id1, id2. F1 содержит два столбца F1 [id1, id2]. F2 содержит три столбца [id1, id2, Description]. Я хочу проверить, существует ли F2 ['id1'] в F1 ['id1' ...
вопрос задан: 31 March 2019 00:16
1
ответ

P=NP: Каковы самые многообещающие методы?

Я знаю, что P=NP не был решен до сих пор, но может кто-либо говорить мне что-то о следующем: Что в настоящее время является самым многообещающим математическим / компьютер научные методы, которые могли быть...
вопрос задан: 8 December 2013 19:03
0
ответов

Доказательство того, что проблема остановки является NP-сложной?

В этом ответе на вопрос об определениях NP, NP-hard и NP -complete, Джейсон утверждает, что проблема остановки является классической NP-сложной проблемой. Это проблема, которая дает ...
вопрос задан: 18 December 2018 06:52
0
ответов

Сумма-подмножество с фиксированным размером подмножества

Задача сумма-подмножество гласит: Для данного набора целых чисел есть есть непустое подмножество, сумма которого равна нулю? Эта проблема в целом NP-полная. Мне любопытно, сложность этого небольшого варианта ...
вопрос задан: 23 May 2017 12:25
0
ответов

Сложность проверки решений NP-сложных задач оптимизации?

Есть многие задачи оптимизации, которые известны как NP-трудные, такие как задача коммивояжера, MAX-SAT или поиск минимального хроматического числа графа. Учитывая проблему такого рода, я '...
вопрос задан: 7 August 2015 14:42
0
ответов

Как 2-CNF SAT находится в P, а 3-CNF SAT находится в NPC?

Я действительно не понимаю, почему 2-CNF SAT находится в P, а 3-CNF SAT находится в NPC. Я читал CLRS, и я понимаю, как они доказывают, что 3-CNF SAT находится в NPC. Разве я не могу использовать ту же сводимость от SAT к 2-CNF-SAT к ...
вопрос задан: 7 April 2015 11:22
0
ответов

Максимальный независимый алгоритм набора

Я не верю, что существует алгоритм для поиска максимального независимого набора вершин в двудольном графе, кроме метода грубой силы нахождения максимума среди всех возможных независимых ...
вопрос задан: 31 August 2013 10:42
0
ответов

Разрешимо ли это за полиномиальное (или псевдо-полиномиальное)время?

Я пытаюсь придумать разумный алгоритм решения этой задачи.:Допустим, у вас есть куча мячей. Каждый шар имеет как минимум один цвет, но может быть и разноцветным. Каждый мяч имеет вес и...
вопрос задан: 12 April 2012 17:38
0
ответов

Что такое NP и NP-полные проблемы? [закрыто]

Я изо всех сил пытаюсь понять, что такое недетерминированные задачи с полиномиальным временем и NP-полные проблемы. Я понимаю, какие задачи решаются за полиномиальное время, и видел в Википедии про NP ...
вопрос задан: 5 January 2012 16:21
0
ответов

Нахождение подмножества, которое удовлетворяет определенному условию

У меня есть несколько массивов чисел (каждый элемент массива может принимать только значение 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; ...
вопрос задан: 16 December 2011 21:45
0
ответов

Как скрыть Div, когда полоса прокрутки перемещается с jQuery?

Я просто хочу, чтобы меню # исчезло, когда полоса прокрутки движется, чтобы обеспечить менее загроможденный интерфейс. Есть ли код, который позволил бы это? Я думаю, что в основном я ищу, как схватить...
вопрос задан: 12 September 2011 18:17
0
ответов

Есть ли проблемы с решением, которые можно решить, но не в NP ? [закрыто]

это мой первый вопрос о переполнении стека, так что будьте осторожны. Я заранее прошу прощения, если он уже забит до смерти ... Я прочитал несколько тем на NP, но не нашел дразнящего ответа на мой ...
вопрос задан: 15 July 2011 20:59
0
ответов

Передача параметров потока Windows C ++

В Windows C ++ следующий поток создает поток : CreateThread (NULL, NULL, функция, параметр, NULL, & threadID); Это запустит "функцию" в новом потоке и передаст ему "параметр" как void * или ...
вопрос задан: 13 April 2011 18:57