#algorithm #search #artificial-intelligence
#алгоритм #Поиск #искусственный интеллект
Вопрос:
Итак, основное различие между поиском с наилучшими результатами (информированный) и поиском с равномерной стоимостью (неинформированный) заключается в том, что в BFS мы используем эвристическую функцию для определения, к какому узлу перейти следующим. В UCS мы всегда берем наименьшую стоимость, которая вычисляется из моего начального состояния.
Какая эвристическая функция используется при поиске с наилучшими результатами? Везде упоминается, что это за эвристическая функция h(n) = f(n) , но что это f(n) такое и как мне получить ее значение, если моя «карта» имеет много узлов и только стоимость путей от одного узла к другому?
Ответ №1:
Эвристическая функция не является уникальной вещью. Принимаемое вами решение в значительной степени зависит от конкретных свойств решаемой задачи. И даже тогда вы можете выбирать между различными подходами (функциями). Часто вы будете проверять, как выбранная функция влияет на качество решений, найденных в примерах, и тестировать альтернативы.
Например, если граф является евклидовым графом, где узлы представляют координаты в n-мерном пространстве, а стоимость ребра равна его длине (расстоянию между соединенными узлами), то одной из возможных эвристик может быть расстояние между исходным и целевым узлом.
Чем меньше вы можете предположить о графике — чем меньше вы знаете о его свойствах — тем сложнее будет найти подходящую эвристическую функцию.
Комментарии:
1. Под n-мерным пространством вы подразумеваете 2D или 3D пространство? Упомянутая вами эвристика будет определяться формулой, которая вычисляет расстояние между двумя точками (в 2D, квадратный корень из квадрата дельты x квадрата дельты y), верно?
2. Кроме этой довольно простой эвристики (используется ли она в практических приложениях или ее просто преподают, чтобы показать нам, что такое эвристическая функция?), какие другие, более сложные, но более точные эвристики мы обычно используем в евклидовом графике, который дает нам только координаты в каждом узле?
3. Я действительно имею в виду n-мерный, а не только 2- или 3-мерный. Действительно, это то, что я имею в виду с расстоянием. Эвристические функции не могут быть сложными, если все, что вы знаете об узле, — это его координаты (и координаты целевого узла), если только у вас нет дополнительной информации (например, о областях, которые не содержат узлов).