Begrænsningstilfredshed

Introduktion

En af de vigtige opgaver for kunstig intelligens (AI) er problemet med begrænsningstilfredshed . UR-teori tilbyder et praktisk apparat og et simpelt formelt skema til at repræsentere og løse kombinatoriske AI-problemer.

Målet med at løse RO-problemet er at finde værdierne af de variable, der opfylder de givne begrænsninger.

Problemet med eksistensen af løsninger på PR-problemet er NP-komplet .

Nært beslægtet med RO-teori er constraint programmering , som er et programmeringsparadigme for deklarativ beskrivelse og effektiv løsning af kombinatoriske problemer. Mange klassiske kombinatoriske problemer, såsom Fermats berømte teorem , Satisfiability Problem (SAT) fra propositionel logik, graffarveproblemet og grafisomorfiproblemet fra grafteori, kan formuleres som VR-problemer (SLT'er). Lad os dvæle mere detaljeret ved et af de mangeårige problemer i matematik - problemet med at farvelægge en graf , et særligt tilfælde af hvilket er det velkendte problem med at farvelægge et kort . Formuleringen af farveproblemet i form af et RO-problem tildeler variabler til hjørnerne af grafen, der skal farves, mulige farver er domæner (domæner) af variable, og ulighedsbegrænsninger mellem tilstødende hjørner er problemets begrænsninger.

Selvfølgelig er det her umuligt at beskrive detaljeret alle aspekter og retninger af teorien om tilfredsstillelse af restriktioner og programmering i restriktioner, derfor kan mere fuldstændig information og bibliografi findes i den oversatte monografi af Russell S., Norvig P., som dækker spørgsmålene om SR og i anmeldelsen af O.A. Shcherbina.

En gennemgang af hovedområderne for begrænset programmering før år 2000 er givet af Ushakov og Telerman (2000).

Historie

Lad os først berøre terminologien og historien om fremkomsten af UR-metoder. Montanari foreslog at bruge VR-modeller til at beskrive en række kombinatoriske problemer, der opstår i computer billedbehandling, og kaldte disse VR-problemer "netværk af begrænsninger" (netværk af begrænsninger). Dette skyldes, at begrænsningssystemet kan repræsenteres som en urettet graf med variable spidser og kanter svarende til begrænsninger mellem to variable. Ifølge Dechter er begrænsningsnetværk en grafrepræsentation, der bruges til at finde strategier til løsning af LR-problemer. Ret hurtigt blev denne tilgang brugt til at løse en meget bredere klasse af problemer. Den videnskabelige litteratur bruger begge disse udtryk begrænsningsnetværk og begrænsningstilfredshedsproblemer.

Mere formelt er constraint satisfaction problem (CR) en tupel , hvor er sættet af variabler, er sættet af variabelværdidomæner og er sættet af begrænsninger. $P = <X,D,C>$ $x$ $D$ $C$

Eksempler på problemer med tilfredshed med begrænsninger

Lad os give en række eksempler, der illustrerer formuleringen af ER-problemer på andre områder af matematikken.

Optimeringsproblemer og RO-problemer

Løsningen af optimeringsproblemet kan reduceres til løsningen af en sekvens af OE-problemer som følger. Der findes en mulig løsning, hvorefter der tilføjes en begrænsning svarende til den objektive funktion, som udtrykker betingelsen om, at værdien af den objektive funktion skal være bedre end for denne løsning. Successive justeringer af denne tærskelværdi, foretaget indtil problemet bliver uløseligt, giver os mulighed for at finde den optimale løsning.

Eksempel 1. Det mest trivielle algebraiske eksempel på EC-problemet er problemet med at løse et ligningssystem. Givet et system af lineære ligninger over et begrænset felt . Har hun en løsning? Det er klart, at i dette eksempel er hver enkelt ligning en begrænsning, hvor ligningens variable danner et område, og sættet af alle tupler svarende til løsninger til ligningen danner en begrænsningsrelation. $F$

Eksempel 2. Standardpropositionel 3-satisfiability (3-SAT)-problemet defineres ved at give en propositionel logisk formel bestående af en konjunktion af sætninger, hvor hver sætning indeholder 3 bogstaver (en bogstavelig er en variabel eller dens negation), og besvare spørgsmålet om der er værdier af variablerne, der gør formlen sand. Lad være sådan en formel, hvor er klausuler . Feasibility-problemet for kan udtrykkes som et SR-problem , hvor er mængden af alle variable i formlen, og er sættet af begrænsninger , hvor hver begrænsning er konstrueret som følger: er listen over variabler inkluderet i , og består af alle tupler, der gør klausulen sand . $\Phi = {\phi _{\rm{1))} \wedge \ldots \wedge {\phi _n}$ ${\phi _i}$ $\Phi$ $\left( {X,\,\left\{ {0,\,1} \right\},\,C} \right)$ $x$ $C$ $\left\{ {\left( {{s_1},\,{\rho _1}} \right), \ldots ,\,\left( {{s_n},\,{\rho _n}} \right)} \ret\}$ $\left( {{s_k},\,{\rho _k}} \right)$ ${s_k}$ ${\phi _k}$ ${\rho_k}$ ${\phi _k}$ $\venstre( {k = 1,\, \ldots ,\,n} \højre)$

Løsningerne på dette RO-problem er at tildele værdier til variabler, der gør formlen sand. Derfor kan ethvert 3-tilfredshedsproblem udtrykkes som et SR-problem. $\Phi$

RO-problemet kan også konverteres til et SAT-gennemførlighedsproblem. For en given ZUO konstruerer vi SAT-tilfredshedsproblemet som følger. Lad os introducere variabler. Variabler sættes til sand, hvis og kun hvis værdien er tildelt variablen. For hver variabel tilføjes klausuler (disjunkter) for alle værdipar af samme variabel for at sikre, at variablen ikke kan have to forskellige værdier på samme tid. En klausul tilføjes for at sikre, at der tildeles mindst én værdi til variablen.

Eksempel 3. Enhver specifik opgave for MA kan udtrykkes i en logisk form. Ved at bruge standardkorrespondancen mellem relationer og prædikater kan man faktisk omskrive RO-problemet som en førsteordensformel, hvor prædikater på og betyder prædikatet anvendt på tuplet af variable. Spørgsmålet er, om denne formel er gennemførlig. Denne opgave er almindeligt brugt i databaseteori, fordi den svarer til evalueringen af en konjunktiv forespørgsel, som vist i følgende eksempel.

Eksempel 4 En relationsdatabase kan ses som et begrænset sæt tabeller. En tabel består af et skema og specifikke data, hvor skemaet er et begrænset sæt attributter, hvor hver attribut har et tilsvarende sæt mulige værdier, kaldet et domæne. Konkrete data er et begrænset sæt rækker, hvor hver række er en mapping, der kortlægger hver skemaattribut til en værdi fra dens domæne. En standardopgave for relationsdatabaser er det konjunktive forespørgselsevalueringsproblem, som spørger, om løsningen har en konjunktiv forespørgsel, dvs. forespørgsel på formen , hvor er atomformler. En konjunktiv forespørgsel over en relationsdatabase svarer til et specifikt eksempel på et LR-problem, som opnås ved en simpel udskiftning af termer: "attributter" erstattes af "variabler", "tabeller" med "begrænsninger", "skema" med " interval", "specifikke data" ved "restriktionsrelation" og "strenge" til "tuples". Derfor svarer en konjunktiv forespørgsel til et specifikt eksempel på en RO-opgave, hvis variabler er forespørgselsattributter. For hver atomformel i forespørgslen er der en begrænsning, således at begrænsningsområdet er en liste over formelvariabler, og begrænsningsrelationen er et sæt modeller.

Litteratur

Russell S. Kunstig intelligens: en moderne tilgang. 2. udg.: Per. fra engelsk. / S. Russell, P. Norvig M.: Williams, 2006. 1408 s.
Shcherbina O.A. Constraint Satisfaction and Constraint Programmering // Intelligente systemer. 2011. 15 (N 1-4). s. 53-170
Dechter R. Constraint Processing / R. Dechter. Morgan Kaufmann, 2003. 481 s.
Montanari U. Netværk af begrænsninger: Grundlæggende egenskaber og applikationer til billedbehandling // Informationsvidenskab. 1974.7(2). s. 95-132.
Ushakov D.M., Telerman V.V. Programmeringssystemer i begrænsninger (gennemgang) // Systeminformatik: Lør. videnskabelig tr. Novosibirsk: Nauka, 2000. Udgave 7: Problemer med teori og metodologi til at skabe parallelle og distribuerede systemer. s. 275-310.