Экспертные системы. Классификация экспертных систем. Разработка простейшей экспертной системы

db_dan('’®ў аЁйҐбвў® ЇаҐ¤ЇаЁЁ¬ вҐ«Ґ©',7605,'ЃЁ« ©')
db_dan('Љ‡Љ’',1165,'’®ў аЁйҐбвў® ЇаҐ¤ЇаЁЁ¬ вҐ«Ґ©')
db_dan('ЉЂ‚‡',7094,'Љ‡Љ’')
db_dan('—’‡',8205,'ЉЂ‚‡')
db_dan('‡„‘',5983,'—’‡')
db_dan('ЉЊ‡',5622,'‡„‘')
db_dan('‘ЁвҐ§',6633,'Ђна®д«®в')
db_dan('ЉЊ‡',6693,'‘ЁвҐ§')
db_dan('Љ‡Љ’',7809,'•Ё¬¬ и')
db_dan('Љ‡Љ’',360,'Љ®дЁ')
db_dan('Љ‘Њ',3790,'Љ‡Љ’')
db_dan('‘ЁвҐ§',2000,'Љ‘Њ')
db_dan('Љал¬',296,'‡€‹')
db_dan('‡„‘',1436,'Љал¬')
db_dan('‚Ђ‡',9840,'Љ®дЁ')
db_dan('Љ‡Љ’',7620,'‚Ђ‡')
db_dan('ЉЊ‡',4321,'•Ё¬¬ и')
db_dan('—’‡',5432,'ЉЊ‡')
db_dan('Љал¬',2345,'•«ҐЎ®Є ¬ЎЁ в')
db_dan('†Ѓ€',1201,'’®ў аЁйҐбвў® ЇаҐ¤ЇаЁЁ¬ вҐ«Ґ©')
db_dan('†Ѓ€',1500,'‹Ђ‡')
db_dan('Љ‘Њ',7680,'†Ѓ€')

Введение

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

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

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

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

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

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

При построенииподсистемвывода используютметоды решениязадач искусственногоинтеллекта.

Глава 1. Экспертныесистемы, ихособенности.

Применениеэкспертныхсистем.

1.1. Определениеэкспертныхсистем. Главноедостоинствои назначениеэкспертныхсистем.

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

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

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

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

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

1.2.ОтличиеЭС от другихпрограммныхпродуктов.

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

базазнаний

входная механизм заключения

информация вывода

рис.1

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

В любоймомент временив системе существуюттри типа знаний:

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

- Структурированныединамическиезнания- изменяемыезнания о предметнойобласти. Ониобновляютсяпо мере выявленияновой информации.

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

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

Результатыанализов

и входныеданные

выбори ввод

исходныхданных

наблюдения пользователи

интерпретация правила

гипотезы усвоение вывод

заключения

рис.2 Схема работыЭС.

1.3. Отличительныеособенности.Экспертныесистемы первогои второго поколения.

1. Экспертизаможет проводиться только в однойконкретнойобласти. Так,программа,предназначеннаядля определениякон-

фигурациисистем ЭВМ, неможет ставитьмедицинскиедиагнозы.

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

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

4. Эти системымогут объяснятьход решениязадачи понятнымпользователюспособом. Обычномы не принимаемответ эксперта,если на вопрос“Почему ?” неможем получитьлогичный ответ.Точно так жемы должны иметьвозможностьспросить систему,основаннуюна знаниях, какбыло полученоконкретноезаключение.

5. Выходныерезультатыявляютсякачественными(а не количественными).

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

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

В экспертныхсистемах первогопоколениязнания представленыследующимобразом:

1) знаниямисистемы являютсятолько знанияэксперта, опытнакоплениязнаний непредусматривается.

2) методыпредставлениязнаний позволялиописывать лишьстатическиепредметныеобласти.

3) моделипредставлениязнаний ориентированына простыеобласти.

Представлениезнаний в экспертныхсистемах второгопоколенияследующее:

1) используютсяне поверхностныезнания, а болееглубинные.Возможно дополнениепредметнойобласти.

2) ЭС можетрешать задачидинамическойбазы данныхпредметнойобласти.

1.4. Областипримененияэкспертныхсистем.

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

а) Медицинскаядиагностика.

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

б) Прогнозирование.

Прогнозирующиесистемы предсказываютвозможныерезультатыили событияна основе данныхо текущем состоянииобъекта. Программнаясистема “ЗавоеваниеУолл-стрита”может проанализироватьконъюнктурурынка и с помощьюстатистическихметодов алгоритмовразработатьдля вас планкапиталовложенийна перспективу.Она не относитсяк числу систем,основанныхна знаниях,посколькуиспользуетпроцедуры иалгоритмытрадиционногопрограммирования.Хотя пока ещеотсутствуютЭС, которыеспособны засчет своейинформациио конъюнктурерынка помочьвам увеличитькапитал, прогнозирующиесистемы ужесегодня могутпредсказыватьпогоду, урожайностьи поток пассажиров.Даже на персональномкомпьютере,установивпростую систему,основаннуюна знаниях, выможете получитьместный прогнозпогоды.

в) Планирование.

Планирующиесистемы предназначеныдля достиженияконкретныхцелей при решениизадач с большимчислом переменных.Дамасская фирмаInformat впервые вторговой практикепредоставляетв распоряжениипокупателей13 рабочих станций,установленныхв холле своегоофиса, на которыхпроводятсябесплатные15-минутныеконсультациис целью помочьпокупателямвыбрать компьютер,в наибольшейстепени отвечающийих потребностями бюджету. Крометого, компания Boeing применяетЭС для проектированиякосмическихстанций, а такжедля выявленияпричин отказовсамолетныхдвигателейи ремонта вертолетов.Экспертнаясистема XCON, созданнаяфирмой DEC, служитдля определенияили измененияконфигурациикомпьютерныхсистем типаVAX и в соответствиис требованиямипокупателя.Фирма DEC разрабатываетболее мощнуюсистему XSEL, включающуюбазу знанийсистемы XCON, с цельюоказания помощипокупателямпри выборевычислительныхсистем с нужнойконфигурацией.В отличие отXCON система XSEL являетсяинтерактивной.

г)Интерпретация.

