Not logged in. · Lost password · Register

Razato
Member since Sep 2013
5 posts
Subject: 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?
Shadow992
Member since Jan 2014
290 posts
Quote by Razato:
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.
aiaiai
Member since Feb 2017
6 posts
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?
Shadow992
Member since Jan 2014
290 posts
Quote by aiaiai:
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.
aiaiai
Member since Feb 2017
6 posts
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.
This post was edited on 2017-02-12, 20:25 by aiaiai.
Shadow992
Member since Jan 2014
290 posts
Nur sicherheitshalber, um Missverständnisse zu vermeiden:
Quote by aiaiai:
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.

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.
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