Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
brrr
0 / 0 / 0
Регистрация: 26.10.2014
Сообщений: 58
1

NP-полные задачи

20.01.2015, 14:11. Просмотров 402. Ответов 2
Метки нет (Все метки)

Друзья! помогите, пожалуйста, разобраться с NP-полными задачами, что это, как это, какие бывают задачи и алгоритмы решений. Только, пожалуйста, простым языком, а то по книгам совсем не понятно
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.01.2015, 14:11
Ответы с готовыми решениями:

Полные системы
Здравствуйте. В контрольной работе 2 задачи, в которых не могу разобраться. Поогите, пожалуйста:...

Не полные данные
в таблице в столбце содержуться словаю. как мне вытуть от туда слова начинаюшеися с определеных...

полные перестановки на си!!!!
#include<stdio.h> #include<conio.h> #include<string.h> int a; int b; int m,n; long l; void...

полные квадраты
Получить кол-во полных квадратов среди а1...аn. то есть 4=2x2 и т.д...вроде решил но чет не...

языки, полные по Тьюрингу.
Которые из языков программирования являются полными по Тьюрингу ?(то есть на которых можно сделать...

2
grikukan
63 / 63 / 54
Регистрация: 23.09.2012
Сообщений: 212
20.01.2015, 16:37 2
brrr,
В смысле примеры или что?

Ну, например, поиск Гамильтонова цикла/пути в графе(пути проходящего 1 раз по каждой вершине), задача о рюкзаке(даны веса и стоимости предметов, надо унести максимальную стоимость с определенным максимальным весом), задача о поиске в массиве подмножества с нулевой суммой, поиск максимальной клики в графе, K-SAT где K>2 и многое-многое другое.

Насчет решений: тут все зависит от размера входных данных. Если речь идет о маленьких наборах, то обычно решают разными переборами, отсечениями и т.д.

Когда даже отсечения не работают(например, O(n!) когда n=500) используют неточные алгоритмы, которые работают быстро, но находят не самый оптимальный ответ(это, например, метод отжига, генетические алгоритмы, различные жадности и т.д.)
1
brrr
0 / 0 / 0
Регистрация: 26.10.2014
Сообщений: 58
22.01.2015, 14:46  [ТС] 3
большое спасибо) поищу по Вашим примерам
0
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.01.2015, 14:46

Сепарабельные, полные пространства
Помогите доказать то, что метрическое пространство ({l}_{2},\rho ) сепарабельное и полное....

Восстановить полные права доступа
Не подскажите как вернуть полные правда доступа?на ноутбуке я единственный владелец,однако,изменив...

Полные GPS координаты в мобильном
Добрый день, с праздником ! Ребят, подскажите пожалуйста, я поэксперементировал с некоторыми...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.