Eine hinreichende Bedingung für rückverfolgungsfreies Suchen

Ein Einschränkungszufriedenheitsproblem dreht sich um das Finden von Werten für eine Menge von Variablen, die bestimmten Einschränkungen (Relationen) unterliegen. Rückverfolgungssuche wird oft verwendet, um solche Probleme zu lösen. Eine Beziehung, die die Struktur der Einschränkungen betrifft, wird beschrieben, die bis zu einem gewissen Grad den Extremfall von minimalem Zurückverfolgen (keines) charakterisiert. Die Beziehung betrifft ein Konzept namens "Breite", das einige Hinweise zur Darstellung von Einschränkungszufriedenheitsproblemen und der Reihenfolge, in der sie durchsucht werden, bieten kann. Das Breitenkonzept wird untersucht und insbesondere auf Einschränkungen angewendet, die Baumstrukturen bilden.