Интерпретирующиесистемы обладаютспособностьюполучать определенныезаключенияна основе результатовнаблюдения.Система PROSPECTOR, однаиз наиболееизвестныхсистем интерпретирующеготипа, объединяетзнания девятиэкспертов.Используясочетаниядевяти методовэкспертизы,системе удалосьобнаружитьзалежи рудыстоимостьюв миллион долларов,причем наличиеэтих залежейне предполагални один из девятиэкспертов.Другая интерпретирующаясистема- HASP/SIAP. Онаопределяетместоположениеи типы судовв тихом океанепо даннымакустическихсистем слежения.

д) Контрольи управление.

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

е) Диагностиканеисправностейв механическихи электрическихустройствах.

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

ж) Обучение.

Системы,основанныена знаниях,могут входитьсоставнойчастью в компьютерныесистемы обучения.Система получаетинформациюо деятельностинекоторогообъекта (например,студента) ианализируетего поведение.Базазнаний изменяетсяв соответствиис поведениемобъекта.Примером этогообучения можетслужить компьютернаяигра,сложностькоторой увеличиваетсяпо мере возрастаниястепени квалификациииграющего.Одной из наиболееинтересныхобучающихЭС являетсяразработаннаяД.Ленатомсистема EURISCO,которая используетпростые эвристики.Эта системабыла опробованав игреТ.Тревевеллера,имитирующаябоевые действия.Суть игры состоитв том,чтобы определитьсостав флотилии,способнойнанести поражениев условияхнеизменяемогомножестваправил.СистемаEURISCOвключилав состав флотилиинебольшие, способныепровести быструюатаку корабли и одно оченьмаленькоескоростноесудно и постоянновыигрывалав течение трехлет,несмотря нато,что встремлениивоспрепятствовать этому правилаигры меняликаждый год.

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

1.5. КритерийиспользованияЭС для решениязадач.

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

1. Данные изнания надежныи не меняютсясо временем.

2. Пространствовозможныхрешений относительноневелико.

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

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

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

Таблица 1.Критерий применимостиЭС.

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

В целомЭС не рекомендуетсяприменять длярешения следующихтипов задач:

- математических,решаемых обычнымпутем формальныхпреобразованийи процедурногоанализа;

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

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

1.6. Ограниченияв применениеэкспертныхсистем..

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

1. БольшинствоЭС не вполнепригодны дляпримененияконечнымпользователем.Если вы не имеетенекоторогоопыта работыс такими системами,то у вас могутвозникнутьсерьезныетрудности.Многие системыоказываютсядоступнымитолько темэкспертам,которые создавалииз базы знаний.

2. Вопросно-ответныйрежим, обычнопринятый втаких системах,замедляетполучениерешений. Например,без системыMYCIN врач может(а часто и должен)принять решениезначительнобыстрее, чемс ее помощью.

3. Навыки системыне возрастаютпосле сеансаэкспертизы.

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

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

6. ЭС неприменимыв больших предметныхобластях. Ихиспользованиеограничиваетсяпредметнымиобластями, вкоторых экспертможет принятьрешение завремя от несколькихминут до несколькихчасов.

7. В тех областях,где отсутствуютэксперты (например,в астрологии),применениеЭС оказываетсяневозможным.

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

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

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

1.7.ПреимуществаЭС перед человеком- экспертом.

Системы,основанныена знаниях,имеют определенныепреимуществаперед человеком-экспертом.

1. У них нетпредубеждений.

2. Они не делаютпоспешныхвыводов.

3. Эти системыработаютсистематизировано,рассматриваявсе детали,часто выбираянаилучшуюальтернативуиз всех возможных.

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

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

6. Эти системыне заменяютспециалиста,а являютсяинструментомв его руках.

1.8. Историяразвития экспертныхсистем.

1.8.1. Основныелинии развитияЭС.

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

1.META-DENDRAL.СистемаDENDRALпозволяетопределитьнаиболее вероятнуюструктурухимическогосоединенияпо экспериментальнымданным (масс-спектрографии,данным ядерноммагнитногорезонанса идр.).M-Dавтоматизируетпроцесс приобретениязнаний дляDENDRAL.Она генерируетправила построенияфрагментовхимическихструктур.

2.MYCIN-EMYCIN-TEIREIAS-PUFF-NEOMYCIN.Это семействомедицинскихЭС и сервисныхпрограммныхсредств дляих построения.

3.PROSPECTOR-KAS.PROSPECTOR- предназначенадля поиска(предсказания)месторожденийна основегеологическиханализов.KAS-система приобретениязнаний для PROSPECTOR.

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

5.HEARSAY-HEARSAY-2-HEARSAY-3-AGE.Первые две системыэтого рядаявляются развитиеминтеллектуальнойсистемы распознаванияслитной человеческойречи,слова которойберутся иззаданногословаря. Этисистемы отличаютсяоригинальнойструктурой,основаннойна использованиидоски объявлений-глобальнойбазы данных,содержащейтекущие результатыработы системы.В дальнейшемна основе этихсистем былисозданы инструментальныесистемы HEARSAY-3 иAGE (Attempt to Generalize- попыткаобщения) дляпостроенияЭС.

6. СистемыAM (Artifical Mathematician- искусственныйматематик) иEURISCO были разработаныв Станфордскомуниверситетедоктором Д.Ленатом дляисследовательскихи учебных целей.Ленат считает,что эффективностьлюбой ЭС определяетсязакладываемымив нее знаниями.По его мнению,чтобы системабыла способнак обучению, внее должно бытьвведено околомиллиона сведенийобщего характера.Это примерносоответствуетобъему информации,каким располагаетчетырехлетнийребенок сосреднимиспособностями.Ленат такжесчитает, чтопуть созданияузкоспециализированныхЭС с уменьшеннымобъемом знанийведет к тупику.

В системуAM первоначальнобыло заложенооколо 100 правилвывода и более200 эвристическихалгоритмовобучения, позволяющихстроить произвольныематематическиетеории и представления.Сначала результатыработы системыбыли весьмамногообещающими.Она могласформулироватьпонятия натуральногоряда и простыхчисел. Крометого, она синтезировалавариант гипотезыГольдбаха отом, что каждоечетное число,большее двух,можно представитьв виде суммыдвух простыхчисел. До сихпор не удалосьни найти доказательстваданной гипотезы,ни опровергнутьее. Дальнейшееразвитие системызамедлилосьи было отмечено,что несмотряна проявленныена первых порах“математическиеспособности”,система неможет синтезироватьновых эвристическихправил, т.е. еевозможностиопределяютсятолько темиэвристиками,что были в нееизначальнозаложены.

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

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

