Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Реферат: Алгоритмы планирования действий

Название: Алгоритмы планирования действий
Раздел: Рефераты по информатике, программированию
Тип: реферат Добавлен 04:27:38 20 января 2011 Похожие работы
Просмотров: 1087 Комментариев: 2 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

Содержание

Введение

Алгоритмы планирования действий

1. Поведение системы

2. Принятие решений в интеллектуальных играх

3. Минимаксный алгоритм

4. Альфа – бета алгоритм

Заключение

Использованы источники

Введение

Тема реферата "Алгоритмы планирования действий" по дисциплине "Проектированиеинтеллектуальных систем".

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

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

Цель работы – рассмотреть алгоритмы планирования действий.

Алгоритмы планирования действий

1. Поведение системы

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

Второе условие вычленяет в этой деятельности еще более узкую область. В поведенческом акте должен принять участие осознаваемый наблюдатель. Его роль может выполнить сам субъект (самонаблюдение) или "мыслимый наблюдатель", который мог бы быть. Другими словами, второе условие требует возможности взгляда со стороны.

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

Классификация типов поведения приведена на рисунке 1.


Рисунок 1 -Классификация типов поведения

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

2. Принятие решений в интеллектуальных играх

В интеллектуальных играх соревнование между участниками заключается в том, что они поочередно принимают решения, не зная, какое следующее решение примет противник. Классический подход, реализуемый мыслящим существом для решения этой задачи, состоит в прогнозировании последующих ходов – своих и ответных ходов противника. Таким образом, может быть построено дерево (или граф) допустимых ходов и возможных игровых позиций, пример которого приведен на рисунке2. На рисунке символами Q обозначены позиции после хода противника, символами R – позиции после хода игрока; вершины графа, у которых стрелки соединены дугой, означают И – вершину, т.е. вершину, для достижения цели в которой, необходимо достичь цели во всех вершинах нижнего уровня; вершины графа, у которых стрелки не соединены дугой, означают ИЛИ – вершину, т.е. вершину, для достижения цели в которой, необходимо достичь цель хотя бы в одной вершине нижнего уровня.

В И – ИЛИ дереве, показанном на рисунке2, вершины соответствуют позициям, а дуги – возможным ходам. Уровни позиций игрока чередуются в дереве с уровнями позиций противника. Для того, чтобы выиграть в позиции P, нужно найти ход, переводящий Р в выигранную позицию Qi . Таким образом, игрок выигрывает в позиции Р, если он выигрывает в Q1 , или в Q2, или Q3 , или … Следовательно, Р – это ИЛИ – вершина. Для любого i позиция Qi – это позиция противника, поэтому если в этой позиции выигрывает игрок, то он выигрывает и после каждого варианта хода противника. Другими словами, игрок выигрывает в Qi , если он выигрывает во всех позициях Ri1 и Ri2 и … Таким образом, все позиции противника – это И – вершины.


Рисунок 2 - Пример дерева при поиске хода

Целевые вершины – это позиции, выигранные согласно правилам игры, например позиции, в которых король противника получает мат. Позициям проигранным соответствуют задачи, которые не имеют решения. Для того, чтобы решить игровую задачу, необходимо построить решающее дерево, гарантирующее победу игрока независимо от ответов противника. Такое дерево задает полную стратегию достижения выигрыша: для каждого возможного продолжения, выбранного противником, в дереве стратегии есть ответный ход, приводящий к победе. Например, для игры в "тик-так-ту" может быть построено полное дерево ходов, которое показано на рисунке3. Из-за симметрии игрового поля только два ответных хода белых являются различными.

Если необходимо найти какое-нибудь решение задачи, то организуется простейший поиск в И – ИЛИ дереве, который заключается в систематическом и полном просмотре дерева, не руководствуясь при этом какими – либо эвристиками. Для сложных задач подобные процедуры неэффективны из–за большой комбинаторной сложности пространства поиска. Например, для игры в шахматы пространство поиска оценивается в 10120 позиций! Поэтому необходимы эвристические алгоритмы управления поиском. Основная идея этих алгоритмов – просмотр только части дерева ходов.

3. Минимаксный алгоритм

Существует стандартный метод поиска, используемый в игровых программах, основанный на минимаксном принципе. Дерево ходов просматривается по одной из ветвей до максимальной глубины (обычно несколько ходов) и оценивается позиция. Очень многое зависит от оценочной функции, которая для большинства игр, является приближенной эвристической оценкой шансов на выигрыш одного из участников игры. Поскольку один из участников игры стремится к высоким оценкам, а другой - к низким, то им даются имена МАКС и МИН соответственно. МАКС всегда выбирает ход с максимальной оценкой; в противоположность ему МИН всегда выбирает ход с минимальной оценкой. Пользуясь этим минимаксным принципом и зная значения оценок для всех вершин подножия дерева поиска, можно определить оценки всех вышерасположенных вершин дерева. Оценки вершин подножия дерева делаются с помощью некоторой оценочной функции и называются статическими. Затем, двигаясь по дереву снизу – вверх, определяется оценка (динамическая) внутренних вершин.

