Not logged in. · Lost password · Register

MiriTheRing
Member since Oct 2011
38 posts
Subject: AC-3 und Forward-Checking
1. Ich kanns jetzt nicht genau aus den Folien oder Buch sehen, aber AC-3 wird wie forward checking in jedem Backtracking-Schritt gemacht oder? (Also, waehle einen nachfolger -> reduziere domains -> steige ab -> revert falls keine lsg)
2. AC-3 enthaelt laut Foliendefinition nichts ueber die Variablen die bereits gesetzt wurden, aber ich vermute man will gesetzte variablen als variablen betrachten deren domain auf groesse 1 geschrumpft ist, oder?
3. Wo ist der Unterschied ziwschen Forward-Checking und Backtracking? Backtracking checkt auch bei jeder auswahl ob das ganze konsistent ist und steigt nur dann ab, d.h. der einzige Unterschied den ich sehe ist, dass die Domains schon vorher reduziert werden anstatt waerend des Nachfolgersuchens, das kommt Reihenfolge und Laufzeittechnisch genau aufs gleiche raus. oder uberesehe ich was?
Jazzpirate
Member since Oct 2016
803 posts
wo ist der Unterschied ziwschen Forward-Checking und Backtracking?
Der unterschied ist, dass früher erkannt wird, wann inkonsistenzen auftreten. Dadurch, dass wir *alle* Domänen in jedem Rekusionsschritt einschränken nutze wir die gesamte Information, die eine zusätzlich belegte Variable mit sich bringt sofort um Inkonsistenz zu folgern, und nicht erst, wenn die betroffene variable versucht wird zu belegen. Das ist zwar rechenaufwändig, wird aber billiger, je "tiefer" ich im baum gehe und pruned jedes mal äste weg:
Angenommen wir sind an einem Knoten, an dem Forward-Checking abbricht weil v keine möglichen Werte mehr hat. Backtracking selbst würde (unter Umständen!) fröhlich noch mit anderen k Variablen weitermachen, die belegen und erst wenn es bei v ankommt feststellen "ups, inkonsistent", dann backtracken und wieder in v laufen, wieder backtracken...

Guck dir mal die Grafik auf slide 301 an. Da bricht forward-checking im letzten schritt ab, aber in der dümmsten Variablenordnung würde Backtracking noch mit T, NSW und NT weitermachen, bevor es in ne Inkonsistenz rennt...
This post was edited on 2016-11-29, 16:37 by Jazzpirate.
Jazzpirate
Member since Oct 2016
803 posts
AC-3 wird wie forward checking in jedem Backtracking-Schritt gemacht oder?
..wenn es forward-checking subsumen soll, ja.

AC-3 enthaelt laut Foliendefinition nichts ueber die Variablen die bereits gesetzt wurden
Die stecken in den Domains; wenn du den den Rahmenalgorithmus für forward-checking mit inference auf slide 299 anschaust ist da der Schritt D'_v={d}. Von dem her muss arc-consistency a gar nicht benutzen. Das ist etwas seltsam, dass in den Slides bei Forward-checking a benutzt wird, aber bei AC-3 dann die Domäne benutzt wird, das muss ich zugeben. Deswegen hab ich jetzt auch ne ganze weile gebraucht um zu kapieren was da schief läuft :D
BTL
Member since Oct 2012
310 posts
Macht die die Minimum Remaining Value Heuristik eigentlich implizit Forward Checking, um zu wissen, wie viele Werte in der Domaene der verbleibenden Variablen noch uebrig sind?
Jazzpirate
Member since Oct 2016
803 posts
Macht die die Minimum Remaining Value Heuristik eigentlich implizit Forward Checking, um zu wissen, wie viele Werte in der Domaene der verbleibenden Variablen noch uebrig sind?
Hmm, möglich, dass du gerade was verwechselst? MRV wird ja benutzt um überhaupt erstmal eine Variable zu wählen, die als nächstes belegt werden soll, anhand der Größe ihrer Domänen. Um forward checking zu betreiben müsste man ja eine konkrete variable bereits konkret belegen...
Shadow992
Member since Jan 2014
290 posts
In reply to post #4
Quote by BTL:
Macht die die Minimum Remaining Value Heuristik eigentlich implizit Forward Checking, um zu wissen, wie viele Werte in der Domaene der verbleibenden Variablen noch uebrig sind?

