Utbytbarhetsalgoritm

Inom datavetenskap är en utbytbarhetsalgoritm en teknik som används för att mer effektivt lösa problem med begränsningstillfredsställelse ( CSP). En CSP är ett matematiskt problem där objekt, representerade av variabler, är föremål för restriktioner för dessa variablers värden; Målet i en CSP är att tilldela värden till variablerna som överensstämmer med begränsningarna. Om två variabler A och B i en CSP kan bytas mot varandra (det vill säga A ersätts med B och B ersätts med A ) utan att ändra problemets natur eller dess lösningar, då är A och B utbytbara variabler. Utbytbara variabler representerar en symmetri av CSP:n och genom att utnyttja den symmetrin sökutrymmet för lösningar på ett CSP-problem minskas. Till exempel, om lösningar med A =1 och B =2 har prövats, behöver lösningar med B =1 och A =2 inte undersökas genom utbytessymmetri.

Konceptet utbytbarhet och utbytbarhetsalgoritmen i problem med begränsningstillfredsställelse introducerades först av Eugene Freuder 1991. Utbytbarhetsalgoritmen minskar sökutrymmet för bakåtspårande sökalgoritmer och förbättrar därigenom effektiviteten hos NP-kompletta CSP-problem.

Definitioner

Fullt utbytbart

Ett värde a för variabel v är helt utbytbart med värde b om och endast om varje lösning där v = a förblir en lösning när b ersätts med a och vice versa.

Neighborhood Interchangeable

Ett värde a för variabel v är grannskapsutbytbart med värdet b om och endast om för varje begränsning på v , värdena som är kompatibla med v = a är exakt de som är kompatibla med v = b.

Fullt utbytbart

Ett värde a för variabel v är fullt utbytbart med värde b om och endast om varje lösning där v = a förblir en lösning när b ersätts med a (men inte nödvändigtvis tvärtom).

Dynamiskt utbytbart

Ett värde a för variabel v är dynamiskt utbytbart för b med avseende på en uppsättning A av variabeltilldelningar om och endast om de är helt utbytbara i delproblemet som induceras av A.

Pseudokod

Algorithm för utbytbarhet i grannskap

Hittar utbytbara kvartersvärden i en CSP. Upprepa för varje variabel:

Bygg ett diskrimineringsträd genom att:

Upprepa för varje värde, v:

Upprepa för varje angränsande variabel W:

Upprepa för varje värde w överensstämmer med v:

Flytta till om det finns, konstruera om inte, en nod för diskrimineringsträdet som motsvarar w|W

K -utbytbarhetsalgoritm

Algoritmen kan användas för att explicit hitta lösningar på ett problem med begränsningstillfredsställelse. Algoritmen kan också köras i k steg som en förprocessor för att förenkla den efterföljande bakåtspårsökningen.

Hittar k-utbytbara värden i en CSP. Upprepa för varje variabel:

Bygg ett diskrimineringsträd genom att:

Upprepa för varje värde, v:

Upprepa för varje ( k − 1)-tuppel av variabler

Upprepa för varje ( k − 1)-tuppel av värden w , som tillsammans med v utgör en lösning på det inducerade delproblemet av W :

Flytta till om det finns, konstruera om inte, en nod i diskrimineringsträdet som motsvarar w|W

Komplexitetsanalys

I fallet med utbytbar grannskapsalgoritm, om vi tilldelar det värsta fallet bundet till varje slinga. Sedan för n variabler, som har högst d- värden för en variabel, då har vi en gräns för : $O(nd(nl )*d)=O(n^{2}d^{2})$ .

På liknande sätt är komplexitetsanalysen av k -utbytbarhetsalgoritmen för ett värsta fall $) {\displaystyle (k-1) )}$$\displaystyle O(n^{k-1})} ,$ med -tuplar av variabler och $d^{k-1}$ , för $(k-1)$ -tupler av värden, då är gränsen : $O(ndn^{kl}d^{k-1})=O(n^{k}d^{k} )$ .

Exempel

Exempel för utbytbarhetsalgoritm.

Figuren visar ett enkelt graffärgningsexempel med färger som hörn, så att inga två hörn som är sammanfogade av en kant har samma färg. De tillgängliga färgerna vid varje vertex visas. Färgerna gul, grön, brun, röd, blå, rosa representerar vertex Y och är helt utbytbara per definition. Om du till exempel ersätter rödbrun med grönt i lösningen orange|X (orange för X), grön|Y kommer att ge en annan lösning.

Ansökningar

Inom datavetenskap har utbytbarhetsalgoritmen använts flitigt inom områdena artificiell intelligens , graffärgningsproblem , abstraktionsramverk och lösningsanpassning.