CSP: Degree Heuristic

Moderator: Einführung in die Künstliche Intelligenz

MoVi
Neuling
Neuling
Beiträge: 2
Registriert: 15. Mai 2018 13:00

CSP: Degree Heuristic

Beitrag von MoVi » 15. Mai 2018 13:07

Hallo,

ich verstehe nicht warum im Beispiel zur "Degree Heuristic" (Folie 15) im letzten Schritt Queensland (rechts oben) ausgewählt wird.

Nach der Definition geht es um die Variable mit den meisten Abhängigkeiten mit ("remaining" = verbliebenen) Variablen.
Queensland hat nur eine Abhängigkeit mit einer verbliebenen Variable, da die anderen beiden bereits eingefärbt wurden.
New South Wales (rechts mitte) hat dagegen noch zwei Abhängigkeiten mit verbliebenen Variablen.
Folglich sollte als nächstes New South Wales eingefärbt werden.

Viele Grüße
David

Tobias Joppen
Mausschubser
Mausschubser
Beiträge: 43
Registriert: 20. Feb 2017 15:08

Re: CSP: Degree Heuristic

Beitrag von Tobias Joppen » 15. Mai 2018 14:11

Für mich gibt es nur eine Variable pro Gebiet: Farbe.

Abhängigkeiten hat ein Gebiet mit allen anderen angrenzenden Gebieten (also me.color != neighbor.color für alle neighbors).
South Australia (unten Mitte) wurde zuerst eingefärbt, da es 5 Nachbarn hat.
Northern Territory (oben Mitte), Queensland (oben rechts) und New South Wales(mitte rechts) haben jeweils drei Nachbarn.
Western Australia und Victoria haben zwei und Tasmanien sehe ich als keinen Nachbar.

Entsprechend dieser Reihenfolge sind die Farben bei der Degree Heuristic zu wählen. Zumindest sehe ich das so.
Ob die Bereiche schon eingefärbt sind oder nicht sehe ich da als unwichtig an.
Edit: Doch, sind wichtig

Nach South Australia sind somit Northern Territory, Queensland und New South Wales einzufärben in beliebiger Reihenfolge.

Ich bin mir selbst aber noch nicht ganz sicher und recherchiere noch :)

Liebe Grüße,
Tobias
Zuletzt geändert von Tobias Joppen am 15. Mai 2018 14:41, insgesamt 1-mal geändert.

Tobias Joppen
Mausschubser
Mausschubser
Beiträge: 43
Registriert: 20. Feb 2017 15:08

Re: CSP: Degree Heuristic

Beitrag von Tobias Joppen » 15. Mai 2018 14:34

Gut, ich kann deine Version bestätigen. Die gewählten Farben sind von interesse.
Außerdem stimmt auch, dass bei der Degree Heuristik statt Queensland (oben rechts) New South Wales (mitte rechts) gewählt werden würde.

In den Folien auf Seite 15 wird das Beispiel aber mit SelectUnassignedVariable eingefärbt, was eine Kombination aus MRV und Degree Heuristik ist. Letztere dient hier nur als tie-breaker wenn Minimum Remaining Values sich nicht entscheiden kann.
Im Buch (AI: A Modern Approach) steht dazu auch
The minimum-remaining-values heuristic is usually a more powerful guide, but the degree heuristic can be useful as a tie-breaker

Antworten

Zurück zu „Einführung in die Künstliche Intelligenz“