Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
AC-3 und Forward-Checking
- 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)
- 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?
- 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?
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…
…wenn es forward-checking subsumen soll, ja.
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 
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…
Ich glaube teilweise gibt es immer noch ein paar Unstimmigkeiten/Verwirrungen, deswegen sollte man das noch einmal explizit hervorheben:
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):
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;
}