22181

Структуры и стратегии поиска в пространстве состояний

Лекция

Информатика, кибернетика и программирование

Решение задачи методом поиска 2. Структуры и стратегии поиска в пространстве состояний 3. Решение задачи методом поиска От выбранного метода поиска то есть стратегии вывода будет зависеть порядок применения и срабатывания правил.

Русский

2013-08-04

360 KB

45 чел.

23

ЛЕКЦИЯ №4

Структуры и стратегии поиска в пространстве состояний

Вопросы:

1.  Решение задачи методом поиска

2. Структуры и стратегии поиска в пространстве состояний

3. Эвристический поиск

4. Индуктивный алгоритм построения дерева решений ID3

5. Языки программирования для ЭС и языки представления знаний

1. Решение задачи методом поиска

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

При разработке стратегии управления выводом важно определить два вопроса:

  1.  Какую точку в пространстве состояний принять в качестве исходной? От вы
    бора этой точки зависит и метод осуществления поиска в прямом или об
    ратном направлении.
  2.  Какими методами можно повысить эффективность поиска решения? Эти методы определяются выбранной стратегией перебора - глубину, в ширину, по
    подзадачам или иначе.

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

В качестве простого примера рассмотрим игру "крестики-нолики". Для любой заданной ситуации всегда существует только конечное число допустимых ходов игрока. Первый игрок может разместить крестик в любой из девяти клеточек пустой игровой доски. Каждый из таких шагов порождает различные варианты заполнения игровой доски, которые позволяют противнику сделать восемь возможных ответных ходов и т.д. Эту совокупность (в зависимости от возможной конфигурации игровой доски) можно представить в виде вершин графа. Дуги графа представляют разрешенные ходы, приводящие от одной конфигурации игровой доски к другой. Узлы этого графа соответствуют различным состояниям игрового поля. Результирующая структура называется графом пространства состояний.

Можно построить граф пространства состояний для игры "крестики-нолики" (рис.1). Корневая вершина этого графа будет соответствовать пустой игровой доске, указывающей на начало игры. Каждый следующий узел графа будет представлять состояние игровой доски, возникающее в процессе игры в результате допустимых ходов, а дуги между ними — связи между вершинами. Значение этого графа состоит в том, что он дает возможность проследить последовательность шагов в любой игре. Проход начинается с вершины, представляющей пустую игровую доску, а перемещения по дугам приводят к вершинам-состояниям, представляющим или очередной ход, или победу. Представление в пространстве состояний, таким образом, позволяет рассматривать все возможные варианты игры "крестики-нолики" как различные пути на графе пространства состояний.

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

Рисунок 1 -  Фрагмент пространства состояний для игры "крестики-нолики"

В качестве примера использования поиска для решения более сложной проблемы рассмотрим задачу диагностирования механических неполадок в автомобиле. Вместо того, чтобы каждой вершине графа пространства состояний ставить в соответствие "состояние игровой доски", будем приписывать вершинам графа состояния частичного знания о механических неполадках автомобиля. Процесс исследования признаков неполадок и устранения их причины может быть представлен как поиск по всем состояниям, расширяющий наши знания о них. Начальная вершина графа пуста, она указывает на то, что о причинах неполадок ничего не известно. Первый вопрос, который механик мог бы задать клиенту, сводится к следующему: какие основные части системы (двигатель, коробка передач, рулевое управление, тормоза и т.д.), возможно, неисправны. Этот фрагмент диалога представлен в виде совокупности дуг, ведущих от начального состояния к состояниям, соответствующим отдельным подсистемам автомобиля (рис. 2).

Рисунок 2 - Описание пространства состояний на первом этапе решения задачи диагностики неисправностей автомобиля

С каждым состоянием графа связаны дуги (соответствующие основным диагностическим проверкам), которые ведут к состояниям, представляющим уточненные знания в процессе диагностики. Например, узел неисправности двигателя связан с узлами "двигатель запускается" и "двигатель не запускается". От узла "двигатель не запускается" можно перемещаться к узлам "заводится" и "не заводится". Узел "не заводится" связан с узлами "аккумулятор не работает" и "аккумулятор в порядке" (рис. 3). Можно построить граф, включающий все возможные вопросы и вершины, представляющие заключительные диагностические выводы. Решающее устройство сможет диагностировать автомобильные неполадки, находя путь в этом графе. Заметим, что конкретные вопросы, задаваемые в данном примере, определяют путь на графе. При этом каждый следующий ответ удаляет из рассмотрения ненужные вопросы. Хотя эта задача очень отличается от алгоритма нахождения оптимального пути в игре "крестики-нолики", она тоже решается путем поиска в пространстве состояний.

