Автор: Мазалова Яна Михайловна
СПОСОБ ПОСТРОЕНИЯ ГАМИЛЬТОНОВОГО ПУТИ С ПРИМЕНЕНИЕМ ЖАДНОГО АЛГОРИТМА РАСШИРЯЮЩЕЙСЯ ВЫДЕЛЕННОЙ ОБЛАСТИ
A METHOD FOR CONSTRUCTING A HAMILTONIAN PATH USING A GREEDY ALGORITHM OF AN EXPANDING SELECTED AREA
УДК 519.674
Поляков Александр Александрович кандидат технических наук,
Черноморское высшее военно-морское училище имени П.С. Нахимова,
Россия, г. Севастополь
Викулин Андрей Игоревич адъюнкт
Черноморского высшего военно-морского училища имени П.С. Нахимова,
Россия,г. Севастополь
Мазалова Яна Михайловна
студент 4 курс, факультет «Экономическая безопасность»
Институт Национальной безопасности РАНХиГС
Россия, г. Москва
Аннотация
В статье поднимается вопрос о построении гамильтонового пути способом расширяющейся выделенной области в неориентированном полносвязанном симметричном взвешенном графе.
В статье рассматриваются вопрос решения задач обработки информации и управления в системах поддержки принятия решений на примере задачи коммивояжера. Предлагаются рассмотреть способ расширяющейся выделенной области при построении гамильтонового пути в неориентированном полносвязанном равновзвешенном графе. Статья найдет отклик у специалистов в области автоматизированного решения задач обработки информации и управления.
Annotation
The article raises the question of constructing a Hamiltonian path by the method of an expanding selected domain in an undirected fully connected symmetric weighted graph.
The article discusses the issues of solving information processing and management problems in decision support systems by the example of the traveling salesman problem. It is proposed to consider the method of expanding the selected area when constructing a Hamiltonian path in an undirected fully connected equally weighted graph. The article will find a response from specialists in the field of automated solutions to information processing and management problems.
Ключевые слова: система поддержки принятия решения, задача коммивояжёра, алгоритмизация, неориентированные графы, поиск наикратчайшего пути в графе, задача оптимизации.
Keywords: decision support system, traveling salesman problem, algorithmization, undirected graphs, search for the shortest path in a graph, optimization problem.
Настоящий способ относится к классу жадных алгоритмов.
Наиболее близким к предлагаемому способу является метод, известный как «Метод эластичных сетей» [Durbin R, Willshaw D (1987)].
Цель настоящего способа заключается в повышении точности при построении гамильтонового пути в неориентированном полносвязанном равновзвешенном графе.
При всех достоинствах прототипа, имеются недостатки, первый заключается в том, что первоначально выделенной областью на плоскости является окружность, что не гарантирует на первичном этапе минимально выбранной фигуры по весу между вершинами. Второй заключается в том, что расширение окружности проводится по двум силам, первая сила: область окружности перемещается в сторону ближайшей вершины, вторая сила: смещает в сторону ее соседей на кольце так, чтобы уменьшить его длину, недостатком является то, что первая и вторая сила описываются вводимыми параметрами, представленными в виде переменных применяемых в формуле по вычислению точки расширения на окружности, которые возможно заменить условиями выполнения при проведении вычислений, также в настоящем методе введено понятие эффективного радиуса, который также присутствует и формуле в виде переменной, настоящее понятие и переменную возможно исключить без потери точности вычислений.
Результат достигается за счёт того, что из конечного множества вершин неориентированного равновзвешенного полносвязанного графа выбираются три вершины имеющие минимальный вес рёбер между собой, соединяются в выделенную область и образуют треугольник, поэтапно к настоящей области присоединяются все свободные вершины не включенные в выделенную область, с минимальным приращением к общему весу выделенной области.
Построение гамильтонового пути способом расширяющейся выделенной области проводится последовательно, но для интуитивного восприятия возможно разделить на три блока.
Первый блок является самым трудоемким и заключается в поиске трех вершин связанных между собой наименьшим весом по отношению к остальным вершинам. Найденные три вершины образуют треугольник, который является геометрической фигурой с наименьшим периметром во всем конечном представленном графе. Данный треугольник является первоначальной выделенной областью, с которой начинается поглощение свободных вершин графа не включенных в выделенную область.
Для этого на плоскости введен конечный граф
, представленный двухмерным массивом весов
(блок 2, рис. 5),
— это число вершин в графе
, а
— число неориентированных ребер в графе
. Для каждого ребра графа
задан вес
, который равновзвешен
.
Для поиска обозначенных трех вершин, введем три одномерных массива: массив
— содержит все комбинации попарно сочетаемых вершин графа, массив
— будет заполняться на первом этапе тремя вершинами графа с минимальными весами между собой, в дальнейшем будет заполнен всеми вершинами графа, последовательно расположенными и образующими гамильтонов цикл, массив
— содержит все свободные вершины не включенные в массив
.
В цикле обходится массив
с первой строкой массива
, содержащей все вершины графа (блок 3, рис. 5).
Пусть ячейка массива
содержит сочетание вершин
, которая сравнивается с вершиной
расположенной в одной из ячеек первой строки массива
и образует сочетание вершин
. Общий вес для трех вершин вычисляется по формуле:
|
. |
(1) |
где
— это общий вес рассматриваемых вершин.
Из всего множества сочетаний, выбираются три вершины с наименьшим общим весом и заносятся в массив
, данная область является первичной выделенной областью. Рассмотрим частный пример неориентированного полносвязанного равновзвешенного графа рис. 1 а., при функционировании настоящего способа рис. 1 б.
Во втором блоке выбирается ближайшая свободная вершина рис. 2 а. на плоскости к выделенной области (блок 4, рис. 5). Вычисления проводится путем поочередного сравнения расстояний от двух смежных вершин выделенной области из массива
к вершинам из массива
.
Пусть
и
свободные вершины из массива
, проводится перебор смежных вершин из массива
к настоящим вершинам.
|
,
. |
(2) |
Пусть ближайшей вершиной к выделенной области является вершина
, настоящая вершина удаляется из массива
.
В третьем блоке выбирается точка на выделенной области, куда ближайшая свободная вершина будет добавлена (блок 5, рис. 5).
Проводится это путем вычисления общего веса выделенной области, путем поочередного добавления свободной вершины
между смежными вершинами на выделенной области из массива
.
|
. |
(3) |
Выбирается наименьшая полученная общая длина из возможных сочетаний. В массив
согласно выбранного сочетания, заносится свободная вершина
.
Второй и третий блок повторяются (блок 6, рис. 5), пока все вершины из массива
не переместятся в массив
(блок 7, рис. 5), рис. 2 б – рис. 4.
Рисунок 1 Пример неориентированного полносвязанного равновзвешенного графа при данном методе
|
|
|
|
Рисунок 1 а.
|
Рисунок 1 б.
|
Рисунок 2 Выбор ближайшей свободной вершины
|
|
|
|
Рисунок 2 а. |
Рисунок 2 б. |
Рисунок 3 Выбор точки на выделенной области, куда ближайшая свободная вершина будет добавлена
|
|
|
|
Рисунок 3 а. |
Рисунок 3 б.
|
Рисунок 4 Нахождение ближайшей свободной вершины на плоскости к выделенной области
|
|
|
Рисунок 4
|
Рисунок 5 Алгоритм построения гамильтонового цикла путем расширяющейся выделенной области представлен в виде блок-схемы
|
|
|
Рисунок 5 |
Выводы:
Таким образом, результатом работы данного способа является построенный гамильтонов цикл с непересекающимися ребрами, представленный в виде, как правило, неправильного многоугольника на основе неориентированного равновзвешенного полносвязанного графа.
Настоящий способ решения подходит к большинству структурно-сложных графов.
Предлагаемый способ является полностью алгоритмизированным, на основании данного алгоритма написано программное обеспечение [5].
Технико-экономическая эффективность предлагаемого способа заключается в повышении точности при построении взвешенного гамильтонового цикла путём последовательного объединения непересекающихся подмножеств и вершин в неориентированном полносвязанном равновзвешенном конечном графе, с допустимой точностью свойственной «жадным» алгоритмам.
Список используемой литературы:
1. Моисеев Д. В. Комплекс методик декомпозиции структурно-сложных систем различного назначения. //Wschodnioeuropejskie Czasopismo Naukowe (East European Scientific Journal) Warsaw, Poland.: «Jerozolimskie», № 7(47), 2019 г. – С. 66 – 70.
2. Кормен, Томас Х. и др. Алгоритмы: построение и анализ, 3-е изд.:
Пер. с анг. – М.: ООО «И.Д. Вильямс», 2013, С. 668-670.
3. Колесников А.В. и др. Решение сложных задач коммивояжера методами функциональных гибридных интеллектуальных систем / Под ред.
А.В. Колесникова. – М.: ИПИ РАН, 2011. — 295 с., ил. — ISBN 978-5-902030-88-1
4. Моисеев Д.В., Поляков А.А., Программа для ЭВМ № 2022683555, Построение гамильтонового пути способом расширяющейся выделенной области. Правообладатель: Федеральное государственное автономное образовательное учреждение высшего образования «Севастопольский государственный университет», дата подачи заявки: 23.11.2022, дата гос. регистрации: 06.12.2022, дата публикации: 06.12.2022, номер заявки: 2022682657.
5. Моисеев Д.В. , Поляков А.А., Программа для ЭВМ № 2022683676, Перестроение структуры гамильтонового пути способом переоценки веса ребер построенного пути с весом ребер локального предполагаемого минимума. Правообладатель: Федеральное государственное автономное образовательное учреждение высшего образования «Севастопольский государственный университет», дата подачи заявки: 23.11.2022, дата гос. регистрации: 07.12.2022, дата публикации: 07.12.2022, номер заявки: 2022682703.