Кратчайшие пути

Cтраница 1

Схемы вариантов разветвленного трубопровода. [1]

Кратчайшие пути ( или пути, удовлетворяющие экстремуму другого критерия оптимальности) для трех участков находятся на дереве, построенном относительно точек разветвления. [2]

Кратчайшие пути и полна кривизна поверхности. [3]

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

Найти кратчайшие пути от вершины 1 ко всем другим вершинам графа на рис. 8.10. Изобразить также 1-базу. [5]

Найти все кратчайшие пути от точки ( 1 1) до прямой у - х в R2 с манхэттенской метрикой. [6]

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

Граф из примера. [8]

Требуется найти все кратчайшие пути от вершины Xi ко всем остальным вершинам. [9]

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

Алгоритм Дейкстры определяет кратчайшие пути в нагруженном графе от данной вершины до любой другой. [11]

Иногда нужно вычислить кратчайшие пути между каждой парой узлов. Следующий метод позволяет эффективно решать эту задачу. [12]

Можно ли находить кратчайшие пути меньше, чем за 0 ( п3) шагов. Алгоритм Штрассена неприменим к замкнутым полукольцам, состоящим из неотрицательных вещественных чисел и оо, но, может быть, удастся свести операции в этом замкнутом полукольце к операциям в некотором кольце, как это было сделано для булевых матриц. [13]

Для всех кабелей определяются кратчайшие пути j учетом запретов на группы раскладки по трассам. [14]

Легко видеть, что кратчайшие пути от к будут теми же самыми один относительно другого, если все веса е - заменить на с е - Н1 - и -, где величины Н - произвольные числа, приписанные вершинам графа. Так как расстояния Л ( в, х), могут быть получены в общем случае с помощью О ( п3) операций, то на самом деле ( преобразуя предварительно веса) и в общем случае можно найти К кратчайших путей, используя О ( Кп3) операций. [15]

Страницы: 1 2 3 4