На рисунке4 показан принцип оценивания вершин и выделен жирными линиями основной вариант игры.

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

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


Рисунок 3 - Полное дерево ходов в игре "тик-так-ту"

Рисунок 4 - Статические и минимаксные оценки вершин

4. Альфа – бета алгоритм

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

- начальная позиция "а";

- переход к "b";

- переход к "d";

- выбор максимальной из оценок преемников позиции "d", получено V(d)=4;

- возврат к "b" и переход к "e";

- рассмотрение первого преемника позиции "e" с оценкой 5. В этот момент МАКС обнаруживает, что ему гарантирована в позиции "e" оценка, не меньшая, чем 5, независимо от оценок других (возможно, более предпочтительных) вариантов хода. Этого вполне достаточно для того, чтобы МИН, даже не зная точной оценки позиции "e", понял, что в позиции "b" ход в "е" хуже, чем ход в "d".

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

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


Рисунок 5 - Результат применения альфа – бета алгоритма

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

"Достаточно хорошую" рабочую оценку V(P, Альфа, Бета) позиции Р можно определить как любое значение, удовлетворяющее следующим ограничениям:

- не более Альфа, если оценка позиции Р меньше либо равна Альфа;

- не менее Бета, если оценка позиции Р больше или равна Бета;

- точно равна оценке V(P), если оценка позиции Р находится между значениями Альфа и Бета.

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


Заключение

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

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


Использованы источники

1. Уоссермен Ф., Нейрокомпьютерная техника, - М.,Мир, 1992.

2. Горбань А.Н. Обучение нейронных сетей. - М.: ПараГраф, 1990

3. Горбань А.Н., Россиев Д.А. Нейронные сети на персональном компьютере. - Новосибирск: Наука, 1996

4. Gilev S.E., Gorban A.N., Mirkes E.M. Several methods for accelerating the training process of neural networks in pattern recognition // Adv. Modelling & Analysis, A. AMSE Press. – 1992. – Vol.12, N4. – P.29-53

5. С. Короткий. Нейронные сети: алгоритм обратного распространения.

6. С. Короткий, Нейронные сети: обучение без учителя. Artificial Neural Networks: Concepts and Theory, IEEE Computer Society Press, 1992.

7. Заенцев И. В. Нейронные сети: основные модели./Учебное пособие к курсу "Нейронные сети" для студентов 5 курса магистратуры к. электроники физического ф-та Воронежского Государственного университета – e-mail: ivz@ivz.vrn.ru

8. Лорьер Ж.Л. Системы искусственного интеллекта. – М.: Мир, 1991. – 568 с.

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений08:06:23 19 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
09:27:51 29 ноября 2015

