Кафедра "Системний аналіз та інформаційно-аналітичні технології"

В методичних вказівках розглядаються основні поняття теорії графів. Надається опис найбільш поширених алгоритмів на графах - визначення кістякового дерева екстремальної ваги, пошуку найкоротшого шляху між вершинами графа, мережевого планування. Наводяться детальні рекомендації щодо виконання розрахункового завдання з теорії графів в рамках дисципліни "Дискретна математика". Для студентів спеціальностей 122 «Комп’ютерні науки», 124 «Системний аналіз».

Предметом исследований является решение задачи поиска гамильтонова цикла на графе, которая в дискретной математике относится к NP классу сложности и по-прежнему сохраняет к себе интерес. Целью работы является разработка нового алгоритма решения этой задачи, гарантирующего нахождение оптимального решения с полиномиальными затратами времени. В работе [1] был выполнен анализ современного состояния проблемы, отмечены недостатки существующих методов решения, изложены новые принципы и метод нахождения решения. Известные методы решения задачи основаны на реализации перебора возможных вариантов решений или на интуитивных эвристиках. Методы с перебором решений неприемлемы по затратам так как характеризуются неполиномиальными затратами времени. Эвристические методы удовлетворительны по времени, но не гарантируют нахождение оптимального решения. Популярность методов перебора объясняется простотой линейного поиска в заранее известном множестве допустимых решений задачи. Но факториальная зависимость мощности множества решений (n-1)! от числа вершин графа n делает невозможным применение таких методов для задач большого размера на практике. Желание существенно снизить временные затраты приводит к попыткам обоснованного редуцирования множества перебора либо к разработке различных эвристик, что фактически свидетельствует о невозможности сформулировать условия нахождения оптимального решения задачи в целом. В данной статье представлены описание условий, определяющих нахождение оптимального решения задачи и полиномиальный алгоритм решения задачи, воплощающий описанный метод. Поиск оптимального решения задачи сводится к поиску замкнутого пути в новом графе кратчайших путей. Граф кратчайших путей строится на основе исходного графа задачи, для чего используется алгоритм Дейкстры. Множество перебора для определения оптимального решения задачи состоит из решений, которые строятся из каждой вершины графа в графе кратчайших путей. Размер этого множества оценивается как n(n -1). Разработанный параллельный алгоритм гарантирует отыскание оптимального решения, значительно сокращает исходное пространство поиска, позволяет находить решение с полиномиальной сложностью. Тестирование программы показало работоспособность разработанного метода и алгоритма решения задачи.

Кафедра "Системний аналіз та інформаційно-аналітичні технології"

Переглянути

Фільтри

Налаштування

Сортувати за

Результатів на сторінку

Результати пошуку