Dold transformation

Den dolda transformationen omformulerar ett problem med begränsningstillfredsställelse på ett sådant sätt att alla begränsningar har högst två variabler. Det nya problemet är tillfredsställbart om och bara om det ursprungliga problemet var, och lösningar kan enkelt konverteras från ett problem till ett annat.

Det finns ett antal algoritmer för begränsningstillfredsställelse som endast fungerar på begränsningar som har högst två variabler. Om ett problem har begränsningar med en större aritet (antal variabler), möjliggör konvertering till ett problem gjord av binära begränsningar exekvering av dessa lösningsalgoritmer. Restriktioner med en, två eller flera variabler kallas unära, binära eller högre ordningens begränsningar. Antalet variabler i en begränsning kallas dess aritet .

Den dolda transformationen ersätter varje begränsning med en ny, dold variabel.

Den dolda transformationen omvandlar ett godtyckligt problem med tillfredsställelse av begränsningar till ett binärt. Transformationen liknar den som genererar det dubbla problemet . Problemet läggs till nya variabler, en för varje begränsning av det ursprungliga problemet. Domänen för varje sådan variabel är uppsättningen av tillfredsställande tuplar av motsvarande begränsning. Restriktionerna för det nya problemet tvingar fram värdet på de ursprungliga variablerna för att överensstämma med värdet på de nya variablerna. Till exempel, om de nya variablerna $c$ , som motsvarar den gamla begränsningen $C(x,y)$ anta värden $(1,2) )$ och $(2,0)$ läggs två nya begränsningar till: den första tvingar $x$ att ta värdet $1$ om $c=(1,2)$ värde $2$ om $c=(2,0)$ och vice versa. Det andra villkoret tvingar fram ett liknande villkor för variabeln $y$ .

Grafen som representerar resultatet av denna transformation är tvådelad eftersom alla begränsningar ligger mellan en ny och en gammal variabel. Dessutom är begränsningarna funktionella: för varje givet värde av en ny variabel kan endast ett värde av den gamla variabeln uppfylla begränsningen.

• Fahiem Bacchus ; Xinguang Chen; Peter van Beek; Toby Walsh (2002). "Binära vs. icke-binära begränsningar" (PDF) . Artificiell intelligens . 140 (1/2): 1–37. doi : 10.1016/S0004-3702(02)00210-2 .