Поиск - кратчайший путь
Cтраница 3
Чтобы подготовить технику для решения задач из приложения к этой главе, мы рассмотрим задачу поиска кратчайшего пути, связывающего пару данных вершин в нагруженном орграфе. Слово кратчайший здесь вполне уместно, поскольку довольно часто веса в орграфе - это расстояния между пунктами. [31]
Если исходная сеть возможных путей развития трассы трубопровода представляет собой ориентированный граф, общим принципом поиска кратчайшего пути будет построение дерева графа. [32]
 |
Перекресток со штрафами за повороты.| Перекресток, соединенный с фиктивным корневым узлом. [33] |
Поместив информацию о штрафах за повороты непосредственно в сети, можно избежать необходимости изменять алгоритмы поиска кратчайшего пути. Эти алгоритмы будут правильно находить кратчайшие пути с учетом штрафов за повороты. [34]
Легко видеть, что, как и в предыдущем случае, исходная задача сводится к задаче поиска кратчайшего пути, соединяющего узлы 0 и N и состоящего ровно из п - - 1 дуги. [35]
Блоки матрицы, реализующие железнодорожные перевозки, рассчитываются на основе железнодорожной сети непосредственно на ЭВМ с помощью алгоритма поиска кратчайшего пути на сети железных дорог. Водный и трубопроводный блок рассчитываются вручную. Они включаются в матрицу при формировании ее на ЭВМ. [36]
Нетрудно заметить, что алгоритм поиска кратчайшего пути фактически состоит в выполнении лишь двух операций: операции формирования рельефа и операции поиска кратчайшего пути. При этом, если поиск кратчайшего пути начинается с момента поступления заявки на выбор пути, то операция формирования ( или переформирования) рельефа осуществляется всегда в начальный момент пуска системы, а в остальное время может выполняться либо в момент удаления или восстановления ребра, либо периодически с той или иной частотой повторения. [37]
С неожиданностями такого рода, возникающими в результате соединения отдельных элементов процесса и воспроизведения в достаточно крупном масштабе реальных промышленных условий, нередко приходится сталкиваться исследователю в поисках кратчайшего пути к полному уяснению процесса. [38]
С неожиданностями такого рода, возникающими в результате соединения отдельных элементов процесса и воспроизведения в достаточно крупном масштабе реальных промышленных условий, нередко приходится Сталкиваться исследователю в поисках кратчайшего пути к полному уяснению процесса. [39]
 |
К примеру определения области поиска оптимальной трассы трубопровода. [40] |
Ввиду того, что практически трудно выразить изменение критерия оптимальности по всей области поиска оптимальной трассы в виде непрерывной функциональной зависимости от координат текущей точки ( хотя такие попытки и делались), большинство задач о выборе оптимальной трассы формулируются как задачи о поиске кратчайшего пути на сети. [41]
Эту задачу можно применять, например, для определения порядка эффективного сбора мусора из баков на улицах города или выбора кратчайшего пути распространения информации по всем узлам компьютерной сети. Поиск кратчайшего пути требует перебора всех этих возможностей. Предположим, что у нас есть алгоритм, способный подсчитать стоимость путешествия через 15 городов в указанном порядке. Если за секунду такой алгоритм способен пропустить через себя 100 вариантов, то ему потребуется больше четырех веков, чтобы исследовать все возможности и найти кратчайший путь. Даже если в нашем распоряжении имеется 400 компьютеров, все равно у них уйдет на это год, а ведь мы имеем дело лишь с 15 городами. Для 20 городов миллиард компьютеров должен будет работать параллельно в течение девяти месяцев, чтобы найти кратчайший путь. Ясно, что быстрее и дешевле путешествовать хоть как-нибудь, чем ждать, пока компьютеры выдадут оптимальное решение. [42]
Приведенные алгоритмы ( кроме первого) могут давать и не кратчайший путь. Для экономного поиска кратчайшего пути в лабиринте можно завести специальные массивы X и Y для списка координат ( лг, у) клеток, которые следует рассмотреть. Такой прием называется поиском в ширину. [43]
Алгоритмы поиска оптимальной трассы могут быть различны, и их выбор зависит от сложности подготовки исходных данных, ресурсов вычислительной техники, необходимой точности вычислений. Описания алгоритмов поиска кратчайшего пути приводятся в специальной литературе и хорошо известны. [44]
 |
Обходы дерева. [45] |
Страницы: 1 2 3 4