Работы, похожие на Реферат: Алгоритмы планирования действий
Психологический словарь
Борис Гурьевич Мещеряков, Владимир Петрович Зинченко Большой психологический словарь Оглавление Предисловие Персоналии Список авторов Список ...
Алгоритмы поиска чувствительны к изменениям в содержании долговременной памяти, так что поступление новой информации может оказывать влияние на доступность старой.
Распространенным при изучении нейронных основ памяти является поиск структур, нейроны которых обнаруживают пластические изменения при научении.
Раздел: Рефераты по психологии
Тип: книга Просмотров: 4614 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Матричные антагонистические игры с нулевой суммой в чистых стратегиях
... ситуации приводят к различным видам игр. Игры различаются по целому ряду признаков: по количеству участвующих в них игроков, по количеству возможных ...
Таким образом, в некоторых играх игрок не в состоянии определить, какой из нескольких возможных ходов был фактически сделан, будь то ход одного из его противников или случайный ход ...
Прямой противоположностью играм такого типа являются игры с постоянной разностью, в которых игроки и выигрывают, и проигрывают одновременно, так что им выгодно действовать сообща.
Раздел: Рефераты по математике
Тип: курсовая работа Просмотров: 8226 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Экспертные системы. Классификация экспертных систем. Разработка ...
db_dan(""°ў аЁйҐбвў° ЇаҐ$ЇаЁЁ= вҐ"Ґ°",7605,"ГЁ" db_dan("Ѭ*Ѭ"",1165,""°ў аЁйҐбвў° ЇаҐ$ЇаЁЁ= вҐ"Ґ°" db_dan("ѬѬ"*",7094,"Ѭ*Ѭ"" db_dan("-"*",8205,"ѬѬ ...
К числу таких стратегий относятся поиск в глубину, поиск в ширину, разбиение на подзадачи и альфа- бета алгоритм.
Блок- схема алгоритма показана на рис.6. Вершины и указатели, построенные в процессе перебора, образуют поддерево всего неявно определенного дерева пространства состояний.
Раздел: Рефераты по информатике, программированию
Тип: реферат Просмотров: 34073 Комментариев: 7 Похожие работы
Оценило: 10 человек Средний балл: 4.5 Оценка: 5     Скачать
Разработка алгоритмов контроля и диагностики системы управления ...
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ "ХАРКІВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ" Факультет І Кафедра "Системи та процеси ...
Кроме гамма-излучения и потока нейтронов выделяются ионизирующие излучения в виде альфа- и бета-частиц, имеющих малую длину свободного пробега, вследствие чего их воздействием на ...
Так для диагностики и контроля отказов чувствительных элементов ГИВУС, можно использовать фильтр Калмана, нейронные сети и элементы искусственного интеллекта.
Раздел: Рефераты по авиации и космонавтике
Тип: реферат Просмотров: 3977 Комментариев: 2 Похожие работы
Оценило: 2 человек Средний балл: 3.5 Оценка: неизвестно     Скачать
Теория принятия решений
Министерство образования и науки Украины Запорожская государственная инженерная академия Теория принятия решений Учебно-методическое пособие Ю.О ...
ЛПР, управляющий своими стратегиями (ходами) А1, А2, ., Аn, и его противник, управляющий стратегиями (ходами) В1, В2, ., Вn в данной ситуации называются игроками.
Цель игры для первого игрока (ЛПР) - побольше выиграть, а для второго игрока - поменьше проиграть.
Раздел: Рефераты по менеджменту
Тип: учебное пособие Просмотров: 6584 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Интуитивное понятие алгоритма и его свойств
Алгоритм отностится к основным понятиям математики, а поэтому не имеет определения. Часто это понятие формулируют так:"точное предписание о порядке ...
Выигрышная стратегия - это набор правил, следуя которым один из игроков обязательно выигрывает.
Двоичное дерево состоит из вершин и дуг, соединяющих вершины.
Раздел: Рефераты по математике
Тип: реферат Просмотров: 1392 Комментариев: 3 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Задача остовных деревьев в k-связном графе
... Молдавский Государственный Университет Кафедра Информатики и Дискретной Оптимизации Дипломная работа: "Задача остовных деревьев в k-связном графе"
Если бы вершины u и v принадлежали разным компонентам графа G, то граф G+uv не имел бы циклов,что потиворечит утверждению 5). Итак, G связен и потому является деревом.
Вывод Целью моей дипломной работы была исследовать задачу на построение разреза в графе по вершине z. Был разработан алгоритм, который строит разрез по заданому графу.
Раздел: Рефераты по математике
Тип: реферат Просмотров: 1728 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Непрерывные генетические алгоритмы
Курсовая работа По дисциплине: "Теория систем и системный анализ" Выполнила тудентка 3 курса 1 группы Специальности ПИУ Антипина Г.С. Государственный ...
Наиболее популярными и проверенными из этих технологий являются нейронные сети и генетические алгоритмы.
... граница, полученная для всех просмотренных до настоящего времени вариантах; любая вершина дерева поиска, нижняя граница которой больше m, может быть исключена из дальнейшего ...
Раздел: Рефераты по математике
Тип: курсовая работа Просмотров: 1568 Комментариев: 3 Похожие работы
Оценило: 1 человек Средний балл: 5 Оценка: неизвестно     Скачать
Игровые моменты и опорные конспекты на уроках истории
Введение В настоящее время практически каждый учитель истории применяет в своей деятельности нетрадиционные формы обучения школьников. На наш взгляд ...
Динамика игровой интриги строится на соперничестве игроков, но в отличие от военного столкновения, где решающим оказывается умение бойца прикрывать себя и своего товарища щитом и в ...
Начнешь снизу, со шкафа АЛЬФЫ, затем перейдешь к шкафу БЕТА, затем - к третьему, его зовут ГАММА, далее - ДЕЛЬТА, ИПСИЛОН, ДЗЕТА И ЭТА.
Раздел: Рефераты по коммуникации и связи
Тип: реферат Просмотров: 10373 Комментариев: 4 Похожие работы
Оценило: 12 человек Средний балл: 4.8 Оценка: 5     Скачать
Экзаменационные билеты по информатике 2000/2001 учебный год
Экзаменационные билеты по информатике. 2000/2001 учебный год. Билет № 1 1. Магистрально-модульный принцип построения компьютера. 2. Технология ...
Алгоритм выигрыша для первого игрока имеет следующий вид:
Человек, пользующийся данным алгоритмом, всегда будет выигрывать в этой игре.
Раздел: Рефераты по информатике, программированию
Тип: шпаргалка Просмотров: 4677 Комментариев: 4 Похожие работы
Оценило: 1 человек Средний балл: 5 Оценка: неизвестно     Скачать

Все работы, похожие на Реферат: Алгоритмы планирования действий (4563)

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

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



Результаты(151452)
Комментарии (1844)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru