Экспертные системы. Классификация экспертных систем. Разработка простейшей экспертной системы
Реферат - Компьютеры, программирование
Другие рефераты по предмету Компьютеры, программирование
?исок ОТКРЫТ пуст, то на выход дается сигнал о неудаче; в противном случае переходи к следующему этапу.
3) Взять из списка ОТКРЫТ ту вершину, для которой f имеет наименьшее значение, и поместить ее в список ЗАКРЫТ. Дать этой вершине название n. (В случае совпадения значений выбирать вершину с минимальными f произвольно, но всегда отдавая предпочтение целевой вершине.)
4) Если n есть целевая вершина, то на выход выдать решающий путь, получаемый прослеживанием соответствующих указателей; в противном случае переходить к следующему шагу.
5) Раскрыть вершину n, построив все непосредственно следующие за ней вершины. (Если таковых нет переходить к шагу (2).) Для такой дочерней вершины ni вычислить значение f(ni).
6) Связать с теми из вершин ni , которых еще нет в списках ОТКРЫТ или ЗАКРЫТ, только что прочитанные значения f(ni). Поместить эти вершины в список ОТКРЫТ и провести от них к вершине n указатели.
7) Связать с теми из непосредственно следующих за n вершинами. которые уже были в списке ОТКРЫТ или ЗАКРЫТ, меньшие из прежних или только что вычисленных значений f. Поместить в список ОТКРЫТ те из непосредственно следующих за n вершин, для которых новое значение f оказалось ниже, и изменить направление указателей от всех вершин, для которых значение f уменьшилось, направив их к n..
8) Перейти к (2).
Общая структура алгоритма идентична структуре алгоритма равных цен (см. рис. 7), поэтому мы не приводим для него блок-схему. Отметим, что множество вершин и указателей, порождаемых этим алгоритмом, образует дерево (дерево перебора), причем на концах этого дерева расположены вершины из списка ОТКРЫТ.
4.6. Использование других эвристик..
4.6.1. Перебор этапами.
Использование эвристической информации может существенно уменьшить объем перебора, необходимого для поиска приемлемого пути. Следовательно, ее использование, позволяет осуществлять перебор на гораздо больших графах. и тем не менее могут возникнуть случаи, когда имеющаяся в нашем распоряжении память оказывается исчерпанной раньше, чем будет найден удовлетворительный путь. В этих случаях может быть полезным не отказываться полностью от продолжения перебора, а “отсечь” часть ветвей дерева, построенного к этому моменту в процессе перебора, освободив тем самым пространство памяти, необходимое для углубления перебора.
Такой процесс перебора может осуществляться этапами, которые отделяются друг от друга операциями отсечения дерева, необходимыми для освобождения памяти. В конце каждого этапа удерживается некоторое подмножество открытых вершин, например вершины с наименьшими значениями f. Наилучшие пути к этим вершинам запоминаются, а остальная часть дерева отбрасывается. Затем начинается перебор снова, уже от этих “лучших” открытых вершин. Этот процесс продолжается до тех пор, пока либо будет найдена целевая вершина, либо будут исчерпаны все ресурсы. Хотя весь процесс заканчивается построением некоторого пути, тем не менее у нас нет теперь гарантии, что этот путь будет оптимальным.
4.6.2. Ограничение числа дочерних вершин.
Другой путь уменьшения перебора, состоит в том, чтобы использовать более информированный оператор Г, который не порождал бы слишком много ненужных вершин, а порождал бы лишь вершины, расположенные на оптимальном пути, снимая тем самым полностью необходимость перебора.
Один из приемов, который может позволить снизить требуемый объем перебора, состоит в том, чтобы сразу же после раскрытия вершины отбросить почти все дочерние вершины, оставив лишь небольшое их число с наименьшими значениями функции f. Конечно, отброшенные вершины могут оказаться расположенными на наилучших (и даже только на наилучших) путях, так что только эксперимент может определить пригодность такого метода отсечения ветвей графа для конкретных задач.
4.6.3. Поочередное построение дочерних вершин.
Когда вершины, непосредственно следующие за некоторой, вычисляются с помощью операторов в пространстве состояний, то очевидно, что эти последующие вершины могут строиться по отдельности и независимо друг от друга. Кроме того, существуют случаи, когда применение всех применимых операторов было бы очень расточительно в смысле вычислительных затрат. Как указывалось выше, более информированный оператор Г выделял бы несколько наиболее перспективных операторов и строил бы только те последующие вершины, которые возникают в результате их применения. Более гибкий подход состоит в том, чтобы сначала допускать применение самого перспективного оператора (что приведет к одно из последующей вершине), оставляя в дальнейшем возможность в процессе перебора построить и другие вершины, непосредственно следующие за данной. Для того, чтобы воспользоваться этой идеей вместе с оценочными функциями для упорядочения вершин, в алгоритм упорядоченного перебора следует внести соответствующие изменения.
Список литературы:
1. И. Братко. Программирование на языке Пролог для искусст-
венного интеллекта.- М.: Мир, 1990.
2. Г. Долин. Что такое ЭС.- Компьютер Пресс, 1992/2.
3. Д. Р. Малпасс. Реляционный язык Пролог и его применение.
4. Д. Н. Марселлус. Программирование экспертных систем на Турб