0 просмотров

ИИ и поиск по графику

Название изображения

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

Вам также могут понравиться: Графические алгоритмы в Neo4j: кратчайший путь для всех пар

Что такое искусственный интеллект?

Оглядевшись вокруг, вы увидите, что четкого и единого определения искусственного интеллекта не существует. Некоторые говорят, что «искусственный интеллект определяется как исследование рациональных агентов», где «рациональным агентом может быть все, что принимает решения, например, человек, фирма, машина или программное обеспечение. Он выполняет действие с наилучшим результатом после рассмотрения прошлого и текущие восприятия (перцептивные входы агента в данный момент)». Другие определения более философски пытаются найти границу между естественным интеллектом человека и тем, что может делать машина. Но все определения пытаются сказать, что ИИ на самом деле является дисциплиной, когда вы хотите знать, что делать, когда не знаете, что делать. И вот появляется рациональный агент, который, воспринимая окружающую среду с помощью некоторых датчиков и глядя на старые действия, которые он уже выполнил, пытается выбрать следующее действие с наилучшим возможным результатом8. Итак, давайте рассмотрим классический поиск маршрута. проблема. У нас есть граф со многими узлами, и вы пытаетесь найти путь с минимальной стоимостью между двумя узлами. А вот и определение агента ИИ. Вы точно не знаете, каков путь, и рациональный агент, воспринимая окружающую среду, в нашем случае граф, найдет этот путь.Но мы знаем, что существует множество алгоритмов, способных решить задачу поиска по графу. Просто посмотрите на DFS, BFS, Dijkstra или A*. Некоторые из нас знают этот алгоритм со школы. Итак, что здесь нового? Это на самом деле то, что делает агент ИИ? Ну да, но не только это. ИИ — это не просто парадигма программирования, как алгоритмы поиска по графу, но, как я уже говорил, это исследование рациональных агентов, которые изучают окружающую среду и пытаются выбрать действие с лучшим результатом. Агент ИИ — это широкий термин. Они доходят до машинного обучения, нейронных сетей, глубокого обучения и многого другого, и они используются в финансах, медицинских учреждениях, безопасности и т. д. Так что поиск по графу — это лишь небольшой подвид ИИ. Разница между классическим алгоритмом поиска по графу и агентом ИИ, способным найти кратчайший путь между двумя узлами, заключается лишь в разнице в терминологии. И важно понимать этот аспект так, как будто вы пытаетесь создать агента ИИ, который на самом деле ничем не отличается от алгоритма старой школы.

Статья в тему:  Почему мы нужны будущему, искусственный интеллект фильм

Алгоритмы старой школы

Существует много способов реализовать поиск по графу. Существуют классические алгоритмы, такие как BFS и DFS, способные найти целевой узел без расчета оптимального пути, а также такие алгоритмы, как Unifrom Cost search, Dijkstra или A*, способные вычислить кратчайший путь от источника к источнику. Цель. Все эти алгоритмы основаны на деревьях, единственная загвоздка которых в том, что графы, в отличие от деревьев, могут содержать циклы. Суть всех этих алгоритмов в том, что после посещения узла мы должны выбрать следующий непосещенный узел и «посетить» его, чтобы увидеть, достигли мы цели или нет.

Подробнее о БФС

Как я уже говорил, поиск в ширину — это древовидный алгоритм. Его название происходит от идеи, что обход графа является послойным. Начиная с исходного узла, мы сначала исследуем соседей, а затем двигаемся дальше вниз. Давайте посмотрим на картинку ниже: Название изображенияНачиная с узла А, мы видим, как этот граф может превратиться в дерево. Название изображенияA — это начальный узел, остающийся на уровне 0, затем B и C находятся на уровне 1, а затем D и E — на уровне 2. Это порядок, в котором BFS будет проходить этот граф. Если мы пройдем по этому графу, используя BFS, порядок будет таким: A -> B -> C -> D -> E. Внимательно взглянув на дерево, мы увидим, что между B и C, E и D есть некоторые связи. Это происходит потому, что наш граф содержит циклы. Но если мы хотим пройти его оптимально, мы не должны снова посещать уже посещенные узлы. Таким образом, одним из условий при выборе узла для посещения является его непосещение.

Статья в тему:  Кто придумал искусственный интеллект

