Реферат: Методы решения задач - текст реферата. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Реферат

Методы решения задач

Банк рефератов / Программирование

Рубрики  Рубрики реферат банка

закрыть
Категория: Реферат
Язык реферата: Русский
Дата добавления:   
 
Скачать
Архив Zip, 75 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникального реферата

Узнайте стоимость написания уникальной работы

МЕТОДЫ ПОИСКА РЕШЕНИЙ В ЭКСПЕРТНЫХ СИ СТЕМАХ Методы решения задач , основанные на сведении их к поиску , зависят от особ енностей предметной области , в которой решает ся задача , и от требований , предъявляемых пользователем к решению . Особенности предметной области : · объем пространства , в котором предстоит искать решение ; · степень изменяемости области во времени и пространстве (статичес кие и динамические области ); · полнота модели , опис ывающей область , если модель не полна , то для описания области используют несколько моделей , дополняющих друг друга ; · определенность дан ных о решаемой задаче , степень точност и (ошибочности ) и полноты (неполноты ) данных. Требования пользователя к результату зада чи , решаемой с помощью поиска , можно харак теризовать : · количеством решений : одно решение , несколько решений , все решения. · св ойствами результата : огранич ения , которым должен удовлетворять полученный результат и (или ) способом его получения . Существующие методы решения задач , используемые в экспертных системах , можно к лассифицировать следующим образом : · методы поиска в одном п ространстве - методы , предназ наченные для использования в следующих услови ях : области небольшой размерности , полнота мод ели , точные и полные данные ; · методы поиска в иерархических пространствах - методы , предна значенные для работы в областях большой р азм ерности ; · методы поиска при неточных и неполных данных ; · методы поиска , использующие несколько моделей , предназначенные для работы с областями , для адекватного описания которых одной модели недостаточно. Предполагается , что перечисленные методам при необходимости должны объединяться для того , чтобы позволить решать задачи , слож ность которых возрастает одновременно по неск ольким параметрам. 3.1. ПОИСК РЕШЕНИЙ В ОДНОМ ПРОСТРАНСТВЕ Методы поиска решений в одном простра нстве обычно делятся на : · поиск в простр анстве состояний (рассмотрим подробно ), · поиск методом редук ции , · эвристический поиск · поиск методом "генер ация-проверка ". 3.1.1. Поиск в пространстве сост ояний Задача поиска в пространстве состояний обычно формулируется в теоретико-граф овой интерпретации. Пусть задана тройка (S 0 , F, S Т ), где S 0 - множество на чальных состояний (условия задачи ), F - множество операторов задачи , отображающих одни состояния в другие , S Т - множество конечных (целевых ) состояний (решений задачи ). Цель : определ ять такую последовательн ость операторов , которая преобразует начальные состояния в конечные . Процесс решения в виде графа G=(Х , Y), где X= х 0 , х 1, ... - множество (в общем случае бесконечное ) вершин графа , состояний , а Y - множество , содержащее пары верши н (x i , x j ), (x i , x j ) X . Если каждая пара (x i , x j ) неупор ядочена , то ее называют ребром , а граф - неориентированным . Если для каждой пары (x i , x j ) задан порядок (направлен ие ), то пару (x i , x j ) называют дугой (ориентированным ре бром ), а граф называют ориентированным (направленным ). Вершины пары (x i , x j ) называют концевыми точками ребра (дуги ). Поиск в пространстве состояний естественн о представить в виде ориентированного графа . Наличие пары (x i , x j ) свидетельствует о существовани и некоторого оператора f ( f F), преобраз ующего состояние , соответствующее вершине x i , в состояние x j . Для некото рой вершины x i выделяем множество всех направленных пар (x i , x j ) Y, т.ь . множество д уг , исходящих из вершины х i , (родительской вершины ), и множество вершин (называемых дочерн ими вершинами ), в которые эти дуги приводя т . Множество дуг , исходящих из вершины x i , соответствует м ножеству операторов , которые могут быть приме нены к состоянию , соо тветствующему вершин е х i . В множестве вершин X выделяют подмножество вершин Х 0 Х , соответствующее множеству начальных состояний (S o ),, и подмножество вершин Х т X, соответствующее множеству конечны х (целевых ) состояний (S Т ). Множество Х т может быть задано как явно , так и неявно , т.е . через свойства , которы ми должны обладать целевые состояния. Отметим , что граф С может быть зад ан явно и неявно . Неявное задание графа G стоит в определении множества Х 0 Х (соответствующ его множеству начальных состояний ) и множеств а операторов , которые , будучи применимы к некоторой вершине графа , дают все ее дочер ние вершины. Итак , граф G задает пространство состояний , т.е . пространство , в ко тором осуществл яется поиск решения . Построение пространства осуществляется с помощью следующего процесса . Берется некая вершина х 0 Х , к ней применяются все возможные операторы , порождающи е все дочерние вершины . Этот процесс на зывают процессом раскрытия вершин . Если получена целевая вершина , то она не рас крывается . Процесс построения пространства состоя ний заканчивается , когда все нераскрытые верш ины являются целевыми , или терминальными (т.е . вершинами , к которым нельзя примени т ь никаких операторов ). В связи с те м , что пространство состояний может содержать бесконечное количество вершин , на практике процесс порождения пространства ограничивают л ибо временем , либо объемом памяти. На практике требуется обеспечить полноту поиска , т. е . организовать поиск так , чтобы все целевые вершины были найдены , если они существуют . Надежным способом обес печения полноты является полный перебор всех вершин . Для задания процесса перебора нео бходимо определить . порядок , в котором будут перебираться в е ршины графа . Обычно выделяют два основных способа поиска : · поиск в глубину (сначала раскрывается та вершина , которая была построена самой последней ). Рис. 3.1.а · поиск в ширину . ( вершины раскрываются в том же порядке , в котором они порождаются .) Рис .3.1.б. Целевые вершины помечены черными квадрата ми , а терминальные - белыми квадратами . При использовании каждого из способов могут быть найдены все решения . При переборе в сего пространства оба метода будут анализиров ать одинаковое количество вершин , однако мето д поиска в ширину будет требовать существенно больше памяти , так как он запоминает все пути поиска (а не один , как при поиске в глубину ). 3.1.2. Поиск методом редукции При поиске методом редукции решение з адачи сводится к решению совокупности образую щих ее подзадач . Этот процесс повторяется для каждой подзадачи до тех пор , пока каждая из полученного набора подзадач , образу ющих решение исходной задачи , не будет иметь очевидное решение . Процесс решения за дачи разбиением ее на подзадачи можно пре дставить в виде специального направленного гр афа G, называемого И /ИЛИ-графом ; Каждой вершине этого графа ставится в соответствие опис ание некоторой задачи (подзад а чи ). В графе выделяют два типа вершин : конъюнкт ивные вершины и дизъюнктивные вершины . Решение задачи при поиске методом ред укции (при поиске в И /ИЛИ-графе ) сводится к нахождению в И /ИЛИ-графе решающего гр афа . Цель процесса поиска в И /ИЛИ-графе - показать , что начальная вершина разрешима , т.е . для этой вершины существует решающий граф . Определение разрешимой вершины в И /ИЛИ-графе можно сформулировать рекурсивно сл едующим образом : Конечные (целевы е ) вершины разрешимы , так как их решение известно по исходному предположению. Вершина ИЛИ разрешима тогда и только тогда , когда разрешима по крайней мере одна из ее дочерних вершин. Вершина И разрешима тола и только то гда , когда разрешима каждая из ее дочерних вершин. Решающий граф определяется как подграф из разрешимых вер шин , который показывает , что начальная вершина р азрешима (в соответствии с приведенн ым выше определением ). На рис . 3.3. разрешимые вершины зачернены , а неразрешимые оставлены б елыми. Для графа И /ИЛИ , так же как дл я поиска в пространстве состояний , можно о пределить поиск в глубину и поиск в ш ирину как в прямом , так и в обра тном направлении . На рис . 3.4. приведен пример поиска в ширину (рис . 3.4., а ) и поиска в глубину (рис . 3.4., б ). На рисунке вершины п ронумерованы в том порядке , в котором они раскрывались , конечные вершины обозначены кв адратами , разре ш имые вершины зачернен ы , дуги решающего графа выделены двойными линиями. 3.1.3. Эвристический поиск При увеличении пространства поиска методы слепого поиск а требуют чрезмерных за трат времени и (или ) памяти . Это привело к созданию эвристических методов поиска , т.е . методов , использующих некоторую информацию о предметной области для рассмотрения не в сего пространства поиска , а таких путей в нем , которые с наи б ольшей вер оятностью приводят .к цели . ' 3.1.4.Поиск методом "генерация-провер ка " Процесс поиска может быть сформулирован в терминах "генерация-проверка ". Для осуществле ния процесса поиска необходимо генерировать о чередное возможное решение (состояние или подзадачу ) и проверить , не является ли о но результирующим . 3.2. ПОИСК В ИЕРАРХИИ ПРОСТРАНСТВ Методы поиска в одном пространстве не позволяют решать сложные задачи , так как с увеличением размера пространства время поиска экспоненциально растет . При боль шом размере пространства поиска можно попробо вать разбить общее пространство на подпростра нства и осуществлять поиск сначала в них . Пространство поиска представлено иерархией пространств. Методы поиска решения в иерархических пространствах обычно делятся н а : · поиск в факторизова нном пространстве , · поиск в фиксированн ом множестве пространств · поиск в изменяющемс я множестве пространств. 3.2.1. Поиск в факторизованном п ространстве Во многих приложениях требуется найти все решения . Например - постанов ка диагн оза . Пространство называется факторизованным , если оно разбивается на непересекающиеся подпрост ранства (классы ) частичными (неполными ) решениями . Причем по виду частичного решения можно определить , что оно не приведет к успех у , т.е . что все полные решения , о бразованные из него , не приведут к целевым решениям . Поиск в факторизованном пространст ве осуществляется на основе метола "иерархиче ская генерация-проверка ". Если пространство поиска удается факторизовать , то поиск даже в очень большом пространс т ве можно организовать эффективно . 3.2.2. Поиск в фиксированном мно жестве пространств Применение метода факторизации пространства ограничено тем , что для ряда областей не удается по частичному решению сделать заключение о его непригодности . Например за да чи планирования и конструирования . В этих случаях могут быть применены методы поиска , использующие идею абстрактного простран ства . Абстракция должна подчеркнуть важные ос обенности рассматриваемой задачи , позволить разби ть задачу на более простые подзадачи и определить последовательность подзадач (план решения ), приводящую к решению основной задачи . 3.2.3. Поиск в изменяющемся множ естве иерархических пространств В ряде приложений не удается все решаемые задачи свести к фиксированн ому набору подзадач . План решения задачи в данном случае должен иметь переменную структуру и не может быть сведен к фиксированному набору подзадач . Для решения подобных задач может быть использован мето д нисходящего уточнения . Этот метод базируетс я на следующих предположениях : · возможно осуществить частичное упорядочение понятий области , приемлемое для всех реша емых задач ; · решения , принимаемые на верхних уровнях , нет необходимости отмен ять на более нижних. 3.3. ПОИСК В АЛЬТЕРНАТИВНЫХ ПРОСТРАНСТВАХ Рассмотренные выше методы поиска ис ходят из молчаливой предпосылки , что знания о предметной области и данные о решаем ой задаче являются точными и полными и для них справедливо следующее : · все утверждения , опи сывающие состояние , являются истинными ; · применение оператора к некото рому состоянию формирует некот орое новое состояние , описание которого состо ит только из истинных фактов. Однако при решении любых практических задач и особенно при решении неформализованных задач распрост ранена обратная ситуация . Эксперту приходится работа ть в условиях неполноты и неточ ности знаний (данных ) и , как правило , в условиях дефицита времени . Когда эксперт реша ет задачу , он использует методы , отличающиеся от формальных математических рассуждений . В этом случае эксперт делает правдоподобные предпол о жения , которые он не мо жет доказать ; тем самым вопрос об их и стинности остается открытым . Все утверждения , полученные на основе этих правдоподобных пред положений , также не могут быть доказаны. Итак , для того чтобы система могла делать умозаключения , основа нные на здр авом смысле , при работе с неполными (неточ ными ) данными и знаниями , она должна быть способна делать предположения , а при полу чении новой информации , показывающей ошибочность предположений , отказываться как от сделанных предположений , так и от у м оза ключений , полученных на основе этих предполож ений . Мнение системы о том , какие факты имеют место , изменяется в ходе рассуждения , т.е . можно говорить о ревизии мнений . Таким образом , даже если рассматривать пробле мную область как статическую , неполнота ( и неточность ) знаний и данных влечет за собой рассмотрение этой области при различных (и даже противоположных ) предположени ях , что , в свою очередь , приводит к пре дставлению области в виде альтернативных прос транств , соответствующих различным , возможно , пр о тиворечивым и (или ) взаимодополняющим предположениям и мнениям. Все неудачи , возникшие при поиске в одном направлении , не запоминаются при пере ходе к поиску в другом направлении . Та же самая причина неудачи может заново обнаруживаться и на новом направлени и . Осуществлять возврат целесообразно не к состоянию , непосредственно предшествующему данно му , а к тому состоянию , которое является причиной возникновения неудачи . В используемых нами терминах причиной неудач являются п редположения , т.е . недоказуемые утве рждения . Поэтому при обнаружении неудачи необходимо возвращаться в состояние , где это предполож ение было сделано , и испытывать другое пре дположение . Этот метод поиска называют поиском , на правляемым зависимостью. 3.4. ПОИСК С ИСПОЛЬЗОВАНИЕМ НЕСКОЛЬКИХ МОД ЕЛЕЙ Все методы поиска , рассмотренные до си х пор , использовали при представлении проблем ной области какую-то одну модель , т.е . рассм атривали область с какой-то одной точки зр ения . При решении сложных задач в условиях ограниченных ресурсов использование не ск ольких моделей может значительно повысить мощ ность системы . Объединение в одной системе нескольких моделей дает возможность преодолеть следующие трудности . · переход с одной модели на другую позволяет обходить тупики , возникающие при поиске в процессе ра спространения ограничений . · использование нескольки х моделей позволяет в ряде случаев уменьш ить вероятность потери хорошего решения (след ствие неполного поиска , вызванного ограниченность ю ресурсов ) за счет конструирования полного решения из ограниченн ого числа частичн ых кандидатов путем их расширения и комби нации . · наличие нескольких моделей позволяет системе справляться с неточ ностью (ошибочностью ) данных. Следует отметит ь , что использование нескольких моделей требу ет дополнительных знаний о том , к ак создавать и объединять различные точки зре ния. 3.5. ВЫБОР МЕТОДА РЕШЕНИЯ ЗАДАЧ Выбор метода решения задачи зависит п режде всего от сложности задачи , которая о пределяется особенностями проблемной области и требованиями , предъявляемыми пользователем к р ешению задачи . Для преодоления трудностей , вызванных большим пространством поиска , испо льзуются методы , основанные на введении иерар хии пространств (конкретных , абстрактных и мет апространств ). Простейший из этих методов осно вывается на факторизуемости про с транс тва решений , что позволяет производить раннее отсечение . Метод обеспечивает получение всех решений . Если пространство поиска не удае тся факторизовать , но при этом не требуетс я получать все решения или выбирать лучше е , то могут быть применены методы , и спользующие иерархию однородных абстрактных пространств . Если пространство поиска таково , что любая задача может быть сведена к известной заранее последовательности подзадач , то используется фиксированное абстрактное п ространство. Эффективность этого метод а определяет ся возможностью использовать безвозвратную страт егию . В случае , если подзадачи взаимозависимы , т.е . для решения некоторой подзадачи може т требоваться информация , получаемая другой п одзадачей , и подзадачи не могут быть упоря дочены , целесообразн о применять принцип наименьших свершений . Этот подход позволяет приостанавливать решение подзадачи , для кото рой недостает информации , переходить к решени ю другой подзадачи и возвращаться к исход ной задаче , когда отсутствующая информация ст анет доступной . ( п оиск в иерархии пространстве ) Для преодоления трудностей , вызванных неп олнотой и (или ) неточностью данных (знаний ), используют вероятностные , размытые и точные м етоды . Все эти методы основываются на идее увеличения надежности путем комбинирования ф актов и использования метазнаний о возм ожностях комбинирования фактов . Для преодоления неадекватности модели про блемной области используются методы , ориентирован ные на использование нескольких моделей . Эти методы позволяют объединить возможности разл ичных моделей , описывающих проблемную област ь с различных точек зрения . Кроме того , использование нескольких моделей позволяет уме ньшить вероятность потери хорошего решения , н есмотря на неполноту поиска , вызванную ограни ченностью вычислительных ресурсов.
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
- Мода в одежде не главное, важнее комфорт и привычное удобство.
- У тебя на компе Windows XP?
- Да, а как ты угадал?
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, реферат по программированию "Методы решения задач", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru