Изменения

Функция <tex>0 \leqslant c(s, s') \leqslant +\infty</tex> будет возвращать стоимость ребра <tex>(s;, s')</tex>. При этом <tex>c(s, s') = +\infty</tex> будет тогда и только тогда, когда ребра <tex>(s;, s')</tex> не существует.

|definition=Будем называть '''rhs-значением''' (англ. ''right-hand side value'') такую функцию <tex>rhs(s)</tex>, которая будет возвращать потенциальное минимальное расстояние от <tex>f</tex> до <tex>s</tex> по следующим правилам:

|definition=Вершина <tex>s</tex> называется '''насыщенной''' (англ. ''locally consistent''), если <tex>g(s) = rhs(s)</tex>

|definition=Вершина <tex>s</tex> называется '''переполненной''' (англ. ''locally overconsistent''), если <tex>g(s) > rhs(s)</tex>

|definition=Вершина <tex>s</tex> называется '''ненасыщенной''' (англ. ''locally underconsistent''), если <tex>g(s) < rhs(s)</tex>

'''Mainfunction'''main(): '''Initialize'''initialize(); '''while (true) '''ComputeShortestPath''true'' computeShortestPath(); <font color="green">//В данный момент мы знаем кратчайший путь из f в t.</font>

'''for ''' всех ориентированных ребер (u; , v) с измененными весами: Обновляем результат функции c(u; , v); '''UpdateVertex'''updateVertex(v);

Теперь опишем составные элементы подробнееФункция инициализации исходного графа устанавливает для всех вершин кроме стартовой (вершины <tex>f</tex>) значения <tex>g(s)</tex> и <tex>rhs(s)</tex> равными бесконечности. Для стартовой <tex>rhs(f)=0</tex>. Очевидно, что минимальное расстояние от стартовой вершины до самой себя должно быть равным 0, но <tex>g(f)=+\infty</tex>. Это сделано для того, чтобы стартовая вершина была ненасыщенной и имела право попасть в приоритетную очередь. '''Initializefunction'''initialize(): <font color="green">// Заведем [[Двоичная куча|приоритетную очередь]] U, в которую будем помещать вершины. </font> <font color="green">// Сортировка будет производиться по функции key(s).</font> U = <tex>\varnothing</tex>; '''for ''' s <tex>\in</tex> V rhs(s) = g(s) = <tex>+\infty;</tex> rhs(f) = 0; U.Insertinsert(f; CalcKey, calcKey(f));

//Функция <tex>key(s)</tex>. Возвращаемые значения сортируются в лексографическом порядке, // т.е. то есть сначала сортируется по <tex>k_1(s)</tex>, потом по <tex>k_2(s)</tex> '''CalcKeyfunction'''calcKey(s): '''return ''' [min(g(s); , rhs(s)) + h(s; , t); , min(g(s); , rhs(s))];

// Обновляет данные вершины в соответствие с данными выше определениями. // Также поддерживает инвариант того, что в очереди U лежат только ненасыщенные вершины. '''UpdateVertexfunction'''updateVertex(u): '''if ''' u <tex>\ne</tex> f <tex>rhs(u) = \min\limits_{s' \in Pred(u)}(g(s') + c(s',u));</tex> '''if ''' u <tex>\in</tex> U U.Removeremove(u); '''if ''' g(u) <tex>\ne</tex> rhs(u) U.Insertinsert(u; CalcKey, calcKey(u));

// Функция несколько раз перерасчитывает значение <tex>g(s)</tex> у ненасыщенных вершин в неубывающем порядке их ключей. // Такой перерасчет значения <tex>g(s)</tex> будем называть ''расширением'' вершины. '''ComputeShortestPathfunction'''computeShortestPath(): '''while (''' U.TopKeytopKey() < CalcKeycalcKey(t) OR '''or''' rhs(t) <tex>\ne</tex> g(t)) u = U.Poppop(); '''if ''' g(u) > rhs(u) g(u) = rhs(u); '''for ''' <tex>s </tex> <tex>\in</tex> Succ(u) UpdateVertex(s); '''else''' g(u) = <tex>+\infty</tex>; '''for ''' s <tex>\in</tex> Succ(u) <tex>\cup</tex> <tex>\{u\}</tex> UpdateVertexupdateVertex(s);

CalcKey'''function''' calcKey(s): '''return''' [min(g(s),rhs(s)) + h(f,s); , min(g(s),rhs(s))];

Initialize'''function''' initialize(): U = <tex>\varnothing</tex>;

U.Insertinsert(t; CalcKey, calcKey(t))

'''UpdateVertexfunction'''UpdateVertex(u):

U.Removeremove(u)