Рисунок 3 -Описание пространства состояний в задаче диагностики неполадок автомобиля

Несмотря на эту очевидную универсальность, поиска в пространстве состояний не достаточно для автоматизации интеллектуального поведения, обеспечивающего (автоматическое) решение проблем. Но это важный инструмент для проектирования интеллектуальных программ. Если бы поиска в пространстве состояний было достаточно, то было бы довольно просто написать программу, играющую в шахматы. Для определения последовательности ходов, ведущих к победе, на каждом этапе игры нужно было бы осуществлять полный поиск по всему пространству состояний. Этот метод решения задач известен как исчерпывающий, или поиск методом полного перебора. Хотя полный перебор может применяться в любом пространстве состояний, огромный размер пространства для интересных задач делает этот подход практически неприемлемым. Игре в шахматы, например, соответствует приблизительно 10120 различных состояний игровой доски. Это на порядок больше, чем число молекул во Вселенной или число наносекунд, которые минули с "большого взрыва" (момента создания Вселенной). Поиск в таком пространстве состояний выходит за рамки возможностей любого вычислительного устройства, размеры которого должны быть ограничены до известной области.

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

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

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

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

2. Структуры и стратегии поиска в пространстве состояний

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

Гарантировано ли нахождение решения в процессе поиска?

Является поиск конечным, или в нем возможны зацикливания? Если решение найдено, является ли оно оптимальным?

Как процесс поиска зависит от времени выполнения и используемой памяти? Как интерпретатор может наиболее эффективно упростить поиск?

Как разработать интерпретатор для наиболее эффективного использования языка представления?

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

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

Теория графов является наилучшим инструментом исследования структуры объектов и их отношений. Именно это и привело к созданию теории графов в начале восемнадцатого века. Швейцарский математик Леонард Эйлер изобрел теорию графов, чтобы решить "задачу о кенигсбергских мостах".

Граф - это множество вершин и дуг между ними. В размеченном графе для каждой вершины задается один или несколько дескрипторов (меток), которые позволяют отличить одну вершину графа от другой. На графе пространства состояний эти дескрипторы идентифицируют состояния в процессе решения задачи. Если дескрипторы двух вершин не различаются, то эти вершины считаются одинаковыми. Дуга между двумя вершинами определяется метками этих вершин.

Дуги графа также могут быть размеченными. Метка дуги используется для задания именованного отношения (как в семантических сетях) либо веса дуги (как в задаче о коммивояжере).

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

Рисунок 4 - Размеченный ориентированный граф

Путь на графе - это последовательность дуг, соединяющих соседние вершины. Путь представляется списком дуг, систематизированным в порядке их следования. На рис.4 список (а,b,с,d) представляет путь, проходящий через вершины а,b,с,d в указанном порядке.

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

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

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

На рис.5 вершина b является родителем вершин е и f (которые являются потомками b и вершинами-братьями). Вершины а и с являются предками вершин  g, h, i, а вершины  g, h, i, являются потомками а и с.

Рисунок 5 - Корневое дерево как пример семейных отношений

2.1. Поиск на основе данных и от цели

Поиск в пространстве состояний можно вести в двух направлениях: от исходных данных задачи к цели и в обратном направлении от цели к исходным данным.

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

Рисунок 6 – Обратный и прямой выводы

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

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

2.2. Реализация поиска на графах

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

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

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

Рисунок 7 - Поиск с возвратами в гипотетическом пространстве состояний

Пунктирные стрелки в дереве указывают направление процесса поиска в пространстве состояний (вниз или вверх). Числа возле каждой вершины указывают порядок их посещения. Ниже приведем  фрагмент алгоритма поиска с возвратами. В нем используются три списка, позволяющих запоминать путь от узла к узлу в пространстве состояний.

SL (State List ) - список исследованных состояний рассматриваемого пути. Если цель уже найдена,  SL содержит список состояний пути решения.

