2
ПОРІВНЯННЯ РІЗНИХ ЕВРИСТИЧНИХ ФУНКЦІЙ В АЛГОРИТМІ А*
Підготував:Шевцов М.В., студент 1 курсу
спеціальності 122 «Комп’ютерні науки»
А* алгоритм
Алгоритм пошуку А* -використовується для пошуку найкоротшого шляху між двома вершинами графу з додатніми вагами ребер.
Алгоритм використовує допоміжну функцію (евристику), аби скеровувати напрям пошуку та скорочувати його тривалість.
f(x) = g(x) + h(x)
Введення
h(x) - функція оцінки відстані від поточної вершини до кінцевої по прямій(евристична). Використана евристика не повинна давати завищену оцінку вартості шляху. Прикладом оцінки може служити пряма лінія: загальний шлях не може бути коротшим за пряму лінію.
Евристика
Евклідова відстань
В алгоритмі А* евклідова відстань може бути ефективною у випадку прямолінійних маршрутів без перешкод.
Евклідова відстань
Манхеттенська відстань
В алгоритмі А* манхеттенська відстань може бути досить ефективною для пошуку шляху в графі з прямокутними блоками на мапі міста.
Манхеттенська відстань
Діагональна відстань
Діагональна відстань
В алгоритмі A* діагональна відстань може бути ефективною для пошуку шляху у просторі, де можливий рух у будь якому напрямку.
Квадратична відстань
В алгоритмі A* квадратична відстань може бути ефективною для пошуку шляху з рівномірною швидкістю руху у просторі.
Квадратична відстань
Список літератури
Список літератури
1. Russell, S. J., & Norvig, P. Artificial intelligence: a modern approach. Prentice Hall. — 2010. — № 3. — C. 94—102
2. Hart, P. E., Nilsson, N. J., & Raphael, B. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics. — 1968. — № 4. — C. 100—107