Все об информированном поиске в искусственном интеллекте

Информированный поиск — это тип алгоритма поиска, который использует знания, специфичные для предметной области, для управления поиском в проблемной области. От навигационных систем до игр, от обработки естественного языка до управления цепочками поставок и более информированного поиска в области искусственного интеллекта значительно сократилось количество времени и вычислительных ресурсов, необходимых для решения различных задач.

Используя знания предметной области для управления поиском, информированные алгоритмы поиска могут быстро исключить нерелевантные или менее перспективные пути, позволяя сосредоточить поиск на наиболее перспективных вариантах. Для этого эти типы алгоритмов поиска в ИИ используют эвристику для повышения эффективности и скорости поиска.

Запишитесь на курс машинного обучения в лучших университетах мира. Заработайте программы Master, Executive PGP или Advanced Certificate Programs, чтобы ускорить свою карьеру.

В этой статье будет обсуждаться концепция информированного поиска в искусственном интеллекте, его эвристические функции, примеры алгоритмов, их преимущества и недостатки.

Эвристическая функция

Проще говоря, эвристическая функция — это подход к решению проблем, который использует эмпирическое правило или «наилучшее предположение» для оценки расстояния или стоимости до целевого состояния в задаче поиска. Эвристическая функция оценивает, насколько далеко целевое состояние от текущего состояния, что можно использовать для направления алгоритма поиска к цели.

Алгоритмы информированного поиска используют эти функции в качестве дополнительного источника информации для принятия обоснованных решений о том, какой путь выбрать. По этой причине эвристические функции необходимы в алгоритмах информированного поиска.

Реальные примеры эвристической функции

Чтобы лучше понять эвристические функции, вот несколько примеров из реальной жизни:

• В классической игре «головоломка со скользящими плитками» простой эвристической функцией может быть подсчет количества неуместных плиток в текущей конфигурации по сравнению с целевой конфигурацией. Чем больше плиток не на своем месте, тем дальше текущее состояние от целевого состояния.
• В шахматах эвристическая функция может состоять в том, чтобы присвоить значение каждой фигуре на доске в зависимости от ее относительной силы и положения и использовать сумму этих значений для оценки преимущества или недостатка текущего игрока. Эту эвристическую функцию можно использовать для направления алгоритма поиска в сторону шагов, которые могут привести к лучшей позиции.

После этого давайте теперь продолжим и разберем некоторые из наиболее часто используемых примеров алгоритмов информированного поиска в искусственном интеллекте.

Примеры алгоритмов информированного поиска

Два наиболее часто используемых алгоритма информированного поиска включают лучший первый поиск и поиск A*. Давайте разберемся с этими двумя алгоритмами вместе с некоторыми примерами, преимуществами, недостатками и их реализацией на Python:

1. Лучший первый поиск

Поиск лучшего первого — это алгоритм поиска, который сначала расширяет наиболее перспективный узел в соответствии с эвристической функцией. Алгоритм начинается с начального узла и проверяет все его дочерние узлы, выбирая дочерний узел с наименьшим эвристическим значением в качестве следующего узла для исследования. Этот процесс продолжается до тех пор, пока не будет найден целевой узел или не будут исследованы все узлы.

Лучший первый поиск — иллюстрированный пример

Вот простой пример, иллюстрирующий наилучший первый поиск:

Предположим, вы пытаетесь найти кратчайший путь от своего дома до ближайшего продуктового магазина. Вы знаете расстояние до продуктового магазина из нескольких близлежащих мест, но не знаете точного маршрута. Чтобы решить эту проблему, используя поиск по первому наилучшему, вы можете:

1. Начните с домашнего местоположения и рассчитайте эвристическое значение для каждого близлежащего местоположения в зависимости от его расстояния до продуктового магазина.
2. Выберите ближайшее местоположение с наименьшим эвристическим значением в качестве следующего узла для исследования.
3. Вычислите эвристическое значение для каждого из его дочерних местоположений из этого соседнего местоположения и выберите одно с наименьшим эвристическим значением в качестве следующего узла для исследования.
4. Повторяйте этот процесс, пока не доберетесь до продуктового магазина.

Лучший первый поиск — реализация Python

Вот как вы можете реализовать лучший алгоритм первого поиска в Python:

импорт кучи

def best_first_search (начальное_состояние, целевое_состояние, эвристическая_функция, действия_функция, стоимостная_функция):

# инициализируем границу и исследуемый набор

граница = [(эвристическая_функция (начальное_состояние, целевое_состояние), начальное_состояние)]

исследовано = установить ()

# инициализируем путь и стоимость

путь = {}

стоимость = {}

путь[начальное_состояние] = нет

стоимость [начальное_состояние] = 0

пока граница:

# получить узел с наименьшим эвристическим значением из границы

(h, current_state) = heapq.heappop(граница)

если текущее_состояние == целевое_состояние:

# вернуть путь, если достигнуто целевое состояние

Обратный путь

исследовано.добавить(текущее_состояние)

# генерируем возможные действия из текущего состояния

для действия в action_func(current_state):

