1? история на изследванията по ии



страница1/3
Дата29.04.2017
Размер0.62 Mb.
#20254
  1   2   3
1? ИСТОРИЯ НА ИЗСЛЕДВАНИЯТА ПО ИИ
Това е научна област,к се развива във въображението на хората и дава надежди за едно по-високо ниво за използване на комп.с-ми. Интереса към тази област е породен от това че човек иска да научи повече за себе си и своите мисловни дейности и да позволи по-лесно общуване с комп. с-ми. Първите постижения са послужили за стимулиране на допълнвителни изследвания. Създават се различни теории и концепции к. са отхвърляни и преоткривани.

Като наука ИИ е съвсем млада. осн. понятия и идеи се формират в средата на 20 век.Идеята за ИИ датира отдавна от преди 2000 години. Други философи са се опитвали да онбяснят човешкото поведение - разсъждения и действия. Теориите за същността на тези процеси к. утвърждават представите че интелектът се създава чрез функциониране на физическа с-ма намират приложение в тази област. В математиката преди 400 години са създадени формални теории в областта на логиката, вероятностите, вземането на решения.

Първата научна разработка в областта на ИИ е на Лоран МакКълоуд и Уолтър Питс през 1943 г. В нея се разгл. идеи за знания за базовата физиология и функциите на невроните в мозъка и се прави формалин ан-з на съждителната логика. През 1950г. Алън Тюринг публикува статията "Изчислителни машини и интелигентност" в к. изказва тезата че РС може да се програмира така че да симулира интелигентно поведение. Той предлага и теста за интелигентност.

Началото на 50-те год. аспирантите във факултета по математика в Принстън Марвин Мински и Дийн Едманс създават първия невронен РС. Той е нар. SNARK и симулира работата на мрежа с 40 неврона.

1956г. в Дортмут се провежда среща к. се счита за първия форум по ИИ организирана от Джон Макарти и Марвин Мински. Младите учени Ален Нюел Харбърт Саймън,Артър Самюел,Клод Шенан и др. участват в тази среща. Те са водещи в създаването на ИИ през следващите 20 години, тогава се обявява и името ИИ.

Първият период на ИИ е от 1952 до 69г. нарича се романтичен. Усилията били насочени към построяване на "разумни машини",к. да наподобяват функционирането на чов. мозък. Типичен представител на този период е машината PERCEPTRON - модел на ретината на чов. око. Не са регистрирани обаче положителни резултати. Създадена е програма за решаване на осн. проблеми. Тя е машина наподобяваща чов. поведение при търсене на решения на основни задачи. През този период се поставят основите на т.нар. предикатна логика от Робинзон. През 1958г. Джон Макарти дефинира език за програмиране от високо ниво LISP, к. е осн. ср-во за ИИ. ПРез тази година Макарти описва програмата Advice Taker к. е първата завършена с-ма за ИИ. Създадени са и др. програми.

1958-59г. е характерна с експерименти- един от тях е Friedberg. Той прокламира схващането, че от мутации на програмни кодове може да се създаде програма за ИИ.

1960-63 г. е х-рна с разработките за невронните мрежи.

1966-74 г. се срещат няколко вида трудности - свърз. с програмите за машинен превод от един език към друг;второ - свърз. с неприложимостта на недостатъчно развитите ср-ва и методи на ИИ към реалните проблеми;трето - в следствие ограничения в базовите стр-ри на генетиката.

1960г. е открит обучаващия алгоритъм за обратно разпространение на грешката Back Propagation. Прилаганите до този момент се нар. "слаби",к. използват ограничена инф-я за обектната област и намират решения чрез обединяване на елементарни стъпки на разсъждение. Създадена е първата експертна с-ма Dendral.

MYCIN за диагностика на бактериални инфекции в кръвта. Съдържа 450 правила, работи с коефициент на увереност. Това е първата с-ма,к. може да обясни "защо нещо е такова каквото е".

PROSPECTOR -1979г. Тя е геологическа с-ма. Може да определя вероятността от находищата на определени минерали.

Фирмите започват да финансират работата на групи по ИИ. В областта на т.нар. разбиране на естествените езици обработката на знания е от съществено значение. Използва се за създаване на приятелски интерфейс към базите данни.

1973г. LUNAR позволява на геолозите да задават въпроси за скалните образци доставени от Луната.

1980г. до наши дни - навлизане на ИИ в практически използвани с-ми. R1/XCON е парвата индустриална експертна с-ма.

1981г. се появяват интилигентни РС.

Възраждането на интереса към ИИ доведе до създаване на много софтуерни разработки. Разработени са черупки "Shells" - празни с-ми к. могат да се запълнят с инф-я по желание. Поставя се началото на нова идеология на експертните с-ми. Създават се спец. РС за изпълнение на листови езици. Интереса към невронните мрежи също е обновен в областта на фи0зиката и химията. Предлага се идеята за т. нар. нормативни експертни с-ми. Създават се по-мощни методи на ИИ. Разработват се цялостни агентни архитектури. SOAR - 1990г намира приложение в обработката на планове.
СЪЩНОСТ НА ПОНЯТИЕТО ИИ.ОСНОВНИ НАПРАВЛЕНИЯ

Не може да се даде точно определение защото интелекта е свързан с възможността да се мисли. Някои чов. функции могат да се моделират със съвременните технологии. Има 4 групи определения за ИИ:

1.ИИ е съвкупност от с-ми,к. мислят рационално

2.с ИИ са с-ми,к. действат рационално

3. с ИИ са всички с-ми,к. мислят като хора

4. с ИИ са всички с-ми,к.действат като хора

Обобщение- същността на ИИ е научния ан-з и автоматизацията на интелектуалните функции на човека. Целите са: изследване на естествения интелект и принцирите на работа на чов. мозък; адекватно моделиране на чов. разсъждения; разширяване на кръга от компютърно решаваните задачи създавани по естествени и достъпни интерфейси към програмни с-ми.

Осн. направления:

1. извличане, представяне и обработка на знания

2. с-ми базирани на знания

3. естествена езикова обработка

4. обработка на образите

5. невронни мрежи

6. машинно обучение

7. генетични алгоритми

8. планиране на деюйствията

Във всяко направление се обработват знания с различни методи и подходи.
2? ВЪВЕДЕНИЕ В СИМВОЛНИТЕ ИЗЧИСЛЕНИЯ
Същност на изчисленията - когато се разглежда технологията на изч-ята може да се каже че по принцип всяко изч-е изисква както представяне на някоя същност (обект, категория) така и процедура за обработване на това представяне. При изч-ята предоставянето и обработката са взаимносвързани. Функциониращите традиционни приложения от различни области на бизнеса и науката се основават на числови изч-я. при тях поведението на алгоритъма е предварително явно разработено и резултатът,к. тр. да се получи при изпълнението на този алгоритъм също са предварително известени какъв тип ще бъдат. При числовите изч-я инф-ята има числов израз на представяне,а обработката представлява предварително известна последователност за прилагане на операции върху числови модели на представяне записана във вид на алгоритъм. Като резултат от разработките на редица учени се доказва че вложената в изч-ята идея надхвърля смятането с числа.

Естествената еволюция на изч-ятя води до появата на нов тип такава, чиито възможности са свързани с реализацията на ИИ. Технологията на ИИ се основава на идеята че чов. интелект може да бъде разгледан като изч-е,к. няма точна форма т.е моделът му на реализация е нееднозначен. Изч-ята свързани с реализиране на ИИ могат да се разделят на 2 осн. типа: символни и конекционни (невронни). При символните изч-я съществува явен модел на представяне на обработванаите същности (категории, отн-я), докато при невронните такъв модел липсва. Невронните изч-я моделират в стр-рно и функционално отн-е чов. мозък. Известни са като невронни мрежи от еволюциата на живата природа и като генетични алгоритми.

Математиката като основа на символните изч-я - същ. няколко области от математиката на к. се базират изч-ята на ИИ и в частност символните изч-я. Една от тях е теорията на логикат, друга е релационната алгебра. Възможността за математическа хар-ка на релациите м/у обектите и св-вата на тези релации често води до постигане на по-компактен модер на представяне на тези обекти. Същността на символните и числовите релации може да бъде изразена най-подходящо чрез 3 концепции: функция,граф и семантична мрежа.

Представянето на дад. релация чрез функция може да стане по следния н-н: нека Х и У които могат да бъдат символи, числа от концепции се намират в отн-е което може да бъде изразено с изречението "Атрибутът R на обекта Х има ст-ст У."Моделът е У=Fу(X,R). Ако домейнът (областта на валидност) на У съдържа само елементите Истина и Неистина, то функцията Fу по своята същност е логическа, т.е. може да бъде съждителна или предикатна. В случай че домейните на Х и R са крайни мн-ва друг н-н на представяне на релацията в това изречение е като наридина тройка (R,X,Y). Форматът е (атрибут,обект,сдт-ст) - (А,О,V). Третата алтернатива за представяне на изречението е като математическа релация: Х е свързана с У посредством R.

