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>\delta(u, v) = f_u(v) - f(v) = g(u) + c(u, v) + h(v) - g(v) - h(v) = g(u) + c(u, v) - g(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>.
[[Файл: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''). Сформулируем следующую лемму.
