Поиск - кратчайший путь
Cтраница 2
Но наилучший известный нам способ поиска кратчайшего пути состоит в переборе всех возможных вариантов путей и сравнении их длин. [16]
Нетрудно заметить, что алгоритм поиска кратчайшего пути фактически состоит в выполнении лишь двух операций: операции формирования рельефа и операции поиска кратчайшего пути. При этом, если поиск кратчайшего пути начинается с момента поступления заявки на выбор пути, то операция формирования ( или переформирования) рельефа осуществляется всегда в начальный момент пуска системы, а в остальное время может выполняться либо в момент удаления или восстановления ребра, либо периодически с той или иной частотой повторения. [17]
В качестве математической модели используется модель поиска кратчайшего пути на графе. [18]
Типичным примером в данном случае служит алгоритм поиска кратчайшего пути. [19]
Жадный алгоритм построения минимального остовного дерева непригоден для поиска кратчайшего пути между двумя вершинами, поскольку на каждом проходе он учитывает длину лишь одного ребра. Если же изменить его так, чтобы при выборе ребра, ведущего в кайму, он выбирал ребро, являющееся частью кратчайшего в целом пути из начальной вершины, то мы получим требуемый результат. [20]
Отыскание оптимальной трассы разветвленного нефтепродукто-провода формулируется как задача поиска кратчайшего пути на графе, соединяющем источники с потребителями, и осуществляется на ЭВМ с использованием алгоритмов, основанных на решении задачи Штей-нера о кратчайшем пути, связывающем точки на плоскости, с учетом метода Лаунгардта, учитывающего количество нефтепродукта, перекачиваемого от источника к каждому потребителю. В результате решения такой задачи путем направленного перебора получают схематическое изображение дерева разветвленной системы трубопроводов, координаты точек разветвления, характеристики участков ( объем перекачки, диаметр трубопровода, длины участков) и другие необходимые данные для оптимального варианта с минимальными приведенными затратами и минимальной суммарной протяженностью. [21]
 |
Граф вершинных соединений подграфов. [22] |
Поиск оптимальных трасс можно эффективно производить на сети как поиск кратчайшего пути на графе. [23]
 |
Максимальные потоки. [24] |
Есть два отличия этого метода от алгоритма коррекции метокдля поиска кратчайшего пути. Во-первых, этот метод не рассматривает связи с нулевой разностной пропускной способностью. Алгоритм поиска кратчайшего пути проверяет все пути независимо от их стоимости. [25]
В этой статье мы рассмотрим особый случай трехмерной постановки задачи поиска кратчайшего пути, известный под названием дискретной геодезической задачи. На поверхности заданного многогранника даны две точки, и требуется найти кратчайший путь между ними, проходящий по этой поверхности. Геодезическая задача представляет определенный интерес для наземной навигации на пересеченной местности, где движущийся аппарат должен оставаться на поверхности, которую можно смоделировать многогранником. Заметим, что длина полученного пути вовсе не обязана быть минимальной для свободного от многогранника пространства, поскольку в нашем случае мы вынуждены оставаться на многогранной поверхности. Чтобы убедиться в том, что приведенная формулировка есть частный случай общей трехмерной постановки, представим себе два многогранных препятствия: открытый многогранник и дополнение к его замыканию. Тогда путь между двумя точками, не пересекающий оба многогранника, есть как раз путь, лежащий на общей для них обоих поверхности. С другой стороны, решаемая нами задача представляет собой обобщение двумерной постановки, поскольку каждое многоугольное препятствие можно представить в виде очень высокой призмы, выступающей над плоскостью, в которой лежит заданный многоугольник. [26]
Метод поиска кратчайшего пути между двумя точками неориентированного графа эффективен при поиске кратчайшего пути на сети с большим числом дуг. Но его эффективность несколько снижается в задачах поиска точек разветвления систем трубопроводов, поскольку во всех возникающих ситуациях многократно повторяются процессы поиска кратчайшего пути между двумя точками. [27]
 |
Матрица примыканий для полного взвешенного графа. [28] |
Сначала кажется, что для решения задачи о коммивояжере можно просто воспользоваться алгоритмом поиска кратчайшего пути, однако ситуация не так проста. Алгоритм Дейкстры предназначен для поиска кратчайшего пути между двумя вершинами, но найденный путь не обязательно проходит через все вершины графа. [29]
После этого измельчают сетку на каждой шкале, окружают путь ls новой трубкой и продолжают поиск кратчайшего пути описанным приемом блуждающих трубок. Процесс измельчения сетки на шкалах и поиска кратчайшего пути указанным способом повторяют, пока два кратчайших пути, полученные после двух последовательных измельчений сетки, не совпадут с удовлетворительной точностью. Попеременно измельчая сетку на шкалах состояния и сетку по времени, поиск с помощью блуждающих трубок продолжают до получения приближенного решения исходной задачи с достаточной точностью. [30]
Страницы: 1 2 3 4