418
правок
Изменения
м
Следствие 2. {{Лемма|about=следствие 3|statement=Пусть <tex>n</tex> будет произвольным узлов узлом в <tex>P(G)</tex>. Если <tex>h</tex> допустимая функция, то <tex>n</tex> никогда не будет удален из <tex>P(G)</tex> после того, как <tex>n</tex> был рассмотрен алгоритмом Дейкстры. |proof=...}}
→4.5 Взаимосвязь алгоритмов Дейкстры и A*
{{Лемма
|about=1
|statement=Все узлы, которые достижимы достижимые из <tex>R(v)</tex> через кучные ребрапо кучным ребрам, для каждой вершины <tex>v</tex> формируют тернарную кучу, упорядоченную в соответствии с <tex>\delta</tex>-значением. Мы назовем такую кучу '''графовой кучей ''' (англ. ''graph heap'') вершины <tex>v</tex> и обозначим её как <tex>H_{G}(v)</tex>.|proof=Те узлы, которые находятся в <tex>H_{T}(v)</tex> или во входящей куче, на которую ссылается узел из <tex>H_{T}(v)</tex>, достижимы по кучным ребрам из <tex>R(v)</tex>. Деревянная куча <tex>H_{T}(v)</tex> формируется через добавление корней входящих куч всех вершин, лежащих на пути из стартовой вершины <tex>s</tex> до <tex>v</tex> в бинарной куче. Каждый из этих корней имеет максимум 3 детей: до 2 в <tex>H_{T}(v)</tex> и дополнительно единственного из входящей кучи. Любой другой узел, живущий во входящей куче имеет не больше 2 детей. Напомним, что каждая входящая куча - это бинарная куча с ограничением, что корень имеет единственного ребенка.Древовидная структура <tex>H_{G}(v)</tex> непосредственный результат древовидных структур <tex>H_{T}(v)</tex> и входящих куч. Более того, кучная характеристика деревянной кучи обеспечивает упорядочивание в соответствии с <tex>\delta</tex>-значением по ребрам из <tex>H_{T}(v)</tex>, а кучная характеристика входящих куч - по всем ребрам из <tex>H_{in}</tex>.Все это приводит к тому, что <tex>H_{G}(v)</tex> - тернарная куча, упорядоченная в соответствии с <tex>\delta</tex>-значением.
}}
Тот факт, что оба алгоритма A* и Дейкстры делят между собой граф путей <tex>P(G)</tex>, вызывает обеспокоенность в отношении правильности работы Дейкстры на <tex>P(G)</tex>. Возобновление A* приводит к изменениям в структуре <tex>P(G)</tex>. Таким образом, после возобновления A*, мы обновляем <tex>P(G)</tex> и проверяет статус поиска Дейкстры (строка 15). В основном, A* может добавить новые узлы, менять <tex>\delta</tex>-значения существующих узлов или даже удалять узлы. A* может также существенно изменять дерево поиска <tex>T</tex>, которое будет в худшем случае разрушать структуру все деревянных куч <tex>H_{T}</tex>. Эти изменения могут приводить к глобальной реструктуризации или даже перестроению <tex>P(G)</tex> с нуля. В худшем случае это может сделать предыдущие поиски Дейкстры на <tex>P(G)</tex> бесполезными таким образом, что нам придется перезапускать алгоритм Дейкстры с нуля.
Если использованная эвристическая оценка допустимая, то наше положение лучше. Нам по-прежнему может понадобится перестроение <tex>P(G)</tex>, но мы покажем, что это перестроение не мешает корректности поиска Дейкстры на <tex>P(G)</tex>. Другими словами, мы не теряем результаты, до сих пор полученные поиском Дейкстры. В случае монотонной эвристической оценки мы даже не нуждаемся в восстановлении или перестроении <tex>P(G)</tex>. Если <tex>h</tex> монотонная, то дерево поиска A* является деревом кратчайшего пути для всех раскрытых вершин. Следовательно, g-значения раскрытых вершин не изменитсяменяются. Это означает, что <tex>\delta</tex>-значения для внутренних ребер никогда не изменятся. Ребра дерева раскрытых вершин не изменятся также. Следовательно, обновление <tex>\delta</tex>-значений, heaping-up, heaping-down (операции в кучах) или удаление узлов не влекут за собой каких-либо изменений в <tex>P(G)</tex>. Только добавление новых узлов приводит к изменениям в <tex>P(G)</tex>. Следовательно, восстановление или глобальное перестроение или глобальная реструктуризация не требуется в данном случае.
В оставшейся части этого раздела, мы сначала покажем, что корректность поиска Дейкстры на <tex>P(G)</tex> поддерживается в случае допустимой эвристической оценки. После этого мы покажем, что изменения в <tex>P(G)</tex> могут помешать завершенности поиска Дейкстры независимо от того, является ли эвристика допустимой или даже монотонной. Следовательно, мы предложим механизм для её поддержания.
Из леммы 6 мы может вывести следующее следствие.
Более того, мы докажем, что структура исследованной части <tex>P(G)</tex> не изменится.
