15
ответов

Решение полной NP проблемы в XKCD

Рассматриваемая проблема/комик: http://xkcd.com/287/ я не уверен, что это - лучший способ сделать это, но здесь - что я придумал до сих пор. Я использую CFML, но это должно быть читаемо любым. <...
вопрос задан: 8 February 2017 14:08
14
ответов

Это корректно, чтобы попросить решать полную NP проблему на собеседовании? [закрытый]

Сегодня был вопрос на Так, где автору дали полную NP проблему во время интервью, и ему, очевидно, не сказали, что это было то. Какова цель задать такие вопросы?...
вопрос задан: 23 May 2017 12:01
14
ответов

Алгоритм для Деления списка чисел в 2 равных списка суммы

Существует список чисел. Список должен быть разделен на 2 равных размерных списка с минимальным различием в сумме. Суммы должны быть распечатаны. #Example:>>> que = [2,3,10,5,8,9,7,3,5,2]> и...
вопрос задан: 21 May 2009 06:21
11
ответов

Что такое NP-полный в информатике?

Что такое NP-полная проблема? Почему это такая важная тема в информатике?
вопрос задан: 15 June 2017 22:01
9
ответов

Хитрая проблема программирования, что я испытываю затруднения при получении моей головы вокруг

Прежде всего позвольте мне сказать, что это не домашняя работа (я - студент A-уровня, это - ничто близко к тому, что мы проблема решает (это - путь тяжелее)), но больше проблемы, которую я пытаюсь разузнать для улучшения...
вопрос задан: 22 September 2011 15:50
9
ответов

У Вас когда-либо было бизнес-требование, которое оказалось Полной NP проблемой?

Полнота NP кажется мне как одна из тех вещей, это главным образом просто теоретически и не действительно что-то, с чем Вы столкнулись в нормальной рабочей среде. Таким образом, мне довольно любопытно если чей-либо когда-либо выполнение...
вопрос задан: 5 August 2009 18:17
8
ответов

Возможная полная NP проблема?

Я был бы точно так же, как кто-то, чтобы проверить, полна ли следующая проблема NP или если существует на самом деле лучшее/легче решение ее, чем простая проверка комбинации "в лоб". У нас есть своего рода...
вопрос задан: 12 April 2010 12:45
7
ответов

Является это “Допустимое математическое выражение” проблемой P или NP?

Этот вопрос просто вне любопытства. Я от школы в течение лета и собирался реализовать алгоритм для решения этого только для забавы. Это привело к вышеупомянутому вопросу, как трудно эта проблема?...
вопрос задан: 10 June 2009 16:18
7
ответов

Найдите лучшую комбинацию от данного набора нескольких наборов

Скажите, что у Вас есть отправка. Это должно пойти от точки, чтобы указать на B, указать на B, чтобы указать на C и наконец указать на C для указания на D. Вам нужен он для получения там за пять дней для наименьшего количества возможной суммы денег. Там..
вопрос задан: 26 September 2008 18:27
6
ответов

Алгоритм для нахождения, который числа из списка размера n суммируют к другому числу

У меня есть десятичное число (давайте назовем его целью), и массив других десятичных чисел (давайте назовем элементы массива), и я должен найти все комбинации чисел от элементов, которые суммируют к цели...
вопрос задан: 14 September 2012 21:39
6
ответов

Действительно ли это - вариант проблемы суммы подмножества, легче решить?

Мне связали проблему с проблемой суммы подмножества, и задаюсь вопросом, помогают ли различия, т.е. разрешимый за разумное количество времени. Учитывая значение V, размер набора L и последовательность...
вопрос задан: 15 August 2011 22:40
6
ответов

Полиномиальный алгоритм времени для нахождения гамильтонова обхода в [закрытом] графике

Существует ли полиномиальный алгоритм времени для нахождения гамильтонова обхода в графике? Мой алгоритм является факториалом N и является действительно медленным.
вопрос задан: 20 July 2010 21:06
6
ответов

Что такое “P=NP?”, и почему это - такой известный вопрос? [закрытый]

Вопрос того, является ли P=NP, возможно, самым известным во всей Информатике.Что это значит? И почему это настолько интересно? О, и для дополнительного кредита, отправьте доказательство оператора...
вопрос задан: 18 February 2010 01:45
5
ответов

Как найти, какие числа в наборе составляют в целом другое данное число?

Вот проблема, что я, кажется, сталкиваюсь с работой с системой учета. У меня есть ряд транзакций, но их сумма не равняется сумме, что департамент бухгалтерского учета думает что это...
вопрос задан: 23 May 2017 11:55
5
ответов

Проблема суммы подмножеств и разрешимость полных NP проблем

