Разтворът на проблеми по метода на намаляване - studopediya

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

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

Ченг и Slagle алгоритъм. Въз основа на трансформацията на произволна И / ИЛИ-графика в специален OR-графика, всеки OR-клон, който има както в началото до края. Реализациите използва идеята за произволна И / ИЛИ-графика като произволна формула на Пропозиционални логика с допълнително преобразуване на произволна формула в разделителния нормална форма. Такава трансформация допълнително позволява да се използва алгоритъм Hart, Nilsson и Рафаел.

ключов метод оператори. Нека там да се възложи задачата и е известно, че F Операторът трябва да се появи в решаването на този проблем. Подобно твърдение се нарича ключ. Да предположим, необходимо условие С, и в резултат на използването му е I (в) за използване е. И тогава връх генерира три деца възли: , Той е разделен на подреден набор от подзадачи, всяка от които се решават по метода на планиране в пространството на състоянието.

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

Метод решаване общ график задача (ARI). ARD е първият най-известният график модел. Той е бил използван, за да реши проблемите на интегралното смятане, извод, анализирането и други ARI комбинира два основни принципа на търсене .:

анализ на цели и средства и рекурсивни решаване на проблеми. Във всеки цикъл, търсене Orz на реши в здраво последователност три типа общи задачи: да се превърне обект А към обект B, D, за да се намали разликата между А и В, да се прилагат операторът е в обект А. Първата задача на втория определя разликата D - подходяща е оператор, третият - приложение изисква състояние С. Ако в е различен от, тогава F оператор се прилага, или с, се появява като друга мишена и цикълът се повтаря, като се започне със задачата "трансформира в с". Цялостна стратегия ARI изпълнява обратната е от предвидената цел на необходимите средства за постигане С, като се използва намаляване на първоначалния проблем до проблеми и <С, В>.

Имайте предвид, че в ARD мълчаливо приема независимостта на разликите едно от друго, което означава гаранция, че намаляването на някои разлики няма да доведе до увеличаване на другите.

3. Планиране с помощта на логически приспадане. Такова планиране включва: описание на държави под формата на добре оформени формули (WFF) на логически смятане, описанието на операторите под формата на PPF или прехвърляне на правата на някой друг PPC. Представителство на операторите под формата на PPC ви позволява да създадете дедуктивни методи за планиране, представителство на операторите под формата на трансферните правила - планиране детайли на дедуктивни методи за извеждане.

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

Продукт ЛЕНТИ метод система. При този метод, операторът представя продукти Р, А => В, където R, А и В - множество PPF първи ред предикатното смятане на, F изразява условията за прилагане на продукт ядро ​​А => В, където В съдържа списък на добавената PPF и списък на изключени PPF, т . д. postconditions. метод Метод OCR повтаря с тази разлика, че стандартната проблема с определянето на различията и използването на подходящи оператори се решават въз основа на принципа на резолюции. Подходящи оператор избран същия начин, както в остра респираторна болест, въз основа на принципа на "Анализ на средства и цели." Наличието на комбиниран метод на планиране е възможно да се ограничи процеса на извод описание на състоянието на света, както и новото поколение на описания на процеса такъв отпуск за евристичен "от целта на средствата за постигането й."

метод на продукта, използвайки makrooperatory [Fikes и сътр. 1973]. Makrooperatory е обобщена разтвор на получени проблеми метод ивици. makrooperatorov Application намалява търсенето на решение, но проблемът опростяване на makrooperatora, същността на която е сума за дадена разлика в желаната част и изключването на последните ненужни отчети.