Область применимости алгоритма А*

При всех своих достоинствах и заслугах алгоритм А* имеет целый ряд имманентно присущих ему особенностей, которые при определенных условиях могут проявлять себя как недостатки.

• • В худшем случае алгоритм, А * имеет экспоненциальные оценки сложности по времени и по памяти. Действительно, пусть в нашем распоряжении нет информированной оценочной функции, удовлетворяющей условию состоятельности. В таком случае придется применять поиск в ширину, h — 0. Допустим (худший случай), что в любом состоянии все правила применимы, и пусть этих правил п. Пусть также количество дуг¹ на оптимальном пути от d_Q к d_t равно 5. Тогда, как нетрудно видеть, общее количество построенных узлов графа поиска составит не менее 1 + п + п^[1][2] + … + + n^s~^x — (и⁵⁻¹ — 1 )/(п — 1).
• • Эффективность алгоритма критическим образом зависит от эвристической функции F. Действительно, выше мы отметили, что при отсутствии эвристики алгоритм в худшем случае совершает количество шагов, экспоненциально зависящее от числа дуг оптимального пути. В то же время если в нашем распоряжении есть предельно информированная оценочная функция, такая что Vd (h (d) = h*(d)) и вдобавок выполнено монотонное ограничение, то алгоритм А* (в худшем случае) построит ns + 1 узлов, поскольку, но теореме предыдущего параграфа, в этом случае раскрываться будут подряд узлы на оптимальном пути. Таким образом, в случае идеальной^[2] эвристики алгоритм А* может иметь трудоемкость, линейную по числу дуг оптимального пути.
• • Алгоритм А* не учитывает структуру базы фактов и использует ее всегда целиком. Это чрезвычайно расточительно по памяти и для очень многих практических задач оказывается неприемлемым. Например, при решении задачи о движении робота в среде с препятствиями база фактов очень невелика — координаты текущего положения робота, и алгоритм А* показывает неплохие результаты. Но если алгоритм Л* применить в экспертной системе над большой реляционной БД, то, формально говоря, каждому узлу в графе соответствует полный слепок (дамп) БД, причем соседние отличаются, может быть, только одной записью.
• • Алгоритм А* не учитывает структуру условий в правилах и повторно вычисляет условия, которые, возможно_у уже проверялись па предыдущих шагах. Это весьма расточительно по времени. В рассмотренном выше примере, при проверке положения робота, вычисления, выполненные для предыдущего положения, нельзя повторно использовать, поскольку координаты изменились. Однако при проверке выполнения некоторого сложного условия для большой реляционной БД 99% работы уже было выполнено при проверке этого условия в предыдущем состоянии, поскольку большая часть данных не изменилась.
• • Алгоритм А* непригоден для случая динамического поиска. Действительно, если продукции, или цель, или веса правил могут динамически меняться в процессе поиска¹, то все рассуждения предыдущих трех подпараграфов утрачивают силу. Состоятельность алгоритма А* основана на том, что выбор дальнейшего пути из некоторого узла не зависит от того, как мы попали в этот узел. В случае динамического поиска это не гак: даже длина пути от текущего до целевого узла может быть различной в зависимости от того, как мы попали в текущий узел.

Вышесказанное отнюдь не означает, что алгоритм А* никуда не годен и его не следует использовать. Напротив, алгоритм А* — это лучшее известное решение, если нет никакой дополнительной конкретизирующей информации о свойствах задачи. Если же дополнительная информация есть, то А* можно и нужно модифицировать с учетом конкретной задачи. Одна из самых элегантных модификаций обсуждается в следующем параграфе.

• [1] Речь идет именно о количестве дуг, а не о длине пути, т. е. нс о сумме весов дуг.
• [2] Строго говоря, если h = hx, то функцию h уже нельзя считать эвристической, посколькуона совпадает с математически точной функцией /?*.
• [3] Строго говоря, если h = hx, то функцию h уже нельзя считать эвристической, посколькуона совпадает с математически точной функцией /?*.