Алгоритм Дейкстры и жадная стратегия - PullRequest
Новая
       38

Алгоритм Дейкстры и жадная стратегия

0 голосов
/ 04 декабря 2018

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

DijkstrasAlgorithm(G, w, s)
    InitalizeSingleSource(G, s)
    S = 0
    Q = G.V
    while Q != 0
        u = ExtractMin(Q)
        S = S∪{u}
        for each vertex v ∈ G.Adj[u]
            Relax(u, v, w)

Пожалуйста, рассмотрите следующий весовой график направления.

Есть 5 вершин: s, t, x, y, z.10 ребер: 

s->t = 3
s->y = 5
t->y = 2
t->x = 6
y->t = 1
y->x = 4
y->z = 6
x->z = 2
z->x = 7
z->s = 3

Наша цель - найти кратчайший путь от s до x.Мой ответ был s-> t-> y-> x с длиной 9, я предположил, что "S" в псевдокоде был кратчайшим путем и что каждый ExtractMin из minQ был добавлен в путь.

MyУчитель, однако, сказал мне, что это неправильно.Правильный ответ s-> t-> x с длиной 9. Разница в нашем ответе состоит в том, включать ли y.Мой учитель говорит, что, поскольку s-> t-> x «найден первым», он не обновляется до s-> t-> y-> x, равной длины.

Это смущает меня.Алгоритм Дейкстры использует жадную стратегию, и я думал, что жадная стратегия заключалась в том, чтобы всегда выбирать кратчайший путь, доступный в то время.И когда выбор между t-> y и t-> x, t-> y короче и поэтому должен быть выбран.

Мои вопросы:

1) При каких обстоятельствахразве жадная стратегия не выберет ближайший кратчайший путь для конечного результата?

2) Если использование ExtractMin в minQ не то, как мы отслеживаем общий путь от s до x, то как мы будем отслеживатьполного пути?

1 Ответ

0 голосов
/ 04 декабря 2018

Ответ вашего учителя предполагает, что мы исследуем пути в следующем порядке: «кратчайший сначала, сломанный первым увиденным первым».

Для начала мы исследуем s->t, мы ставим x по стоимости 9 от s->t->x на список вещей, чтобы исследовать «когда-нибудь».Но сначала мы исследуем s->t->y, потому что оно короче.В этот момент мы видим, что s->t->y->x является вариантом, также стоимостью 9. Однако, поскольку это не улучшение, мы отбрасываем его.

Поэтому, как только мы доберемся до путей длины 9, мы найдем s->t->x из-за того, что он сначала попал в очередь.

Вы получите ответ, если измените Relax, чтобы сохранить возможный путь, если он лучше или равен лучшему из найденных на данный момент.Это даст правильный ответ.

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

...