NSL ( New State List ) - список новых состояний, он содержит вершины, подлежащие рассмотрению, т.е. список вершин, потомки которых еще не были порождены и рассмотрены.

DЕ (Dead Ends) - список тупиков, т.е. список вершин, потомки которых уже были исследованы, но не привели к цели. Если состояние из этого списка снова встречается в процессе поиска, то оно обнаруживается в списке DЕ и исключается из рассмотрения.

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

Обозначим текущее состояние при поиске с возвратами через CS (current state). Состояние CS всегда равно последнему из состояний, занесенных в список SL, и представляет "фронтальную" вершину на построенном в данный момент пути. Правила вывода, ходы в игре или иные соответствующие операторы решения задачи упорядочиваются и применяются к CS. В результате возникает упорядоченное множество новых состояний, потомков CS. Первый из этих потомков объявляется новым текущим состоянием, а остальные заносятся в список новых состояний NSL для дальнейшего изучения. Новое текущее состояние заносится в список состояний SL, и поиск продолжается. Если текущее состояние CS не имеет потомков, то оно удаляется из списка состояний SL (именно в этот момент алгоритм "возвращается назад"), и исследуется какой-либо из оставшихся потомков его предка в списке состояний SL.

Алгоритм поиска с возвратами на графе из рис.7 работает следующим образом.

Инициализируем списки.

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

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

  1.  Формируется список неисследованных состояний (NSL), для того чтобы иметь возможность возвратиться к любому из них.
  2.  Поддерживается список "неудачных" состояний (DE), чтобы оградить алгоритм от проверки бесполезных путей.
  3.  Поддерживается список узлов (SL) текущего пути, который возвращается по достижении цели.
  4.  Каждое новое состояние проверяется на вхождение в эти списки, чтобы предотвратить зацикливание.

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

2.3 Поиск в глубину и в ширину

Поиск в ширину

Поиск начинается с корневой вершины (рис.8), определяются все последователи корневой вершины, затем все последователи последователей и т.д., пока не будут найдены все вершины, соответствующие целевым состояниям.

Рисунок 8 – Дерево поиска в ширину

Если полагать что число последователей каждой вершины l , то число вершин S при глубине поиска k равно:

                                                                                            (1)

При конкретных значениях l и k по этой формуле вычисляется максимальное число вершин дерева поиска.

Поиск в глубину

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

Рисунок 9 – Дерево поиска в глубину

Сравнение стратегий поиска.

Сравним поиск в глубину и в ширину на примере.

Рассмотрим в качестве примера задачу построения слова из некоторого множества букв. Задавшись набором операций установки букв, можно сформировать пространство состояний. .

Предположим, что множество доступных букв включает P = {К, Т, О}. На каждом уровне графа мы будем добавлять по одной определенной букве. Каждая ветвь, исходящая из узла, соответствует установке буквы в определенную позицию в последовательности, а эта последовательность должна образовать осмысленное слово. Если это произошло, то головоломка считается собранной. Целью работы будет построить все распознаваемые человеком последовательности и найти слово КОТ.

Примем за начальную точку – O . Дерево пространства состояний (неизменно) рис.10:

 

Рисунок 10 – Дерево пространства состояний

Метод формирования, анаграмм последовательным перечислением является примером применения алгоритма, получившего наименование generate-and-test  (порождение и проверка).

  1.  Генерировать новое состояние, модифицируя существующее; например, изменитьоследовательность букв, добавив новую в существующую последовательность.
  2.  Проверить, не является ли образовавшееся состояние конечным (решением); например, проверить, не является ли образовавшаяся последовательность осмысленным словом. Если это так, то завершить, иначе перейти к шагу (1).

Алгоритм имеет два основных варианта: поиск в глубину и поиск в ширину. Отличаются варианты порядком формирования состояний на шаге (1).

Алгоритм поиска в ширину - сначала формируются все "соседи" узла N , а потом уже строятся его потомки. Таким образом, в алгоритме поиска в ширину просматриваются последовательно состояния, представленные узлами одного и того же уровня на графе.  Дерево решений при использовании поиска в ширину:

 

Рисунок 11 – Дерево решений при использовании поиска в ширину