С 1990 годадоктор Ленатво главе исследовательскойгруппы заняткодированиеми вводом несколькихсот тысяч элементовзнаний, необходимых,по его мнению,для создания“интеллекту-

альной”системы. Этотпроект названCyc (“Цик”, от английскогослова enciklopaedia).

1.8.2.Проблемы,возникающиепри созданииЭС.Перспективыразработки.

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

КаталогЭС и инструментальных программныхсредств дляих разработки,опубликованныйв США в 1987 году,содержит более1000 систем (сейчасих уже значительнобольше). В развитыхзарубежныхстранах сотнифирм занимаютсяих разработкойи внедрением.Имеются иотечественныеразработкиЭС, в том числе- нашедшийпромышленноеприменение.

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

Перваятрудностьвозникает всвязи с постановкойзадач. Большинствозаказчиков,планируя разработкуЭС, в следствиенедостаточнойкомпетентностив вопросахпримененияметодов ИИ,склонна значительнопреувеличиватьожидаемыевозможностисистемы.Заказчик желаетувидеть в нейсамостоятельномыслящегоэксперта висследуемойобласти, способногорешать широкийкруг задач.Отсюда и типичныепервоначальныепостановкизадачи по созданиюЭС: “РазработатьЭС по обработкеизображения”;“Создать медицинскиеЭС по лечениюзаболеванийопорно-двигательногоаппарата удетей”. Однако,как уже отмечалось,мощностьэвристическихметодов решениязадач при увеличенииобщности ихпостановкирезко уменьшается.Поэтому наиболеецелесообразно(особенно припопытке созданияЭС в области,для которойу разработчиковеще нет опытасоздания подобныхсистем) ограничитьсядля начала неслишком сложнойобозримойзадачей врассматриваемойобласти, длярешения которойнет простогоалгоритмическогоспособа (тоесть неочевидно,как написатьпрограмму длярешения этойзадачи, не используяметоды обработкизнаний). Крометого, важно,чтобы ужесуществоваласложившаясяметодика решенияэтой задачи“вручную” иликакими-либорасчетнымиметодами. Дляуспешной разработкиЭС необходимыне только четкаяи конкретнаяпостановказадач, но иразработкаподробного(хотя бы словесного)описания “ручного”(или расчетного)метода ее решения.Если это сделатьзатруднительно,дальнейшаяработа по построениюЭС теряет смысл.

Втораяи основнаятрудность -проблема приобретения(усвоения) знаний.Эта проблемавозникает при“передаче”знаний, которымиобладаютэксперты-люди,ЭС. Разумеетсядля того, чтобы“обучить” имкомпьютернуюсистему, преждевсего требуетсясформулировать,систематизироватьи формализоватьэти знания “набумаге”. Этоможет показатьсяпарадоксальным,но большинствоэкспертов (заисключением,может быть,математиков),успешно используяв повседневнойдеятельностисвои обширныезнания, испытываютбольшие затрудненияпри попыткесформулироватьи представитьв системномвиде хотя быосновную частьэтих знаний:иерархию используемыхпонятий, эвристики,алгоритмы,связи междуними. Оказывается,что для подобнойформализациизнаний необходимопределенныйсистематическийстиль мышления,более близкийматематиками программистам,чем, например,юристам и медикам.Кроме того,необходимы,с одной стороны,знания в областиматематическойлогики и методовпредставлениязнаний, с другой- знания возможностиЭВМ, из программногообеспечения,в частности,языков и системпрограммирования.

Такимобразом, выясняется,что для разработкиЭС необходимоучастие в нейособого родаспециалистов,обладающихуказаннойсовокупностьюзнаний и выполняющихфункции “посредников”между экспертамив предметнойобласти икомпьютерными(экспертными)системами. Ониполучили названиеинженеры знаний(в оригинале- knowledgeengineers), а сампроцесс разработкиЭС и другихинтеллектуальныхпрограмм, основанныхна представлениии обработкезнаний - инженериейзнаний (knowledgeengineering). Вразвитыхзарубежныхстранах специальность“инженер знаний”введена вомногих вузах,в нашей странеосновы инженериизнаний изучаютсяпока в рамкахспециализацийпо системномупрограммированию.Функции экспертаи инженеразнаний редкосовмещаютсяв одном лице.Чаще функцииинженера знанийвыполняетразработчикЭС. Как показалопыт многихразработок,для первоначальногоприобретениязнаний, в которыхучаствуютэксперты, инженерызнаний иразработчикиЭС, требуетсяактивная работавсех трех категорийспециалистов.Она может длитьсяот несколькихнедель до несколькихмесяцев.

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

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

Однойиз причин неудачв созданииЭС стала недооценкаавторами ЭСобъемов и ролинеявных знаний.Системы, базызнаний которыхсоздавалисьна основесправочников,в лучшем случаетак справочникамии остались.Большинствоже таких системоказывалисьдаже хужесправочников,так как сковывалиисследовательскуюмысль пользователя.Вторым “узкимместом” ЭСоказаласьмодель, на которойбыли основаныих первые экземпляры,и лишь модельзнаний, принимающаявид пороговойнаправленнойиерархическойсети с возможностьювыбора в конечномиз логическихузлов (где каждаяотдельнаяситуация похожана дерево слистьями), можетстать базойдля построенияЭС.

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

Рассмотримфакторы, стимулировавшиеразвитие системс базами знаний:

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

-разработаныновые технологиисоздания баззнаний, являетсянеобходимымсредством,которое можетизменить бизнес-поцесс;

-современныесистемы реализованыне наспециализирован-ном,а на стандартномоборудовании.

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

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

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

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

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

Методикаобъектно-ориентированногопрограммированияоснована намодели, напоминающейобразы, возникающиев мозгу аналитика,которая представляетпредметы ипроцессы в видеобъектов исвязей междуними. Наблюдаясобытие, экспертлегко выделяетзнакомые образы.Для решенияпроблем ониспытываетконкретныеправила, рассматриваяпри этом исследуемуюпроблему подопределеннымракурсом.

Приразработкесистем автоматизированногопроектирования(САПР) уже нельзяобойтись безЭС; их использованиепризнаноэкономическивыгодным.

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

Глава 2. Структурасистем, основанныхна знаниях

2.1. КритерийпользователяЭС

СтруктураЭС изображенана схеме:

пользователь

эксперт+ диалоговый

инженерзнаний процессор

подсистема подсистема

приобретения база знаний вывода

знаний

подсистема

объяснения

рис.3

Экспертныесистемы имеютдве категориипользователей и два отдельных“входа”, соответствующихразличным целямвзаимодействияпользователейс ЭС:

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

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

2.2. Подсистемаприобретениязнаний

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

2.3. Базазнаний

База знаний-наиболее важнаякомпонентаэкспертнойсистемы, накоторой основаныее «интеллектуальныеспособности».В отличие отвсех остальныхкомпонентЭС, база знаний-«переменная»часть системы,которая можетпополнятьсяи модифицироватьсяинженерамизнаний и опыта использованиеЭС, между консультациями(а в некоторыхсистемах и впроцессеконсультации).Существуетнесколькоспособовпредставлениязнаний в ЭС,однако общимдля всех нихявляется то,что знанияпредставленыв символьнойформе(элементарнымикомпонентамипредставлениязнаний являютсятексты, спискии другие символьныеструктуры). Темсамым, в ЭСреализуетсяпринцип символьнойприродырассуждений,который заключаетсяв том, что процессрассужденияпредставляетсякак последовательностьсимвольныхпреобразований.

Наиболеераспространенныйспособ представлениязнаний - в видеконкретныхфактов иправил,по которым изимеющихсяфактов могутбыть выведеныновые. Фактыпредставлены,например, ввиде троек:

(АТРИБУТ ОБЪЕКТ ЗНАЧЕНИЕ).

Такой фактозначает, чтозаданный объектимеет заданныйатрибут (свойства)с заданнымзначением.Например, тройка (ТЕМПЕРАТУРА ПАЦИЕНТ1 37.5)представляетфакт «температура больного,обозначаемогоПАЦИЕНТ1, равна37.5». В более простыхслучаях фактвыражаетсянеконкретнымзначениематрибута, акаким либопростым утверждением,которое можетбыть истиннымили ложным,например: «Небопокрыто тучами».В таких случаяхфакт можнообозначитькаким-либократким именем(например, ТУЧИ)или использоватьдля представленияфакта сам текстсоответствующейфразы.

Правилав базе знанийимеют вид:

ЕСЛИ А ТО S,где А- условие;S-действие.Действие Sисполняется,если А истинно.Наиболее частодействие S,так же, как иусловие, представляетсобойутверждение,которое можетбыть выведеносистемой (тоесть становитсяей известной),если истинноусловие правилаА.

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

Простойпример правилаиз повседневнойжизни:

ЕСЛИ небопокрыто тучами

ТО скоропойдет дождь.

В качествеусловия Aможет выступатьлибо факт(какв данном примере),либо несколькофактовA1,...,AN, соединенныелогическойоперацией и:

A1и A2и ...и AN.

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

ЕСЛИ

небопокрыто тучамии барометрпадает

ТО

скоро пойдетдождь. (Правило1).

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

Если системане может вывестинекоторый факт,истинностьили ложностькоторого требуетсяустановить,то системаспрашиваето нем пользователя.Например:

ВЕРНО ЛИ,ЧТО небо покрытотучами?

При полученииположительногоответа отпользователяфакт«Небопокрыто тучами»включаетсяв рабочеммножество.

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

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

2.4. Подсистемавывода

2.4.1 Подсистемавывода,способылогическоговывода

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

Цель ЭС- вывестинекоторыйзаданный факт,который называетсяцелевымутверждением(то есть в результатепримененияправил добитьсятого, чтобыэтот факт былвключен в рабочеемножество),либо опровергнутьэтот факт (тоесть убедиться,что его вывестиневозможно,следовательно,при данномуровне знанийсистемы онявляется ложным).Целевое утверждениеможет быть либо«заложено»заранее в базузнаний системы,либо извлекаетсясистемой издиалога спользователем.

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

Прямойпорядок вывода-от фактов, которыенаходятся врабочем множестве,к заключению.Если такоезаключениеудается найти,то оно заноситсяв рабочее множество.Прямой выводчасто называютвыводом,управляемымданными.

Для иллюстрациидобавим к нашемупримеру базызнаний о погодееще одно правило:

ЕСЛИ скоропойдет дождь

ТО нужновзять с собойзонтик. (правило2)

Предположимтакже, что факты«Небо покрытотучами» и «Барометрпадает» имеютсяв рабочем множестве,а целью системыявляется ответна вопроспользователя:

«Нужно взятьс собой зонтик?»

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

Шаг 1.Рассматриваетсяправило 1. Егоусловие истинно,так как обаэлемента коньюнкцииимеются в рабочеммножестве.Применяемправило 1; добавляемк рабочемумножеству факт”Скоро пойдетдождь”.

Шаг 2.Рассматриваетсяправило 2. Егоусловие истинно,т.к. утверждениеиз условияимеется в рабочеммножестве.Примеряемправило 2; добавляемк рабочемумножеству факт“Нужно взятьс собой зонтик”.Целевое утверждениевыведено.

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

В рассматриваемомпримере выводцелевого утверждения“Нужно взятьс собой зонтик”обратной цепочкойрассужденийвыполняетсяследующимобразом:

Шаг 1.Рассматриваетсяправило 1. Ононе содержитцели в правойчасти. Переходимк правилу 2.

Шаг 2.Рассматриваетсяправило 2. Оносодержит цельв правой частиправила. Переходимк правой частиправила ирассматриваемв качестветекущей целиутверждения “Скоро пойдетдождь”.

Шаг 3.Текущей целинет в рабочеммножестве.Рассмотримправило 1, котороесодержит цельв правой части.Обе компонентыего условияимеются в рабочеммножестве, такчто условиеистинно. Применяемпривило 1; врезультатевыводим утверждение“Скоро пойдетдождь”; котороебыло нашейпредыдущейцелью.

Шаг 4.Применяемправило 2, условиемкоторого являетсяданное утверждение.Получаем выводисходногоутверждения.

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

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

Рис 4. Стратегиявывода.

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

Обратныйвывод Прямойвывод

4 Начало 1

3 поиска 2

5 2 Начало 3

6 1 поиска 4

7

Заключения

Заключения

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

Начало

8 Начало поиска 1

поиска 12

