2.2 Евристичні алгоритми

Евристичний алгоритм - це алгоритм, спроможний видати прийнятне рішення проблеми серед багатьох рішень, але неспроможний гарантувати, що це рішення буде найкращим. Отже, такі алгоритми є приблизними і неточними. Зазвичай такі алгоритми знаходять рішення, близьке до найкращого і роблять це швидко. Іноді такий алгоритм може бути точним, тобто він знаходить дійсно найкраще рішення, але він все одно буде називатися евристичним доти, доки не буде доведено, що рішення дійсно найкраще.

Використання евристичних, а не точних, алгоритмів для пошуку траєкторії руху мобільного робота на динамічно змінній місцевості може призвести до зростання швидкодії та мінімізації випадків, коли час, відведений на обрахунок траєкторії руху перевищує час, за який ситуація на карті змінюється.

2.2.1 Алгоритм a*

Даний алгоритм є алгоритмом пошуку по першому найкращому збігу на графі, який знаходить маршрут з найменшою вартістю від однієї вершини (початкової) до іншої (цільової, кінцевої).

Порядок обходу вершин визначається евристичною функцією «відстань плюс вартість» (зазвичай позначається як f(x)). Ця функція - сума двох інших: функції вартості досягнення розглянутої вершини (x) з початкової (зазвичай позначається як g(x) і може бути як евристичною, так і звичайною) і евристичної оцінки відстані від розглянутої вершини до кінцевої (позначається як h(x )).

Функція h(x) повинна бути припустимою евристичною оцінкою, тобто не повинна переоцінювати відстані до цільової вершині. Наприклад, для задачі маршрутизації h(x) може являти собою відстань до цілі по прямій лінії, так як це фізично найменша можлива відстань між двома точками.

Алгоритм використовує допоміжну функцію (евристику), аби вказувати напрям пошуку та скорочувати його тривалість. Алгоритм повний в тому сенсі, що завжди знаходить оптимальний шлях при умові його існування.

A* покроково переглядає всі шляхи, що ведуть від початкової вершини в кінцеву, поки не знайде мінімальний. Як і всі інформовані алгоритми пошуку, він переглядає спочатку ті маршрути, які «здаються» ведуть до мети. Від жадібного алгоритму (який теж є алгоритмом пошуку за першим кращим збігом) його відрізняє те, що при виборі вершини він враховує, крім іншого, весь пройдений до неї шлях (складова g(x) - це вартість шляху від початкової вершини, а не від попередньої, як в жадібному алгоритмі). На початку роботи проглядаються вузли, суміжні з початковим; вибирається той з них, який має мінімальне значення f(x), після чого цей вузол розкривається. На кожному етапі алгоритм оперує з безліччю шляхів з початкової точки до всіх ще не розкритих (листових) вершин графа («безліччю приватних рішень»), які розміщуються у черзі з пріоритетом. Пріоритет шляху визначається за значенням f(x) = g(x) + h(x). Алгоритм продовжує свою роботу до тих пір, поки значення f(x) цільової вершини не виявиться меншим, ніж будь-яке значення в черзі (або поки все дерево не буде переглянуто). З множинних рішень вибирається рішення з найменшою вартістю.

Як і точні алгоритми, A* є повним в тому сенсі, що він завжди знаходить рішення, якщо таке існує [10].

Якщо евристична функція h допустима, тобто ніколи не переоцінює дійсну мінімальну вартість досягнення мети, то A* сам є допустимим (або оптимальним), також за умови, що ми не відсікаємо пройдені вершини. Якщо ж ми це робимо, то для оптимальності алгоритму потрібно, щоб h(x) була ще й монотонною, або наслідуючою евристикою. Властивість монотонності означає, що якщо існують шляхи A-B-C і A-C (не обов'язково через B), то оцінка вартості шляху від A до C повинна бути менше або дорівнює сумі оцінок шляхів A-B і B-C. (Монотонність також відома як нерівність трикутника: одна сторона трикутника не може бути довше, ніж сума двох інших сторін.) Математично, для всіх шляхів x, y (де y - нащадок x) виконується:

g(x) + h(x) ≤ g(y) + h(y)...................................................(2.5)

A* також оптимально ефективний для заданої евристики h. Це означає, що будь-який інший алгоритм досліджує не менше вузлів, ніж A * (за винятком випадків, коли існує кілька виняткових рішень з однаковою евристикою, точно відповідної вартості оптимального шляху).

У той час як A* оптимальний для «випадково» заданих графів, немає гарантії, що він зробить свою роботу краще, ніж більш прості, але і більш інформовані щодо проблемної області алгоритми. Наприклад, в деякому лабіринті може знадобитися спочатку йти у напрямку від виходу, і тільки потім повернути назад. У цьому випадку обстеження спочатку тих вершин, які розташовані ближче до виходу (по прямій дистанції), буде втратою часу.