Теормин (1156628), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Ключевая идеяэтой эвристики такова: поиск различий между тем, что дано в поставленной задаче, и тем, что надо получить; последовательное устранение найденных различий с помощью подходящих средств–операций.Работая в соответствии с этой эвристикой, GPS применяла несколько схем редукции задач, и наоснове выявления различий между объектами задачи и применения уменьшающих эти различияоператоров рекурсивно формировала систему (дерево) задач-целей (подзадач).7A* алгоритм:Предположим, что эвристическая оценочная функция Est(V) построена таким образом, чтобы оцениватьстоимость оптимального решающего пути, идущего из начальной вершины к одной из целевой вершин, приусловии, что этот путь проходит через вершину V. Тогда значение оценочной функции можно представить ввиде суммы двух слагаемых:Est(V) = g(V) + h(V)(*)где g(V) – оценка оптимального пути от начальной вершины до вершины V,а h(V) – оценка оптимального пути от вершины V до целевой вершины.Вариант алгоритма эвристического поиска, применяемого для поиска оптимального решающегопути и использующего при этом оценочную функцию указанного выше вида (*), известен в литературе как Аалгоритм.

Были доказаны важные свойства этого алгоритма, прежде всего, утверждение о егодопустимости.Алгоритм перебора называют допустимым (или состоятельным), если для произвольного графаон всегда заканчивает свою работу построением оптимального пути к цели, при условии, что такой путьсуществует.Пусть h*(V) – стоимость оптимального пути из произвольной вершины V в целевую вершину. Вернаследующая теорема о допустимости А-алгоритма:А-алгоритм, использующий некоторую эвристическую функцию вида (*), гдеg(V) – стоимость пути от начальной вершины до вершины V в дереве перебора, аh(V) – эвристическая оценка оптимального пути из вершины V в целевую вершину,является допустимым, еслиh(V)  h*(V) для всех вершин V пространства состояний.А-алгоритм эвристического поиска, применяющий функцию h(V), удовлетворяющую этому условию,получил название А*-алгоритма.Практическое значение этой теоремы в том, что для допустимости А-алгоритма достаточно найтикакую-либо нижнюю грань функции h*(V) и использовать ее в качестве h(V) – тогда оптимальностьнайденного алгоритмом решения будет гарантирована.Если взять тривиальную нижнюю грань, т.е.

установить h(V) = 0 для всех вершин пространствасостояний, то допустимость будет обеспечена. Однако этот случай соответствует полному отсутствию какойнибудь эвристической информации о задаче, и оценочная функция Est не имеет никакой эвристическойсилы, т.е. не сокращает возникающий перебор. А*-алгоритм ведет себя при этом аналогично поиску вширь.Точнее, приEst(V) = g(V) (где g(V) – стоимость пути от начальной вершины до вершины V ), мыполучаем алгоритм, известный как алгоритм равных цен (или Алгоритм Дейкстры). Алгоритм равныхцен представляет собой более общий вариант метода перебора в ширину, при котором вершиныраскрываются в порядке возрастания стоимости g(V) , т.е.

в первую очередь раскрывается вершина изсписка нераскрытых вершин, для которой величина g имеет наименьшее значение.Обе предложенные для игры в восемь эвристические функции Est1(V) и Est2(V) удовлетворяютусловию допустимости А*-алгоритма. Первое их слагаемое d(V) есть стоимость пути к вершине V пристоимости всех дуг с(VA, VB) = 1. Функции отличаются лишь вторым слагаемым, и можно показать, чтозначение второй функции всегда (т.е. для всех состояний), больше значения первой функции:Est1(V) Est2(V) , что равнозначно k (V)  s (V) .Из последнего неравенства следует, что условие допустимости достаточно доказать только длявторой функции Est2. Справедливость нужного условия s(V)  h*(V) следует из такого соображения. Если быфишки не мешали друг другу и могли двигаться до «своего» места по кратчайшему пути, как если бы другихфишек на квадрате не было, то сумма длин таких путей для всех фишек была бы в точности равна значениюs(V) . На самом же деле фишки редко когда могут двигаться по кратчайшей траектории из-за того, что на нейрасположены другие фишки, поэтому длина (стоимость) оптимального решения h*(V) будет не меньше s(V).Минимаксный принцип:* ИЛИ-вершине дерева игры приписывается оценка, равная максимуму оценок ее дочерних вершин;* И-вершине игрового дерева приписывается оценка, равная минимуму оценок ее дочерних вершин.Минимаксный принцип положен в основу минимаксной процедуры, предназначенной для определениянаилучшего (более точно, достаточно хорошего) хода игрока исходя из заданной конфигурации игры S прификсированной глубине поиска N в игровом дереве.

Предполагается, что игрок ПЛЮС ходит первым (т.е.начальная вершина есть ИЛИ-вершина). Основные этапы этой процедуры таковы:1. Дерево игры строится (просматривается) одним из известных алгоритмов перебора (как правило,алгоритмом поиска вглубь) от исходной позиции S до глубины N;2. Все концевые вершины полученного дерева, т.е. вершины, находящиеся на глубине N, оцениваются спомощью статической оценочной функции;83.

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

Среди вершин, дочерних к начальной, выбирается вершина с наибольшей оценкой: ход, который к нейведет, и есть искомый наилучший ход в игровой конфигурации S.Правила вычисления оценок вершин дерева игры, в том числе предварительных оценок промежуточныхвершин, которые для удобства будем называть альфа- и бета-величинами: концевая вершина игрового дерева оценивается статической оценочной функцией сразу, как только онапостроена; промежуточная вершина предварительно оценивается по минимаксному принципу, как только сталаизвестна оценка хотя бы одной из ее дочерних вершин; каждая предварительная оценкапересчитывается (уточняется) всякий раз, когда получена оценка еще одной дочерней вершины; предварительная оценка ИЛИ-вершины (альфа-величина) полагается равной наибольшей извычисленных к текущему моменту оценок ее дочерних вершин; предварительная оценка И-вершины (бета-величина) полагается равной наименьшей из вычисленных ктекущему моменту оценок ее дочерних вершин.Укажем очевидное следствие этих правил вычисления: альфа-величины не могут уменьшаться, абета-величины не могут увеличиваться.Сформулируем теперь правила прерывания перебора, или отсечения ветвей игрового дерева:.A) Перебор можно прервать ниже любой И-вершины, бета-величина которой не больше, чем альфавеличина одной из предшествующих ей ИЛИ-вершин (включая корневую вершину дерева);B) Перебор можно прервать ниже любой ИЛИ-вершины, альфа-величина которой не меньше, чем бетавеличина одной из предшествующих ей И-вершин.При этом в случае А говорят, что имеет место альфа-отсечение, поскольку отсекаются ветви дерева,начиная с ИЛИ-вершин, которым приписана альфа-величина, а в случае В  бета-отсечение, посколькуотсекаются ветви, начинающиеся с бета-величин).9Основные школы психологии мышленияАссоциативная психология (XVIII-XIX вв.) – предшественники: Ньютон, Локк.(мышление как ассоциации представлений)(Общее в психологических теориях того времени: психическое = осознанное, психология = психологияиндивида, интроспекция, т.е.

самонаблюдение – как главный метод исследования)Гартли (Англия, XVIII в.): впервые ассоциация трактуется как универсальное понятие психологии,объясняющее всю психическую деятельность человека.- механистический материализм, психофизиологический параллелизм: вибрации в периферическойнервной системе → аналогичные вибрации в головном мозгу – база идей;- детерминанты ассоциаций: смежность по времени, частота повторений;- замечено, что если ощущения A, B, C ассоциируются с идеями a, b, c, то при появлении A могут возникнутьb, c;- попытка объяснения бессознательного (головной мозг – осознанное, идеи; вне – ощущения);- мотивация: удовольствие, страдание.Беркли, Юм (Англия, XVIII в.): ощущения – единственный объект, другой познаваемой реальности нет.- из ассоциаций удаляется физический субстрат;- расширяется набор ассоциативных связей: рассматриваются ассоциации по сходству, по контрасту;- ассоциации отрываются от реальных объектов.Гербарт (Германия, XIX в.): представление – "первичное единство, возникающее в виде акции души,стремящейся (в противовес внешним воздействиям) к самосохранению"; представления следуют друг задругом вне зависимости от чего-либо внешнего;апперцептивная масса – представления, силой которых в сознании (фокусе внимания) удерживаютсянекоторые представления;Недостатки Ассоциативной психологииОписательный характер.Не вскрыты внутренние механизмы динамики потока ассоциаций; не объяснена целенаправленностьмыслительной (интеллектуальной) деятельности человека, ее связь с предметной деятельностью.В то же время, изучены некоторые аспекты ассоциаций – явлений, действительно играющих заметную рольв психической деятельности человека.

Понятие ассоциация использовалось в рамках других школпсихологии.Вюрцбургская школа психологии мышления (Германия, XIX- XX вв.).(мышление как действие)Переход к экспериментальному интроспективному изучению мышления (комментируются психическиефеномены, испытуемые – психологи). Замысел – использовать интроспективный метод для описания вэкспериментальных условиях мыслительных процессов.Существенное достижение – изменение взглядов на мышление:мышление – решение задач;решаемые задачи – важны для человека;необходим лабораторно-экспериментальный анализ мышления.Ключевые понятия: задача, представление цели, детерминирующая тенденция (придает мышлениюцеленаправленный характер), установка – регулятор мыслительной деятельности у принявшего задачу,определяет ход мышления, регулирует (в соответствии с задачей) его содержание.Экспериментальные исследования:Опыты Марбе (1901 г.): сравнить веса предметов и прокомментировать, как выбирали.Опыты Уатта и Мессера (1905 г.): решить арифметическую/логическую задачу и проследить путь, которыйпривел к решению; в ассоциативном эксперименте проследить, какие психические процессы связываютстимул (исходное понятие) и реакцию (понятие, связанное с ним ассоциацией).Обобщение результатов:чувственно-образные феномены (прослеживаемые с помощью самонаблюдения) и ассоциации неопределяют итоговую реакцию, мышление не сводится к ассоциациям;в мышлении есть другое содержание, у мышления есть другие детерминанты;основные факторы мышления находятся вне "непосредственно данного" (ощущений, интроспекции),мышление управляется не ассоциативными связями, а тем, что задано;контекст мышления – задача (Уатт), детерминирующая тенденция (Ах), установка.Концепция Зельца (XX вв.).(мышление как функционирование интеллектуальных операций)10Серьезный анализ начальных этапов решения задачи (проблемный комплекс); введение в рассмотрениеинтеллектуальных операций: антиципация (выявление отношений: известное ↔ искомое), дополнениекомплекса, абстракция, репродукция сходства.Бихевиоризм (США, XIX- XX вв.).(мышление как поведение)Главный момент концепции: предметом психологии должно стать поведение, только тогда возможнообъективное исследование психической деятельности.И.П.Павлов: "Деловой американский ум, обращаясь к практике жизни, нашел, что важнее точно знатьвнешнее поведение человека, чем гадать об его внутреннем состоянии со всеми его комбинациями иколебаниями".Торндайк:- опыты с проблемными ящиками (дверь открывается изнутри, "испытуемые"– мыши, крысы);- мышление можно изучать без обращения к идеям и другим явлениям сознания;- ассоциативные связи (которые можно объективно изучать) – связи между движениями и ситуациями,ситуациями и реакциями (на эти ситуации);- ассоциации могут возникать в результате "слепого поиска" решения, выбора удачного варианта, а затемукрепления и упрочения ассоциативных связей, т.е.

Характеристики

Список файлов ответов (шпаргалок)