7 2 13

1 11

6 3

2 10

5 4

3 9

4 5

8

6 Заключения

7

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

2.4.2. Компонентвывода

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

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

Мэриискала ключ.

Здесь дляслова «ключ»допустимы какминимум двазначения «родник»и «ключ от квартиры».В следующихже двух предложенияходно и то жеслово имеетсовершенноразные значения:

Мызаблудилисьв чаще.

Нужночаще ходитьв театр.

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

ЕСЛИ Белыйавтомобильлегко заметитьночью

И АвтомобильДжека белый

ТО АвтомобильДжека легкозаметить ночью

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

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

2.4.3. Управляющийкомпонент.

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

1. Сопоставление-образец правиласопоставляетсяс имеющимисяфактами;

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

3. Срабатывание-если образецправила присопоставлениисовпал с какими-либо фактамииз рабочегомножества, топравило срабатывает.

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

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

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

сопоставление конфликтное критерий

множество выбора правил

разрешение

конфликта

рабочее база

множество правил

выполняемое действие

правило

рис.5 Циклработы интерпретатора

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

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

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

ких структурныхзнаний) и структурныхдинамическихзнаниях (эвристиках).

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

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

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

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

Участиепользователявыражаетсяв следующем:

- конкретныезадачи. Пользователь,сталкиваясьс конкретнымипроблемами,может объяснитьвозникновениепроблем и предложитьвозможныеварианты ихрешения;

- общение.Интерфейспользователядолжен соответствоватьсловарю пользователяи уровню егоподготовки;

- установлениесвязей. Знакомствопользователяс причинамии последствиями,вызывающимито или иноедействие впроцессефункционированиясистемы, неоценимов определениивзаимосвязейфактов в базезнаний;

- обратнаясвязь. Отличительнойособенностьюудобной виспользованииЭС являетсяее способностьобъяснитьконечномупользователюход своихрассуждений.

2.5. Диалогс ЭС. Объяснение.

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

Итак, напримере простойЭС и базы знанийдиалог пользователяс системойможно представитьсебе следующимобразом:

Система:Вы хотите узнать,нужно ли взятьс собой зонтик?

Пользователь: Да.

Система: Верно ли, чтонебо покрытотучами?

Пользователь: Да.

Система: Верно ли, чтобарометр падает?

Пользователь: Да.

Система:(после некоторого“размышления”)Нужно взятьс собой зонтик.

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

Чтобыудостоверитьсяв “разумности”и “компетентности”ЭС, пользовательможет обратитьсяк ее подсистемеобъяснения.

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

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

Нужновзять с собойзонтик.

правило2

Скоропойдет дождь.

правило1

Небо покрытотучами. Барометрпадает.

Здесь впростых рамкахприведены узлыдерево вывода,соответствующиефактам, в двойных-узлы, соответствующиеназваниемправил. Сверхуот узла- правилаизображен факт,находящийсяв его правойчасти (в принятойтерминологии-предокузла- правила).Листьядерева (узлы,образующиеего нижний“ярус”), соответствуютфактам, истиностныезначения которыхзапрашиваютсяу пользователя,или первоначальноизвестнымфактам из базызнаний, кореньдерева(самый верхнийузел)- целевомуутверждению.

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

Рассмотримтеперь работуподсистемыобъяснения.Для полученияобъясненияв процессеконсультациипользовательможет “перехватитьинициативу”диалога в тотмомент, когдасистема задаеточереднойвопрос, “переспро-

сив” в ответсистему, почемуона его задала.Таким образом,вместо ответана вопрос системы,пользовательможет задатьей встречныйвопрос:

ПОЧЕМУ?

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

Пусть внашем примередиалога с ЭСпользовательвместо ответана вопрос системы:“Верно ли, чтобарометр падает?”задает ей встречныйвопрос: ”ПОЧЕМУ?”.ЭС обращаетсяк подсистемеобъяснения,которая выдаетпользователюследующеесообщение:

[1.0] Эта информациянеобходима,чтобы установить,что скоро пойдетдождь.

Ранее былоустановлено,что :

[1.1] Небо покрытотучами.

Следовательно,если:

[1.2] Барометрпадает, то скоропойдет дождь.

(Правило1).

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

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

ПОЧЕМУ?

(“Почемунеобходимоустановить,что скоро пойдетдождь?”). Второйответ системыаналогиченпервому; в немуказывается,что это необходимодля примененияправила 2 с цельюустановить,что нужно взятьс собой зонтик:

[2.0] Эта информациянеобходима,чтобы установить,что нужно взятьс собой зонтик.Если:

[2.1] Скоропойдет дождь,то нужно взятьс собой зонтик.

(Правило2).

Утверждение[2.0] являетсяисходным целевымутверждениемсистемы. Такимобразом, теперьход рассужденийсистемы пользователюполностьюпонятен. Вопрос“ПОЧЕМУ?” позволяетпроследитьход рассужденийсистемы отпосылок кзаключениям.Однако дляболее детальногоосмысленияпроцесса выводаудобно былобы иметь возможностьизучать егои в противоположномпорядке- отзаключенийк посылкам. Дляэтого служитдругой вопрос,который также“понимает”подсистемаобъяснений:

КАК N?

где N- номерутверждения,выданный подсистемойобъясненияна одном изпредыдущихшагов диалога.Например, вответ на вопрос:

КАК 2.0?

“Как полученутверждение2.0?” подсистемаобъяснениявыдает информациюв правиле, котороебыло примененодля его получения:

[3.1] Используетсяправило 2, заключениемкоторого является, что нужновзять с собойзонтик.

Чтобыполучить болееподробнуюинформациюо том, как былоиспользованоправило 2, следуетповторно задатьвопрос “КАК?”:

КАК 3.1?

“Как былоиспользованоправило 2?”. Ответсистемы:

Ранее установлено,что:

[4.1] Скоро пойдетдождь.

Следовательно,нужно взятьс собой зонтик.

Выяснимтеперь, какполучено утверждение4.1:

КАК 4.1?

Ответ системы:

[5.1] Используетсяправило 1, заключениемкоторого является,что скоро пойдетдождь. Наконец,выясним. какиспользованоправило 1:

КАК 5.1?

Ответ системы:

Ранее установлено,что:

[6.1] Небо покрытотучами.

[6.2] Барометрпадает.

Следовательноскоро пойдетдождь.

Как былиполучены утверждения6.1 и 6.2 пользовательпомнит, посколькуон отвечал навопросы системыотносительноэтих утверждений.Если все же онзадаст системевопрос КАК6.1? или КАК 6.2?, тосистема напомнитему об этом.

Описаннаямодель объясненияиспользуетсяв системе MYCIN.Достоинствомее являетсявозможностьполученияобъяснениялюбого шагаработы системы,недостатком-жесткая привязкак дереву вывода.Для пользователя-непрограммистатакой способобъясненияможет показатьсяизлишне детализованными слишком формальным,а нужно былобы объяснениена “более высокомуровне”- с точкизрения здравогосмысла и безуглубленияв детали. Подобныемодели объяснениятолько начинаютпоявлятьсяв ЭС и требуютболее сложнойорганизациизнаний.

Глава 3. Стратегииуправлениявыводом

3.1. Разработкастратегии.

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

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

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

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

3.2. Повышениеэффективностипоиска

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

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

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

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

При поискев ширину, напротив,система проанализируетвсе признаки,находящиесяна одном уровнепространствасостояний, илишь затемперейдет кпризнакамследующегоуровня детальности.

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

б) Альфа-бета алгоритм.

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

в) Разбиениена подзадачи.

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

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

Рассмотрим,например, задачуо проезде наавтомобилеиз Пало-Альто(штат Калифорния)в Кембридж(штат Массачусетс).Эта задачаможет бытьсведена, скажем,к следующимподзадачам:

Подзадача1. Проехатьиз Пало-Альтов Сан-Франциско.

Подзадача2.Проехатьиз Сан-Францисков Чикаго.

Подзадача3. Проехатьиз Чикаго вОлбани.

Подзадача4. Проехатьиз Олбани вКембридж.

Здесь решениевсех четырехподзадач обеспечилобы некотороерешение первоначальнойзадачи.

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

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

г) Использованиеформальнойлогики прирешении задач.

Часто длярешения задачлибо требуетсяпроведениелогическогоанализа вопределенномобъеме, либопоиск решениясущественноотличаетсяпосле такогоанализа. Иногдатакой анализпоказывает,что определенныепроблемы

неразрешимы.В игре в пятнадцать,например, можнодоказать, чтоцелевая конфигурация(1) не может бытьполучена изначальнойконфигурации(2).

1. 2.

15	14	13	12
11	10	9	8
7	6	5	4
3	2	1 1

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15

3.3. Представлениезадач в пространствесостояний

3.3.1. Описаниесостояний

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

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

3.3.2 Операторы.Состояния иоператоры.

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

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

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

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

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

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

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

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

Такимобразом, мывидим, что дляполного представлениязадачи в пространствесостоянийнеобходимозадать:

а) формуописания состоянийи, в частности,описание начальногосостояния;

б) множествооператорови их воздействий на описаниясостояний;

в) свойстваописания целевогосостояния.

Пространствосостоянийполезно представлятьсебе в виденаправленногографа.

3.4.3. Записьв виде графа.

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

Последовательностьвершин n_i1,n_i2,...,n_ik.,в которой каждаявершина n_ij дочерняядля n_i,j-1,j=2,k, называетсяпутем длиныk от вершиныn_i1, квершине n_ik.Если существуетпуть, ведущийот вершины n_i к вершинеn_j, товершину n_j называютдостижимойиз вершины n_i или потомкомвершины n_i. В этомслучае вершинаn_i называетсятакже предкомдля вершиныn_j. Видно,что проблеманахожденияпоследовательностиоператоров,преобразующиходно состояниев другое, эквивалентназадаче поискапути на графе.

Глава 4. Методыпоиска в пространствесостояний

4.1. Процессыпоиска на графе

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

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

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

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

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

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

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

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

4.2. Методыперебора

4.2.1. Методыполного перебора

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

1) Поместитьвершину в список,называемыйОТКРЫТ.

2) Если списокОТКРЫТ пуст,то на выходподается сигнало неудаче поиска,в противномслучае переходитьк следующемушагу.

3) Взять первуювершину изсписка ОТКРЫТи перенестиее в

список ЗАКРЫТ;назовем этувершину n.

4) Раскрытьвершину n, образоваввсе вершины,непосредственноследующие заn. Если непосредственноследующихвершин нет, топереходитьсразу же к шагу(2). Поместитьимеющиесянепосредственноследующие заn вершины в конецсписка ОТКРЫТи построитьуказатели,ведущие от нихназад к вершинеn.

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

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

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

Пуск

ПоместитьS в список

ОТКРЫТ

нет да

Пустли список Неудача

ОТКРЫТ?

Взятьпервую вершинуиз списка ОТКРЫТ

и поместитьее в списокЗАКРЫТ.

Обозначитьэту вершинучерез n

Раскрытьn. Поместитьдочерние

вершиныв конец спискаОТКРЫТ.

Провестиот них к n указателю.

нет Являютсяли да

какие-либоиз Успех

дочернихвершин

целевыми?

рис.6 Блок-схема программыалгоритмаполного перебора

для дерева.

4.2.2 Методравных цен.

Могутвстретитсязадачи, в которыхрешению предъявляютсякакие-то иныетребования,отличные оттребованияполучениянаикратчайшейпоследовательностиоператоров.Присваиваниедугам деревьевопределенныхцен (с последующимнахождениемрешающего пути,имеющего минимальнуюстоимость)соответствуетмногим из такихобещанныхкритериев.Более общийвариант методаполного перебора,называемыйметодом равныхцен, позволяетво всех случаяхнайти некоторыйпуть от начальнойвершины к целевой,стоимостькоторого минимальна.В то время какв выше описанномалгоритмераспространяютсялинии равнойдлины пути отначальнойвершины, в болееобщем алгоритме,который будетописан ниже,распространяютсялинии равнойстоимости пути.Предполагается,что нам заданафункция стоимостиc(n_i,n_j),дающая стоимостьперехода отвершины n_iк некоторойследующей заней вершинеn_j.

В методеравных цен длякаждой вершиныn в дереве переборанам нужно помнитьстоимость пути,построенногоот начальнойвершины s к вершинеn. Пусть g(n)- стоимостьот вершины s квершине n в деревеперебора. Вслучае деревьевперебора мыможем бытьуверены, чтоg(n) является ктому же стоимостьютого пути, которыйимеет минимальнуюстоимость (т.к.этот путьединственный).

