Not logged in. · Lost password · Register

MiriTheRing
Member since Oct 2011
38 posts
Subject: Anzahl constraints
Zwei Fragen bezeglich Constraints:

1.
Definition 1.16 (Folie 275) sieht vor, dass es fuer jedes Variablenpaar einen Constraint (Menge an paaren von Belegung) vor.
Definition 2.4 (Folie 285): Ich glaub da is u und v vertauscht, oder?
Falls ich die Definition richtig verstehe werden hier Constraints gezaehlt.
Das beisst sich, weil so immer alle gleich viel Constraints haetten. Aber vermutlich nur wenn mans mit 1.16 zu genau nimmt.. ich denk, man zaehlt bei 2.4 nur die Constraints, die auch wirklich eine Einschraenkung sind?

2.
Ausserdem ist die Frage als wie viel man Constraints zaehlt, das is laut Definitionen genau definiert, aber man kann ja noch mal nachfragen...
Constraints werden pro Paar gezaehlt.
D.h. wenn ich fuer X, Y zwei einschraenkungen hab: X /= Y und X /= Y+3, dann zaehlt das als ein Constraint.
Wenn dann Y und Z die Bedingung haben Z /= Y, Z /= Y +3, Z /= Y-7. dann haetten trotzdem X und Z gleich viele Constraints.
Vvalter
Member since Dec 2012
119 posts
Bei der Teilaufgabe (6.1.2) stellt sich mir auch die Frage ob wir da MRV, degree heuristic und least constraining value zusammen machen sollen oder jedes einzeln?
Jazzpirate
Member since Oct 2016
767 posts
In reply to post #1
Das beisst sich, weil so immer alle gleich viel Constraints haetten. Aber vermutlich nur wenn mans mit 1.16 zu genau nimmt.. ich denk, man zaehlt bei 2.4 nur die Constraints, die auch wirklich eine Einschraenkung sind?
Jupp, das ist irgendwie widersprüchlich... ich würde behaupten hier wurden zwei Formalismen durcheinandergewürfelt, nämlich
ein-constraint-pro-paar, was schön einheitlich und relativ implementationsnah ist (es gibt halt ne Funktion CheckConstraints(v1,v2):Bool ) und
ein-constraint-pro-tatsächlicher-Einschränkung, was angenehmer ist um probleme als CSP auszudrücken. Im Rest der slides scheint er variante zwei zu benutzen; i.e.
ein constraint C_uv liegt nur dann in C, wenn C_uv NICHT alle wertepaare akzeptiert. Letzteres lässt sich natürlich immer zu ersterem umschreiben, also...
joa. Letzteres ist aber vor allem das, was man für constraint graphs benutzt (sonst wären das ja immer einfach die vollständigen graphen...).
Constraint graphs sind auch das, was du dir am besten für so sache wie die degree heuristic vorstellst.

Constraints werden pro Paar gezaehlt.
dem Formalismus nach richtig; es gibt also höchstens einen constraint pro paar (denk wieder an constraint graphs). Allgemein kommt das aber halt irgendwie auch auf die Problemstellung draruf an; ich kann mir gut vorstellen dass es Probleme gibt,
in denen es gerade wegen solcher constraint-zählereien sinn macht manche situationen mit mehr als einem constraint pro paar zu modellieren (untere und obere schranken für werte z.B....). Dann hat man halt nen
Multigraph. Für die Zwecke der Vorlesung (und weil ich keine Ahnung hab, ob ich nicht grad blödsinn erzähl) würd ich aber mal von höchstens-ein-constraint-pro-variablenpaar ausgehen
MiriTheRing
Member since Oct 2011
38 posts
Um noch mal sicher zu gehen:
Angenommen ich hab Variablen X, Y, Z und als Bedingungen die ich einbauen will X /= Y und X /= Y + 3.
Dann hat X einen Constraint (mit Y), Y einen (mit X) und Z keinen?
Jazzpirate
Member since Oct 2016
767 posts
Dann hat X einen Constraint (mit Y), Y einen (mit X) und Z keinen?
Jupp. Und wenn du (sagen wir) Y belegst, haben X und Z beide keine constraints mehr.
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen