Solutia problemelor prin metoda de reducere - studopediya

Această metodă conduce la rezultate bune, deoarece sarcinile are adesea o structură ierarhică. Dar aceasta nu impune în mod necesar ca sarcina principală și toate sarcinile secundare ale sale rezolvate aceleași metode. Reducerea este utilă pentru a reprezenta aspectele globale ale problemei și în rezolvarea problemelor specifice metodei de preferat ca de planificare. statele metodă de planificare poate fi considerată ca un caz special al metodei de planificare cu ajutorul reducerilor, pentru fiecare cerere a operatorului în spațiul stărilor este reducerea problemei inițiale în două simple, dintre care unul este elementar. În general, reducerea problemei inițiale nu se limitează la formarea a două sub-probleme, dintre care cel puțin unul a fost elementar.

sarcini de planificare de căutare în spațiu este reducerea consistentă a problemei inițiale la o mai simplu, atâta timp până când au primit doar sarcini elementare. Parțial set ordonat de sarcini va fi soluția problemei inițiale. Dezmembrării problemei seturi alternative de subactivități prezentate convenabil sub formă de AND / OR grafic. In acest grafic, fiecare nod, cu excepția terminalului fie a nodurilor asociate copilului (I conjunctiv-vârf) sau disjunctiv asociate (sau nod). În cazul particular, în absența I-topuri, există un grafic al spațiului de stat. sunt nodurile finale sau finale (acestea corespund problemei de bază), sau o fundătură. vertex inițial (rădăcină și / sau grafic) este problema originală. Ținta de căutare în AND / sau grafic este de a arăta că vârful inițial este rezolvabilă. Solubil este vârful final (și vârful), care a rezolvat toate nodurile copil, și OR-top, care rezolvau cel puțin un nod copil. Permite grafic este format din vârfuri solubile și indică modul în care Solvabilitatea nodului inițial. Prezența vârfurilor interblocare duce la vârfuri nerezolvabile. top netratabil impas, și noduri, care este insolubilă în cel puțin un nod copil, și OR-top-uri, care este insolubilă în fiecare nod copil.

Cheng și Slagle algoritm. Pe baza transformării AND / OR-graf arbitrar într-un OR-grafic special, fiecare OR-ramura-care are atât de sus, până la sfârșitul anului. Conversia folosește ideea AND / OR-graph arbitrar ca o formulă arbitrară a logicii propoziționale cu transformarea ulterioară a unei formule arbitrar în formă normală disjunctivă. O astfel de transformare va permite în continuare să se utilizeze un algoritm Hart, Nilsson și Raphael.

cheie metoda de operatori. Să se dea sarcina și este cunoscut faptul că operatorul f trebuie să apară în rezolvarea acestei probleme. O astfel de declarație se numește o cheie. Să presupunem condiție necesară C, iar rezultatul utilizării sale este I (c) pentru utilizare f. Și apoi vertex generează trei noduri copil: , Acesta este împărțit într-un set ordonat de sub-sarcini, fiecare dintre acestea fiind rezolvate prin metoda de planificare în spațiul de stat.

alternative posibile pentru selectarea operatorilor cheie, astfel încât, în general, va avea un câmp și / sau grafic. Cele mai multe probleme nu sunt posibile pentru identificarea operatorului cheie și singurul set punct, acesta conține. În acest caz, problema calculată prin diferența dintre A și B, care este asociat cu operatorul, eliminând această distincție. Ultima este cheia.

Metoda de planificare sarcină Solver generală (ARI). ARD a fost primul model de programare cel mai bine cunoscut. Acesta a fost folosit pentru a rezolva problemele de calcul integral, deducție, parsare și alte ARI combină două principii de bază de căutare .:

Analiza obiectivelor și a mijloacelor și rezolvarea problemelor recursiv. In fiecare ciclu, căutare ORZ decide în succesiune strânsă sunt trei tipuri de sarcini comune: pentru a converti obiectul A la obiect B, D pentru a reduce diferența dintre A și B, pentru a aplica operatorul f la obiectul A. Prima sarcină a doua determină diferența D - potrivit operatorului f, al treilea - aplicare condiție necesară C. Dacă C este diferit de un operator, atunci operatorul f este aplicat, sau C, apare ca o altă țintă și ciclul se repetă, începând cu sarcina „transforma o în C“. Strategia generală ARI efectuează o căutare inversă este de ținta dorită în mijloacele necesare pentru a atinge C, folosind o reducere a problemei inițiale la problemele și <С, В>.

Rețineți că, în mod tacit independența ARD asumat diferențelor unul de altul, ceea ce implică o garanție că o reducere a unor diferențe nu va duce la o creștere în altele.

3. Planificarea folosind deducție logică. O astfel de planificare include: descrierea statelor sub forma unor formule bine formate (WFF) ale unui calcul logic, descrierea operatorilor sub forma unui PPF sau transfera drepturile alte PPC. Reprezentarea operatorilor sub formă de PPC vă permite să creați metode deductive de planificare, de reprezentare a operatorilor sub forma regulilor de transfer - elemente de planificare a metodelor de inferență deductive.

Metoda de planificare sistem deductiv QA3. ARI nu a justificat speranțele fixate pe ea se datorează în principal sarcini de prezentare săraci. Încercarea de a rezolva situația a dus la crearea unui sistem QA3 întrebare-răspuns. Sistemul este proiectat pentru un anumit domeniu arbitrar și este capabil să răspundă prin deducție la întrebarea dacă este posibil să se realizeze în starea A? În principiu, rezoluțiile utilizate ca metodă de ieșire automată. Pentru direcția de inferență QA3 utilizează o varietate de strategii, cea mai mare parte de natură sintactică, ținând cont de particularitățile rezoluțiile principiului formalism. Operațiunea QA3 a arătat că producția unui astfel de sistem se transformă lent, detaliat, care nu este tipic raționamentul uman.

FOLIE produsului Metoda de sistem. În această metodă, operatorul prezintă produsele P, A => B, unde R, A și B - pluralitatea PPF primul predicatelor de ordinul calculului, F exprimă condițiile de aplicare a nucleului produsului A => B, unde B conține o listă a adăugat PPF și o listă a exclus PPF, t . e. postconditiilor. Metoda Metoda OCR repetă cu diferența că problema standard a determinării diferențelor și utilizarea operatorilor adecvați sunt rezolvate pe baza principiului rezoluțiilor. Operatorul adecvat selectat în același mod ca și în bolile respiratorii acute, bazat pe principiul „Analiza mijloace și scopuri.“ Prezența metodei de planificare combinată posibil pentru a limita procesul de descriere a inferență starea lumii, iar noua generație de descrieri de proces astfel de concediu pentru euristic „de la țintă la mijloacele de realizare a acesteia.“

Metoda Produs folosind makrooperatory [Fikes și colab., 1973]. Makrooperatory este o soluție generalizată a metodei FOLII problemelor derivate. makrooperatorov Aplicație reduce căutarea unei soluții, dar simplificarea problema makrooperatora, esența, care este alocarea pentru o anumită diferență în partea sa dorit și excluderea din urmă declarații inutile.