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.
Loesungsblatt Aufgabe 6
Hi, ich glaube, die auf Studon bereitgestellte Loesung von Aufgabe 6 hat einen Fehler beim Backtracking mit Heuristiken und AC-3 auf Seite 41 ff.
Vielleicht habe ich den Algorithmus auch falsch verstanden, aber muessten die verbleibenden Moeglichkeiten von Q3 nach Revise(Q3,Q4) auf Seite 41 nicht 1 und 4 sein?
Die Lösung hatte definitiv irgendwo einen kleinen Leichtsinnsfehler (ich glaube das war genau die Stelle, die du meinst).
Ich habs mir auch noch einmal eben angeschaut und tatsächlich steht ja links in den Kommentaren sogar: „Q3=1 hat noch einen Partner, Q3=2 nicht, Q3=3 nicht, Q3=4 schon“. 
Edit: Das heißt: Ja 1,4 sind die übrigbleibenden Werte.
Bei Seite 36 steht dass für jeden Wert von Q4 es einen Wert für Q3 gibt - aber das stimmt doch auch nicht. Bei d = 3 in D4 wuerde ich keinen gültigen Wert mehr für D3 erhalten.
Hier sind auch die Domainmengen doch falsch. Wenn ich Q1 = 1 setze, dann loescht mir das doch automatisch die Werte beispielsweise aus D2-4 oder nicht? Oder passiert dieses Löschen erst mit dem Forward Checking?
Forward Checking in AC3? Ich glaub du wirfst da bisschen was durcheinander.
Zuerst einmal: Ja für einen Menschen ist es total ersichtlich und logisch, dass Q3 keinen validen Wert mehr kriegen kann. Aber der Algorithmus hat zu diesem Zeitpunkt noch nicht Q1 mit Q3 bzw. Q4 „verglichen“, weswegen zu diesem Zeitpunkt dem Algorithmus noch nicht klar ist, dass es keine Lösung gibt.
Bei der 6.1.5 komme ich nicht darauf, wie man auf die Anzahl der Konflikte kommen soll. Das ist dasselbe Problem wie in den Folien Seite 165.
Für mich heisst Konflikt dass ich gucke mit wie vielen Queens ich auf einer Position in einer Zeile/Reihe oder Diagonalen bin.
Bei Folie 165 beispielsweise wuerde ich niemals auf eine Zahl >= 8 kommen und in der Lösung zu 6.1.5 komme ich auch beim ersten Schritt für Q1 = 1 auf 1, Q2 = 2, Q3 = 1. Im Endeffekt kommt es auf dasselbe hinaus, mich würde nur interessieren wie man auf diese Zahlen kommen soll
Edit: Ah ich sehe… man zaehlt die alle bijektiven Beziehungen von Queens die in derselben row/col/diag sitzen… Also original für Q1=1 ist das (Q1,Q2), (Q1,Q3), (Q1,Q4), für Q2 dann (Q2,Q3), (Q2,Q4) und für Q3 (Q3, Q4)… und dann fallen eben ein paar davon weg sobald ich Q1=1 etc setze.
Nur sicherheitshalber, um Missverständnisse zu vermeiden:
Soweit so gut. Das kann man auch so machen, genau so gut kann man aber auch sagen, dass ich jede Queen lokal anschaue und immer zähle wie viele diese Eine Queen bedrohen. Oder anders ausgedrückt: Ich schaue wie viele Constraints verletzt werden, egal ob es Q1,Q2 ist oder Q2,Q1 (was de facto dasselbe ist). Es gibt da verschiedene Interpretationsmöglichkeiten, aber die gängigste (weil am einfachsten zu implementieren) ist es einfach zu zählen wie viele Constraints verletzt werden unabhängig davon, ob das Constraint „in die andere Richtung“ schon gezählt wurde.