Конструктивно решаване на задачи



Дата18.11.2017
Размер55.84 Kb.
Размер55.84 Kb.

КОНСТРУКТИВНО РЕШАВАНЕ НА ЗАДАЧИ

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

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

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

Елементарният подход към задачите за конструиране води до голяма изчислителна сложност, тъй като размерът на съответното пространство на състояния (решения) е експоненциална функция на броя на елементите на решението. Това не създава затруднения, ако решенията са многобройни и не се държи на качеството на решението. Чрез неуправлявано (неинформирано) търсене може да се намери удовлетворително решение за разумно време. Но ако за дадена сложна задача е необходимо да се намери решение, близко до оптималното, неуправляваното търсене по принцип е обречено на неуспех. Необходими са знания, които да се използват за конструиране на пространството от решения, а търсенето трябва да се фокусира върху комбинации от елементи, които водят до добри решения.



  1. КОНСТРУКТИВНИ СТРАТЕГИИ

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

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

Както вече беше споменато, конструктивните задачи са трудни, тъй като често няма начин да се посочи предварително дали дадено частично решение ще върши работа. Ако трябва да се подредят мебели, да се проектира електронна схема или да се планират серия от поръчки, то със сигурност може да се наложи отново подреждане, проектиране или планиране. Общата стратегия отдолу нагоре, която обикновено се използва за решаване на малки задачи, е следната:



  1. Ако е възможно, започва се с частична наредба, която удовлетворява ограниченията. В противен случай се започва от самото начало;

  2. Ако подреждането е пълно, край. В противен случай се извършва “обещаващо” разширение на текущото подреждане;

  3. Ако новото подреждане нарушава някое ограничение, се предлага (намира) поправка, която генерира ново подреждане, като за целта се пренебрегват възможно най-малко от направените досега стъпки;

  4. Преминава се към стъпка 2.

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

За сложни нареждания пространството на търсене изглежда твърде голямо и проблемът става неразрешим в реално време. Една задача за нареждане обаче може да бъде опростена чрез разглеждането й на различни нива на детайлизация. Например нека разгледаме задачата за проектиране на къща и в частност създаването на план на стаите. Както отбелязва Розенмън, конфигурациите на стаите (помещенията) могат да бъдат описани на различни абстрактни нива, например:



  • в термините на съседство (стаята А е до стаята B);

  • в термините на ориентация (стаята А е на север от стаята В);

  • чрез координати, които точно описват пространствените връзки (например между стаите А и В).

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

Този йерархичен подход е особено популярен в областта на планирането. Наследниците на системи от типа на STRIPS опростяват пространството на търсене чрез:



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

  • решаване на задачата за планиране в термините на частична наредба на тези единици;

  • последователно детайлно попълване на по-ниските нива на абстракция, докато планът се окаже напълно специфициран.

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



  1. ОЦЕНКА НА СТРАТЕГИЯТА НА НАЙ-МАЛКОТО ОБВЪРЗВАНЕ

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



  • наличните знания са непълни, или

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

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

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


©zdrasti.info 2017
отнасят до администрацията

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