Алгоритм поиска в глубину. Для любого данного узла N алгоритм поиска в глубину строит потомок этого узла,  т.е. формирует состояние,  которое образуется в результате применения операторов к узлу N, а потом переходит к формированию узла, ближайшего к N, на том же уровне графа ("соседу" N ), т.е. формирует состояние, которое образуется в результате применения оператора к узлу-родителю N.

Дерево решений при использовании поиска в глубину:

Рисунок 12 – Дерево решений при использовании поиска в глубину

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

Поиск в глубину может быстрее найти решение, особенно если используются эвристики для выбора очередной ветки, но алгоритм может никогда не закончиться, если пространство состояний неограниченно. Оба алгоритма завершат работу (найдут конечное состояние) после формирования узла «кот». Но алгоритму поиска в ширину придется для этого "посетить" пять узлов (сформировать и проанализировать пять состояний), а алгоритму поиска в глубину - четыре.

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

3. Эвристический поиск

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

,

где  - соответствует расстоянию на графе от узла  до начального состояния;

- оценка расстояния от  до узла, представляющего конечное состояние(целевое).

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

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

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

Рисунок 12 - Эвристический поиск в гипотетическом пространстве состояний и алгоритм

4. Индуктивный алгоритм построения дерева решений ID3

Один способ сокращения перебора состоит в выборе более "информированного" оператора, который не строит так много вершин, не относящихся к делу.

Одно из направлений исследований в этой области – автоматизированное извлечение знаний. Идея состоит в том, чтобы машина училась решать проблемы примерно так, как учиться человек.

Можно предложить три варианта приобретения знаний, которые позволят обойтись без создания базы знаний "вручную" объединенными усилиями человека-эксперта и инженера по знаниям, которые имеют прямое отношение к проблемам экспертных систем:

- извлечение множества правил из предъявляемых примеров;

- анализ важности отдельных правил;

- оптимизация производительности набора правил.

Существуют и другие аспекты машинного обучения, которых мы здесь касаться не  будем.

Индуктивное обучение

Точное, определение термину "обучение" дать довольно трудно, но большинство авторов сходятся во мнении, что это - качество адаптивной системы, которая способна совершенствовать свое поведение (умение справляться с проблемами), накапливая опыт, например опыт решения аналогичных задач.

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

Рассмотрим одну из методик обучения, которая получила наименование пространство версий. Поиск в пространстве версий основан на том, что операция обобщения упорядочивает понятия в пространстве поиска. Затем этот порядок используется для выбора направления поиска.

Рассмотрим один из алгоритмов.

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

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

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

Таблица 1 - Данные о кредитной истории

Дерево решений на рисунке 13 содержит приведенные в таблице 1 данные и позволяет корректно классифицировать все объекты в таблице.

Рисунок 13 - Дерево решений для оценки кредитного риска

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

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

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

Рисунок 14 - Упрощенное дерево решений для оценки кредитного риска

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

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

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

Построение дерева решений сверху вниз

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

Например, рассмотрим процесс построения дерева, представленного на рисунке 14  на основе данных из таблицы 1. Имея полную таблицу примеров, алгоритм ID3 выбирает в качестве корневого свойства значение дохода на основе функции выбора. При этом множество примеров делится на три части, как показано на рисунке 15. Элементы каждой части представлены порядковыми номерами примеров в таблице.

Рисунок 15 - Упрощенное дерево решений для оценки кредитного риска

Алгоритм индукции начинает свою работу с отбора корректно классифицированных элементов целевых категорий. Алгоритм строит дерево решений следующим образом:

Function induce_tree (example_set, Properties)  

Begin

если все элементы набора примеров example_set  принадлежат к

одному и тому же классу,

то вернуть конечный узел,

      отнеся его к этому классу, иначе, если множество Properties  пусто,

то вернуть конечный узел, именем которого является объеденение всех  

           имен классов в example_set  

иначе  Begin

      выбрать  свойство Р и назначить  его  корнем

                   текущего дерева;

         удалить  свойство Р из множества Properties  для  каждого  

           значения  V свойства Р 

      Begin

               создать  ветвь  дерева  с меткой  V; 

                       к разделу partition  отнести

элементы множества example_set,   для которых  свойство Р            

             принимает  значение  V;

вызвать  функцию induce_tree (partitionv Properties),   добавить       

результаты к ветви V

