Всё сдал! - помощь студентам онлайн Всё сдал! - помощь студентам онлайн

Реальная база готовых
студенческих работ

pencil
Узнай стоимость на индивидуальную работу!
icon Цены в 2-3 раза ниже
icon Мы работаем
7 дней в неделю
icon Только проверенные эксперты

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

Тип Реферат
Предмет Информатика и программирование
Просмотров
456
Скачиваний
891
Размер файла
61 б
Поделиться

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

Содержание

Введение

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

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 с.


Нет нужной работы в каталоге?

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

Цены ниже, чем в агентствах и у конкурентов

Вы работаете с экспертами напрямую. Поэтому стоимость работ приятно вас удивит

Бесплатные доработки и консультации

Исполнитель внесет нужные правки в работу по вашему требованию без доплат. Корректировки в максимально короткие сроки

Гарантируем возврат

Если работа вас не устроит – мы вернем 100% суммы заказа

Техподдержка 7 дней в неделю

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

Строгий отбор экспертов

К работе допускаются только проверенные специалисты с высшим образованием. Проверяем диплом на оценки «хорошо» и «отлично»

1 000 +
Новых работ ежедневно
computer

Требуются доработки?
Они включены в стоимость работы

Работы выполняют эксперты в своём деле. Они ценят свою репутацию, поэтому результат выполненной работы гарантирован

avatar
Экономика
Маркетинг
Информатика
icon
113201
рейтинг
icon
2764
работ сдано
icon
1252
отзывов
avatar
Математика
Физика
История
icon
107621
рейтинг
icon
5381
работ сдано
icon
2415
отзывов
avatar
Химия
Экономика
Биология
icon
75673
рейтинг
icon
1881
работ сдано
icon
1192
отзывов
avatar
Высшая математика
Информатика
Геодезия
icon
62710
рейтинг
icon
1046
работ сдано
icon
598
отзывов
Отзывы студентов о нашей работе
49 111 оценок star star star star star
среднее 4.9 из 5
Спбгуптд
спасибо большое!!! работа выполнена досрочно, антиплагиат проходит на 50%как и требовалось!!!
star star star star star
КФУ
Работа выполнена очень быстро и в соответствии со всеми критериями. Огромная благодарность.
star star star star star
ЗабГу
Советую исполнителя, ответственный и общительный, побольше бы таких людей.Спасибо большое!!!!
star star star star star

Последние размещённые задания

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

презентация с докладом

Презентация, Гражданское право

Срок сдачи к 8 февр.

2 минуты назад

Лабораторная работа

Лабораторная, техническая механика

Срок сдачи к 9 февр.

3 минуты назад

Сделать практическую работу, вариант 2

Контрольная, Практикум по информационной безопасности, информационная безопасность

Срок сдачи к 14 февр.

4 минуты назад

задача

Решение задач, системный анализ

Срок сдачи к 12 февр.

4 минуты назад
5 минут назад

Решение задач по экономике предприятия

Решение задач, Экономика предприятия

Срок сдачи к 7 февр.

5 минут назад

Лаб. 8 Профилограф-профиометр и Лаб.2 пересчитать

Лабораторная, Метрология, стандартизация и сертификация

Срок сдачи к 18 февр.

5 минут назад

Отчёт о прохождении ознакомительной практики

Отчет по практике, Подземная и надземная разработка рудных месторождений

Срок сдачи к 8 февр.

6 минут назад

Лабораторная работа

Лабораторная, техническая механика

Срок сдачи к 9 февр.

6 минут назад

Тесты

Другое, Органическая химия

Срок сдачи к 20 февр.

7 минут назад

Сделать теорию и практику, вариант 2

Контрольная, Учет и анализ в кредитных организациях

Срок сдачи к 14 февр.

7 минут назад
7 минут назад

Планирование и отчетность в публичной библиотеке

Диплом, Библиотечное дело

Срок сдачи к 10 февр.

9 минут назад

Решить 6 задачников пользуясь прикрепленными материалами

Решение задач, Финансовый менеджмент

Срок сдачи к 13 февр.

9 минут назад

кроме 5 и 11 темы на выбор

Реферат, Геология

Срок сдачи к 10 февр.

9 минут назад

Задание по культурологии

Другое, Культурология

Срок сдачи к 8 февр.

10 минут назад

решить 3 задачи

Решение задач, Химия технологии нефти и газа

Срок сдачи к 13 февр.

10 минут назад

Электрические устройства безопасности лифта

Диплом, Электромеханик по лифтам, электротехника

Срок сдачи к 15 мар.

11 минут назад
planes planes
Закажи индивидуальную работу за 1 минуту!

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

«Всё сдал!» — безопасный онлайн-сервис с проверенными экспертами

Используя «Свежую базу РГСР», вы принимаете пользовательское соглашение
и политику обработки персональных данных
Сайт работает по московскому времени:

Вход или
регистрация
Регистрация или
Не нашли, что искали?

Заполните форму и узнайте цену на индивидуальную работу!

Файлы (при наличии)

    это быстро и бесплатно