Алгоритм - нахождение - кратчайший путь - Большая Энциклопедия Нефти и Газа, статья, страница 1
Дипломатия - это искусство говорить "хоро-о-ошая собачка", пока не найдешь камень поувесистей. Законы Мерфи (еще...)

Алгоритм - нахождение - кратчайший путь

Cтраница 1


Алгоритм нахождения кратчайшего пути, Вычислительные системы, Новосибирск, 1963, вып.  [1]

Алгоритм нахождения кратчайшего пути, приведенный в разд.  [2]

Алгоритм нахождения кратчайшего пути, который применим к графу с ребрами произвольной длины, а также алгоритм построения стягивающего дерева с минимальной стоимостью ( который является усовершенствованием второго алгоритма из разд.  [3]

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

5 Алгоритм нахождения кратчайшего пути из одного источника. [5]

Покажите, что алгоритм нахождения кратчайшего пути из разд.  [6]

7 Стоимости ребер для графа с 5 узлами.| Матрица положительных целых чисел. [7]

Докажите, что алгоритм нахождения кратчайшего пути, приведенный на рис. 5.38, строит кратчайший путь из и в каждый узел v произвольного графа, у которого могут быть ребра с отрицательными стоимостями, но циклов с отрицательными стоимостями нет.  [8]

Рекуррентное соотношение ( 8) эквивалентно алгоритму нахождения кратчайшего пути на ориентированной ациклической сети.  [9]

Подобный подход очень тесно связан с алгоритмом нахождения кратчайшего пути, описанным в разд.  [10]

Существует нечто, о чем стоит упомянуть прежде, чем описывать алгоритм нахождения кратчайшего пути. Во многих задачах, связанных с графами, необходимо уточнить, в каком виде должен быть дан ответ. Ясно, что ответы на первый и второй вопросы мы хотим получить в виде чисел, но не очевидно, в какой форме следует представить все кратчайшие пути от X до У. Если кратчайших путей много, то наиболее компактным представлением их всех может быть сам граф, а не, скажем, перечисление вершины за вершиной для каждого пути.  [11]

Задачи о кратчайшем пути, в которых на пути накладываются некоторые ограничения ( см. [4], [12], [23]), в настоящей главе не рассматриваются, так как к ним непосредственно не применимы те методы расстановки пометок, на которых базируются все описанные здесь алгоритмы нахождения кратчайшего пути. Эти задачи с ограничениями часто настолько сложны, что соответствующие алгоритмы позволяют находить оптимальные решения лишь таких задач, размеры которых ( например, число вершин) на несколько порядков меньше, чем у аналогичных задач без ограничений.  [12]

Задачи о кратчайшем пути, в которых на пути накладываются некоторые ограничения ( см. [4], [12], [23]), в настоящей главе не рассматриваются, так как к ним непосредственно не применимы те методы расстановки пометок, на которых базируются все описанные здесь алгоритмы нахождения кратчайшего пути. Эти задачи с ограничениями часто настолько сложны, что соответствующие алгоритмы позволяют находить оптимальные решения лишь таких задач, размеры которых ( например, число вершин) на несколько порядков меньше, чем у аналогичных задач без ограничений.  [13]

Таким образом, возникает следующий смешанный алгоритм. Выберем стационарную стратегию и вычислим результирующее пробное значение г. Применим алгоритм итераций по критерию ( о), приведенный в разд. Еслп при расчетах обнаруживается цикл, для которого соответствующая сумма ctj отрицательна, должным образом изменим стратегию, повторно вычислим с для этого улучшающего цикла, пересчитаем ctj и повторно выполним операции. Как только вычисления по алгоритму нахождения кратчайшего пути завершатся получением значений WL.  [14]

Заданная система кабелеводов образует связывающую сеть, полюсами которой являются размещаемые объекты. В конкретной математической интерпретации возникает следующая задача. Для каждой пары полюсов - нужно найти длину кратчайшего пути между ними и один кратчайший путь, соединяющий эти полюсы. Решение задачи распадается на две последовательно работающие части. Вторая часть представляет собой алгоритм нахождения кратчайшего пути на связывающей сети с использованием данных матрицы кратчайших расстояний. Суть этого алгоритма заключается в следующем.  [15]



Страницы:      1