Анализ применения алгоритма поиска порождённого подграфа для NP-полных задач
Вид работы:
Курсовая работа |
Предмет работы:
Программирование
|
Количество листов:
28
ОТРЫВОК ИЗ РАБОТЫ:
Существует множество NP- полных задач. Класс NP определяется как
задачи, которые можно лишь проверить некоторое решение за
полиномиальное время, но алгоритм, чтобы мы смогли решить задачу быстро
нам неизвестен.
Алгоритмы для NP используются каждый день во многих областях,
хотя мы этого можем и не подозревать. Например, при восстановление
поврежденных фалов, или оптимизации маршрута или в логистике про
доставке товаров
1. Введение……………………………………………………………………………..3
2. NP – полные задачи……………………………………………………………4
2.1 Описание NP-полных задач……………………………………………7
2.1.1 Задача о Коммивояжере ……………………………………………7
2.1.2 Нахождение гамильтонового пути …………………………….10
3. Поиск порожденного подграфа ………………………………………….13
3.1 Порожденный путь ………………………………………………………14
3.2 Клики ………………………………………………………………………….16
4. Заключение……………………………………………………………………….18
5. Список наибольшее литературы …………………………………………………………..19
6. Приложения……………………………………………………………………….20