ПОИСКА КРАТЧАЙШЕГО ПУТИ

Введение

Проблема распределения ресурсов возникает в различных областях науки, техники и общества. В зависимости от области применения и конкретных рассматриваемых задач характер распределения ресурсов может различаться.В предметной области сетей связи эта задача является одной из приоритетных, так как от ее решения напрямую зависит поддержание работоспособности сети. В общем случае она сводится к построению пути доставки услуги связи конкретному пользователю сети связи. В процессе решения задачи распределения ресурсов в сети связи можно выделить несколько основных этапов: выявление свободных ресурсов, установление кратчайшего пути для подключения пользователей, проверка выполнения всех требований и принятие окончательного решения. Наиболее сложными из этих этапов являются второй и третий этапы. На этапе построения кратчайшего пути из-за большого количества узлов связи и точек переключения в случае территориально распределенных сетей связи возникают трудности получения вероятности оптимального пути без использования вычислительной техники. Маршруты значительно сократились. Использование необоснованной маршрутизации может привести к отказу в обслуживании будущих пользователей из-за нехватки свободных ресурсов и повлечь за собой дополнительные материальные и трудовые затраты. Также важным шагом является проверка того, что маршрут соответствует всем требованиям. Сложность заключается в том, что линии связи, из которых состоит коммуникационная сеть, имеют множество факторов, которые необходимо учитывать. В противном случае невыполнение установленных требований может повлечь за собой отказ в предоставлении услуг связи пользователям или снижение качества предоставляемых услуг.В настоящее время степень автоматизации решения этой задачи в области сетей связи слабая. Использовать эвристики для принятия и принятия решений на основе профессионального опыта участников системы менеджмента. Такие решения в основном субъективны. В век информационных технологий необходимо уменьшить влияние субъективных факторов на качество принятия решений. В области управления сетью связи это может быть достигнуто за счет разработки алгоритма распределения ресурсов сети связи, который будет удовлетворять всем требованиям и соответствовать специфике предметной области.Благодаря прикладной универсальности теория о нахождении кратчайшего пути в графе в настоящее время интенсивно развивается и используется в различных областях науки и техники, например, в картографических сервисах, для прокладки трассировки электрических соединений на кристаллах микросхем и на печатных платах, в системах коммутации информационных пакетов в сети Internet и т.д.Метод кратчайшего пополняющего пути для задач динамического назначения Задача о кратчайшем пути — это задача нахождения кратчайшего пути (цепи) между двумя точками (вершинами) на графе, где минимизируется сумма весов ребер, составляющих путь.Задача о кратчайшем пути — одна из важнейших классических задач теории графов. На сегодняшний день существует множество алгоритмов ее решения. У этой задачи есть и другие названия: задача о минимальном пути или, в устаревших версиях, задача о дилижансе.Важность этого вопроса зависит от его различных практических применений. Например, GPS-навигаторы ищут кратчайший путь между двумя перекрестками. Перекрестки действуют как вершины, а дороги — как ребра, лежащие между ними. Кратчайший путь находится, если сумма длин дорог между перекрестками наименьшая.Рассмотрим несколько наиболее популярных алгоритмов поиска кратчайшего пути в графе:• алгоритм Дейкстры;• алгоритм Беллмана-Форда;• алгоритм поиска А*;• алгоритм Флойда-Уоршелла;• алгоритм Ли (волновой алгоритм) [4]. Алгоритм Дейкстры. Самый известный и широко распространенный алгоритм. Был разработан голландским ученым Эдсгером Дейкстрой в 1959 году и используется для нахождения пути в графе из одной вершины до всех остальных. Алгоритм работает исключительно для графов с ребрами положительного веса. Вычислительная сложность алгоритма - 0(п* + ш).Рисунок 1 – Алгоритм ДейкстрыЭтот алгоритм считается одним из самых простых. Он хорошо работает в графах с небольшим количеством вершин. В случае коммуникационных сетей количество вершин в графе может достигать нескольких тысяч. Тогда использование этого алгоритма будет не лучшим выбором для решения задачи построения маршрутизации пользовательских соединений в сетях связи. Также в нашем случае недостатком алгоритма Дейстры является то, что он находит кратчайший путь от одной вершины графа ко всем остальным вершинам графа.Алгоритм Беллмана-Форда. Это алгоритм поиска кратчайшего пути во взвешенном графе, который находит путь от одной вершины до всех остальных. В отличие от алгоритма Дейкстры, алгоритм Беллмана-Форда допускает наличие в графе ребер с отрицательным весом. Был предложен независимо американцами Ричардом Беллманом и Лестором Фордом. Вычислительная сложность алгоритма - 0(п * ш) [3].Рисунок 2 – Алгоритм Беллмана-ФордаЭтот алгоритм находит кратчайший путь от одной вершины графа ко всем остальным вершинам графа. Условием нашей задачи является нахождение разумного пути между двумя точками коммуникационной сети. Слишком много лишней маршрутной информации требует дополнительных ресурсов компьютера, а алгоритм использует полный перебор всех вершин графа, что приводит к большим потерям времени и занимает больше памяти компьютера.Алгоритм поиска А*. Был разработан в 1968 году Питером Хартом, Нильсом Ниль-соном и Бертрамом Рафаэлем. Данный алгоритм по сути является расширением алгоритма Дейкстры, но достигает более высокой производительности за счет введения в работу алгоритма эвристической функции.Алгоритм А* является алгоритмом поиска по первому наилучшему совпадению на графе, который находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной). Порядок обхода вершин определяется эвристической функцией «расстояние + стоимость» (обычно обозначаемой как /(:£)).Данный алгоритм пошагово просматривает все пути, ведущие от начальной вершины в конечную, пока не найдет минимальный. С точки зрения требуемого результата, а именно нахождения кратчайшего маршрута между двумя точками графа, алгоритм А* нам подходит. Но его недостатком является то что, он осуществляет поиск среди всех вершин графа. В случае, если граф будет иметь большое количество вершин этот алгоритм будет являться неэффективным.Алгоритм Флойда-Уоршелла. Этот алгоритм был разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом. Является динамическим алгоритмом для поиска кратчайших расстояний между всеми вершинами взвешенного ориентированного графа.Рисунок 3 – Алгоритм Флойда-УоршеллаДанный алгоритм имеет вычислительную сложность. При применении его к решению задач на значительно разветвленном графе, он потребует значительных затрат со стороны ресурсов вычислительной машины. К тому же, алгоритм Флойда-Уоршела применяется для нахождения путей из одной вершины во все остальные, что противоречит условиям нашей задачи.Алгоритм Ли (волновой). Ли разработал этот алгоритм в 1961 году при формализации алгоритмов трассировки печатных плат. В основном используется при компьютерной разводке печатных плат, соединительных проводников на поверхности микросхем. Другое применение волнового алгоритма - поиск кратчайшего расстояния на карте в компьютерных стратегических играх.Рисунок 4 – Алгоритм ЛиАлгоритм работает на дискретном рабочем поле (ДРП), представляющем собой ограниченную замкнутой линией фигуру, не обязательно прямоугольную, разбитую на прямоугольные ячейки, в частном случае - квадратные. Множество всех ячеек ДРП разбивается на подмножества: «проходимые» (свободные), т. е при поиске пути их можно проходить, «непроходимые» (препятствия), путь через эту ячейку запрещён, стартовая ячейка (источник) и финишная (приемник). Назначение стартовой и финишной ячеек условно, достаточно - указание пары ячеек, между которыми нужно найти кратчайший путь.Алгоритм предназначен для поиска кратчайшего пути от стартовой ячейки к конечной ячейке, если это возможно, либо, при отсутствии пути, выдать сообщение о непроходимости. Вычислительная сложностьПутем анализа структурных характеристик и условий работы сети связи можно определить множество факторов, затрудняющих использование рассматриваемого алгоритма в качестве базового алгоритма решения задачи оптимального распределения ресурсов сети связи.Граф, описывающий структуру коммуникационной сети, имеет большое количество вершин. Для уменьшения объема вычислений рекомендуется на предварительном этапе исключать из рассмотрения ресурсы, явно непригодные для решения той или иной задачи распределения, выбирая тем самым подграф, в котором будет работать основной алгоритм поиска пути. Такой этап может быть основан на алгоритме Ли. Кроме того, этот алгоритм является наиболее подходящим с точки зрения наименьшей вычислительной сложности.Рассмотренный алгоритм подходит для взвешенных графов. Невзвешенные графы — это частный случай взвешенных графов с равными весами. В этом случае длина маршрута зависит от количества вершин, через которые он проходит. Требования станций и оконечного оборудования сети связи определяют предельные значения технических параметров линии (например, сопротивление шлейфа или емкость линии) и максимально возможное количество точек коммутации (по модели - апекс). Коммуникационная сеть представляет собой сложную систему со многими свойствами, которые влияют на пригодность выбранного маршрута и должны рассматриваться комплексно. Следовательно, веса ребер используемого графа должны быть представлены некоторыми векторными индексами. Рассмотренные алгоритмы работают в основном на основе скалярных или низкоразмерных векторных значений весов ребер графа.Определение интервалов устойчивости назначенияМатематическая задача о назначениях или задача о выборе формулируется следующим образом. Требуется выбрать такую последовательность элементов  из следующей квадратной матрицычтобы  достигала своего максимального значения, причем  при . Другими словами, нужно выбрать из каждого столбца и каждой строки ровно по одному элементу так, чтобы их сумма была максимальной.Отметим, что если бы матрица C была устроена так, что максимальные элементы каждой строки лежали бы в разных столбцах, то решение задачи было бы элементарным, т.е. к качеству решения нужно было выбрать эти максимальные элементы. Однако обычно максимальные элементы нескольких строк(столбцов) расположены в одном и том же столбце (строке) и решение проблемы затрудняется.При решении задачи о назначениях применяется венгерский метод, что существенно упрощает решение задачи. Разработайте алгоритмы для решения проблемПри разработке алгоритмов для решения задач важно использовать язык блок-схем. Для решения одной и той же задачи могут использоваться различные алгоритмы, которые различаются по времени вычислений, объему вычислений и их сложности. Документирование этих алгоритмов с помощью блок-схемы позволяет сравнивать их, выбирать лучший алгоритм, упрощать, находить и устранять ошибки.Отказ от языков блок-схем при разработке алгоритмов и непосредственная разработка алгоритмов на языках программирования приводит к значительным потерям времени, что приводит к выбору неоптимальных алгоритмов. Поэтому необходимо сначала разработать алгоритм решения задачи на языке блок-схем, а затем перевести алгоритм на язык программирования.Поэтапный подход к разработке используется при разработке алгоритмов для сложных задач. В качестве первого шага рассмотрим общую структуру алгоритма, не рассматривая подробно его отдельные части. Блоки, требующие уточнения, выделены пунктирными линиями и рассматриваются, и детализируются на последующих этапах разработки алгоритма.В процессе разработки алгоритма решения задачи можно выделить следующие этапы:Этап 1 . Математическое описание решения задачи.Этап 2 . Определение входных и выходных данных.Этап 3 . Разработка алгоритма решения задачи.Базовые алгоритмические конструкцииВ теории программирования доказано, что для записи любого, сколь угодно сложного алгоритма достаточно трех базовых структур:следование (линейный алгоритм);ветвление (разветвляющийся алгоритм);цикл-пока (циклический алгоритм).Линейные алгоритмыЛинейный алгоритм образуется из последовательности действий, следующих одно за другим. Например, для определения площади прямоугольника необходимо сначала задать длину первой стороны, затем задать длину второй стороны, а уже затем по формуле вычислить его площадь.Рисунок 5. Линейный методПримерЗАДАЧА. Разработать алгоритм вычисления гипотенузы прямоугольного треугольника по известным значениям длин его катетов a и b.На примере данной задачи рассмотрим все три этапа разработки алгоритма решения задачи:Этап 1. Математическое описание решения задачи.Математическим решением задачи является известная формула:,где с-длина гипотенузы, a, b – длины катетов.Этап 2. Определение входных и выходных данных.Входными данными являются значения катетов a и b. Выходными данными является длина гипотенузы – c.Этап 3. Разработка алгоритма решения задачи.Словесное описание алгоритмаЗапись алгоритма на языке блок-схемНачало алгоритма.Ввод значений длин катетов a и b.Вычисление длины гипотенузы с по формулеВывод значения длины гипотенузы.Конец алгоритмаНа данной схеме цифрами указаны номера элементов алгоритма, которые соответствуют номерам пунктов словесного описания алгоритма.Разветвляющиеся алгоритмыАлгоритм ветвления содержит условие, в зависимости от которого выполняется та или иная последовательность действий.ПримерЗАДАЧА. Разработать алгоритм вычисления наибольшего числа из двух чисел x и y.Этап 1. Математическое описание решения задачи.Из курса математики известно, если x > y, то наибольшее число x, если x < y, то наибольшее число y, если x = y, то число x равно числу y.Этап 2. Определение входных и выходных данных.Входными данными являются значения чисел x и y. Выходным данными являются:наибольшее числолюбое из чисел, если числа равныДля решения задачи нам необходимо знать значения x и y.Этап 3. Разработка алгоритма решения задачи.Словесное описание алгоритмаЗапись алгоритма на языке блок-схемНачало алгоритма.Ввод значений x и y.Сравниваем x и y. Если x = y, то переход к шагу 4, иначе к шагу 5.Вывод информации: числа x и y равны. Переход к шагу 8.Сравниваем x и y. Если x > y, то переход к шагу 6, иначе к шагу 7.Вывод информации: число x больше y. Переход к шагу 8.Вывод информации: число y больше x. Переход к шагу 8.Конец алгоритма.В схеме алгоритма решения задачи цифрами указаны номера элементов алгоритма, которые соответствуют номерам шагов словесного описания алгоритмаВ рассматриваемом алгоритме имеются три ветви решения задачи:первая: это элементы 1, 2, 3, 4, 8.вторая: это элементы 1, 2, 3, 5, 6, 8третья: это элементы 1, 2, 3, 5, 7, 8.Выбор ветви определяется значениями x и y в элементах 3 и 5, которые являются условиями, определяющими порядок выполнения элементов алгоритма. Если условие (равенство), записанное внутри символа «решение», выполняется при введенных значениях x и y, то следующими выполняется элементы 4 и 8. Это следует из того, что они соединены линией с надписью «да» и направление (последовательность) вычислений обозначена стрелочкой.Если условие в элементе 3 не выполняется, то следующим выполняется элемент 5. Он соединен с элементом 3 линией с надписью «нет». Если условие, записанное в элементе 5, выполняется, то выполняется элементы 6 и 8, в противном случае выполняются элементы 7 и 8.Циклические алгоритмыЦиклический алгоритм – определяет повторение некоторой части действий (операций), пока не будет нарушено условие, выполнение которого проверяется в начале цикла. Совокупность операций, выполняемых многократно, называется телом цикла.Рисунок 6. Циклическая схема Алгоритмы, отдельные действия в которых многократно повторяются, называются циклическими алгоритмами, Совокупность действий, связанную с повторениями, называют циклом.При разработке алгоритмов петлевых структур необходимо различать следующие понятия:• Параметры цикла - изменение значения связано с повторным выполнением цикла;• Начальные и конечные значения параметров контура;• Шаг цикла — значение параметра цикла, которое изменяется при каждом повторении.Циклы организованы по определенным правилам. Алгоритм цикла состоит из подготовки цикла, тела цикла и условия продолжения цикла.Подготовка цикла включает в себя действия, связанные с установкой начальных значений параметров цикла:• начальное значение цикла;• конечное значение цикла;• Шаги цикла.В тело (структуру) цикла входят:• Повторяющееся действие вычисления ожидаемого значения;• Подготовка значение параметра цикла;• Подготовка других значений, необходимые для повторения действия в теле цикла.Там, где цикл продолжается, определяется допустимость выполнения повторяющихся действий. Цикл должен быть завершен, если параметр цикла равен или превышает значение конца цикла.ЗаключениеЗадача нахождения кратчайшего пути — классическая задача теории графов — раздела дискретной математики, изучающего свойства графов. Этот раздел используется во многих сферах нашей жизни: геоинформационные системы, дорожное строительство, сетевые коммуникации и многое другое.История возникновения теории графов берет свое начало в проблеме Кенигсбергского моста — старой математической задаче о том, как пересечь все семь мостов Кенигсберга, не пересекая ни один из них дважды. Эта задача впервые была решена в 1936 году русско-немецким математиком Леонардом Эйлером. В письме от 13 марта 1736 года итальянскому математику и инженеру Маринони он изложил основные выводы теории графов, положившие начало этой математической дисциплине.Интерес к развитию теории графов возродился на рубеже 19 и 20 вв. В изучении графов есть много причин для этого ренессанса. Естественные науки внесли свой вклад в это, исследуя электрические сети и молекулярные цепи. Теория графов также набрала обороты, когда резко увеличилось количество публикаций в области топологии и комбинаторики.В данной работе раскрываются некоторые плюсы и минусы алгоритмов поиска кратчайших путей в графах. Для решения задачи распределения ресурсов сети связи наиболее удобным методом является использование алгоритма, основанного на алгоритме Ли, так как он учитывает многие характеристики рассматриваемого процесса.Посредством анализа могут быть определены приоритетные направления решения задачи оптимального распределения ресурсов коммуникационной сети, в том числе: предварительная разработка алгоритмов выделения фактических подграфов; формулировка правил принятия решений, учитывающих многомерность и неоднородность коммуникаций. характеристики сетевого элемента, важные для принятия решений.

