Алгоритм обхода препятствий

Алгоритм обхода препятствий Предлагаемый алгоритм обхода препятствий - это, так называемый, обобщенный алгоритм Дейкстры. В англоязычной литературе он называется алгоритмом A*. ·1. Карта разбита на квадратные части, назовем их клетками. ·2. Каждая клетка имеет несколько показателей: ·1) стоимость прохождения по этой клетке, ·2) предыдущая клетка - клетка из которой пришли в эту клетку, ·3) статус клетки (непосещенная, граничная, отброшенная), ·4) оценка пройденного пути, ·5) оценка оставшегося пути. ·3. Имеется две клетки - начальная и конечная. ·4. Сосед клетки - клетка в которую можно попасть из рассматриваемой за 1 шаг. Общий принцип: на каждой итерации из всех граничных точек выбирается та, для которой сумма уже пройденного пути и пути до конца по прямой является минимальной, и от нее осуществляется дальнейшее продвижение. Алгоритм этот проще реализовать, чем описать: Start - начальная клеткаFinish - конечная клетка.Алгоритм итерационный1 шаг: Помечаем Start как граничную точку.2 шаг: Среди всех граничных точек находим Клетку1 - клетку с минимальной суммой оценки пройденного пути g и оценки оставшегося пути h.3 шаг: Для Клетки 1 рассматриваем соседей. Если сосед имеет статус непосещенного, то мы обозначаеми его как граничную клетку, и указываем Клетку1 как предыдущую для него. Оценку g1 для соседа принимаем равной g+p, где p-стоимость прохождения по клетке сосед, а g - оценка пройденного пути для Клетки1 . Оценка h для любой клетки равна длине кратчайшего пути (по прямой от рассматриваемой клетки до клетки Finish) Рассматриваемую Клетку1 помечаем как отброшенную. 4 шаг: Если на предыдущем шаге один из соседей оказался равен клетке Finish, то путь найден. Если ни одного нового соседа не существует, то нет и пути. 5 шаг: Переход на шаг 2. DelphiWorld 6.0

Отправить комментарий

Проверка
Антиспам проверка
Image CAPTCHA
...