Математическо определание на понятието релация е ако А и В са мн-ва релацията от А към В е подмн-во на А*В, където под А*В се разбира декартовото произведение на А по В. Това определение се отнася за двуичната релация. При математематическото разглеждане на въпроса за представяне и обработка на двуичните релации отн-е имат как точно се свързват мн-вата и какви са те.

Най-интересни са релациите имащи символни параметри.Такива релации м/у същностите могат да имат три аспекта - пространствен, времеви и процедурен. Пространствения аспект на релациите изразява пространственото положение на дад. обект спрямо друг. Релацията на a,b,c,d се основава на модела на насочения граф. L=(a,b,c,d)

Реилацията L е релация м/у относително обособени същности. Унарните релации изразяват концепцията за това че всяка същност притежава св-ва, т.е. атрибути и м/у св-вата на дад. същност и самата същност съществуват връзки. Св-вата могат да се отнасят до цвят,възраст, функция, приложение и т.н. Ако се налага да се представи факта че РС има чипове чрез използване на символния подход първия н-н е да се използва релациата - наредената двойка (РС, чипове). Този н-н на представяне на дад. същност се нар. унарна релация. Унарните релации като ИМА, Е, ЩЕ Е и др. представящи св-ва на същности се използват в схемите на семантичните мрежи.

Тпите най-съществени хар-ки на релациите са:

- рефлексивност - дад. релация R е рефлексивна ако за всяко a принадлежащо на А наредената двойка (а,а) принадлежи на R

- симетричност - релацията R e симетрична ако за всяко (а,b) принадлежащо на R наредената двойка (b,a) принадлежи на R

- транзитивност -релацията R е транзитивна ако за всяко (a,b) прин. на R и (b,c) пприн. на R, то (a,c) прен. на R.

Чрез определяне на двуичните релации,к. съществуват м/у обектите в реалния свят се формира стр-ра, к. е от особено значение в случаите когато предстои да се създаде модел на тези обекти. Бинарните релации описват връзките м/у групирани по двойки обекти,к. са наредени двойки. Обектите от реалния свят могат да се групират в тройки, четворки и т.н. тогава връзките м/у тези обекти се предсавят като наредени тройки,четворки и т.н.Такива релации се нар. релации от по-висок ред. За тях е хар-рно това че могат да бъдат разгл. като наредени n-членни обекти. Тези n-членни обекти могат да бъдат разгледани като двойки като (n-1) и 1 единичен елемент. (a,b,c,d,e) -> ((a,b,c,d),e)

