418
правок
Изменения
м
Нет описания правки
== 4.2 Стоимость объезда ==
[[Файл:kstar-figure-3.png|600px|thumb|center|'''Рисунок 3.'''. Исходный граф, в котором сплошные линии представляют построенное A* дерево поиска <tex>T</tex>. Пунктирные линии являются запасными ребрами.]]
Для ребра <tex>(u, v)</tex> стоимость '''объезда''' (англ. ''detour'') <tex>\delta(u, v)</tex> представляет стоимость '''ущерба''' (англ. ''disadvantage'') из-за взятия ребра объезда <tex>(u,v)</tex> в сравнении с кратчайшим путем <tex>s-t</tex> через <tex>v</tex>. Ни длина кратчайшего пути <tex>s-t</tex> через <tex>v</tex>, ни длина пути <tex>s-t</tex>, включающего запасные ребра <tex>(u, v)</tex> не известны, когда A* обнаруживает <tex>(u, v)</tex>. Обе длины могут быть оценены с помощью функции оценки <tex>f</tex>, которая использует эвристическую функцию <tex>h</tex>. Пусть <tex>f(v)</tex> будет <tex>f</tex>-значением с соответствии с деревом поиска <tex>T</tex> и <tex>f_u(v)</tex> будет <tex>f</tex>-значением в соответствии с родителем u, т.е. <tex>f_u(v) = g(u) + c(u, v) + h(v)</tex>. Тогда <tex>\delta(u, v)</tex> может быть определена так:
Входящая куча <tex>H_{in}(v)</tex> содержит узлы для каждого запасного ребра к вершине <tex>v</tex>, которые до сих пор были обнаружены A*. Узлы <tex>H_{in}(v)</tex> будут упорядочены в соответствии с <tex>\delta</tex>-значением соответствующих переходов. Узел владеющий ребром с минимальной стоимостью ущерба будет расположен на вершине кучи. Мы ограничим структуру кучи <tex>H_{in}(v)</tex> таким образом, что её корень в отличие от остальных узлов, будет иметь не более 1 ребенка. Обозначим его <tex>root_{in}(v)</tex>.
'''Пример 4.''' Рисунок 4 иллюстрирует входящие кучи графа из рисунка 3. Цифры рядом с узлами кучи соответствуют <tex>\delta</tex>-значениям. [[Файл:kstar-figure-4.png|600px|thumb|center|'''Рисунок 4.'''. Входящие кучи <tex>H_{in}(s_i)</tex>, полученные из графа, показанного на рисунке 3.]]
Деревянная куча <tex>H_{T}(v)</tex> для произвольной вершины <tex>v</tex> строится следующим образом. Если <tex>v</tex> - стартовая вершина, т.е. <tex>v = s</tex>, то <tex>H_{T}(v)</tex> будет изначально пустой кучей. Затем в неё будет добавлен <tex>root_{in}(s)</tex>, если <tex>H_{in}(s)</tex> не пустая. Если <tex>v</tex> не стартовая вершина, то пусть вершина <tex>u</tex> будет родителем вершины <tex>v</tex> в дереве поиска <tex>T</tex>. Мы можем представить, что <tex>H_{T}(v)</tex> конструируется как копия <tex>H_{T}(u)</tex>, в которую добавлен <tex>root_{in}(v)</tex>. Если <tex>H_{in}(v)</tex> пустая, то <tex>H_{T}(v)</tex> идентична <tex>H_{T}(u)</tex>. Однако, для экономии памяти мы создаем только дешевую копию <tex>H_{T}(u)</tex>. Это осуществляется через создание копий только тех узлов кучи, которые лежат на обновленном пути в <tex>H_{T}(u)</tex>. Оставшаяся часть <tex>H_{T}(u)</tex> не копируется. Другими словами, <tex>root_{in}(v)</tex> вставляется в <tex>H_{T}(u)</tex> неразрушающим путем так, что структура <tex>H_{T}(u)</tex> сохраняется. В куче <tex>H_{T}(v)</tex> к <tex>root_{in}(v)</tex> могут быть присоединены 1 или 2 ребенка. К тому же, <tex>root_{in}(v)</tex> хранит только 1 собственного ребенка из <tex>H_{in}(v)</tex>. Мы обозначим корень <tex>H_{T}(v)</tex> как <tex>R(v)</tex>.
[[Файл:kstar-figure-5.png|600px|thumb|center|'''Рисунок 5.'''. Деревянные кучи <tex>H_{T}(s_i)</tex>, полученные из графа, показанного на рисунке 3.]]
Назовем ребра, которые берут начало из входящих или деревянных куч, '''кучными ребрами''' (англ. ''heap edges''). Сформулируем следующую лемму.
Лемма 1 подразумевает, что куча упорядоченная в соответствии с <tex>\delta</tex>-значанием поддерживается для любого кучного ребра из <tex>P(G)</tex>. Эта упорядочивание кучи подразумевает, что <tex>\Delta(n,n')</tex> неотрицательна для любого кучного ребра <tex>(n,n')</tex>. Следовательно, <tex>\Delta</tex> также неотрицательна, т.е. <tex>\Delta(n,n') >= 0</tex> для любого ребра <tex>(n,n')</tex> в <tex>P(G)</tex>. Стоимость пути <tex>\sigma</tex>, т.е. <tex>C_{P(G)}(\sigma)</tex> равна <tex>\sum_{e \in \sigma}\Delta(e)</tex>.
'''Пример 6.'''
В оставшейся части этого раздела мы проиллюстрируем особенности структуры графа путей, которые актуальны для нахождения кратчайших путей <tex>s-t</tex>.
Первое наблюдение в том, что <tex>P(G)</tex> ориентированный взвешенный граф. Каждый узел в <tex>P(G)</tex> несет запасное ребро из G. Использование бинарных куч в конструкции <tex>P(G)</tex> извлекает выгоду из следующих 2 свойств. Во-первых, произвольный узел в <tex>P(G)</tex> имеет не более 4 выходящих ребер. Одним из ребер будет точно кросс-ребро в то время, как оставшимися будут кучные ребра. Во-вторых, функция веса <tex>\Delta</tex> неотрицательна. Как станет ясно в разделе 5, эти свойства необходимы для доказательства правильности и определения сложности K*.
Второе наблюдение заключается в существовании соответствия один-к-одному между путей <tex>s-t</tex> в <tex>G</tex> и путей в <tex>Р(G)</tex>, которые начинаются в <tex>\mathrm{R}</tex>.
...
