рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Слепой перебор.

Слепой перебор. - раздел Компьютеры, Искусственный интеллект Двумя Основными Разновидностями Слепого Перебора Являются Алгоритмы Перебора ...

Двумя основными разновидностями слепого перебора являются алгоритмы перебора вширь и перебора вглубь.

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

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

Шаг 1. Поместить начальную вершину в список нераскрытых вершин Open.

Шаг 2. Если список Open пуст, то окончание алгоритма и выдача сообщения о неудаче поиска, в противном случае перейти к следующему шагу.

Шаг 3. Выбрать первую вершину из списка Open (назовем ее Current) и перенести ее в список Closed.

Шаг 4. Раскрыть вершину Current, образовав все ее дочерние вершины. Если дочерних вершин нет, то перейти к шагу 2, иначе поместить все дочерние вершины (в любом порядке) в конец списка Open и построить указатели, ведущие от этих вершин к родительской вершине Current.

Шаг 5. Проверить , нет ли среди дочерних вершин целевых. Если есть хотя бы одна целевая вершина, то окончание алгоритма и выдача решения задачи, получающегося просмотром указателей от найденной целевой вершины к начальной. В противном случае перейти к шагу 2.

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

На рис.13 приведено дерево, полученное в результате применения алгоритма поиска вширь к некоторой начальной конфигурации игры в восемь, причем алгоритм работал только до глубины 4. В вершинах дерева помещены соответствующие описания состояний. Эти вершины занумерованы в том порядке, в котором они были раскрыты.

Глубину вершины в дереве можно определить следующим образом:

  • глубина корня дерева равна нулю;
  • глубина каждой некорневой вершины равна глубине ее родительской вершины плюс единица.

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

Основные шаги алгоритма ограниченного перебора вглубь таковы:

Шаг 1. Поместить начальную вершину в список Open.

Шаг 2. Если список Open пуст, то окончание алгоритма и выдача сообщения о неудаче поиска, в противном случае перейти к следующему шагу.

Шаг 3. Выбрать первую вершину из списка Open (назовем ее Current) и перенести ее в список Closed.

Шаг 4. Если глубина вершины Current равна граничной глубине, то перейти к шагу 2, в ином случае перейти к следующему шагу.

Шаг 5. Раскрыть вершину Current, построив все ее дочерние вершины. Если дочерних вершин нет, то перейти к шагу 2, иначе поместить все дочерние вершины (в произвольном порядке) в начало списка Open и построить указатели, ведущие от этих вершин к родительской вершине Current.

Шаг 6. Если среди дочерних есть хотя бы одна целевая вершина, то окончание алгоритма и выдача решения задачи, получающегося просмотром указателей от найденной целевой вершины к начальной. В противном случае перейти к шагу 2.

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

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

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

Если перебор осуществляется на графах, а не на деревьях, необходимо внести некоторые очевидные изменения в указанные алгоритмы. В алгоритме полного перебора следует дополнительно проверять, не находится ли уже вновь построенная вершина в списках Open и Closed по той причине, что она уже строилась раньше в результате раскрытия какой-то вершины. Если это так, то такую вершину не нужно снова помещать в список Open. В алгоритме же ограниченного поиска вглубь кроме рассмотренного изменения может оказаться необходимым пересчет глубины порождающейся вершины, уже имеющейся либо в списке Open, либо в списке Closed.

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

В целом алгоритмы слепого перебора являются неэффективными методами поиска решения, приводящими в случае нетривиальных задач к проблеме комбинаторной сложности. Действительно, если L − длина решающего пути, а B – количество ветвей (дочерних вершин) у каждой вершины, то для нахождения решения надо исследовать BL путей, ведущих из начальной вершины. Величина эта растет экспоненциально с ростом длины решающего пути, что приводит к ситуации, называемой комбинаторным взрывом.

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

– Конец работы –

Эта тема принадлежит разделу:

Искусственный интеллект

На сайте allrefs.net читайте: "Цель преподавания дисциплины искусственный интеллект"

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

Что будем делать с полученным материалом:

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

Все темы данного раздела:

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

Терминология
Термин интеллект (intelligence) происходит от латинского intellectus — что означает ум, рассудок, разум; мыслительные способности человека. Соответственно искусственный интеллект (artificial intell

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

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

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

Активационные функции
Сигнал NET далее, как правило, преобразуется активационной функцией F и дает выходной нейронный сигнал OUT. Активационная функция может быть обычной линейной функцией OUT =K(

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

Неформальные (семантические) модели представления знаний.
1. Сетевые модели (Семантические сети). В основе моделей этого типа лежит конструкция, названная семантической сетью. Сетевые модели формально можно задать в виде H

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

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

Основной этап
1. "Накачка" поля знаний: а) в зависимости от предметной области выбор способа интервьюирования; б) протоколирование мыслей вслух или запись на магнитофон рассуждении эксперта (аналитик п

Способы формализации задач. Представление задач в пространстве состояний
Типичным представителем класса задач, для которых подходит представление (формализация) в пространстве состояний, является головоломка, известная как игра в пятнадцать. В ней используется пятнадцат

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

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

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

Альфа-бета процедура
Минимаксная процедура организована таким образом, что процесс построения частичного дерева игры отделен от процесса оценивания вершин. Такое разделение приводит к тому, что в целом минимаксная проц

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

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

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

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

Работа генетического алгоритма
Представим себе искусственный мир, населенный множеством существ (особей), причем каждое существо — это некоторое решение нашей задачи. Будем считать особь тем более приспособленной, чем лучше

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

Понятие образа
Образ, класс — классификационная группировка в системе классификации, объединяющая (выделяющая) определенную группу объектов по некоторому признаку. Образное восприятие мира — одно из зага

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

Гипотеза компактности
Если предположить, что в процессе обучения пространство признаков формируется исходя из задуманной классификации, то тогда можно надеяться, что задание пространства признаков само по себе задает св

Обучение и самообучение. Адаптация и обучение
Все картинки, представленные на Рис. 1, характеризуют задачу обучения. В каждой из этих задач задается несколько примеров (обучающая последовательность) правильно решенных задач. Если бы удалось по

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги