Benutzerdefinierte Heuristik in ECLIPSE CLP

Question

Betrachten Sie das folgende Rätsel:

Eine Zelle ist entweder markiert oder nicht markiert. Zahlen auf der rechten und unteren Seite des Puzzles bezeichnen die Gesamtsumme für eine bestimmte Zeile oder Spalte. Zellen tragen (wenn markiert) zur Summe in ihrer Zeile und Spalte bei: Eine Zelle in Position (i, j) trägt i zur Spaltensumme und j zur Zeilensumme bei. Zum Beispiel sind in der ersten Zeile im Bild oben die 1., 2. und 5. Zelle markiert. Diese tragen 1 + 2 + 5 zur Zeilensumme bei (also insgesamt 8) und jeweils 1 zu ihrer Spaltensumme.

Ich habe einen Löser in ECLiPSe CLP für dieses Puzzle und ich schreibe eine benutzerdefinierte Heuristik dafür.

Die einfachsten Zellen, mit denen ich anfange, sind diejenigen, für die der Hinweis auf Spalten und Zeilen so niedrig wie möglich ist. Im Allgemeinen ist die untere N, desto weniger Möglichkeiten bestehen, N als Summe der natürlichen Zahlen zwischen 1 und N zu schreiben. Im Kontext dieses Puzzles bedeutet dies, dass die Zelle mit dem niedrigsten column hint + row hint die geringste Wahrscheinlichkeit hat falsch zu sein, also weniger Backtracking.

In der Implementierung habe ich ein NxN Array, das die Platine darstellt, und zwei Listen der Größe N, die die Hinweise darstellen. (. Die Zahlen auf der Seite und auf der Unterseite)

Ich sehe zwei Möglichkeiten:

• eine benutzerdefinierte Auswahl Prädikat schreiben für search/6. Wenn ich jedoch richtig verstehe, kann ich nur 2 Parameter angeben. Es gibt keine Möglichkeit, die Summe aus Zeile und Spalte für eine gegebene Variable zu berechnen, weil ich sie an das Prädikat weitergeben muss. Ich brauche 4 Parameter.

• Ignoriere Suche/6 und schreibe eine eigene Beschriftungsmethode. So habe ich es jetzt, siehe den Code unten.

Es nimmt die Platine (die NxN Array alle Entscheidungsvariablen enthält), beide Listen von Hinweisen und gibt eine Liste aller Variablen enthält, nun ihre Zeile + Spaltensumme sortiert nach. Dies kann jedoch möglicherweise nicht mehr umständlich werden, wie Sie sehen können. Um sortieren zu können, muss ich die Summe an jede Variable anhängen, aber um dies zu tun, muss ich sie zuerst in einen Ausdruck umwandeln, der auch die Koordinaten der Variablen enthält, so dass ich wieder in die Variable as umwandeln kann sobald die Sortierung abgeschlossen ist ...

lowest_hints_first(Board,RowArr,ColArr,Out) :- 
    dim(Board,[N,N]), 
    dim(OutBoard,[N,N]), 
    (multifor([I,J],[1,1],[N,N]), foreach(Term,Terms), param(RowArr,ColArr) do 
     RowHint is ColArr[I], 
     ColHint is RowArr[J], 
     TotalSum is RowHint + ColHint, 
     Term = field(I,J,TotalSum) 
    ), 
    sort(3,<,Terms,SortedTerms), % Sort based on TotalSum 
    terms_to_vars(SortedTerms,Board,Out), % Convert fields back to vars... 
    (foreach(Var,Out) do 
     indomain(Var,max) 
    ). 

terms_to_vars([],_,[]). 
terms_to_vars([field(I,J,TotalSum)|RestTerms],Vars,[Out|RestOut]) :- 
    terms_to_vars(RestTerms,Vars,RestOut), 
    Out is Vars[I,J]. 

Am Ende ist diese Heuristik kaum schneller als input_order. Ich vermute es aufgrund der schrecklichen Art und Weise, wie es implementiert wird. Irgendwelche Ideen, wie man es besser macht? Oder ist mein Gefühl, dass diese Heuristik eine große Verbesserung inkorrekt sein sollte?

Answer 1

Ich sehe, Sie sind bereits mit der von Joachim vorgeschlagenen Verbesserung zufrieden; Wenn Sie jedoch nach weiteren Verbesserungen Ihrer Heuristik fragen, bedenken Sie, dass es nur einen Weg gibt, um 0 als Summe zu erhalten, und es gibt nur eine Möglichkeit, 15 zu erhalten. Es gibt nur einen Weg, um 1 und 14 zu erhalten, 2 und 13; zwei Möglichkeiten, 3 und 12 zu bekommen. Im Allgemeinen, wenn Sie K Weisen haben, Summe N zu erhalten, haben Sie auch K Weisen, 15-N zu erhalten.

Also die schwierigen Summen sind nicht die Großen, sondern die Mittleren.