Большинство задач, интересных с практической точки зрения, имеют полиномиальные (работающие за полиномиальное время) алгоритмы решения. То есть время работы алгоритма на входе длины n составляет не более О ( пк) для некоторой константы k (не зависящей от длины входа). Разумеется, не каждая задача имеет алгоритм решения, удовлетворяющий этому свойству. Некоторые задачи вообще не могут быть решены никаким алгоритмом. Классический пример такой задачи — «проблема остановки» (выяснить останавливается ли данная программа на данном входе). Кроме того, бывают задачи, для которых существует решающий их алгоритм, но любой такой алгоритм работает «долго» — время его работы не есть O(n к ) ни для какого фиксированного числа k.
Если мы хотим провести пусть грубую, но формальную границу между «практическими» алгоритмами и алгоритмами, представляющими лишь теоретический интерес, то класс алгоритмов, работающих за полиномиальное время, является разумным первым приближением. Мы рассмотрим, руководствуясь [1], класс задач, называемых NP-полными. Для этих задач не найдены полиномиальные алгоритмы, однако и не доказано, что таких алгоритмов не существует. Изучение NP-полных задач связано с так называемым вопросом «P = NP». Этот вопрос был поставлен в 1971 году и является сейчас одной из наиболее сложных проблем теории вычислений.
Зачем программисту знать о NP-полных задачах? Если для некоторой задачи удается доказать ее NP-полноту, есть основания считать ее практически неразрешимой. В этом случае лучше потратить время на построение приближенного алгоритма, чем продолжать искать быстрый алгоритм, решающий ее точно.
Одной из актуальных задач теории алгоритмов является проблема P versus NP отношения класса P задач, разрешаемых за полиномиальное время на детерминированной машине, с классом NP задач распознавание, разрешаемых за полиномиальное время на недетрминированной машине.
Фундамент теории NP - полных задач заложен в работе С.Кука [2], в которой были введены класс NP, понятия полиномиальной сводимости и NP - полной задачи, т.е. задачи к которой может быть сведена любая задача из класса NP за полиномиальное время [13].
Позднее относительно широкого круга задач была доказана их NP - полнота, в частности это относится и к рассматриваемой задаче «Гамильтонов путь». Наиболее полным руководством по теории NP - полноты является монография [3].
В настоящее время вопрос «Являются NP - полные задачи труднорешаемыми?» считается одним из основных вопросов современной математики. Доказательство возможности решения хотя бы одной NP - полной задачи полиномиальным алгоритмом будет доказательством совпадения классов P и NP.
На данный момент существует несколько методов такие как: приближенные и эвристические методы, псевдополиномиальные алгоритмы, метод локальных улучшений, метод ветвей и границ, метод случайного поисках[4][5].
Во многих отраслях промышленности возникает следующая задача. Нужно произвести n единиц продукта на одном типе аппаратуры. Нужно, после того как был произведен продукт дь перенастроить аппарат на производство продукта д j. Стоимость перенастройки постоянна. Предположим, что продукты производятся в цикле, то есть после производства дп, нужно произвести д 1. Возникает вопрос, можно ли настроить производство таким образом, чтобы не перенастраивать аппарат, или если представить задачу в виде ориентированного графа, то «имеет ли этот граф гамильтонов цикл или нет?». Пока неизвестен какой-либо простой критерий, или алгебраический метод, который ответит на этот вопрос. Следует упростить задачу: «имеет ли этот граф гамильтонову цепь?». Так как из цепи создать цикл можно путем добавления одного ребра, то последний вопрос является подзадачей нахождения гамильтоново цикла[6]. Для решения поставленного вопроса воспользуемся метод эллипсоидов.
Объектами исследования является метод эллипсоидов.
Предметом исследования является метод эллипсоидов как способ распознавания гамильтоновой цепи в графе.
Целью работы является определить, может ли метод эллипсоидов использоваться как способ распознавания гамильтоновой цепи в графе.
В работе поставлены и решены следующие задачи:
• Описание метода эллипсоидов, как решение NP - трудной задачи;
• Изучение алгоритма генератора графов содержащих гамильтонову цепь и не содержащих гамильтонову цепь;
• Реализация метода эллипсоидов;
• Анализ эффективности метода эллипсоидов, как способ
распознавания гамильтоновой цепи в графе.
Информационной базой работы являются следующие издания:
• Панюкова Т.А. Комбинаторика и теория графов/ Т.А. Панюкова - Изд. 3¬е, испр. - Москва : Ленанд, 2014. - 206 с.
• Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность / Х. Пападимитриу, К. Стайглиц - Москва издательство «МИР», 1984 - 512 с.
Работа состоит из введения, трех разделов, заключения, библиографического списка и приложения. Объем работы составляет n страниц, объем библиографии - n источников.
Первая глава работы описывает задачу коммивояжера, гамильтонов покрытие графа, сведение задачи к системе неравенств, метод эллипсоидов.
Во второй главе описаны генераторы тестовых задач.
Третья глава посвящена программной реализации метода эллипсоидов, а также программной реализации визуализации гамильтоновой цепи на графе.
В четвертой главе проводится численный эксперимент.
В заключении формулируются выводы по дипломной работе, оценивается степень выполнения поставленных задач.
В ходе выполнения выпускной квалификационной работы был рассмотрен метод эллипсоидов как способ распознавания гамильтоновой цепи в графе и по этому методу составлена программа.
В работе решены следующие задачи:
• Описан метод эллипсоидов, как решение NP - трудной задачи;
• Изучен алгоритм генератора графов содержащих гамильтонову цепь и не содержащих гамильтонову цепь;
• Реализован метода эллипсоидов с помощью стандартной библиотеки C++;
• Проведен анализ эффективности метода эллипсоидов, как способ распознавания гамильтоновой цепи в графе.
Тестирование программы проведено на сгенерированных шести примерах, а именно на трех примерах с графами, содержащих гамильтонову цепь, и трех примерах с графами, не содержащих гамильтонову цепь. Все результаты работы программы представлены в виде рисунков.
Программа справляется с графами, содержащими гамильтонову цепь, но не справляется с графами, не содержащими гамильтонову цепь. Вероятная причина - недостаточная точность вычисления. Направление дальнейшего исследования - использование нестандартных библиотек, распараллеливание вычислений.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
