Полная версия

Главная arrow Математика, химия, физика arrow Комбинаторные алгоритмы: множества, графы, коды

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

ЗАДАНИЕ 7 Построение кратчайших путей

В задании формулируется оптимизационная задача, которая интересна своими многочисленными приложениями: задача

о кратчайшем пути. Здесь рассматриваются два классических алгоритма её решения (алгоритм Дейкстры и алгоритм Флойда), которые должен знать каждый математик и программист. Цель задания: изучение данных алгоритмов и практика их использования при решении прикладных задач.

Формулировка задачи

Пусть дан орграф G = (V,E), V- {vb ..., v„}, п > 1, Е-ь ..., ет}, т> 1, дугам которого приписаны веса, устанавливаемые матрицей W= {Wy}. Элемент этой матрицы, т. е. число W[vh у,] = Wy, будем называть длиной дуги е = (v„ vy). Если в орграфе G отсутствует некоторая дуга (v,-, v,), положим wy = со. Определим длину пути как сумму длин отдельных дуг, составляющих этот путь.

Задача о кратчайшем пути состоит в нахождении пути минимальной длины (кратчайшего пути) от заданной начальной вершины s е V до заданной конечной вершины t е V при условии, что такой путь существует, т. е. вершина t достижима из вершины s.

Элементы матрицы весов W могут быть положительными, отрицательными вещественными числами или нулями. Однако если орграф G содержит контур отрицательной длины, вершины которого достижимы из s, то решение задачи о кратчайшем пути не существует. Действительно, если такой контур все же есть и v, - некоторая его вершина, то, двигаясь от s к v„ обходя данный контур достаточно большое число раз и попадая, наконец, в t, можно получить путь сколь угодно малой длины. Таким образом, для любых двух вершин 5 и t орграфа G с произвольной вещественной матрицей весов W решение задачи о кратчайшем (s, 0-пути существует, если

  • - вершина t достижима из s;
  • G нет контуров отрицательной длины.

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

Существует много практических интерпретаций задачи о кратчайшем пути. Например, вершины графа могут соответствовать городам, а каждая дуга - некоторой дороге, длина которой представлена весом дуги. Выполняется поиск кратчайшего пути между городами. Если вес дуги интерпретировать как стоимость передачи информации между вершинами, то в этом случае ищется самый дешевый путь передачи данных. Возникает другая ситуация, когда вес дуги е — (у„ у,) равен вероятности безотказной работы канала связи. Если предположить, что отказы каналов не зависят друг от друга, то вероятность исправности пути передачи данных равна произведению вероятностей составляющих его дуг. Заменяя веса ptj на величины qtj = - log ру, поиск наиболее надежного пути можно свести к нахождению кратчайшего пути в графе. Далее рассматриваются два общеизвестных алгоритма решения задачи о кратчайшем пути [11-17].

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>