Учитывая график с набором из 5 узлов, 2 из которых являются узлами цели.A * алгоритм с несколькими целями
Запустив алгоритм, он находит узел цели 1 со стоимостью 7 и завершает работу.
Хозяева выбраны целиком - 2, со стоимостью 6.
Есть, так как цель 1 - правильное решение? Или оптимальное решение для A *, чтобы найти цель-2 со стоимостью 6?
Есть, находя цель-1, как первое решение правильно?
Да правильно, но не оптимальна
Или оптимальное решение для А *, чтобы найти цель-2 со стоимостью 6?
Действительно
A * полагаться на эвристики для выполнения поиска. Вы должны предоставлять различные эвристики в зависимости от того, выполняете ли вы поиск «одна цель» или «несколько целей». Если у вас есть admissible heuristic за один гол, это не значит, что это допустимо для нескольких целей.
Ваша первоначальная эвристика - h(x) = somedistance(x,g).
Обобщенная версия h'(x) = min{ somedistance(x,gi), gi in GoalSet }.
Проблема определяет нашу эвристику следующим образом: Минимальное количество путей от текущего узла до узла цели. Итак, мы должны использовать эту эвристическую функцию. Учитывая вышеизложенное, поиск цели-1 является приемлемым решением, верно? A * найти оптимальную стоимость пути для цели-1, так как есть еще один путь со стоимостью 12. – Chris
сообщение в вопрос, как вы внедрили эту функцию – UmNyobe
«минимальное количество путей»? действительно ? – UmNyobe
он должен найти цель 2. Эвристика не должна быть одинаковой от одного поиска цели до нескольких целей поиска – UmNyobe
Это ваша домашняя работа? –
@UmNyobe: Но A * просто использует функцию f, которая вычисляет сумму стоимости пути, что узел N (функция g), а эвристическая функция просто имеет расстояние от текущей цели до узла цели. То есть в математическом выражении: f (n) = g (n) + h (n). – Chris