В методеравных ценвершины раскрываютсяв порядке возрастаниястоимости g(n).Этот методхарактеризуетсятакой последовательностьюшагов:

1) Поместить начальнуювершину s в список,называемыйОТКРЫТ. Положитьg(s)=0.

2) Если списокОТКРЫТ пуст,то на выходподается сигнало неудаче поиска,в противномслучае переходитьк следующемушагу.

3) Взять изсписка ОТКРЫТту вершину, длякоторой величинаg имеет наименьшеезначение, ипоместить еев список ЗАКРЫТ.Дать этой вершиненазвание n. (Вслучае совпадениязначений выбиратьвершину сминимальнымиg произвольно,но всегда отдаваяпредпочтениецелевой вершине.)

4) Если n естьцелевая вершина,то на выходвыдать решающийпуть, получаемыйпутем просмотраназад в соответствиис указателями;в противномслучае переходитьк следующемушагу.

5) Раскрытьвершину n, построиввсе непосредственноследующие заней вершины.(Если таковыхнет переходитьк шагу (2).) Длякаждой из такойнепосредственноследующей(дочерней) вершиныn_i вычислитьстоимость g(n),положив g(n_i)=g(n)+c(n,n_i).Поместить этивершины вместес соответствующимиим только чтонайденнымизначениямиg в список ОТКРЫТи построитьуказатели,идущие назадк n.

6) Перейти кшагу (2).

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

Алгоритм,работающийпо методу равныхцен, может бытьтакже использовандля поискапутей минимальнойдлины, еслипросто положитьстоимостькаждого ребраравнойединице.Если имеетсянескольконачальныхвершин, о алгоритмпросто модифицируется:на шаге (1) всеначальныевершины помещаютсяв список ОТКРЫТ.Если состояния,отвечающиепоставленнойцели, могутбыть описаныявно, то процессперебора можнопустить в обратномнаправлении,приняв целевыевершины в качественачальных ииспользуяобращениеоператора Г.

Пуск

Поместитьs в список ОТКРЫТ.

Положитьg(s)=0.

нет Пуст ли да

список неудача

ОТКРЫТ?

Взятьиз списка ОТКРЫТвершину

с наименьшимзначением g

и поместитьее в списокЗАКРЫТ.

Обозначитьее через n.

нет Является лиn да успех

вершинойцели?

Раскрытьn. Вычислитьзначение g

для дочернихвершин.

Поместитьэти вершиныв список ОТКРЫТ.

Провестиот них указателик n.

рис.7 Блок-схема программыалгоритмаравных цен длядеревьев.

4.3 Методперебора вглубину.

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

Глубинакорня дереваравна нулю.

Глубиналюбой последующейвершины равнаединице плюсглубина вершины,которая непосредственноей предшествует.

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

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

Методперебора вглубину определяетсяследующейпоследовательностьюшагов:

1) Поместить начальнуювершину в список,называемыйОТКРЫТ.

2) Если списокОТКРЫТ пуст,то на выходподается сигнало неудаче поиска,в противномслучае перейтик шагу (3).

3) Взять первуювершину изсписка ОТКРЫТи перенестив список ЗАКРЫТ.Дать этой вершиненазвание n.

4) Если глубинавершины n равнаграничнойглубине, топереходитьк (2), в противномслучае к (5).

5) Раскрытьвершину n, построиввсе непосредственноследующие заней вершины.Поместить их(в произвольномпорядке) в началосписка ОТКРЫТи построитьуказатели,идущие от нихк n.

6) Если однаиз этих вершинцелевая, то навыход выдатьрешение , просматриваядля этогосоответствующиеуказатели, впротивномслучае переходитьк шагу (2).

На рис.8приведена блок-схема для методаперебора вглубину.

Пуск

Поместитьs в список ОТКРЫТ.

нет Пуст ли да

список неудача

ОТКРЫТ?

Взятьпервую вершинуиз списка

ОТКРЫТ

и поместитьее в списокЗАКРЫТ.

Обозначитьее через n.

да Равнали глубина нет

n граничнойглубине

Раскрытьn. Вычислитьзначение g

для дочернихвершин.

Поместитьэти вершиныв список ОТКРЫТ.

Провестиот них указателик n

Являютсяли

нет какие- либо да

из дочернихвершин успех

целевыми?

рис.8 Блок-схемапрограммыалгоритмапоиска в глубинудля деревьев.

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

4.4. Изменениепри переборена произвольныхграфах

При переборена графах, а нена деревьях,нужно внестинекоторыеестественныеизменения вуказанныеалгоритмы. Впростом методеполного переборане нужно вноситьникаких изменений,следует лишьпроверять, ненаходитьсяли уже вновьпостроеннаявершина в списокОТКРЫТ илиЗАКРЫТ по тойпричине, чтоона уже строиласьраньше в результатераскрытиякакой- то вершины.Если это так,то ее не нужновновь помещатьв список ОТКРЫТ.

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

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

4.5. Обсуждениеэвристическойинформации

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

Для многихзадач можносформулироватьправила, позволяющиеуменьшить объемперебора. Всетакие правила,используемыедля ускоренияпоиска, зависятот специфическойинформациио задаче, представляемойв виде графа.Будем называтьтакую информациюэвристическойинформацией (помогающейнайти решение)и называтьиспользующиеее процедурыпоиска эвристическимиметодамипоиска. Одиниз путей уменьшитьперебор состоитв выборе более“информированного” оператора Г,который нестроит многоне относящихсяк делу вершин.Этот способприменим какв методе полногоперебора, таки в методе переборав глубину. Другойпуть состоитв использованииэвристическойинформациидля модификациишага (5) алгоритмаперебора вглубину. Вместотого, чтобыразмещать вновьпостроенныевершины впроизвольномпорядке в началесписка ОТКРЫТ,их можно расположитьв нем некоторымопределеннымобразом, зависящимот эвристическойинформации.Так, при переборев глубину впервую очередьбудет раскрыватьсята вершина,которая представляетсянаилучшей.

Болеегибкий (и болеедорогой) путьиспользованияэвристическойинформациисостоит в том,чтобы, согласнонекоторомукритерию, накаждом шагепереупорядочиватьвершины спискаОТКРЫТ. В этомслучае перебормог бы идтидальше в техучастках границы,которые представляютсянаиболееперспективными.Для того, чтобыприменитьпроцедуруупорядочения,нам необходимамера, котораяпозволяла быоценивать“перспективность”вершин. Такиемеры называютоценочнымифункциями.

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