U.Insertinsert(u; CalcKey, calcKey(u))

'''function''' ComputeShortestPath(): '''while''' U.TopKeytopKey() < CalcKeycalcKey(f) or rhs(f) <tex>\ne</tex> g(f) u = U.Poppop()

UpdateVertexupdateVertex(s)

'''for''' <tex>s </tex> <tex>\in</tex> Pred(u) <tex>\cup</tex> {u} UpdateVertexupdateVertex(s)

'''Mainfunction'''main(): Initializeinitialize() ComputeShortestPathcomputeShortestPath()

Передвинулись вдоль найденного пути и изменили вершину <tex>f</tex>;

'''for''' всех ориентированных ребер <tex>(u; , v) </tex> с измененными весами: Обновляем результат функции <tex>c(u; , v)</tex> UpdateVertexupdateVertex(u) '''for''' <tex>s </tex> <tex>\in</tex> U U.Updateupdate(s; ''', CalcKey'''(s)); '''ComputeShortestPath'''computeShortestPath()

Допустим, что после того, как робот продвинется вдоль найденного пути на предыдущих итерациях, из вершины <tex>s </tex> в <tex>s'</tex>, он обнаружит изменения в графе. Первая компонента ключей <tex>k_1(s')</tex> может уменьшится максимум на <tex>h(s,s')</tex> (по определению ключа). Вторая компонента не зависит от функции h. Аналогично первой версии алгоритма, мы должны уменьшить первую компоненту ключа у всех вершин в очереди U. Очевидно, что <tex>h(s,s')</tex> будет одинаковым для всех вершин из U. Порядок в очереди не изменится, если произвести уменьшение. Следовательно уменьшение можно отложить, тем самым очередь не придется перестраивать на каждой итерации. Так же исходя из нового определения функции <tex>h</tex>, её значение будет всегда меньше, чем разность первых компонент ключей у соседних по приоритету вершин. Таким образом мы можем добавлять h(s,s') ко всем <tex>k_1(s')</tex> у ключей вершин из U.

Будем называть <tex>K_m</tex> ключевым модификатором. В нем мы и будет хранить сумму <tex>h(s,s')</tex>, которые нужно добавить ко всем вершинам из U.

'''CalcKeyfunction'''calcKey(s): '''return ''' [min(g(s);, rhs(s)) + h(f;, s) + <tex>K_m</tex>;, min(g(s); , rhs(s))];

'''Initializefunction'''initialize(): U = <tex>\varnothing</tex>;

'''for ''' s <tex>\in</tex> V

U.Insertinsert(t; , CalcKey(t));

'''UpdateVertexfunction'''updateVertex(u): '''if (''' u <tex>\ne</tex> t) rhs(u) = <tex>\min\limits_{s' \in Succ(u)}(c(u,s')+g(s'));</tex> '''if (''' u <tex>\in</tex> U) U.Removeremove(u); '''if (''' g(u) <tex>\ne</tex> rhs(u)) U.Insertinsert(u; CalcKey, calcKey(u));

'''ComputeShortestPathfunction'''computeShortestPath(): '''while (''' U.TopKeytopKey() < CalcKeycalcKey(f) OR '''or''' rhs(f) <tex>\ne</tex> g(f)) <tex>K_{old}</tex> = U.TopKeytopKey(); u = U.Poppop();

'''if (''' <tex>K_{old}</tex> < '''CalcKey'''calcKey(u)) U.Insertinsert(u; '''CalcKey''', calcKey(u));

'''if ''' (g(u) > rhs(u)) g(u) = rhs(u); '''for ''' <tex>s </tex> <tex>\in</tex> Pred(u) UpdateVertexupdateVertex(s); '''else''' g(u) = <tex>+\infty</tex>; '''for ''' <tex>s </tex> <tex>\in</tex> Pred(u) <tex>\cup</tex> <tex>\{u\} </tex> '''UpdateVertex'''updateVertex(s);

'''Mainfunction'''main():

'''Initialize'''initialize() computeShortestPath(); '''ComputeShortestPathwhile'''(); while (f <tex>\ne</tex> t) <font color="green">// if (g(f) = <tex>+\infty</tex>) тогда путь на данной итерации не найден.</font>

Передвинулись вдоль найденного пути и изменили вершину <tex>f</tex>;.

'''if (''' граф изменился) <tex>K_m = K_m + h(s_{last}, h_{start})</tex>; <tex>s_{last} = f</tex>; '''for ''' всех ориентированных ребер (u; , v) с измененными весами: Обновляем результат функции c(u; , v); '''UpdateVertex'''updateVertex(u); '''ComputeShortestPath'''computeShortestPath();

==СсылкиИсточники информации==