Список литературы

Колмогоров А. Н. А. Н. Колмогоров. Избранные труды. В 6 томах. Том 3. Теория информации и теория алгоритмов; Наука - , 2008. - 264 c.Мельников О.И. Занимательные задачи по теории графов; С.-Петербург: Типография главного управления Удлов - Москва, 2012. - 689 c.ОИ3. Палий, И. А. Дискретная математика : учебное пособие для среднего профессионального образования / И.А. Палий. – М.: Издательство Юрайт, 2019 — 352 с. — (Профессиональное образование).— Текст : электронный // ЭБС Юрайт [сайт]. — URL: https://biblio-online.ru/bcode/441865 . С. 238-245 (раздел 3.4.3 «Задача о кратчайшем пути и алгоритм Дейкстры ее решения»).ОИ2. Попов, А. М. Теория вероятностей и математическая статистика : учебник для среднего профессионального образования / А. М. Попов, В. Н. Сотников. — 2-е изд., испр. и доп. — Москва : Издательство Юрайт, 2019 — 434 с. — (Профессиональное образование). — ISBN 978-5-534-01058-9. — Текст : электронный // ЭБС Юрайт [сайт]. — URL: https://biblio- online.ru/bcode/433536. Режим доступа: авториз. пользователи. – С. 267-275 (раздел 14.4 «Приложение теории графов к решению задач»).Харари Ф. Теория графов; Либроком - Москва, 2019. - 302 c.