Was ist der geringste einschränkende Wert?

Bei Problemen mit der Einschränkungszufriedenheit können Heuristiken verwendet werden, um die Leistung eines Bactracking-Lösers zu verbessern. Drei häufig verwendete Heuristiken für einfache Backtracking-Löser sind:

• Minimal verbleibende Werte (wie viele Werte sind für diese Variable noch gültig)
• Gradheuristik (wie viele andere Variablen sind von dieser Variablen betroffen)
• Am wenigsten einschränkender Wert (welcher Wert hinterlässt die meisten anderen Werte für andere Variablen)

Die ersten beiden sind ziemlich offensichtlich und einfach zu implementieren. Wählen Sie zuerst die Variable aus, deren Domäne die wenigsten Werte enthält, und wählen Sie bei Bindungen diejenige aus, die die meisten anderen Variablen betrifft. Wenn ein übergeordneter Schritt im Solver eine schlechte Zuordnung ausgewählt hat, werden Sie dies wahrscheinlich früher herausfinden und dadurch Zeit sparen, wenn Sie die Variable mit den geringsten verbleibenden Werten auswählen, die die meisten anderen Dinge beeinflusst.

Diese sind einfach, klar definiert und leicht zu implementieren.

Der am wenigsten einschränkende Wert ist nirgendwo klar definiert, wo ich hingeschaut habe. Künstliche Intelligenz: Ein moderner Ansatz (Russel & Norvig) sagt nur:

Es wird der Wert bevorzugt, der die wenigsten Auswahlmöglichkeiten für die benachbarten Variablen im Einschränkungsdiagramm ausschließt.

Die Suche nach dem "am wenigsten einschränkenden Wert" ergab nur viele Diashows der Universität, die auf diesem Lehrbuch basierten, ohne weitere Informationen darüber, wie dies algorithmisch erfolgen würde.

Das einzige Beispiel für diese Heuristik ist ein Fall, in dem eine Wertauswahl alle Auswahlmöglichkeiten für eine benachbarte Variable eliminiert und die andere nicht. Das Problem bei diesem Beispiel ist, dass es sich um einen trivialen Fall handelt, der sofort beseitigt wird, wenn die potenzielle Zuordnung auf Übereinstimmung mit den Einschränkungen des Problems überprüft wird. In allen Beispielen, die ich finden konnte, hat die Heuristik mit dem geringsten einschränkenden Wert die Leistung des Lösers in keiner Weise verbessert, abgesehen von einem kleinen negativen Effekt durch das Hinzufügen einer redundanten Prüfung.

Das einzige andere, was ich mir vorstellen kann, wäre, die möglichen Zuordnungen der benachbarten Variablen für jede Zuordnung zu testen und die Anzahl der möglichen Zuordnungen der Nachbarn zu zählen, die für jede mögliche Zuordnung dieser Variablen existieren, und dann die Werte für diese Variable zu ordnen basierend auf der Anzahl der verfügbaren Nachbarzuweisungen, wenn dieser Wert ausgewählt wird. Ich sehe jedoch nicht, wie dies eine Verbesserung gegenüber einer zufälligen Reihenfolge bieten würde, da dies sowohl das Testen zahlreicher Variablenkombinationen als auch das Sortieren basierend auf den Ergebnissen der Zählung erfordert.

Kann jemand eine nützlichere Beschreibung des Werts mit der geringsten Einschränkung geben und erklären, wie diese Version des Werts mit der geringsten Einschränkung tatsächlich zu einer Verbesserung führen würde?

siehe diesen Link:

https://people.cs.pitt.edu/~wiebe/courses/CS2710/lectures/constraintSat.example.txt

Es wählt zuerst die Variable "O" aus und testet dann "O" mit allen zulässigen Werten "i", um die Anzahl der Reduzierungen auf den Nachbarn "N" von "O" zu sehen. Es fügt alle hinzu. und wählt ein "i", das weniger Reduzierungen verursacht:

   sums = {0:0,1:0,2:0,3:0,4:0,5:0,6:0,7:0,8:0,9:0}
   For i from 0 to 9:  
     plug "o=i" into the constraint formulas
     For each neighbor "N" of "o" in the constraint graph:
       sums[i] += the number of values remaining for "N"

Es wählt "i", so dass:

sums[i] = MAX{sums[i] | for all "i" that is a member of "O",s valid values}

Ich hoffe, dies kann Ihnen helfen, Ihre Antwort zu finden!

Ich denke, die Hauptsache hier ist, dass diese Heuristiken abhängig von der Aufgabe angewendet werden, für die der Löser geschrieben wurde. Und wenn die Möglichkeit besteht, dass der ausgewählte Wert einer Variablen keinen einzigen Wert in der Domäne einer anderen Variablen hinterlässt (sagen wir, wir haben ein stark eingeschränktes Problem mit nur einer Lösung), kommt die Lösung zum Stillstand . Und eine zufällige Suche kann den richtigen Weg gehen, der zu einer Entscheidung führt, und den falschen. Und wenn es schief geht, müssen Sie ein Backtracking durchführen (siehe konfliktgesteuertes Backjumping), und es dauert Rechenzeit. Es ist jedoch wahrscheinlicher, dass der Algorithmus, der LCV-Heuristiken verwendet, einen korrekteren Weg einschlägt und keine Rückgabe erforderlich ist. Aber wenn es ein unterbeschränktes Problem gibt, wird es meiner Meinung nach einer zufälligen Suche ähneln.