Алгоритмы поиска путей

Путь минимальной суммарной длины во взвешенном графе с неотрицательными весами (алгоритм Дейкстры).

Алгоритмы поиска путей.

Тема 2. Поиск пути в графе.

Гамильтоновы графы.

Граф называется гамильтоновым, если в нем имеется простой цикл, соединяющий каждую вершину графа. Сам цикл также называется гамильтоновым. Гамильтоновой называется и цепь, соединяющая все вершины графа.

В 1859 году известный ирландский математик У. Гамильтон придумал задачу «Кругосветное путешествие».

Каждой вершине додекаэдра приписывается название одного города. Задача состоит в том, чтобы, переходя по ребрам от одной вершины к другой вернутся в исходную вершину, т.е нужно отыскать в графе простой цикл, содержащий все вершины.

Не все графы гамильтоновы, хотя бы по тому, что граф, имеющий простой цикл, должен быть двусвязным.

В отличие от эйлерова графа, для гамильтонова графа не существует простого алгоритма нахождения гамильтонова цикла. До сих пор эта задача представляет интерес и до конца не решена.

Однако существует ряд теорем, доказывающих различие гамильтоновых циклов в связных графах. Их можно использовать на практике.

2.3 Путь минимальной суммарной длины во взвешенном графе с произвольными весами для всех пар вершин (алгоритм Флойда).

2.4 Путь с минимальным количеством промежуточных вершин (волновой алгоритм).

2.5 Нахождение K путей минимальной суммарной длины во взвешенном графе с неотрицательными весами (алгоритм Йена).

Здесь рассматриваются алгоритмы работы с графами. Граф - пара G= (V, E), где V - множество вершин (вершинами могут быть объекты произвольной природы) и E - множество ребер, ребра - элементы вида e = (vi, vj), где vi, vj принадлежат множеству вершин, т.е. ребро это элемент из декартова произведения множества V на себя. Достаточно подробно терминология теории графов разобрана на странице А.Чернобаева, поэтому за более полной информацией можно обратиться туда, там же можно найти алгоритмы для работы с графами, как те которые представлены здесь, так и многие другие. Нам же для дальнейшей работы понадобится рассмотреть способы задания и структуры для хранения информации о графе.

Первый способ задания графа (не взвешенного) это задать матрицу связности S размера n*n, где n количество вершин графа, т.е. мощность множества V, при этом элемент sij = 1, если существует ребро из i-ой в j-ую вершины и sij = 0, если такого ребра нет. Нетрудно видеть, что матрица S - симметрична, если граф неориентированный, и может быть не симметричный в противном случае. При этом полагаем, что sii = 0, т.е. в графе нет петель. Такой способ задания графа используется, например, в волновом алгоритме.

Второй способ используется для задания взвешенного графа, т.е. графа каждому ребру которого соответствует некий параметр - вес. Для определения такого графа используется матрица весов W размер которой n*n, где n количество вершин графа. При этом элемент wij равен весу ребра соединяющего i-ую и j-ую вершины. Если такого ребра нет, то wij полагаем равным бесконечности (на практике это максимальное число возможное на данном языке программирования). Этот способ задания используется, например, в алгоритмах поиска пути во взвешенном графе.

При решении практических задач с помощью сетевого моделирования часто возникает задача поиска пути, наилучшего по тому или иному критерию, между двумя вершинами графа.

Пример: несколько городов, в том числе А и Б, связаны между собой сетью автомобильных дорог. Путешественник отправляется из города А в город Б. Какой маршрут он должен выбрать, чтобы добраться до Б, проехав минимальное расстояние.

В приведенном примере требуется найти в графе путь между двумя узлами, оптимальный по определенному критерию. В этом случае это сумма длин ребер пути.

Критерии оптимальности требуемого маршрута могут быть качественно различными. В первую очередь рассмотрим проблему поиска пути, минимальной по длине, которая представляет собой суммарную длину ребер, входящих в данный путь.

Предположим, что каждой дуге (i, j) ориентированного графа (случай неографа или смешанного графа качественно ничем не отличаются) поставлено в соответствие число a_ij –длина дуги (a_ij-действительные числа). Каждой паре узлов (i, j), для которых не существует дуги, соединяющих их, приписывается длина a_ij=∞. Задача состоит в нахождении в данном графе такого пути из узла S в узел T, для которого суммарная длина дуг минимальна.

Дата добавления: 2014-01-15