Cогласно алгоритму функция induce_tree рекурсивно вызывается для каждого раздела. Например, пусть к разделу {1,4,7,11} относятся клиенты с высоким риском; алгоритм создаст соответствующий конечный узел. Затем в качестве корневого узла поддерева раздела {2, 3, 12, 14} выбирается свойство "кредитная история". На рисунке 16  элементы этого раздела в свою очередь разбиваются на три группы: {2, 3}, {14} и {12}.

Рисунок 16 - Фрагмент  дерева решений

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

Эвристика  выбора свойств на основе теории информации

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

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

Предположим, что существует монета, при подбрасывании которой в трех из четырех случаях выпадает решка. Если знать, что вероятность выпадения решки составляет 3/4, то в 3/4 случаев можно правильно угадать результат игры.

Шеннон формализовал эти наблюдения, определив количество информации в сообщении как функцию от вероятности р передачи каждого возможного сообщения, а именно- log2 p. Имея пространство сообщений М={m1, m2 …..mn} и зная вероятности р(mi) для каждого сообщения, информативность этих сообщений можно вычислить следующим образом:

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

Если же монета такова, что вероятность выпадения решки составляет 75%, то информативность сообщения равна

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

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

Следовательно, информативность распределения D1 описанного в таблице 1, а значит и любого дерева, покрывающего эти примеры, составляет

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

Предположим, что существует набор обучающих примеров С. Если корнем текущего дерева является свойство Р, которое может принимать n значений, то множество С будет разделено на подмножества 1 С2,.. , Сn}. Информация, необходимая для завершения построения дерева при выборе свойства Р, составляет

Выигрыш от использования свойства Р вычисляется как разность общей информативности дерева и объема информации, необходимого для завершения построения дерева.

Возвращаясь к примеру из таблице 1, при выборе в качестве корня дерева свойства "доход" примеры будут разделены на три группы: С,={1,4,7, 11},С2={2, 3, 12, 14} и С3={5, 6, 8, 9, 10, 13}. Информация, необходимая для завершения построения дерева, составляет

Информационный выигрыш от такого разбиения данных таблице1, составляет

Аналогично можно показать, что

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

5. Языки программирования для ЭС и языки представления знаний

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

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

  1.  Разработка систем представления знаний (СПЗ) путем прямого использова
    ния широко распространенных языков обработки символьной информации и,
    все чаще, языков программирования общего назначения.
  2.  Расширение базисных языков ИИ до систем представления знаний за счет специализированных библиотек и пакетов.
  3.  Создание языков представления знаний (ЯПЗ), специально ориентированных на поддержку определенных формализмов, и реализация соответствующих
    трансляторов с этих языков.

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

До недавнего времени наиболее популярным базовым языком реализации систем ИИ вообще и ЭС, в частности, был ЛИСП [1978].

Как известно, язык ЛИСП был разработан в Стэнфорде под руководством Дж. Мак-карти в начале 60-х годов и не предназначался вначале для программирования задач ИИ. Это был язык, который должен был стать следующим за ФОРТРАНОМ шагом на пути автоматизации программирования.

К концу 80-х годов ЛИСП был реализован на всех классах ЭВМ, начиная с персональных компьютеров и кончая высокопроизводительными вычислительными системами/Новый толчок развитию ЛИСПа дало создание ЛИСП-машин, которые и в настоящее время выпускаются рядом фирм США, Японии и Западной Европы.

В середине 60-х годов, то есть на этапе становления ЛИСПа, разрабатывались языки, предлагающие другие концептуальные основы. Наиболее важными из них в области обработки символьной информации являются, по нашему мнению, СНОБОЛ [1978], разработанный в лабораториях Белла, и язык РЕФАЛ [Турчин, 1968], созданный в АН СССР.

В основу языка РЕФАЛ положено понятие рекурсивной функции, определенной на множестве произвольных символьных выражений. Базовой структурой данных этого языка являются списки, но.не односвязные, как в ЛИСПе, а двунаправленные. Обработка символов ближе, как мы бы сказали сегодня, к продукционному формализму. При этом активно используется концепция поиска по образцу, характерная для СНОБОЛа. Таким образом, РЕФАЛ вобрал в себя лучшие черты наиболее интересных языков обработки символьной информации 60-х годов. В настоящее время можно говорить о языке РЕФАЛ второго [Климов и др., 1987] и даже третьего поколения; Реализован РЕФАЛ на всех основных типах ЭВМ и активно используется для автоматизации построения трансляторов, для построения систем аналитических преобразований, а также, подобно ЛИСПу, в качестве инструментальной среды для реализации языков представления знаний [Хорошевский, 1983].