` На практика точно математически това решение можеи да стане като бинарна релация. както двуичните релации, така и релациите от по-видсок ред могат да се опишат чрез т.нар. релационни таблици. По-подходящи са обаче за описание на двуичните релации.Таблиците изброяват дад. релация като наредени n-членни елементи в таблична форма.За представяне на релации от по-рисок ред по-подходящ е подхода нар. семантична мрежа. Семантичнат мрежи са идеално ср-во за визуализация, к. се използва широко в ИИ. Тово ср-во дава начална представа как трябва са изглежда модела на знанията,к. предстои да се разработи. Логическия модел на знанията реализиран като семантична мрежа организира знанията по такъв н-н, че да отразява по естествен н-н йерархичните зависимости м/у обектите и да позволява наследяване. При символните релационни изч-я съществуват случаи в к. се налага да се представят понятия, действия и ситуации, т.е. предсавените същности не са просто обекти от реалния свят, а носят по-дълбок смисъл. Всеки обект има опр. роля в преставянето. Такива рел-и се нар. концептуални - рел-ции м/у понятия. Определените от същностите понятия се нар. концептуален граф. Концептуалните релации посочват ролята, к. дадена същност играе в предоставянето като по този н-н се улеснява определянето кой на кого какво прави.Предимство на концептуалния граф е че смисълът може да бъде представен явно.

Релациионната алгебра може да се използва както за цифрови така и за символни изч-я.

Най-подходящо ср-во за представяне на бинарни рел-ии е насочения граф. Когато рел-циите са от по-висок ред най-подходящ н-н за предсавяне са семантичните мрежи. Чрез св-вата на рел-иите при семантитичните мрежи е възможно на база явно представени рел-ии да се правят изводи за рел-ии к. явно не се виждат но ги има. Тази идея лежи в основата на принципа на наследяване.

Класификация на символните изч-я - тя се прави в 4 аспекта.

1-я е свързан с модала на пресмятане от една страна и естеството на самото пресмятане от друга. Според този асп. изч-ята се делят на последователни и паралелни. Последов. биват числови и символни, а паралелните- числови, символни и невронни.

Символните изч-я вкл. символи, превила, отн-я. При тях се използват описателни езици за програмиране. Има евристично търсене на реш-я т.е. реш-ето се търси м/у мн-во хипотези, не е известно предварително че алгоритъма ще стигне до някакво реш-е, има неточно представяне на инф-я , няма предварително изграден алгоритъм.

Числовите изч-я са обратни на символните- има точен алгоритъм, точно представяне на инф-ята, точен резултат.

2-я има отн-е за разглеждане на подходите за реализиране на символните изч-я. Тук има реализация по декларативна схема, по процедурна и по комбинирана схема. По деклар. схема модела на представяне е съждителна и педикатна логика, семантична мрежа, ч/з правила. Процедурна схема - модел на представяне е с-ма от процедури на DEMO. Комбинир. схема е с-ма от т.нар. фрейми (frames).

3-я се отнася до моделите на предст-е на същностите к. участват в изч-ята. Моделите се реализират на концептуално, физ-ко и лог-ко ниво. Минава се през 3-те етапа: изготвяне на концептуален, логич. и физч. модел.

4-я взема предвид подходите за реализиране на обработваните и представяните в символните изч-я същности. Това е т.нар. дедуктивна обработка на логич. ниво : ралични модели - различни видове обработки.;



3? МОДЕЛИЛАНЕ И ОБРАБОТКА НА ЗНАНИЯ НА КОНЦЕПТУАЛНО НИВО
Същностите от реалноста могат да се моделират с цел компт. обработка ако за тях има събрана инф-я. Описанието на техните хар-ки и състояние може да се изрази ч/з регистриране на опр. факти, което в КС-ми се реализира като въвеждане на Д. Отн-ята и връзките м/у обектите и явленията в същноста си са знания. Най-общо знанията се представят ч/з символни описания, к хар-рат емпирични (от опит) или дефинитивни (по опред.) отн-я м/у същностите в дадена област и от процедури за обръщение към тях. За да може да се изп-ват в КС-ми знанията се формализират ч/з модели за представяне. Отделните конструкции на всеки модел са Д. РС-те не обработват инф-я, те обраб. Д.

В областа на ИИ се прави разлика м/у Д и знания. Знанията са Д от по-високо ниво, защото съдържат и връзките м/у тях. Рязка граница обаче не може да се направи. За да се моделират знанията те най-напред трябва да бъдат извлечени от различни източници- спец. литература, документи, разговори със специалисти, БД, личен опит. Процеса на подбор и стр-риране на знанията и връзките м/у тях за изграждане на базта знания се нар. инженеринг на знанията (когнитивен инженеринг). Тази техн-я възниква в областта на ИИ като част от него, но в развитието си се формира като самостоят. научно направление. В основата му лежи принципа че интелектуалното ниво на работа рядко се свежда до алгоритмичен пр-с, но въпреки това се поддава на компютъризация. Целта на ИЗ е да се извличат знания за дадена предметна област и да се организират те за ефективно компют. използване. Преди да започне работата по проекта когнитологът тр. да е запознас с проблема, а и да придобие първонач. знания за предметната област. Необх. е да се опер-ят границите на пердметната област където ще работи интелектуалната с-ма и да се установят задачите, които тя ще решава. Освен това инжинера по знанията тр. да познава хар-ките на моделите за представяне на знанията и порцедурите за тяхната обработка, за да може да използва подходящ формализъм

за огранизиране на знанията в саотвествие с изразните ср-ва. Извл-нето на знания е пр-с на предаване и преобразуване ан опита по решаване на задачи от някакъв източник на знания в интелектуалната програма. Знанията които са цел на този пр-с представляват правила за разсъждение, оценки, процедури и факти от тясна предметна област, а не са знания от общ х-р. при извличане ан знания могат да бъдат изпол-ни различни програмни ср-ва, но най-често става с директни разговори със специял. от дад. област. Получаването на знания от тях е един от най-трудните и времеотнемащи етапи в пр-са на изграждане на с-ми в ИИ. Обективни причини : няма достатъчно адекватни методи за извличане на знания от хората при к. да се отчита непълнотата, неопределеността, неточността на тези знания. Субективни причини: трудности при формулиране на изпол-то на знания. Когато експерта предава своите знания той съзнателно или не ги филтрира или не съобщава всички известни факти и закономерности. Това е така защ. специалиста има собствена представ за областа и за причините за явленията. Това се отразява на н-на на обработване на звавията. Много от ескпертите правят нещата без да могат да ги обяснят. Самият експерт често пъти използва евристика- метод по к. на базата се стеснява абласта и тамсе намира рещ-е. Трудността при формулиране на натрупаните знания е че експертите са натрупали опит с течение на времето.

Има няколко основни подхода които се използват за извличане на знания:

1-ви - връзката е Експерт-Инжин. по знания. Инжинера провежда интервюта, анкети, наблюдения на работат на експерта и после заедно обсъждат осн. стратегии използвани за реш-не на конкретен проблем.

2-ри -връзката е Експерт-Софтуер за редактиране на знания - Знания. Програмата за редактиране тр да има познания за стр-та на знанията и да има диалогови компоненти.

3-ти - връзката е Примери (данни) - Индуктивна програма- Зависимости. Извличането на знания се извършва в началото на всеки проект за създаване на интелигентна с-ма, но не приключва с придобиването на тяхната осн. част.

СЪЩНОСТ НА КОНЦЕПТУАЛНОТО МОДЕЛИРАНЕ НА ЗНАНИЯ

Концеп. модел на знания започва веднага след като има извлечен известен макар и не пълен обем знания. След като се определят осн. понятия и обекти се преминава към фиксиране на връзките м/у тях. Тъй като те са подобни на мрежа и са неравномерни се избират по-главните от тях. Неотчитането на опр. взаимовръзки и факти може да доведе до неверни резултати противоречиви указания от с-мата и дори разпространяване на некомпетентност. Оценката на събраната инф-я се рави от инжинера по знания при разговор с експерта. Ч/з описани е на обектите се формира интелигентната с-ма.

На концептуално ниво се определят:

1. Категориите к. се използват - те вкл. обекти с общи х-ки (длъжност, образование) Правилното им подбиране е от важно значение.

2. Метриките к. се прилагат към обектите (р-р, цена) - не е проблем когато се измерва количествено. За онези понятия,к. нямат утвърдена скала за отчетане се използват спецф. подходи.

3. Композиционните обекти (сложни) - там се опр. каква стр-ра имат, а също така и отн-ята от типа част - цяло.

4. Как ще се отчита времето, пространството, промените в състоянието. Действията и събитията имат различна продължителност но могат да се случат и в едно и също време. Използва се онтология на времето.

5. Събитя и пр-си к. се наблюдават.

6. Мисловни обекти и обеждения .

Извлечените знания се класифицират на факталогични - представящи х-ките на същностите, също така и някои факти И знания за отн-ята и връзките м/у обектите И метазнания (знания за знанията).

Друг важен тип знания к. инж. по знания се стреми да получи са знанията за осн. стратегии на разсъждение, използвани от експерта за да реши дад. проблем. Важно е да се изясни от къде започва работата му, какви предположения първоначално се правят и с какви факти се подкрепят. Тези знания се изп-ват по-късно за избор на подходящ механизъм за обработка на базат знания. Инж. по знанията изобразява откритите концептуални връзки и осн. обекти ч/з някакви формализми (графи, мрежи, диаграми). В процеса на работа той изп-ва някои конструкции от избран модел за представяне на знанията, но това е спомагателна форма. След проверките на прототипите на интелиг. с-ма може да се окаже че само един модел не стига и тр. да се прилагат и др. модели за представяне на знанията.

Един от подходите при решаване на нестр-ни проблеми със ср-вата на ИИ е ч/з търсене. Ч/з него на концепт. ниво може да се установи н-на за намиране на 1 или няколко реш-я или да се покаже че задачета няма реш-е. При методите за намиране на реш-е ч/з търсене се задава модел за представяне на ръзсъжденията при решаване на група близки задачи. Като се променят изходните факти модела не се променя а се променят крайните резултати. Задачите к. се решават ч/з търсене тр. да имат дефинирано начало и цел, както и опр. действия к. се осъществ. за постигане на целта. Понятието "състояние" представлява такава стр-ра от Д, к. представя абстрактна снимка на проблема в опред. стадий на реш-ето. За да може да се преобразува едно състояние към др. се използват оператори. Получените нови състояния се нар. наследници. Предполага се че наследниците са по-близо до целта но това не винаги е вярно. За да се реши задачата тр. дасе открие последователност от оператори, к. освен че са приложими в тек. състояние, водят към някое от целевите състояния. Ако не е известно дали същест. реш-е търсенето продължава докато се установи че няма реш-е. В пр-са на прилагане на оператори за намиране на реш-я се генерират различни състояния, чиято съвкупност представлява пространство на търсенето. Обикновено пространството се изобразява с дърво. Коренът на което е начално състояние, клоните (звездите) са междинни, а листата са решения на задачата.

За да се осъществи търсенето е необходим алгоритъм и ф-я за приверка - дали изследваното състояние е целево. В алгоритъма участват 2 вида ф-ции, к. зависят от избраната стратегия на търсетне. Първата от тях служе за избор и подреждане ан операторите в съотв-е с реда на прилагането им и пораждане на нови състояния. Тази ф-я се нар. генератор на разумните ходове, в нея се съдържат самонеоб. минимум от знания за проблемната област достатъчен за генериране на всички възможни състояния. Натрупването на знания във ф-ята ще намали простванството на търсене, но ще увелчи р-дит за генериране на следните състояния.

Втората ф-ция е оценъчна. Та може да бъде различна в зависимост от стратегията на търсене. Напр. в pesi от use на оценачната ф-я се задава ч/з чеслова величина колко близо до целта е на възел за изследване. Оценъчната ф-я може да връща число, к. е количестване оценка на необходимите ресурси (памет) за достигане на дед. цел. След прилагане на определен оператор генерираните нови състояния се разгл. с/д ст-ста получ. от приложената оценъчна ф-я.

Имаме начално състояние при к. прилагаве оператор1 и 2 и получ новите състояния. Ако използваме оценъчната ф-я тогава тя връща като резултат чесло, к ако е < като число от рез-тата на др. разглеждани състояния определя добър за момента избор на възел. След това прилагаме следното съст. А отпр. 3 и 4 Получ. съст. C и D. Опер. 5 следва съст.В- получ. съст. Е. В резултат прилагането на оценачната ф-я виждаме .....

За повечето реални задачич оценъчната ф-я се базира на евристика (практич. правила). Ако не съществува подходяща оценъчна ф-я или пространство на търсене е малко се осъществява пално търсене. Можем да начертаем обща алгоритмична с-ма за търсене на реш-е:.....

Основните задачи за търсене в пространството на състоянията се класифицират така:

1.Търсене на целево състояние при зададени ограничителни условия - тук се разширява първоначал. мн-во от ограничит. условия с тези , к. са логич. следствие от входните. Аконе се намери реш-е се прави хипотеза за някои от неуточнените параметри. Така ограниченията се засилват след като новополуч. производни отново се разпространяват. Целта е да се стигне до намиране на р-е или дя достигне до противоречие.

При противоречие се прави въвеждане назад и се предполага нова ст-ст на съответния параметър. Това продължава докато се стигне до реш-е.

2. Търсене на път до целево състояние, т.е. на последователност от ходове, к. да доведат до успешен изход. Х-рно за тези задачи е че бр. на състоянията е краен като има 1 начало и 1 или няколко крайни състояния. Тук са зададени правилата за преход м/у отделните състояния.

3. Търсенето нан печеливша стратегия - при този вид метод се построява цялото дърво от състояния и се намират оценките на листата. Преди да бъде приложена стратегия за търсене реалния проблем тр. да се формулира целта, к. представлява реш-е. Дефинирането на проблема означ. да се зададе:

- нач. състояние

- мн.вото от оператори, к. се допуска дасе приложат към дад. състояние

- ф-я за изчисляване на р-дите на компютърно време и памет неомх. за изследване на възлите на дървото до намиране на целевотот състояние

- ф-я тест за проверка дали разглежданото състояние е целево.

За да се определят тези неща към проблема се подхожда абстрактно.

В зависимост от сложността на решавания проблем се избират различни методи за търсене:

1) Търсене в едно пространство - използва се за малки относително непроменливи задачи, работещи със сравнит. точни и пълни Д.

2) Търсене в йерархични пространства - прилага се при проблеми възникв. в големи статични области.

3) Търсене в алтернативни пространства - използва се при моделиране на различни с-ми от мнения ч/з отделни пространства

4) Търсене в динамични проблемни области - обл. променливи във времето и пространството

5) Търсене с използване на няколко модела за описание на предметната област.

1. Основните групи стратегии за търсене в 1 пространство са неинформорането (сляпо) и информирано (евристично) търсене. Оценяването на всяка от тези стратегии се извършва по следните критерии:

- намира ли се изобщо реш-е? , т.е. стратегияга тр. да гарантира намирането на р-е ако то съществува.

- р/д на машинно време и оперативна памет при изследване на възлите за намиране на р-е.

- оптималностна р-ето.

При търсене в 1 простр-во пр-сът спира когато е намерено целево (крайно) състояние - това означава че е достигнато до р-е. В завис. от задачата и желанието на потребителя пр-сът може да продължи с търсене на др. реш-е - при достигане на крайно състояние се прави връщане в предходно и търсенето продължава.

Сляпо търсене – то се прилага при липса на нъсочващи зн-я за опрад. на бр. стъпки до целта или за р-дите на ресурси к. ще се направят за това. То представлява с-матично генериране на нови състояния и тестването им за установяване дали някое от тях не е целево. Единственото място където се прилагат зн-я при неинформираното търсене е при избор на възел, к. е наред да се разглежда. При този избор също се използва резл върнат от оценяващата ф-я, к. описва в числова форма до колко е "привлекателен" разглеждания възел.Неинф. търсене е неефективно и често води до т.нар. комбинаторен взрив - когато се породят толкова много състояния, че с-мата се запушва. Прилага се обаче, тъй като съществяват много проблеми за к. липсва допълнит. инф. за намиране на реш-е, т.е. няма насочваща инф. От свэя страна сляпото търсене може да става в дълбочина в ширина или двупосочно.

1) Търсене в ширина. Същността му се състои в пораждане и проверка на всички възможни алтернативи ва зададеното ниво, след това на следващото и т.н. (със стрелките е показанреда на обхождане на възлите). Ако съществува реш-е тази стратегу гарантира намирането му. Когато р-ята са няколко, най-напред се открива онова, к. е на най-малка дълбочина в дървото. Дълбочината се определя като величина к. е 0 за коренния нъзел, а да всички останали е 1+дълбочината на най-близкия родителски възел. Броя на наследниците за отделния възел се нар. ф-р на разклоняване. Нека предполажим че за 1 хипотетично простр-во от състояниу всеки възел поражда n - наследника тогава на първо ниво се получ. n-възела, на второ ниво-n на квадрат, на трето n на трета степен, ако дълбочината на разклоняване е к, то общия бр. породени възли ще се изчисли така 1+n+n2+n3+....+nK.

Възможно е при намиране на р-е на поранен етап бр.възли да бъде по-малък. Търсенето в ширината изисква много повече памет защ. при него се запомнят всички пътища на р-е в най- плитко ниво.

1.1 Търсене в ширина с минимизиране на р-дите - дава се предимство на възела, до к. р-дите на ресурсите са най-малки.

5? 2) Търсене в дълбочина. При него се разгл. възел к. се намира на най-голяма дълбочина в дървото. Когато при тази стратегия се попадне на безусловен край или се достигне състояние, к. е недупостимо зазадачата се прави връщане на зад. до предходното родителско състояние и се прави търсене за следния клон (възел) . Този механизъм на възврат се нар. back trucking. Той работи на дисциплинатана която работят стековете последния възел пръви излиза. Ако проблема въобще има р-е ч/з back trucking то ще мъде намерено. При тази стратегия на търсенето изискванията за обем на паметта са умерени т.като се запомнят само пътят по разглеждане d и max дълбочина mе необх. памет за запомняне на d*m възела (в ширина е d на степен m).

В чеслово изражение с дълбочина m=12 и ф-р на разклоняване d=10 ще са необх. само 12КВ, а в ширина търсенето паметта ще е 120ТВ.

За проблеми с много възможни р-я тестването в дълбочина е по-бързо от търсенето в ширина, т.като може да се намери целево състояние ч-з изследване на по-малка част от пространството.

При 2-те стратегии може да се получат всички реш-я.

Основния недостатък на търс. в дълбочина е с мн. дълбоки нива (възли) или ако дървото е с мн. голяма

В този случай се получ. търсене к. продължава надолу без възможн. за връщане даже когато съществува реш-е на предходно ниво. Целевото съст-е не се постига , но дори да с е постигне няма да бъде оптимално по отн-е на р-дите на време и памет. Затова тази стратегия не се прилагат за дървета с голяма и дори безкрайна дълбочина.

2.1 Ограничено търсене в дълбочина - ч-з тази стратегия се ликвидира недостатъка ч-з отчитане максим. дълбочина на пътя. За всяка задача се подготвя и прилага спец. алгоритъм за ограничаване на търсенето. Така се гарантира намиране на р-е, но не и неговато оптималност.

2.2 Итеративно задълбочаващо се търсене - то е стратегия с избор на лимит за ограничаване на нивото от възли за изследване. Проверяват се възлите на всички възможни дълбочини, започвайки от ниво 0 като на всяко следващосе преглеждат и предходните. Многократно отбелязване и преглеждане на едни и същи възли е недостатък. За да се повиши ефективността натърсене има някои подходи:

-използване на ф-я, к. да отхвърля пораждането на наследник, к. е в същото състояние както родителския възел

- да несе създава път с цикли през пространството на търсене

- да не се генерира състояние, к. вече е било формулирано.

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

Първия вид се нар. търсене в права посока (от Д към целта), а втория на търсене в обратна посока.

2. Двупосочно търсене - цели се пр-са да започне от нач. състояние към листата на дървото, и от предполагаемото ниво на целево съст-е към началното. Когато започне разгл. на едни и същи възли т.е. реализира се т.нар. срещане, търсенето се прекратява. Занякои проблеми това е трудно или невъзможно.

При всички видове пълно търсене времето за намиране на р-е се увеличава с нарастване бр. на състоянията. Зада се избегне това се използва т.нар. евристично търсене.

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

Един от н-ните за наследяване пространството на търсене е използването на т.нар. "информирани" оператори. Те не генерират възли к. нямат отн-е към проблема. Друг вариант за намаляване пространството на търсенето е използване на оценъчни фу-и, к. количествено определят растоянието или р-дите на време и памет от текущия възел до целевия. Ще разгл. 2 метода:

1) Минимизиране на разходите от възела до целта - 1 от евристичните ..... за търсенето е тази. След като се генерират състоянията в рез. на прилагане на оператор се изчисляват р-дите от там до целта. За повечето проблеми това е възможно. Ф-ята к. изпълнява такива изчисления е евристична и специфична за всеки от потребителите. Еврист. ф-я е коректна ако при състояние съвпадащо е целта връща оценка 0-нула, напр. нека се търси път от А до т.Х следва схема.....

Известни са следните разсояния до целта по права линия ВХ=45, СХ=32, МХ=48, DX=25, PX=35, AX=50, LD=18, SD=22. Тази стратегия работи по следния н-н. От нач. състояние А се пораждат възли В,С,М. След това според посочените данни най-малкото разстояние на тези точки до Х е СХ=32 затова се избира за разглеждане възел С. Всички възможни състояния променят възел С в L -D и Р. Избира се възел D т.като разстоянието от него до Х е най-малкото. Търсенето реш-е в тази задача е АСDX. Проблемът при тази стратегия е възможността да се попадне в клон, к. не садържа реш-е и алгоритъмът да формира цикълът без изход. Напр. нека се търси път от К до D. Възел К генерира L и S. Избира се L но това не може да бъде реш-е, защ. нама пат от L до D. Затова за проверка на конкретността на избора тр. да се включат допълнителни зн-я.

2) Минимизиране на общите р-ди - време и памет. Тази стратегия е комбинация от това к. разглеждахме преди 1) с търсенето в ширина с минимиз. на р-дите.

Предимствата на двата метода може да се обединят ако се комбинират оценъчните фу-и, к. те използват.

Ака означим с P(n) р-дите за достигане от нач. състояние до състояние n и с h(n) евристич. оценените най-малки р-ди от възел n до целта то комбинираната ф-я f(n)=p(n)+h(n) и поради своята същност тя тр. да извежда винаги най-малката ст-ст на р-дите. Ако тр. да се намери най- евтиното реш-е първо се търси възел с най-малка f(n).


Каталог: referats
referats -> Специализирани микропроцесорни системи (курс лекции) Учебна година 2008/2009
referats -> Програмата Internet Explorer
referats -> Високоскоростни компютърни мрежи. Високоскоростни км-класификация
referats -> Бройни системи основни бройни системи
referats -> Морфология и расология съдържание
referats -> 1 Строеж на атомите – модели Ръдърфор, Бор, квантово механични представи основни принципи, атомни орбитали, квантови числа
referats -> Международно наказателно право понятие за международното наказателно право
referats -> Тема 11. Връзка на асемблер с езиците от високо ниво
referats -> Въведение в операционите системи
referats -> Тема първа


Сподели с приятели:
  1   2   3




©obuch.info 2024
отнасят до администрацията

    Начална страница