Ich glaube teilweise gibt es immer noch ein paar Unstimmigkeiten/Verwirrungen, deswegen sollte man das noch einmal explizit hervorheben:

Minimum-remaining-values (how many values are still valid for this variable)
Degree heuristic (how many other variables are affected by this variable)
Least-constraining-value (what value will leave the most other values for other variables)

http://cs.stackexchange.com/questions/47870/what-is-least-…

Das heißt bei MRV "arbeitest du nur" auf den Variablen (ohne Nachbarn), bei Degree "arbeitest du lokal" auf den Variablen (also Variable + Nachbarn) und bei LCV arbeitest du auf den Values + Nachbar-Values.

Ebenfalls vom stackexchange link (LCV-Erklärung):
It first picks variable "O" and then tests "O" with all of it's legal values "i" to see the number of reductions on "O"'s neighbors "N". It adds all of them. and picks an "i" that causes less reductions.

It picks "i" so that:
sums[i] = MAX{sums[i] | for all "i" that is a member of "O",s valid values}
This post was edited on 2017-02-12, 15:32 by Shadow992.
frececroka
Member since Oct 2014
57 posts
Was BTL wahrscheinlich gemeint hat: Um MRV anwenden zu können muss ich erstmal wissen, welche Werte jede Variable noch annehmen kann, ohne direkt Inkonsistenzen zu erzeugen. Diese Information ist erst nach einem Durchlauf von Forward-Checking bekannt.
Shadow992
Member since Jan 2014
290 posts
Quote by frececroka:
Was BTL wahrscheinlich gemeint hat: Um MRV anwenden zu können muss ich erstmal wissen, welche Werte jede Variable noch annehmen kann, ohne direkt Inkonsistenzen zu erzeugen. Diese Information ist erst nach einem Durchlauf von Forward-Checking bekannt.

Ich glaub ich verstehe worauf ihr hinaus wollt, aber im Grunde ist Forward-Checking keine Voraussetzung (auch wenn es natürlich sinnvoll ist).
Man kann ja auch einfach Domains definieren, wie folgt:

D of X1, ..., Xn = {1,2,3,4,5}
D of X0 = {1,2}

Dann kann man da auch MRV anwenden, aber wie gesagt das gleich zu kombinieren ist natürlich das Beste/Intuitivste.

Edit:
Hoffentlich versteht ihr mich nicht falsch, man muss trotzdem lokal checken welche Werte bei der Variable überhaupt möglich sind, um zu zählen wie viele insgesamt bei dieser einen Variable möglich sind.

Als an C# angelehnter Pseudo-Code also ungefähr das:

Variable MinimumRemainingValues(List<Variable> variables)
{
    int min = Infinity;
    Variable bestVar;
    ForEach (var in variables)
    {
            if (!var.assigned && var.getValidValuesLeft() < min)
            {
                bestVar=var;
                min = var.getValidValuesLeft();
            }
     }
    return bestVar;
}

int Variable::getValidValuesLeft()
{
     int availableAssignments=0;
     // values = list of all possible values for this variable/object
     ForEach (val in values)
     {
          this.setValue(val);
          if (this.checkValidAssignement())
          {
               availableAssignments++;
          }
     }
     this.resetValue();
     return availableAssignments;
}

Edit2:
Bei Arc-Consistency würde sich die ganze getValidValuesLeft-Funktion reduzieren auf das:
{
     // values = list of all possible values for this variable/object
     return values.Length;
}
This post was edited on 2017-02-12, 16:27 by Shadow992.
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