Задача поиска маршрутов в графе (путей в орграфе)
Задача поиска маршрутов в графе (путей в орграфе)
Алгоритм Тэрри поиска маршрута в связном графе, соединяющем вершины и.
Правила.
- 1) Идя по произвольному ребру всегда отмечать направление его прохождения. 2) Исходя из некоторой вершины всегда следовать по тому ребру, которое не было пройдено или было пройдено в противоположном направлении. 3) Для всякой вершины отмечать ребро, по которому в вершину попали в первый раз 4) Исходя из некоторой вершины идти по первому заходящему в ребру лишь тогда, когда нет других возможностей.
Найти маршрут соед. и. +, значит прошли
Замечание: из полученного пути можно выделить простую цепь.
Поиск оптимального пути (маршрута) (т. е пути с наименьшим числом дуг или ребер)
Утверждения:
1) каждый минимальный путь (маршрут) является простой цепью
Доказательство.
Пусть минимальный путь в орграфе D, не являющийся простой цепью. Тогда i и j такие, что и vI=vJ. Рассмотрим путь. Его длина меньше, чем, что противоречит предположению.
2) (о минимальности подпути минимального пути). Пусть - минимальный путь (маршрут) в орграфе D (в графе G). Тогда для i и j таких, что путь (маршрут) тоже является минимальным.
Доказательство. Предположим, что не является оптимальным, тогда т. ч. он короче чем. Тогда заменив на в можно найти более короткий, чем путь не является минимальным. Пришли к противоречию.
Пусть орграф - некоторая вершина.
Обозначим - образ вершины ;
- - прообраз вершины ; - образ множества вершин V1;
прообраз множества вершин V1.
Для неориентированного графа образ и прообраз совпадают.
Пусть граф.
Обозначим - образ вершины ;
- образ множества вершин V1.
Пусть орграф с n2 вершинами и v, w (vw) - заданные вершины из V
Алгоритм поиска минимального пути из в в орграфе D (алгоритм фронта волны).
- 1) Помечаем вершину индексом 0, затем помечаем вершины образу вершины индексом 1. Обозначаем их FW1 (v). Полагаем k=1. 2) Если или k=n-1, и одновременно то вершина не достижима из. Работа алгоритма заканчивается.
В противном случае продолжаем:
3) Если, то переходим к шагу 4.
В противном случае мы нашли минимальный путь из в и его длина =k. Последовательность вершин
Есть этот минимальный путь. Работа завершается.
4) Помечаем индексом k+1 все непомеченные вершины, которые принадлежат образу множества вершин c индексом k. Множество вершин с индексом k+1 обозначаем. Присваиваем k:=k+1 и переходим к 2).
Замечания
Множество называется фронтом волны kГо уровня.
Вершины могут быть выделены неоднозначно, что соответствует случаю, если несколько min путей из в.
Пример 1. Дана матрица смежности. Найти минимальный путь из v1 в v6.
Исхвход | |||||
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
2 |
2 |
1 |
1 |
3 |
,
Пример 2. Дан орграф.
Задание. Найти минимальный путь из v1 в v6.
Матрица смежности
Исхвход | |||||
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
1 |
1 |
3 |
Расстояния в графе
Пусть - граф (или псевдограф).
Расстоянием между вершинами наз. min длина пути между ними. .
Расстояние в графе удовл. аксиомам метрики
- 1) , 2) (не орграф) 3) 4) в связном графе ( в орграфе, если не пути).
Пример
1 |
2 |
3 |
4 |
5 |
6 | |
1 |
1 |
1 |
0 |
0 |
21 |
0 |
2 |
0 |
0 |
1 |
0 |
0 |
0 |
3 |
0 |
0 |
0 |
0 |
0 |
1 |
4 |
1 |
1 |
0 |
0 |
0 |
0 |
5 |
0 |
0 |
1 |
1 |
0 |
0 |
6 |
0 |
1 |
0 |
0 |
0 |
0 |
Из 1 |
0 |
1 |
2 |
2 |
1 |
3 |
Из 2 |
0 |
1 |
2 | |||
Из 3 |
2 |
0 |
1 | |||
Из 4 |
1 |
1 |
2 |
0 |
2 |
3 |
Из 5 |
2 |
3 |
1 |
1 |
0 |
2 |
Из 6 |
1 |
2 |
0 |
Опр || Пусть связный граф (или псевдограф).
Величина - называется диаметром графа G.
Пусть.
Величина - называется максимальным удалением (эксцентриситетом) в графе G от вершины.
Радиусом графа G наз. величина
Любая верш. такая, что наз. центром графа G.
Матрица смежности
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
Матрица расстояний
0 |
1 |
2 |
2 |
3 |
1 |
0 |
1 |
1 |
2 |
2 |
1 |
0 |
1 |
2 |
2 |
1 |
1 |
0 |
1 |
3 |
2 |
2 |
1 |
0 |
Центры в вершинах 2, 3, 4
Примеры.
Матрица смежности
1 |
2 |
3 |
4 |
5 |
6 | |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
2 |
1 |
0 |
0 |
1 |
0 |
1 |
3 |
0 |
0 |
0 |
0 |
1 |
1 |
4 |
0 |
1 |
0 |
0 |
1 |
0 |
5 |
1 |
0 |
1 |
1 |
0 |
0 |
6 |
0 |
1 |
1 |
0 |
0 |
0 |
Матрица расстояний
1 |
2 |
3 |
4 |
5 |
6 | |
1 |
0 |
1 |
2 |
2 |
1 |
2 |
2 |
1 |
0 |
2 |
1 |
2 |
1 |
3 |
2 |
2 |
0 |
2 |
1 |
1 |
4 |
2 |
1 |
2 |
0 |
1 |
2 |
5 |
1 |
2 |
1 |
1 |
0 |
2 |
6 |
2 |
1 |
1 |
2 |
2 |
0 |
, центр - все вершины
Маршрут граф дуга смежность
Похожие статьи
-
Наличие особых ситуаций на террайне зависит от характеристик его сложности. Ниже приведена возможная классификационная схема характеристик сложности...
-
Введение, Основные положения - Эволюционные процедуры решения комбинаторных задач на графах
Среди набора комбинаторно-логических задач на графах важное место занимает проблема определения паросочетаний, раскраски графа, выделения в графе...
-
О клике. Определим формально задачу поиска максимальной клики, согласно статьи On the maximum quasi-clique problem [17]. Пусть G=(V, E) - простой...
-
Рассмотрим взвешенный предфрактальный граф, порожденный затравкой и K процессоров, где. Параллельный алгоритм выделения дольного графа основан на...
-
Алгоритмы поиска квази-клики в графе. - Использование квази-клик для анализа графа рынка России
Как и для поиска клик существуют алгоритмы поиска квази-клик в графе. Далее мы рассмотрим некоторые из них. Как было сказано ранее, задача поиска...
-
Задачи, связанные с поиском гамильтоновых циклов - Гамильтоновы циклы
В ряде отраслей промышленности возникает следующая задача планирования. Нужно произвести n продуктов, используя единственный тип аппаратуры. Аппарат...
-
Формирование З -областей в матрице R осуществляется в процессе ее эволюционной модификации. Эволюционная модификация матрицы R производится путем...
-
О квази-клике. - Использование квази-клик для анализа графа рынка России
Квази-клика - представляет собой релаксацию строгого условия полноты клики, то есть допускается отсутствие некоторых ребер в искомом подграфе. На данный...
-
Расчет верхней и нижней границы надежности схемы методом минимальных путей и сечений Как видно из схемы, она не является последовательно-параллельной,...
-
Задача маршрутизации реализуется набором алгоритмов, каждый из которых осуществляет решение задачи коммивояжера. Коммивояжер (распространитель товаров)...
-
РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ: ОСНОВНАЯ СХЕМА - Задача коммивояжера
Пусть - конечное множество и - вещественно-значная функция на нем; требуется найти минимум этой функции и элемент множества, на котором этот минимум...
-
ПОСТАНОВКА ЗАДАЧИ - Задача коммивояжера
Пусть имеется п городов. Расстояния между любой парой городов (i, j) известны и составляют dij, где i=1, m; j=1, n; i?j. Если прямого маршрута...
-
В зависимости от содержания задачи может быть два случая: когда ребра графа G единичной длины; когда ребра графа произвольной длины. Для каждого из этих...
-
Если ответы экспертов - кластеризованные ранжировки, то вычисление медианы Кемени является задачей целочисленного программирования. Для ее нахождения...
-
Введение - Использование квази-клик для анализа графа рынка России
Графы, состоящие из вершин и ребер, представляют удобный инструмент моделирования для изучения различных сетевых структур, в том числе, социальных сетей,...
-
Введение - Моделирование крупномасштабной транспортной сети предфрактальными графами
Транспорт - важный стратегический комплекс, в значительной степени определяющий мощь экономики страны и обеспечивающий нужды общества в перемещении людей...
-
При анализе больших объемов данных зачастую их можно представить в виде графа. Основными атрибутами графа являются вершины и ребра, поэтому изучение...
-
Моделирование транспортной сети большой размерности с помощью предфрактальных графов позволяет строить эффективные алгоритмы благодаря свойству...
-
Это раздел математического программирования, изучающий методы решения таких экстремальных задач, в которых результаты (эффективность) возрастают или...
-
Определим понятие предфрактального графа индуктивно. Обозначим через - конечный связный n-вершинный граф с множеством вершин и множеством ребер, который...
-
РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ. ПРИМЕРЫ - Задача коммивояжера
Рассмотрим конкретный пример реализации метода ветвей и границ для решения задачи о коммивояжере. Итак, требуется найти легчайший простой основный...
-
В настоящее время Российская Федерация входит в состав ВТО, в связи с чем, для устойчивого развития, для надежности, для стойкости [1, 2] появляется...
-
Применительно к предприятию КУП "СПЕЦКОММУНТРАНС" данная задача представляет собой задачу нахождения наилучшего маршрута движения автомобиля,...
-
Построение графа рынка России - Использование квази-клик для анализа графа рынка России
Для начала работы с алгоритмической частью требуется построить граф рынка. Для того, чтобы проанализировать правильность подхода с применением...
-
Пока неизвестно никакого простого критерия или алгебраического метода, позволяющего ответить на вопрос, существует или нет в произвольном графе G...
-
Заключение - Использование квази-клик для анализа графа рынка России
Данная выпускная работа была посвящена проблеме поиска плотных подграфов в графе. Основные усилия в ней были направлены на разработку алгоритма поиска...
-
Пусть на некотором отрезке [a, b] задана кусочно-монотонная функция f(x). Покажем, что данную функцию в точках ее непрерывности можно представить в виде...
-
Задача кластеризации может быть сведена к задаче раскраски вершин графа. Для этого строится граф несовместимости. Вершинам графа соответствуют...
-
Задача кластеризации реализуется набором методов (алгоритмов), каждый из которых осуществляет разбиения региона на компактные зоны обслуживания. Аппарат...
-
Для заданного региона обслуживания с помощью технологии ГИС предоставляется карта автомобильных дорог, на которой указаны пункты, соответствующие...
-
В работах [22, 14, 15] приведены результаты изучения свойств медианы Кемени, полученные с помощью расчетов по алгоритмам В. Н. Жихарева [18], описанным...
-
Все генетические алгоритмы участвовали в двух группах тестов. В каждой группе исследовались различные наборы значений управляющих параметров МГА:...
-
Задача о загрузке рюкзака (задача о ранце) - Метод динамического программирования для решения задач
Постановка задачи. Пусть имеются N видов грузов с номерами. Единица груза j-го вида имеет все aJ. Если груз j-го вида берется в количестве xJ, то его...
-
Необходимость введения нового ограничения может возникнуть, например, когда первоначально для сокращения затрат машинного времени некоторые интуитивно...
-
Выводы, Литература - Моделирование крупномасштабной транспортной сети предфрактальными графами
В качестве модели карты дорог предлагается использовать предфрактальные графы, которые естественным образом отражают структуру связей при рассмотрении...
-
Ограничение чувствительность задача программирование Вариации правых частей ограничений приводят к изменению области допустимых решений ЗЛП, в действии...
-
Вариации коэффициентов целевой функции ЗЛП приводят к изменению направления вектора градиента. Так как при этом не затрагивается допустимое множество, то...
-
При решении экономических задач часто анализировать ситуации, в которых сталкиваются интересы двух или более конкурирующих сторон, преследующих различные...
-
Пусть функция определена в промежутке Х (рис.1). Исходя из некоторого значения независимой переменной, придадим ему приращение, не выводящее его из...
-
Разработаны разные способы поиска итогового ранжирования мнений группы экспертов, например Метод средних арифметических рангов, В котором каждому объекту...
Задача поиска маршрутов в графе (путей в орграфе)