следующее_состояние = действие (текущее_состояние)

# рассчитать стоимость нового пути

new_cost = стоимость[текущее_состояние] + cost_func(текущее_состояние, действие, следующее_состояние)

если next_state не в исследованном и next_state не в [состояние для (h, состояние) на границе]:

# добавляем новый штат к границе

heapq.heappush(граница, (heuristic_func(next_state, target_state), next_state))

путь[следующее_состояние] = текущее_состояние

стоимость[следующее_состояние] = новая_стоимость

# вернуть None, если целевое состояние недостижимо

возврат Нет

Как видите, вам нужно определить следующие функции:

• heuristic_func(current_state, target_state): эта функция принимает текущее состояние и целевое состояние в качестве входных данных и возвращает оценку стоимости достижения целевого состояния из текущего состояния.
• action_func(current_state): эта функция принимает текущее состояние в качестве входных данных и возвращает список действий, которые можно выполнить из текущего состояния.
• cost_func(current_state, action, next_state): эта функция принимает текущее состояние, действие и следующее состояние в качестве входных данных и возвращает стоимость выполнения действия из текущего состояния в следующее состояние.

Пример лучшего первого поиска

начальное_состояние = (0, 0)

цель_состояние = (4, 4)

def heuristic_func (текущее_состояние, целевое_состояние):

вернуть абс (текущее_состояние [0] — целевое_состояние [0]) + абс (текущее_состояние [1] — целевое_состояние [1])

определение action_func (текущее_состояние):

действия = []

если текущее_состояние[0] > 0:

action.append (лямбда-состояние: (состояние [0]-1, состояние [1]))

если текущее_состояние[0] < 4:

action.append (состояние лямбда: (состояние [0] + 1, состояние [1]))

если текущее_состояние[1] > 0:

action.append (состояние лямбда: (состояние [0], состояние [1] -1))

если текущее_состояние[1] < 4:

action.append (состояние лямбда: (состояние [0], состояние [1] + 1))

обратные действия

def cost_func (текущее_состояние, действие, следующее_состояние):

вернуть 1

путь = лучший_первый_поиск (начальное_состояние, целевое_состояние, эвристическая_функция, действия_функция, стоимость_функция)

если путь:

# построить путь от начального состояния к целевому состоянию

текущее_состояние = целевое_состояние

в то время как текущее_состояние != начальное_состояние:

печать (текущее_состояние)

текущее_состояние = путь[текущее_состояние]

печать (начальное_состояние)

еще:

print("Целевое состояние недостижимо")

Преимущества лучшего первого поиска

• По сравнению с поиском в ширину временная сложность поиска наилучших результатов ниже.
• Наилучший первый поиск получает и реализует преимущества алгоритмов BFS и DFS.

Недостатки лучшего первого поиска

• Иногда он может покрывать большее расстояние, чем предполагалось.
• Вероятность застрять в петле высока.

Поиск

Поиск A* — это алгоритм поиска, который использует как стоимость достижения узла от начального узла, так и оценку оставшейся стоимости достижения целевого узла, чтобы управлять его поиском. Алгоритм начинается с начального узла и проверяет все его дочерние узлы, выбирая дочерний узел с наименьшей совокупной стоимостью и предполагаемой оставшейся стоимостью в качестве следующего узла для исследования. Этот процесс продолжается до тех пор, пока не будет найден целевой узел или не будут исследованы все узлы.

Поиск A* – иллюстрированный пример

Давайте еще раз посмотрим на предыдущий пример, когда вы пытаетесь найти кратчайший путь от вашего дома до ближайшего продуктового магазина. Теперь вы можете:

1. Начните с местоположения вашего дома и рассчитайте общую стоимость достижения каждого близлежащего местоположения как сумму расстояния от вашего дома до этого местоположения и расчетной оставшейся стоимости, чтобы добраться до продуктового магазина из этого местоположения.
2. Выберите ближайшее место с наименьшей общей стоимостью в качестве следующего узла для исследования.
3. Из этого близлежащего местоположения вычислите общую стоимость для каждого из его дочерних местоположений как сумму расстояния от этого местоположения до дочернего местоположения, стоимости достижения этого местоположения из начального узла и расчетной оставшейся стоимости для достижения продуктового магазина. из этого дочернего местоположения. Выберите дочернее местоположение с наименьшей общей стоимостью в качестве следующего узла для исследования.
4. Повторяйте этот процесс, пока не доберетесь до продуктового магазина.

Здесь важно отметить, что поиск A* — это оптимальный алгоритм поиска, гарантирующий нахождение кратчайшего пути к целевому состоянию. Он эффективен в задачах с большим пространством поиска и широко используется в видеоиграх, робототехнике и планировании маршрутов. Однако для эффективной работы требуется четко определенная эвристическая функция. По этой причине алгоритм может потреблять много памяти и замедляться в сложных задачах со многими узлами.

Поиск A* — реализация Python

Вот как вы можете реализовать алгоритм поиска A* с помощью программирования на Python:

импорт кучи