В начале 70-х годов появился еще один новый язык, способный составить конкуренцию ЛИСПу при реализации систем, ориентированных на знания* — язык ПРОЛОГ [1982]. Он не дает новых сверхмощных средств программирования по сравнению с ЛИСПом, но поддерживает другую модель организации вычислений. Подобно тому, как ЛИСП скрыл от программиста устройство памяти ЭВМ, ПРОЛОГ позволил ему не заботиться (без необходимости) о потоке управления в программе. ПРОЛОГ предлагает такую парадигму мышления, в рамках которой описание решаемой задачи представляется в виде слабо структурированной совокупности отношений. Это удобно, если число отношений не слишком велико и каждое отношение описывается небольшим числом альтернатив. В противном случае ПРОЛОГ-программа становится весьма сложной для понимания и модификации. Возникают и проблемы эффективности реализации языка, так как в общем случае механизмы вывода, встроенные в. ПРОЛОГ, обеспечивают поиск решения на основе перебора возможных альтернатив и декларативного возврата из тупиков.

В 70-х годах в программировании вообще и программировании задач ИИ, в частности, центр тяжести стал смещаться от процедурных к декларативным описаниям. К этому же времени в ИИ сформировались и концепции представления знаний на основе семантических сетей и фреймов. Естественно, что появились и специальные языки программирования, ориентированные на поддержку этих концепций. Но из десятков, а может и сотен языков представления знаний (ЯПЗ) первого поколения лишь несколько сыграли заметную роль в программной поддержке систем представления знаний. Характерными чертами этих ЯПЗ были: двухуровневое представление данных (абстрактная модель предметной области в виде иерархии, множеств понятий и конкретная,модель ситуации как совокупность взаимосвязанных экземпляров этих понятий); представление связей между понятиями и закономерностей предметной области в виде присоединенных процедур; семантический подход к сопоставлению образцов и поиску по образцу.

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

–  выделении классов объектов;

–  установлении характерных свойств объектов и методов их обработки;

–  создании иерархии классов, наследовании свойств объектов и методов их обработки.

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

Из языков объектного программирования, популярных среди профессионалов, следует назвать прежде всего:

С++ (Си++). Си++ - это объектно-ориентированное расширение языка Си, созданное Бьярном Страуструпом в 1980 году. Множество новых мощных возможностей, позволивших резко повысить производительность работы программистов, наложилось на унаследованную от языка Си определенную низкоуровневость, в результате чего создание сложных и надежных программ потребовало от разработчиков высокого уровня профессиональной подготовки;

Delphi (Дельфи) – язык объектно-ориентированного "визуального" программирования. Явился развитием языка Паскаль.

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

Анализ формализмов представления знаний и методов вывода решений позволяет сформулировать следующие требования к ЯПЗ:

наличие простых и вместе с тем достаточно мощных средств представления
сложно структурированных и взаимосвязанных объектов;

возможность отображения описаний объектов на разные виды памяти ЭВМ;

наличие гибких средств управления выводом, учитывающих необходимость
структурирования правил работы решателя;

«прозрачность» системных механизмов для программиста, предполагающая
возможность их доопределения и переопределения на уровне входного языка;

возможность эффективной реализации.

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


 

А также другие работы, которые могут Вас заинтересовать

26693. Неогей 78 KB
  В течение обоих циклов в погружение вовлекались преимущественно северозападные и югозападные зоны Русской плиты которые либо простирались грубо параллельно СевероАтлантическому Грампианскому геосинклинальному поясу отделяясь от него Балтийским щитом обширная палеоБалтийская синеклиза либо примыкали к Средиземноморскому поясу ЛьвовскоКишиневский перикратонный прогиб. В кембрии осушилась его северовосточная часть район Мезенской синеклизы а на западе он распространился в пределы западной части Советской...
