Человеческий фактор. Том 3. Часть 1 - Сальвенди Г.
ISBN 5-03-001815-8
Скачать (прямая ссылка):
98
Глава 2
где g(n) —мера стоимости перехода из начального узла в узел п, a h(n) —оценка дополнительной стоимости перехода из узла п в целевой узел (т. е. f(n) представляет собой оценку стоимости перехода из начального узла в целевой узел по пути, который обязательно проходит через узел п).
Алгоритм А*
Шаг 1. Начать со списка OPEN, содержащего только начальный узел. Установить значение g этого узла в 0, присвоить h
то значение, которое необходимо, а значение f записать как ft-J-О, или h. Присвоить списку CLOSED значение «пустой список».
Шаг 2. До тех пор пока не будет найден целевой узел, повторять описываемую ниже процедуру. Если в OPEN нет ни одного узла, выдать сообщение о неудачной попытке поиска. В противном случае выбрать узел в OPEN с наименьшим значением f. Назвать этот узел BESTNODE (наилучший узел) и изъять его из списка OPEN, поместив в список CLOSED. Проверить, является ли BESTNODE целевым узлом. Если да, то осуществить выход из процедуры и выдать сообщение о том, что решение найдено (когда нас интересует только узел, выдается информация относительно BESTNODE; когда же важен путь, то сообщаются данные о пути между начальным узлом и узлом BESTNODE). При отрицательном ответе осуществить формирование преемников BESTNODE, но пока BESTNODE не должен содержать указателей на них. (Сначала надо проверить, не сформированы ли уже некоторые из преемников.) Для каждого такого преемника (SUCCESSOR) выполнить следующее.
1. Установить SUCCESSOR так, чтобы он указывал обратно на BESTNODE. Эти связи в обратном направлении позволяют восстановить путь после нахождения решения.
2. Вычислить g'(SUCCESSOR) = g(BESTNODE)-^-Стоимость перехода из BESTNODE в SUCCESSOR.
3. Проверить, не совпадает ли SUCCESSOR с каким-либо узлом в OPEN (он может быть уже сформирован, но еще не обработан). Если совпадает, то считать этот узел старым (OLD). Поскольку этот узел уже существует в графе, мы теперь можем отбросить SUCCESSOR и добавить OLD к списку преемников узла BESTNODE. Теперь мы должны решить, следует ли переориентировать связь узла OLD со своим родителем так, чтобы она указывала на BESTNODE. Переориентация требуется, если путь к SUCCESSOR, который мы только что нашли, дешевле текущего наилучшего пути к OLD (поскольку на самом деле SUCCESSOR и OLD — это один и тот же узел). Поэтому следует проверить, что дешевле: переход к OLD от его теку*
Искусственный интеллект
99
щего родителя или переход к SUCCESSOR от BESTNODE. Для этого сравниваются значения g. Если первый путь дешевле (или равен по стоимости второму), то делать ничего не требуется. Если дешевле второй путь, то связь OLD со своим родителем надо переориентировать (чтобы она указывала на BESTNODE), зафиксировать новый, более дешевый путь в g(OLD) и изменить /(OLD) соответствующим образом.
4. Если узла SUCCEESOR нет в OPEN, то проверить, нет ли его в CLOSED. Если он есть в CLOSED, то назвать его OLD и добавить его к списку преемников BESTNODE. 'Аналогично шагам 2 и 3 проверить, какой путь (старый или новый) дешевле, после чего установить величины g и f и связь с узлом-родителем соответствующим образом. Если только что обнаружен лучший путь к OLD, то мы должны распространить это улучшение и на преемников OLD. Однако сделать это не так-то просто. Узел OLD указывает на своих преемников. Каждый преемник, в свою очередь, указывает на своих преемников и т. д., до тех пор пока каждая ветвь не завершится узлом, который либо все еще находится в списке OPEN, либо не имеет преемников. Поэтому для распространения нового значения стоимости вниз по дереву надо-осуществить проход в глубину по дереву, начиная с OLD и изменяя значение g (а следовательно, и значение /) каждого узла, причем каждая ветвь завершается, когда мы либо дошли до узла, не имеющего преемников, либо до узла, к которому уже найден эквивалентный или лучший путь. Это условие легко проверить. Связь каждого узла с его родителем указывает назад на родительский узел, который точно известен. По мере того как мы переходим вниз и доходим до некоторого узла, следует проверить, указывает ли его родитель на узел, из которого мы вышли. Если да, то необходимо продолжить прохождение вниз. Отрицательный ответ означает, что величина g или данного узла свидетельствует о наличии лучшего пути, элементом которого он является; следовательно, в данной точке можно остановиться. Однако возможен и такой случай, когда при распространении вниз значения g обнаруживается, что путь, которым мы следуем, становится лучше пути, проходящего через существующий родительский узел. Поэтому надо сравнить эти два пути. Если путь через существующий узел-родитель все же лучше, то следует прекратить поиск; если же лучшим оказывается тот путь, который прокладывается, то необходимо перевести родительский узел в исходное состояние и продолжить прохождение вниз.
5. Если узла SUCCESSOR нет еще ни в OPEN, ни в CLOSED, то следует поместить его в OPEN и добавить его к списку преемников BESTNODE. Вычислить: f (SUCCESSOR) = = g (SUCCESSOR) -f-ft (SUCCESSOR).