def astar_search (начальное_состояние, целевое_состояние, эвристическая_функция, действия_функция, стоимость_функция):

# инициализируем границу и исследуемый набор

граница = [(эвристическая_функция (начальное_состояние, целевое_состояние), начальное_состояние)]

исследовано = установить ()

# инициализируем путь и стоимость

путь = {}

стоимость = {}

путь[начальное_состояние] = нет

стоимость [начальное_состояние] = 0

пока граница:

# получить узел с наименьшим f-значением от границы

(f, current_state) = heapq.heappop(граница)

если текущее_состояние == целевое_состояние:

# вернуть путь, если достигнуто целевое состояние

Обратный путь

исследовано.добавить(текущее_состояние)

# генерируем возможные действия из текущего состояния

для действия в action_func(current_state):

следующее_состояние = действие (текущее_состояние)

# рассчитать стоимость нового пути

new_cost = стоимость[текущее_состояние] + cost_func(текущее_состояние, действие, следующее_состояние)

если next_state не в исследованном и next_state не в [состояние для (f, состояние) на границе]:

# добавляем новый штат к границе

heapq.heappush(граница, (new_cost + heuristic_func(next_state, target_state), next_state))

путь[следующее_состояние] = текущее_состояние

стоимость[следующее_состояние] = новая_стоимость

elif next_state в [состояние для (f, состояние) на границе] и new_cost < cost[next_state]:

# обновить стоимость существующего состояния на границе

index = [i for (i, (f, state)) в перечислении (граница), если состояние == next_state][0]

граница [индекс] = (новая_стоимость + эвристическая_функция (следующее_состояние, целевое_состояние), следующее_состояние)

путь[следующее_состояние] = текущее_состояние

стоимость[следующее_состояние] = новая_стоимость

# вернуть None, если целевое состояние недостижимо

возврат Нет

Лучшие онлайн-курсы по машинному обучению и курсы по искусственному интеллекту

Пример поиска A*

Вот пример того, как вы можете использовать функцию astar_search с этими функциями:

начальное_состояние = (0, 0)

цель_состояние = (4, 4)

def heuristic_func (текущее_состояние, целевое_состояние):

вернуть абс (текущее_состояние [0] — целевое_состояние [0]) + абс (текущее_состояние [1] — целевое_состояние [1])

определение action_func (текущее_состояние):

действия = []

если текущее_состояние[0] > 0:

action.append (лямбда-состояние: (состояние [0]-1, состояние [1]))

если текущее_состояние[0] < 4:

action.append (состояние лямбда: (состояние [0] + 1, состояние [1]))

если текущее_состояние[1] > 0:

action.append (состояние лямбда: (состояние [0], состояние [1] -1))

если текущее_состояние[1] < 4:

action.append (состояние лямбда: (состояние [0], состояние [1] + 1))

обратные действия

def cost_func (текущее_состояние, действие, следующее_состояние):

вернуть 1

путь = astar_search (начальное_состояние, целевое_состояние, эвристическая_функция, действия_функция, стоимость_функция)

если путь:

# построить путь от начального состояния к целевому состоянию

текущее_состояние = целевое_состояние

в то время как текущее_состояние != начальное_состояние:

печать (текущее_состояние)

текущее_состояние = путь[текущее_состояние]

печать (начальное_состояние)

еще:

print("Целевое состояние недостижимо")

Преимущества поиска A*

• Это один из ведущих эвристических методов.
• Поиск A* можно использовать для решения сложных задач поиска.

Актуальные навыки машинного обучения

Недостатки поиска A*

• Эффективность поиска A* в значительной степени зависит от точности эвристических алгоритмов.
• Имеет низкую эффективность поиска.

Популярные блоги об искусственном интеллекте и машинном обучении и бесплатные курсы

Еда на вынос

Алгоритмы информированного поиска необходимы в искусственном интеллекте, поскольку они позволяют компьютеру эффективно и действенно искать целевое состояние. Эти алгоритмы используют эвристические функции для оценки стоимости каждого возможного хода и направляют процесс поиска к целевому состоянию. Best First Search и A* Search являются примерами алгоритмов информированного поиска, широко используемых в различных областях. Однако четко определенная эвристическая функция имеет решающее значение для успеха алгоритмов информированного поиска.

Если вы хотите узнать больше об искусственном интеллекте и машинном обучении, ознакомьтесь с программой UpGrad Masters in Machine Learning & Artificial Intelligence, предлагаемой Ливерпульским университетом Джона Мура . Эта программа охватывает различные темы машинного обучения и искусственного интеллекта, включая такие алгоритмы, как информированный поиск. Принимая участие в этой программе, вы можете получить навыки и знания, необходимые для достижения успеха в различных сферах деятельности, связанных с ИИ.

Вы также можете ознакомиться с нашимибесплатными курсами,предлагаемыми upGrad, по менеджменту, науке о данных, машинному обучению, цифровому маркетингу и технологиям.Все эти курсы включают в себя первоклассные учебные ресурсы, еженедельные живые лекции, отраслевые задания и сертификат об окончании курса — и все это бесплатно!