26694. Геологическая характеристика и палеогеографические условия осадконакопления отложений девона, карбона и перми Восточно-Европейской платформы. Полезные ископаемые 126 KB
  В пределах ВолгоУральской области с нижневизейскими песчаными толщами связаны месторождения нефти. Месторождения нефти и газа ВЕП связаны как с палеозойскими так и мезозойскими отложениями. Месторождения бурых углей находятся в Подмосковье где они приурочены к низам визейского яруса. В ВолгоУральской антеклизе с отложениями нижнего карбона связаны крупные месторождения углей.
26695. Сибирская платформа: границы и основные структурные элементы. Геологическое строение фундамента. Полезные ископаемые 109 KB
  Некоторая часть пород принадлежит к первичноосадочным компонентам продукты переотложения первичных кор выветривания. Оленёкский выступ представлен нижнепротерозойскими терригенными отложениями метаморфизированными смятыми в пологие складки. В отложениях архея много обломочного кварцевого и глиноземистого материала – источник магматические породы кислого и среднего состава. Главные результаты: впервые вскрыт и детально изучен наиболее полный разрез триасовых и юрских отложений; опровергнуты представления о непрерывном уплотнении...
26696. Алтае-Саянская область: геологическое строение и история развития. Полезные ископаемые 81 KB
  АлтаеСаянская область: геологическое строение и история развития. АлтаеСаянская горная страна охватывает горные сооружения Восточного и Западного Саян Кузнецкого Алатау Горной Шорин и Горного Алтая. Восточный Саян – сложная морфоструктура сформированная на древнейших образованиях АлтаеСаянского региона. Стратиграфия и тектоника Горные породы представлены комплексами скальных вулканогенных образований сосредоточенных в восточной части Алтае – Саянского региона и нескальных осадочных несцементированных грунтов в составе которых по...
26697. Основные тектонические элементы северо-западной части Тихоокеанского подвижного пояса 387 KB
  Основные тектонические элементы северозападной части Тихоокеанского подвижного пояса. Формирование ОхотскоЧукотского вулканоплутонического пояса происходило в раннем мелупалеогене. С вулканитами тесно пространственно и генетически связаны интрузии гранитоидов и более основных пород занимающие до 20 площади пояса. СРЕДИЗЕМНОМОРСКИЙ ПОДВИЖНЫЙ ПОЯС В состав Средиземномосркого подвижного пояса в пределах бывшего Советского Союза входят складчатые сооружения Карпат Горного Крыма Большого и Малого Кавказа Копетдага так называемая...
26698. Кавказское складчатое сооружение 52.5 KB
  Месторождения нефти сосредоточены в основном в Башкортостане Пермской и Оренбургской областях и в Удмуртии природного газа – в Оренбургском газоконденсатном месторождении. Месторождения осадочных сидеритов и связанные c ними бурые железняки Бакальское распространены в западной мегазоне Южного Урала. Для TагильскоMагнитогорской зоны Восточной мегазоны характерны полигенные скарновомагнетитовые месторождения железных руд TагилоKушвинская гуппа Mагнитогорское и др. Kрупные месторождения хромитов Kемпирсайское PайИзское и др.
26699. Кредитный договор 62.49 KB
  Общая характеристика кредитного договора. Заключение кредитного договора и исполнение обязательств по нему. Расторжение кредитного договора...
26700. Строение фундамента ВЕП 119 KB
  Строение фундамента ВЕП Архейские и частично нижнепротерозойские отложения представляют собой толщи первичноосадочных вулканогенноосадочных и вулканогенных пород метаморфизованных в различной степени. Для расчленения пород фундамента важны данные определения абсолютного возраста. Выходы фундамента на поверхность. Рельеф фундамента и современная структура платформы В пределах ВЕП структуры первого порядка выделяются Балтийский и Украинский щиты и Русская плита.
26701. Сибирские траппы 1.13 MB
  Отложения нижнего рифея распространены на востоке платформы в КамскоБельском Пачелмском Ладожском Среднерусском и Московском авлакогенах. Местами в нижнем рифее известны вулканогенные породы: горизонты базальтовых пеплов туфов и покровы базальтов а в западных районах платформы в это время внедрялись габбродиабазовые интрузии. Возможно что первоначально эти отложения имели более широкое площадное распространение а позднее они были частично размыты и сохранились лишь в наиболее прогнутых участках платформы. На западе и в...