Пошук А*!!!
Пошук А*, як і«найкращий-перший» пошук, оцінює простір пошуку за допомогою евристичної функції. Але A * використовує як вартість отримання від початкового стану до поточного стану (g (n)), так і оцінювану вартість (евристичну) шляху від поточного вузла до мети (h (n)). Вони підсумовуються до функції витрат f (n). Пошук A *, на відміну від першого, є оптимальним і повним.
Списки OPEN та CLOSED знову використовуються для визначення межі пошуку (OPEN) та оцінених вузлів до цих пір (CLOSED). Список OPEN реалізується як пріоритетна черга, замовлена в нижчому порядку f (n). Що робить A * цікавим, що він постійно переоцінює функцію вартості для вузлів, коли вона повторює їх. Це дозволяє A * ефективно знайти мінімальний шлях від початкового стану до стану кінцевого. Давайте тепер подивимося на A * на високому рівні, а потім копатимемо далі і застосуємо його до загальновідомих проблем. Нотатка забезпечує високий рівень потоку для A *.
Нотатка: Висопопоточний алгоритм для пошуку А*.
Initialize OPEN list (priority queue) Initialize CLOSED list Place start node on the OPEN list Loop while the OPEN list is not empty Get best node (parent) from OPEN list (least f (n)) if parent is the goal node, done Place parent on the CLOSED list Expand parent to all adjacent nodes (adj_node) if adj_node is on the CLOSED list discard adj_node and continue else if adj_node is on the OPEN list if adj_node’s g value is better than the OPEN.adj_node’s g value discard OPEN.cur_node calculate adj_node’s g, h and f values set adj_node predecessor to parent add adj_node to OPEN list continue end else calculate adj_node’s g, h and f values set adj_node predecessor to parent add adj_node to OPEN list end end end loop
Зверніть увагу, як видно з нотатки, що як тільки ми виявимо найкращий вузол з списку OPEN, ми розкриємо всі дочірні вузли (можливі легальні структури з кращого вузла). Якщо нові легальні структури не знайдені в списках OPEN або CLOSED, вони додаються як нові вузли (встановлюючи попередник кращого вузла або предка). Якщо новий вузол знаходиться в списку CLOSED , то ми відкинемо його і продовжуватимемо. Нарешті, якщо новий вузол знаходиться у списку OPEN, але новий вузол має краще значення g, ми відкидаємо вузол у списку OPEN та додаємо новий вузол до списку OPEN (в іншому випадку новий вузол буде відкинутий, якщо його g значення гірше). Переоцінюючи вузли в списку OPEN та замінюючи їх, коли дозволяють функції витрат, ми дозволяємо вийти з простору структури кращими шляхами.
Як ми вже визначили, A * є повним, поки пам'ять підтримує глибину та розгалуження дерева. А * також оптимально, але ця характеристика залежить від використання «прийнятної» евристики. Оскільки A * слід відстежувати поки що оцінені вузли (а також виявлені вузли, що підлягають оцінці), складність часу та простору є О (b^d).
ПРИМІТКА.
Евристичний визначається як допустимий, якщо він точно оцінює вартість шляху до цілі або її недооцінює (залишається оптимістичним). Це вимагає, щоб евристичний монотонний, що означає, що вартість ніколи не зменшується по шляху, а замість цього монотонно зростає. Це означає, що g (n) (шлях коштує від вихідного вузла до поточного вузла) монотонно зростає, а h (n) (шлях коштує від поточного вузла до цільового вузла) монотонно зменшується.
