Я планирую использовать алгоритм A * для поиска пути на бесконечной сетке с препятствиями, где допускаются только диагональные движения. Но я не уверен в том, какую эвристику использовать. Я знаю, что я не могу использовать Манхэттенское расстояние. Кто-нибудь может предложить что-то?Эвристика для A *, когда разрешено только диагональное перемещение
Подумайте, шахматы. Поверните на 45 градусов. Если разрешено только диагональное движение, по сути, это похоже на сетку с ортогональным движением, но половина точек на исходной сетке недостижима.
Да, какой эвристикой я должен использовать, чтобы это допустимо? – Arun
@Arun: сначала убедитесь, что цель достижима. Затем преобразуйте координаты в обычную сетку и используйте любую эвристику, которую вы будете использовать для такой сетки. –
Если разрешены только диагональные движения, то в зависимости от исходного положения половина решетки не может быть доступна. Правильно ли это? (например, епископ в шахматах) – Demplo
@ Demplo Да, вы правы. – Arun
Тогда я бы сказал, что ответ Тома прекрасно работает. Как только вы узнаете, достигнут ли цель, вы вращаетесь на 45 градусов и используете Манхэттен. Предполагая, что диагональные ходы стоят 1. – Demplo