Два важных алгоритма объясняются наглядно и просто вместе с современными приложениями.
В искусственном интеллекте (ИИ) существует множество алгоритмов поиска, но некоторые из наиболее распространенных — это восхождение на вершину, генетические алгоритмы и оптимизация роя частиц. Алгоритм поиска — это любой алгоритм, решающий задачу поиска пути из одного места в другое. Например, рассмотрим задачу поиска маршрута на карте. Можно использовать алгоритм поиска грубой силы, перебирая все возможные пути, пока не будет найден тот, который ведет к месту назначения. Однако существуют более эффективные алгоритмы поиска, учитывающие такие факторы, как рельеф местности и наличие препятствий на пути.
Эта проблема может быть устранена с помощью алгоритма поиска, начиная с текущего местоположения, выполняя все возможные шаги, которые можно предпринять оттуда, а затем возвращаясь к исходной точке. После каждого из этих шагов алгоритм поиска будет рекурсивно вызывать себя, чтобы определить наиболее эффективный путь из нового местоположения. Через какое-то время рекурсивные вызовы придут в точку, когда больше не будет никаких действий, которые можно предпринять; когда это происходит, алгоритм поиска повторяет свои шаги через свои прошлые решения, чтобы найти маршрут с наименьшей стоимостью (или кратчайшим расстоянием).
Историю поискового алгоритма в ИИ можно проследить до первых дней развития искусственного интеллекта. Артур Сэмюэл создал один из первых поисковых алгоритмов в 1950-х и 1960-х годах, который он использовал для игры в шашки. Этот метод был построен на эвристических функциях, которые оценивали ценность каждого хода и направляли поиск на ходы, которые с большей вероятностью приведут к выигрышу. Он был эффективен в решении этой задачи, потому что использовал методическую стратегию для сортировки всех возможных ходов и выбора наилучшего. Используемый метод представлял собой поиск в глубину.
Алгоритм поиска в глубину
Алгоритм поиска в глубину в ИИ — это алгоритм, который сначала исследует самые глубокие узлы дерева. Он начинается с корня (выбирая некоторый узел в качестве корня в случае графа) и исследует как можно дальше каждую ветвь, прежде чем вернуться. В качестве иллюстрации:
— Старт в начальном узле.
— Разверните все узлы на этом уровне.
— Перейдите на следующий уровень и разверните все эти узлы.
— Повторяйте этот процесс, пока не дойдете до конечного узла.
Хотя он может найти целевое состояние, если он находится близко к корневому узлу, он может быть восприимчив к увязанию в бесконечном цикле и потенциально может полностью пропустить целевое состояние, если он разветвляется слишком далеко от корневого узла.
Применительно к реальному миру подход поиска в глубину имеет множество применений. Одно из применений этого метода - в компьютерных сетях, где его можно использовать для определения пути, который является кратчайшим расстоянием между двумя узлами. Другой иллюстрацией этого может служить процесс поиска конкретной информации путем поиска в базе данных.
Алгоритм в ширину
Они предназначены для поиска кратчайшего пути от начального узла к конечному узлу путем расширения всех узлов на каждом уровне перед переходом на следующий уровень. Чтобы расширить дальше, имеет место следующая последовательность. Сначала алгоритм проверяет корневой узел, чтобы определить, является ли он целевым состоянием. Если это не так, то алгоритм расширяет корневой узел, создавая его дочерние узлы. Затем он проверяет эти новые узлы, чтобы увидеть, являются ли они целевыми состояниями. Процесс продолжается до тех пор, пока не произойдет одно из двух: (1) будет достигнуто целевое состояние или (2) все возможные пути будут исчерпаны, но целевое состояние не будет найдено.
Его подход заключается в поиске кратчайшего пути к целевому состоянию, поскольку он равномерно расширяется наружу от корневого узла, пока не достигнет решения. В контексте задачи с лабиринтом, показанной здесь, показано, как ее можно оптимизировать для таких задач. И наоборот, потенциально он может занимать больше памяти, чем поиск в глубину, поскольку каждый уровень должен быть расширен перед переходом к расширению на следующем уровне (и не так быстро, как поиск в глубину в некоторых случаях).
Одним из наиболее типичных реальных случаев использования метода поиска в ширину является определение пути от начальной точки до одного или нескольких целевых местоположений. Например, предположим, что вы пытаетесь ориентироваться в неизвестном городе. Технику обхода в ширину можно использовать для изучения всех возможных маршрутов через город и определения наиболее быстрого и простого маршрута (при условии, что вы отправились в желаемый пункт назначения). Точно так же, если вы хотите организовать несколько полок в своей кладовой, использование алгоритма поиска в ширину может помочь предложить оптимальные варианты хранения на основе того, что уже доступно в вашем пространстве.
Прощальные мысли
Если у вас есть какие-либо рекомендации для этого поста или предложения по расширению темы, я был бы признателен, если бы вы их услышали. Кроме того, пожалуйста, рассмотрите возможность подписаться на мою рассылку.
Я создал следующий список на Medium, который вы можете посетить, чтобы ознакомиться со всеми другими сообщениями в этой серии «Руководство по искусственному интеллекту».
Если вам нравится читать такие истории и вы хотите поддержать меня как писателя, подумайте о том, чтобы зарегистрироваться, чтобы стать участником Medium и получить неограниченный доступ ко всем историям на Medium: ***Подпишитесь на Medium***.
Кроме того, рекомендуем прочитать следующие статьи из Руководства по искусственному интеллекту:
Использованная литература:
- OpenAI помог в разработке этого визуального
Анил Тильбе
