#java #artificial-intelligence #a-star #heuristics
#java #искусственный интеллект #a-star #эвристика
Вопрос:
Я пытаюсь решить проблему с ИИ. У меня есть «робот», который должен перемещаться из точки A в B как можно быстрее и дешевле. Этот ровер не может подниматься на высоту более 10 единиц, а стоимость его маршрута зависит от типа местности. Мне нужна ваша помощь, потому что мне нужно найти допустимую эвристику для решения моей проблемы. Я уже пробую евклидово расстояние, но этого недостаточно. Вы можете мне помочь?
Комментарии:
1. A* уже является эвристикой. Он находит кратчайший путь на карте. Дополнительные примитивы движения необходимы только в том случае, если в спецификации игры есть дополнительные функции, такие как использование правой полосы движения, движение в скрытом режиме или объезд препятствий определенного радиуса.. (Извините, но я не могу проголосовать, оценка остается прежней.)
2. Что вы имеете в виду, говоря «я уже пробую евклидово расстояние, но его недостаточно».? Вы имеете в виду, что, используя эту эвристическую функцию, алгоритм возвращает неправильные решения? Или что это слишком медленно? Или вообще не находит решений? @ManuelRodriguez A * уже не является эвристикой, это алгоритм поиска, который использует эвристическую функцию
3. Привет, чувак, спасибо за ответ! Этого недостаточно, потому что мне нужно больше эвристики! Для этой работы требуется две или более эвристики, поскольку я сравниваю решения для проверки, какая эвристика является лучшей. И да, A * это не эвристика. Эвристика — это функция, которая помогает алгоритму искать лучшие узлы для исследования. Евклидиан работает нормально, но мне нужно больше! С наилучшими пожеланиями @Dennis Soemers
Ответ №1:
Я бы рекомендовал взглянуть на эту страницу для получения некоторых идей эвристики. Не все они будут применимы в вашей ситуации, поскольку я не верю, что у вас есть карта сетки? Но вы можете хотя бы взглянуть.
Кроме того, я бы рекомендовал попытаться учесть различные затраты, которые возможны в разных типах местности. Если, например, вы знаете, что каждый отдельный возможный тип местности имеет минимальную стоимость 2, вы можете безопасно умножить свое евклидово расстояние на 2. Если наиболее распространенный тип местности имеет стоимость 2, но существуют также некоторые типы местности с более низкой стоимостью, вы теряете гарантию нахождения оптимального решения, если начнете умножать на 2, но на практике вы все равно можете быстрее находить решения.
Для меня вопрос звучит как домашнее задание (поправьте меня, если я ошибаюсь), что затрудняет однозначный ответ. Я предполагаю, что смысл домашнего задания даже в том, чтобы немного исследовать и попробовать разные вещи и посмотреть, как они работают (или не работают), что может улучшить ваше понимание того, как работает алгоритм. Итак, действительно, просто попробуйте некоторые вещи.