Я читал о проблеме сумм подмножества, когда я придумал то, что, кажется, алгоритм общего назначения для решения ее: (defun subset-contains-sum (сумма набора) (позволяют ((подмножества) (новое подмножество) (...
вопрос задан: 1 March 2010 02:04
5
ответов

Неэкспоненциальное решение проблемы с лабиринтом?

Учитывая n*n-sized многоголовый граф без петель, где каждый узел имеет самое большее трех детей и трех родителей, там неэкспоненциальный алгоритм, чтобы определить, существует ли путь n-длины где никакие два...
вопрос задан: 11 February 2009 08:38
4
ответа

Оптимизация проблемы Парковки. Какие алгоритмы я должен использовать для установки большей части суммы автомобилей в партии?

Что алгоритмы (грубая сила или не) были бы я использовать, чтобы вставить как много автомобилей (предположите, что все автомобили являются тем же размером) на парковке так, чтобы был по крайней мере один выход (от контейнера), и автомобиль не может быть..
вопрос задан: 9 November 2018 16:14
4
ответа

Найдите набор чисел в одном наборе, который составляет в целом число в другом

Для игры, которую я делаю, у меня есть ситуация, где у меня есть список чисел – говорят [7, 4, 9, 1, 15, 2] (названный для этого) – и другого списка чисел – говорят [11, 18, 14, 8, 3] (названный B) и...
вопрос задан: 5 July 2010 11:46
4
ответа

Эта проблема np-complete?

Скажите, что существует строка x мусорных ведер, заполненных пустяками (случайная сумма) в простом виде (Вы видите, сколько пустяков там находится в каждом мусорном ведре). Теперь существует два игрока, которые могут, когда это - их выбор поворота...
вопрос задан: 25 June 2010 09:32
4
ответа

Все планируют NP-трудные проблемы?

Я знаю, что существуют некоторые проблемы планирования там, которые являются NP-hard/NP-complete... однако, ни один из них не указан таким способом показать, что эта ситуация является также NP. Если у Вас есть ряд задач...
вопрос задан: 29 January 2010 14:07
4
ответа

Как разработать приемную функцию вероятности для моделируемого отжига с несколькими отличными затратами?

Я использую моделируемый отжиг для решения полной NP проблемы планирования ресурса. Для каждого кандидата, заказывающего задач, я вычисляю несколько различных затрат (или энергетическая ценность). Некоторые примеры (...
вопрос задан: 21 July 2009 10:52
3
ответа

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

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

Настольная игра, “Идут” завершенный NP?

Существует много Шахмат AI вокруг, и очевидно некоторые достаточно хороши для избиения некоторых самых великих игроков в мире. Я услышал, что много попыток были предприняты для записи успешного AI для...
вопрос задан: 14 February 2013 11:08
2
ответа

Является этой проблемой NP, и это имеет имя?

Эта проблема подошла в реальном мире, но я перевел его в более универсальную "подобную учебнику" формулировку. Я подозреваю, что это - NP, но я особенно интересуюсь знанием, если это имеет имя или...
вопрос задан: 12 April 2010 12:44
2
ответа

Время выполнения лучшего случая для решения Полной NP проблемы?

Каков самый быстрый алгоритм, который существует с решить конкретную Полную NP проблему? Например, наивная реализация коммивояжера является O (n!), но с динамическим программированием это может быть...
вопрос задан: 22 November 2009 01:40
2
ответа

Каково различие между 'комбинаторным алгоритмом' и 'линейным алгоритмом'?

Или скорее каково определение комбинаторного алгоритма и линейного алгоритма, resp.? Для прояснения, потому что, очевидно, первые респонденты неправильно поняли вопрос: Я не ищу...
вопрос задан: 16 June 2009 17:18
2
ответа

как первые полные NP проблемы, как показывали, были полны NP?

Из статьи в Википедии о Полном NP: "Самый легкий способ доказать, что некоторая новая проблема полна NP, является первым, чтобы доказать, что это находится в NP, и затем уменьшать некоторую известную полную NP проблему до него" я'...
вопрос задан: 20 November 2008 21:38
1
ответ

Алгоритм / аппроксимация для комбинированного независимого набора / расстояния Хэмминга

Вход: график G Вывод: несколько независимых наборов, так что принадлежность узла ко всем независимым наборам уникальна. Следовательно, узел не имеет соединений с каким-либо узлом в своем собственном наборе. Вот пример ...
вопрос задан: 1 May 2015 05:41
1
ответ

Действительно ли минимизация булевых выражений полна NP?

Я знаю, что булева выполнимость Полна NP, но является минимизацией/упрощением булева выражения, которым я означаю брать данное выражение в символьной форме и производить...
вопрос задан: 1 March 2009 16:42
0
ответов

Java: коммивояжер - Найден полиномиальный алгоритм

Изменить: улучшение этого алгоритма было найдено. Добро пожаловать, чтобы увидеть это. Этот вопрос является улучшением моего старого вопроса. Теперь я хочу показать вам пример кода Java и объяснить мой ...
вопрос задан: 23 May 2017 11:46