4.5.Использованиеоценочныхфункций

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

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

Условимсярасполагатьвершины, предназначенныедля раскрытия,в порядке возрастанияих значенийфункции f. Тогдаможно использоватьнекоторыйалгоритм (подобныйалгоритмуравных цен), вкотором дляочередногораскрытиявыбираетсята вершинасписка ОТКРЫТ,для которойзначение fоказываетсянаименьшим.Будем называтьтакую процедуруалгоритмупорядоченногоперебора.

Чтобыэтот алгоритмупорядоченногоперебора былприменен дляперебора напроизвольныхграфах (а нетолько на деревьях),необходимопредусмотретьв нем возможностьработы в случаепостроениявершин, которыеуже имеютсялибо в спискеОТКРЫТ, либов списке ЗАКРЫТ.При использованиинекоторойпроизвольнойфункции f нужноучесть, чтовеличина f длянекоторойвершины изсписка ЗАКРЫТможет понизится.если к ней найденновый путь(f(n) может зависетьот пути из s кn даже для вершиниз списка ЗАКРЫТ).Следовательно,мы должны тогдаперенести такиевершины назадв список ОТКРЫТи позаботитьсяоб изменениинаправлений соответствующихуказателей.

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

1) Поместитьначальнуювершину s в список,называемыйОТКРЫТ, и вычислитьf(s).

2) Если список ОТКРЫТ пуст,то на выходдается сигнало неудаче; впротивномслучае переходик следующемуэтапу.

3) Взять изсписка ОТКРЫТту вершину, длякоторой f имеетнаименьшеезначение, ипоместить еев список ЗАКРЫТ.Дать этой вершиненазвание n. (Вслучае совпадениязначений выбиратьвершину сминимальнымиf произвольно,но всегда отдаваяпредпочтениецелевой вершине.)

4) Если n естьцелевая вершина,то на выходвыдать решающийпуть, получаемыйпрослеживаниемсоответствующихуказателей;в противномслучае переходитьк следующемушагу.

5) Раскрытьвершину n, построиввсе непосредственноследующие заней вершины.(Если таковыхнет переходитьк шагу (2).) Длятакой дочернейвершины n_iвычислитьзначение f(n_i).

6) Связатьс теми из вершинn_i , которыхеще нет в спискахОТКРЫТ илиЗАКРЫТ, толькочто прочитанныезначения f(n_i).Поместить этивершины в списокОТКРЫТ и провестиот них к вершине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. Д. Н. Марселлус.Программированиеэкспертныхсистем на ТурбоПрологе.- М.: Финансыи статистика,1994.

5. К. Нейлор.Как построитьсвою экспертнуюсистему.- М.:Энергоатомиздат,1991.

6. Н. Д. Нильсон.Искусственныйинтеллект.Методы поискарешений.- М.: Мир,1973.

7. В. О. Сафонов.Экспертныесистемы- интеллектуальныепомощникиспециалистов.-С.-Пб: Санкт-Петербургскаяорганизацияобщества “Знания”России, 1992.

8. К. Таунсенд,Д. Фохт. Проектированиеи программнаяреализация экспертныхсистем наперсональныхЭВМ.- М.: Финансыи статистика,1990.

9. В. Н. Убейко.Экспертныесистемы.- М.: МАИ,1992.

10. Д. Уотермен.Руководствопо экспертнымсистемам.- М.:Мир, 1980.

11. Д. Элти,М. Кумбс. Экспертныесистемы: концепциии примеры.- М.:Финансы и статистика,1987.

81

Содержание

Глава 1.Экспертныесистемы, ихособенности.Применениеэкспертных систем. Историяразвития.

1.1. Определениеэкспертныхсистем. Главноедостоинствои назначение

экспертныхсистем.

1.2. Отличиеэкспертныхсистем от другихпрограммныхпродуктов.

1.3. Отличительныеособенности.Экспертныесистемы первогои второ-

го поколения.

1.4. Областиприменения.

а) Медицинскаядиагностика.

б) Прогнозирование.

в) Планирование.

г) Интерпретация.

д) Контрольи управление.

е) Диагностиканеисправностейв механическихи электрических

устройствах.

ж) Обучение.

1.5. Критериииспользованияэкспертныхсистем длярешения задач.

1.6. Ограниченияв примененииэкспертныхсистем.

1.7. Преимуществаэкспертныхсистем передчеловеком-экспертом.

1.8. Историяразвития экспертныхсистем.

1.8.1. Основныелинии развитияэкспертныхсистем.

1.8.2. Проблемы,возникающиепри созданииэкспертныхсистем.

Перспективыразвития.

Глава 2.Структурасистем, основанныхна знаниях.

2.1. Категориипользователейэкспертныхсистем.

2.2. Подсистемаприобретениязнаний.

2.3. База знаний.

2.4. Подсистемавывода.

2.4.1. Подсистемавывода, способылогическоговывода.

2.4.2. Компонентавывода.

2.4.3. Управляющийкомпонент.

2.5. Диалог сэкспертнойсистемой.Объяснение.

Глава 3.Стратегииуправлениявыводом.

3.1. Разработкастратегииуправлениявыводом.

3.2. Повышениеэффективностипоиска.

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

б) Альфа-бетаалгорнтм.

в) Разбиениена подзадачи.

г) Использованиеформальнойлогики прирешении задач.

3.3. Представлениезадач в пространствесостояний.

3.3.1. Описаниесостояний.

3.3.2. Состоянияи операторы.

3.3.3. Запись ввиде графа.

Глава 4.Методы поискав пространствесостояний.

4.1. Процессыпоиска на графе.

4.2. Методыполного перебора.

4.2.1.Метод полногоперебора.

4.2.2. Метод равныхцен.

4.3. Метод переборав глубину.

4.4. Измененияпри переборена произвольныхграфах.

4.5. Обсуждениеэвристическойинформации.

4.6. Использованиеоценочныхфункций.

4.7. Использованиедругих эвристик.

4.7.1. Переборэтапами.

4.7.2. Ограничениечисла дочернихвершин.

4.7.3. Поочередноепостроениедочерних вершин.

Приложение1.

Приложение2.