Как работает алгоритм

Учитывая, что после того, как мы посетим стартовый узел, мы продолжим посещать всех его соседей, а затем перейдем к следующему «слою» и нам понадобится очередь. Когда мы посещаем узел, мы проверяем его соседей, и если соседи еще не посещались, мы добавляем их в очередь. Затем мы практически просто выбираем следующий узел для посещения из очереди. Еще одна вещь, которую нам нужно сделать, это пометить посещенные узлы, чтобы они больше не посещались. Таким образом, мы посетим все узлы графа только один раз. Посмотрим на псевдокод:

BFS(G, s, target) Пусть Q будет очередью Q.enqueue(s) Пометить s как посещенную, пока (Q не пуста) //Удаление этой вершины из очереди v = Q.dequeue() Если v является целью, возвращаем «найдено» цель» //обработка всех соседей v для всех соседей w для v на графике G, если w не посещается //Сохраняет w в Q для дальнейшего посещения своего соседа Q.enqueue(w) пометить w как посещенный

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

Поиск пути с наименьшими затратами

Название изображения

Давайте изменим наш граф, добавив некоторые затраты на вершины. Теперь мы хотим пройти от A до D по пути с наименьшими затратами. Мы видим, что есть несколько способов перейти от А к Д. Мы могли бы пойти по этому пути, A -> B -> D со стоимостью 20, или мы можем выбрать A -> C -> B -> D с меньшей стоимостью 16. Но есть и другой путь с наименьшей стоимостью из 3, A -> C -> E -> D. Итак, что мы должны сделать, чтобы найти этот путь? Нам нужно изменить способ получения следующего узла для посещения. В классическом алгоритме BFS мы выбираем следующий узел для посещения, используя порядок очереди FIFO (первым пришел, первым ушел). В конце концов мы найдем цель, но не самый дешевый путь. Чтобы добраться до цели по пути с наименьшими затратами, нам нужно внести изменения в способ получения следующего узла для посещения из очереди. Алгоритм, который я собираюсь вам представить, называется «Поиск единой стоимости» и представляет собой слегка модифицированную версию Дейкстры, в которой мы останавливаемся, когда находим пункт назначения. Классический алгоритм Дейкстры продолжает посещать все узлы до тех пор, пока очередь не опустеет, находя минимальную стоимость от начального узла до каждого другого узла в графе. Что отличается от BFS, так это то, что здесь мы должны сохранить новое значение, представляющее общую стоимость от начала до текущего посещенного узла. Очередь не будет упорядочена по правилу FIFO, вместо этого мы упорядочим очередь на основе текущего значения стоимости, отдавая приоритет непосещенным узлам с наименьшей стоимостью на данный момент. Давайте посмотрим на код:

UniformCostSrearch(G, s) s.costSoFar = 0; для всех узлов w в G, кроме s w.costSoFar = Int.maxInt Пусть Q будет приоритетной очередью, упорядоченной по cost_so_far Q.enqueue(s) while (Q не пуста) //Удаление этой вершины из очереди v = Q.dequeue( ) Если v является целью, возвращаем «найдена цель» // обработка всех соседей v для всех соседей w для v в графе G currentCost = dist[v,w] newCost = v.costSoFar + currentCost; Если (newCost < w.costSoFar) w.costSoFar = newCost ; Q.в очереди(ж)

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

