Найти путь

Найти путь

То поиск путей, обычно называемый Найти путь состоит в том, чтобы найти, как перемещаться в среде между начальной и конечной точками с учетом различных ограничений.

Определение графа со значениями

Значенный граф — это граф, с дугами которого мы связываем действительное число, называемое длиной дуги.

Обозначим через w(x,y) длину дуги (x,y) между вершинами x и y.

По аналогии с матрицей смежности можно представить граф со значениями квадратной матрицы, коэффициенты которой соответствуют значениям дуг.

Рассмотрим граф со значениями, вершины которого пронумерованы от 1 до n. Матрица оценки G представляет собой квадратную матрицу M = m_ij, размер n*n, определяемый формулой

Вот пример:

Таким образом, мы можем вывести следующую линейную программу с x_ij=1, если дуга является частью кратчайшего пути, 0 в противном случае:

• минимизировать с A множество дуг
• при условии

и для всех я,

Хотя это линейное программирование, этот метод может быть очень затратным по памяти и даже невозможным в некоторых случаях (например, если это распределенная система). Другой способ узнать кратчайший путь — узнать кратчайший из всех путей из одной вершины в другую.

Определим вес пути с=(и,…,в)

в виде суммы весов дуг, составляющих его, отмеченных Туалет).Затем мы определяем минимальное расстояние (кратчайший путь) между двумя вершинами u и v следующим образом:

Мы хотели бы иметь метод, способный для любого графа и для любой пары вершин Икс и там, чтобы определить кратчайший путь между ними. Для этого мы должны как можно лучше понять и охарактеризовать структуру решения: какими свойствами обладает кратчайший путь?

Лемма Кенига. Кратчайший путь между двумя вершинами является элементарным. Путь называется элементарным, если каждая его вершина посещается только один раз.

Перечисление всех путей для определения кратчайшего обнаруживает серьезный недостаток: время его выполнения. Если число элементарных путей действительно конечно, то тем не менее оно очень велико, порядка нет! на графике заказов нет.

Субоптимальная проблема

Нам нужно второе фундаментальное свойство, т. субоптимальность (см. Динамическое программирование). Речь идет о том, чтобы заметить, что кратчайший путь рекурсивный : последовательность кратчайшего пути по-прежнему является кратчайшим путем между ее конечными точками. Или если самый быстрый маршрут между а и в проходит через 2 вершины Икс и там, этот путь обязательно проходит по кратчайшему пути между Икс и у.

да р=(и,…,в) это кратчайший путь между а и в, то для любой вершины Икс в дороге п :

• подпуть п вплоть до Икс, (у,…,х), это кратчайший путь а в Икс
• подпуть п поскольку Икс, (х,…,в), это кратчайший путь Икс в в

Par absurdum предположим, что существует, например, между а и Икс путь д длины строго меньше длины р=(и,…,х,…,в). Таким образом, мы можем построить новый путь п' Между а и в заменив д на (у,…,х) в пути п. Длина п' тогда строго меньше, чем у п, что противоречит тому п это кратчайший путь а в в.

Дерево дорожек

Eсть дерево кратчайшие пути из начальной вершины во все остальные. Предположим, что граф связен, ребра ненаправлены, а веса неотрицательны. Мы расширяем облако вершин, начиная с s и заканчивая всеми вершинами. Мы храним в каждой вершине v метку d (v), представляющую расстояние от v до s в подграфе, состоящем из облака и смежных с ним вершин. На каждом шаге: добавляем в облако вершину вне облака с наименьшей меткой расстояния; мы обновляем метки вершин, смежных с u (см. остовное дерево).

Рассмотрим ребро e = (u, z), такое что u является вершиной, добавленной в облако последней, а z не находится в облаке. Ослабление ребра e обновляет расстояние d(z) следующим образом: d (z) ← min {d(z), d(u) + вес(e)}