Поиск - кратчайший путь
Cтраница 4
Обход в ширину часто используют алгоритмы, осуществляющие полный поисквдереве. В алгоритме поиска кратчайшего пути с установкой меток ( см. главу 12) применяется поиск в ширину кратчайшего дерева внутри сети. [46]
 |
Окно программы Work. [47] |
Многие другие сетевые алгоритмы применяются не так очевидно. Например, алгоритмы поиска кратчайшего пути подходят для разбиения на районы, составления плана работ и графика коллективной работы. [48]
 |
Дерево и его представление нумерацией связей. [49] |
По этой причине большая часть литературы по сетевым алгоритмам использует представление нумерацией связей. Многие статьи о поиске кратчайшего пути предполагают, что данные записаны в подобном формате. Прежде чем изучать эти алгоритмы по журналам, таким как Management Science или Operations Research, вы должны освоить представление нумерацией связей. [50]
Нетрудно заметить, что алгоритм поиска кратчайшего пути фактически состоит в выполнении лишь двух операций: операции формирования рельефа и операции поиска кратчайшего пути. При этом, если поиск кратчайшего пути начинается с момента поступления заявки на выбор пути, то операция формирования ( или переформирования) рельефа осуществляется всегда в начальный момент пуска системы, а в остальное время может выполняться либо в момент удаления или восстановления ребра, либо периодически с той или иной частотой повторения. [51]
Сначала кажется, что для решения задачи о коммивояжере можно просто воспользоваться алгоритмом поиска кратчайшего пути, однако ситуация не так проста. Алгоритм Дейкстры предназначен для поиска кратчайшего пути между двумя вершинами, но найденный путь не обязательно проходит через все вершины графа. [52]
Во-вторых, этот алгоритм проверяет все узлы не больше одного раза. Алгоритм коррекции меток для поиска кратчайшего пути будет обновлять узел и помещать его снова в список возможных узлов, если позднее обнаружится улучшенный путь от корня до этого узла. При поиске расширяющего пути не нужно проверять его длину, поэтому нет необходимости обновлять пути и помещать узлы назад в список возможных. [53]
В любой момент ситуация на сети может измениться, поэтому выбранные маршруты могут оказаться далеко не кратчайшими в отношении своевременности доставки сообщений. В таком случае необходимо повторить поиск кратчайших путей, или, иначе, произвести коррекцию плана распределения информации. [54]
 |
Граф вариантов ТП восстановления детали. [55] |
Определим длину каждого ребра графа как затраты на подготовку и выполнение последующей операции, отнесенные к одной детали. Оптимизация - задачи выражается в поиске кратчайшего пути из вершины О в одну из вершин нижнего яруса графа, а соответственно подмножество вершин на этом пути определяет оптимальный состав операций ТП. [56]
После этого измельчают сетку на каждой шкале, окружают путь ls новой трубкой и продолжают поиск кратчайшего пути описанным приемом блуждающих трубок. Процесс измельчения сетки на шкалах и поиска кратчайшего пути указанным способом повторяют, пока два кратчайших пути, полученные после двух последовательных измельчений сетки, не совпадут с удовлетворительной точностью. Попеременно измельчая сетку на шкалах состояния и сетку по времени, поиск с помощью блуждающих трубок продолжают до получения приближенного решения исходной задачи с достаточной точностью. [57]
Каждый город можно представить вершиной графа, наличие пути между двумя городами - ребром, а стоимость путешествия между ними - весом этого ребра. Отсюда можно сделать вывод, что алгоритм поиска кратчайшего пути из § 6.5 решает и задачу коммивояжера, однако это не так. Какие два условия задачи о коммивояжере отличают ее от задачи о кратчайшем пути. Во-первых, мы должны посетить все города, а алгоритм поиска кратчайшего пути дает лишь путь между двумя заданными городами. Если собрать путь из кратчайших кусков, выдаваемых алгоритмом поиска кратчайших путей, то он будет проходить через некоторые города по нескольку раз. Второе отличие состоит в требовании возвращения в исходную точку, которое отсутствует в поиске кратчайшего пути. [58]
В работе предлагается метод решения задач оптимального приближения кусочно-постоянных функций. Метод основан на переходе к сетевой модели и использовании процедур поиска кратчайших путей в сети. С вычислительной точки зрения процедуры поиска кратчайших путей крайне просты, так как они не связаны с вычислением значений целевых функций. Учитывая комбинаторный характер исходных задач, такой результат можно считать достаточно хорошим. [59]
На данный момент алгоритм не содержит методов поиска расширяющих путей в разностной сети. Один из подходящих для этой задачи методов похож на алгоритм коррекции меток для поиска кратчайшего пути. Сначала поместите узел-источник в список возможных узлов. [60]
Страницы: 1 2 3 4