currentCost = dist[v,w] newCost = v.costSoFar + currentCost; Если (новая стоимость

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

Статья в тему:  Что такое предикат в искусственном интеллекте

Какая связь между поиском по графу и искусственным интеллектом?

Что ж, давайте подытожим, что такое ИИ. Как я уже говорил, искусственный интеллект определяется как исследование рациональных агентов, где рациональным агентом может быть что угодно, кто принимает решения, например, человек, фирма, машина или программное обеспечение. Он выполняет действие с наилучшим результатом после рассмотрения прошлых и текущих восприятий (перцептивных входных данных агента в данный момент). И что мы получаем с алгоритмом поиска по графу? Мы получаем функцию, программу, агента, который по заданному графу, среде и начальному узлу, учитывая прошлые и текущие восприятия, вычисляет ряд действий для нахождения целевого узла.

Название изображения

Что ж, здесь мы видим, что то, что делает алгоритм поиска по графу, соответствует определению агента ИИ. Итак, у нас есть базовая форма ИИ. Видите ли, ИИ — это не совсем ракетостроение. Определение достаточно широкое, чтобы включать простые алгоритмы поиска по графу. Эти примеры дают нам возможность понять основную концепцию ИИ. Учитывая концепции ИИ, давайте напишем ИИ-агент, который анализирует окружающую среду и вычисляет ряд действий, которые могут помочь нам достичь цели (в основном мы построим алгоритм поиска по графу, но будем использовать терминологию ИИ). Ниже представлена ​​карта Румынии.Допустим, мы в Араде и хотим пройти кратчайшим путем в Бухарест. Мы видим, что есть несколько путей, по которым мы можем пойти. Мы можем отправиться из Арада в Тимишоару, затем в Лугож и так далее, или мы можем выбрать Сибиу, затем Фагарас и сразу отправиться в Бухарест. Но мы не знаем, какой путь имеет наименьшую стоимость.

Статья в тему:  Как искусственный интеллект поможет разработчикам обнаруживать и использовать

Каково определение проблемы?

  • У нас есть начальное состояние: находясь в Араде
  • У нас есть функция action(s). Он возвращает набор возможных действий, когда мы находимся в состоянии. Например: находясь в Араде, мы можем отправиться в Зеринд, Сибиу или Тимишоару.
  • У нас есть результат функции (s,a) -> s’ . Находясь в состоянии s, если мы применим действие a, мы перейдем к s’
  • У нас есть функция проверки цели targettest (s) -> t/f. Он говорит нам, достигли ли мы цели
  • step_cost (s,a,s’) -> стоимость действия. Он сообщает нам стоимость шага от перехода от s к s’ с помощью действия a.
  • стоимость (S1 -> S2 -> … -> Sn) -> n (стоимость пути). Общая стоимость пути

Давайте теперь посмотрим, как это соотносится с нашей задачей поиска целей. Начальное состояние находится в Араде, и функция targettest возвращается, если мы достигаем Бухареста. Все возможные состояния называются пространством состояний. Мы должны исследовать пространство состояний, применяя действия и переходя от состояния к состоянию. Начав с Арада и применив функциональные действия («Арад»), мы получим три возможных действия. Поездка в Зеринг, Тимишоару или Сибиу. Теперь, имея это в виду, мы можем разделить пространство состояний на три части:

  • У нас есть исследованная часть штата (например, пока только Арад)
  • У нас есть граница. Мы называем это самыми дальними из исследованных штатов (Тимишоара, Зеринд и Сибиу).
  • И неизведанный штат: все остальные города
Статья в тему:  В чем разница между искусственным интеллектом и программными вычислениями

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

TreeSearch(G, s) s.costSoFar = 0; для всех узлов w в G, кроме s w.costSoFar = Int.maxInt Пусть граница будет приоритетной очередью, упорядоченной по cost_so_far frontier.enqueue(s) while (граница не пуста) //удаление той вершины из границы, чей сосед будет посещенный сейчас v = frontier.dequeue() Если v является целью, возвращаем «найдена цель» // обработка всех соседей v для всех соседей w для v в графе G currentCost = dist[v,w] newCost = v.costSoFar + текущая стоимость; Если (newCost < w.costSoFar) < w.costSoFar = newCost ; frontier.enqueue(w)

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

Теперь, в зависимости от того, как вы получите новое состояние от границы, вы можете реализовать классический BFS, поиск по единой стоимости или алгоритм A*. Здесь вы могли более четко увидеть различия между этими алгоритмами и лучшим алгоритмом для определения кратчайшего пути из Арада в Бухарест.

Вывод

Конечно, агенты ИИ не возвращаются к простому поиску по графу. У нас есть алгоритмы искусственного интеллекта для распознавания лиц, у нас есть машинное обучение, нейронные сети и алгоритмы, основанные на статистике, где единственным ограничением является математика. Но это не должно пугать, так как основные понятия не так уж сложны для понимания.

голоса
Рейтинг статьи
Статья в тему:  Что такое дерево поиска в искусственном интеллекте на примере ppt
Ссылка на основную публикацию
0
Оставьте комментарий! Напишите, что думаете по поводу статьи.x
Adblock
detector