Вісники НТУ "ХПІ"

Зараз показуємо 1 - 3 з 3

Новый метод поиска гамильтонова цикла на графе
(Національний технічний університет "Харківський політехнічний інститут", 2020) Прокопенков, Владимир Филиппович
В дискретной математике существует много задач, которые относятся к NP классу сложности. Решение этих задач имеет как теоретическую, так и практическую ценность. Одной из них является задача поиска гамильтонова цикла на графе. Целью работы является разработка нового метода и алгоритма решения этой задачи предпочтительного имеющимся по затратам времени и качеству получаемого решения. В работе выполнен анализ проблемы и существующих методов её решения, определены недостатки этих методов. Показано, что все известные методы решения этой задачи строятся на реализации перебора вариантов решений либо на интуитивных эвристиках. Первые из них характеризуются неполиномиальными затратами времени, а вторые – не обеспечивают получение оптимального решения. Причиной такого состояния является невозможность сформулировать условия, определяющие оптимальное решение задачи. В таком случае единственно возможным способом решения задачи по-прежнему остаётся перебор вариантов, а для снижения затрат нахождения решения необходимо прибегать к сокращению пространства перебора вариантов. В работе изложены новые принципы нахождения решения и предложен новый метод решения задачи. На основе нового метода разработан полиномиальный алгоритм решения задачи. Поиск гамильтонова цикла в графе сводится к поиску замкнутого пути в новом графе кратчайших путей. Для построения графа кратчайших путей используется алгоритм Дейкстры. Пространство перебора вариантов решения задачи состоит из решений, которые строятся из каждой вершины графа в графе кратчайших путей. Тестирование разработанной программы показало работоспособность разработанного метода и алгоритма решения задачи. Предложенный метод решения существенно сокращает пространство перебора и позволяет находить оптимальное решение с полиномиальной сложностью, как в полном, так и неполном графах. Рассмотренный метод пригоден для параллельной реализации, что даёт дополнительный выигрыш во времени и позволяет на всю мощь использовать параллельные возможности современных многоядерных процессоров.
Оптимизация работы производственного участка машиностроительного предприятия на основе метода муравьиных колоний
(НТУ "ХПИ", 2010) Скобцов, Ю. А.; Ченгарь, О. В.
Рассматривается задача оптимизации оперативного планирования машиностроительного предприятия на основе муравьиных алгоритмов, выбраны критерии оптимизации. Предложен граф для моделирования работы участка и нахождения оптимальных расписаний работы оборудования. Исследовано влияние основных параметров муравьиных алгоритмов таких, как начальное расположение и мощность популяций муравьиных колоний для партий деталей и т.п.
Комплексная оценка состояния канала связи и обобщенного критерия живучести
(НТУ "ХПИ", 2015) Головкина, Л. В.; Борисенко, А. С.
Предложено определение обобщенного критерия живучести в беспроводной сенсорной ZigBee сети с ячеистой топологией при разрушающих действиях и учетом состояния реального канала связи, условной надежности узлов. Задача определения живучести сети сведена к задаче связности графа. Изменения структуры сети в результате разрушающих действий учтены в виде изменения графовой модели. Сделаны выводы о методах маршрутизации, которые используются в оценке состояния канала связи в сети.

Вісники НТУ "ХПІ"

Переглянути

Фільтри

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

Сортувати за

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

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