 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Гамильтонов цикл
|
|
Дан граф G c n вершинами. Существует ли в графе простой цикл, проходящий через все вершины графа? Простым называется цикл, в котором вершины не повторяются. Таким образом, гамильтонов цикл — это последовательность вершин и дуг (ребер) графа, содержащая все вершины графа G по одному разу, но, может быть, содержащая не все дуги.
Задача коммивояжера.
Дан граф G с п вершинами. Каждому ребру графа приписано положительное целое число d i, задающее длину ребра. Кроме этого, задано некоторое положительное целое число L. Требуется ответить на вопрос: найдется ли в графе G маршрут, проходящий через все вершины графа G, такой, что его длина не превышает L?
Другие модификации задачи о коммивояжере требуют отыскания маршрута минимальной длины, гамильтонова цикла и т. п. Неизменным остается требование однократного прохождения через все вершины.
Кроме класса NP-полных проблем рассматривают еще и класс NP-трудных проблем.
Проблема Т называется NP-трудной, если она удовлетворяет условию: Если R Î NP, то R сводится к T за полиномиальное время.
Заметим, что это условие совпадает со вторым условием для NP-полных проблем. Следовательно, NP-полная проблема — это NР-трудная задача, принадлежащая классу NP.
Для того чтобы уяснить себе возможное различие между классами Р и NP, продолжим анализ проблемы выполнимости логического выражения.
Кроме общей задачи о выполнимости, могут быть поставлены задачи с ограничивающими условиями. Например, ограничение на длину дизъюнктов.
Задача о k-выполнимости — это задача о выполнимости для выражений, в которых длины дизъюнктов не превосходят величины k.
Разумеется задача о k-выполнимости проще задачи о (k + 1)-выполнимости, и проще общей задачи о выполнимости для любого конечного k. Самая простая — задача об 1-выполнимости. В этом случае любой дизъюнкт состоит только из одной переменной или ее отрицания, т. е. Если все переменные в записанной конъюнкции различны, то выражение выполнимо, а если одна и та же переменная встречается два раза, в одном случае с показателем 1, а в другом случае с показателем 0, то в соответствии с известным тождеством х 1 &х° = 0 выражение тождественно равно нулю, т. е. не выполнимо. Проверка этого требует времени, линейного по отношению к длине выражения.
Вывод: задача об 1-выполнимости принадлежит классу Р.
Проблема останова не единственная, для которой не существует алгоритмов решения. Многие другие проблемы, часто важные для практики, оказались алгоритмически неразрешимыми. Перечислим некоторые из них.
1. Проблема эквивалентности алгоритмов: по двум произвольным заданным алгоритмам (представленным, например, в виде программ для машины Тьюринга или на языке программирования Pascal) определить, будут ли они выдавать одинаковые выходные результаты на любых исходных данных.
2. Проблема эквивалентности грамматик: по двум произвольным грамматикам, представленными в виде наборов синтаксических диаграмм, определить, совпадают ли определяемые ими языки.
3. Проблема тотальности: по произвольному заданному алгоритму определить, будет ли он завершаться (останавливаться) на всех возможных входных наборах.
4. Десятая проблема Гильберта: «Найти алгоритм, который по заданному многочлену P (x1,…,xn) с целыми коэффициентами определяет, имеет ли уравнение P=0 решение в целых числах». Ю.В.Матиясевич показал, что такого алгоритма не существует.
Дата публикования: 2015-03-26; Прочитано: 336 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
