Diode modelling: Difference between revisions

Revision as of 01:06, 4 February 2014

In constraint satisfaction, backmarking is a variant of the backtracking algorithm.

Backmarking works like backtracking by iteratively evaluating variables in a given order, for example, $x_{1},\ldots ,x_{n}$ . It improves over backtracking by maintaining information about the last time a variable $x_{i}$ was instantiated to a value and information about what changed since then. In particular:

An example, in which search has reached xi=d the first time.

for each variable $x_{i}$ and value $a$ , the algorithm records information about the last time $x_{i}$ has been set to $a$ ; in particular, it stores the minimal index $j<i$ such that the assignment to $x_{1},\ldots ,x_{j},x_{i}$ was then inconsistent;
for each variable $x_{i}$ , the algorithm stores some information relative to what changed since the last time it has evaluated $x_{i}$ ; in particular, it stores the minimal index $k<i$ of a variable that was changed since then.

The first information is collected and stored every time the algorithm evaluates a variable $x_{i}$ to $a$ , and is done by simply checking consistency of the current assignments for $x_{1},x_{i}$ , for $x_{1},x_{2},x_{i}$ , for $x_{1},x_{2},x_{3},x_{i}$ , etc.

When search reaches xi=d for the second time, part of the path is the same as the first time.

The second information is changed every time another variable is evaluated. In particular, the index of the "maximal unchanged variable since the last evaluation of $x_{i}$ " is possibly changed every time another variable $x_{j}$ changes value. Every time an arbitrary variable $x_{j}$ changes, all variables $x_{i}$ with $i>j$ are considered in turn. If $k$ was their previous associated index, this value is changed to $min(k,j)$ .

The data collected this way is used to avoid some consistency checks. In particular, whenever backtracking would set $x_{i}=a$ , backmarking compares the two indexes relative to $x_{i}$ and the pair $x_{i}=a$ . Two conditions allow to determine partial consistency or inconsistency without checking with the constraints. If $k$ is the minimal index of a variable that changed since the last time $x_{i}$ was evaluated and $j$ is the minimal index such that the evaluation of $x_{1},\ldots ,x_{j},x_{i}$ was consistent the last time $x_{i}$ has been evaluated to $a$ , then:

if $j<k$ , the evaluation of $x_{1},\ldots ,x_{j},x_{i}$ is still inconsistent as it was before, as none of these variables changed so far; as a result, no further consistency check is necessary;
if $j\geq k$ , the evaluation $x_{1},\ldots ,x_{k},x_{i}$ is still consistent as it was before; this allows for skipping some consistency checks, but the assignment $x_{1},\ldots ,x_{i}$ may still be inconsistent.

Contrary to other variants to backtracking, backmarking does not reduce the search space but only possibly reduce the number of constraints that are satisfied by a partial solution.

References

20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.

My blog: http://www.primaboinca.com/view_profile.php?userid=5889534

@@ Line 1: / Line 1: @@
-Jayson Berryhill is how I'm called and my spouse doesn't like it at all. Invoicing is what I do. One of the very best issues in the world for him is doing ballet and he'll be starting some thing else along with it. Her family members life in Ohio.<br><br>Visit my web site; psychic readers ([http://www.weddingwall.com.au/groups/easy-advice-for-successful-personal-development-today/ weddingwall.com.au])
+In [[constraint satisfaction]], '''backmarking''' is a variant of the [[backtracking]] algorithm.
+Backmarking works like backtracking by iteratively evaluating variables in a given order, for example, <math>x_1,\ldots,x_n</math>. It improves over backtracking by maintaining information about the last time a variable <math>x_i</math> was instantiated to a value and information about what changed since then. In particular:
+[[Image:Backmarking-1.png|thumb|180px|An example, in which search has reached xi=d the first time.]]
+# for each variable <math>x_i</math> and value <math>a</math>, the algorithm records information about the last time <math>x_i</math> has been set to <math>a</math>; in particular, it stores the minimal index <math>j<i</math> such that the assignment to <math>x_1,\ldots,x_j,x_i</math> was then [[inconsistent]];
+# for each variable <math>x_i</math>, the algorithm stores some information relative to what changed since the last time it has evaluated <math>x_i</math>; in particular, it stores the minimal index <math>k<i</math> of a variable that was changed since then.
+The first information is collected and stored every time the algorithm evaluates a variable <math>x_i</math> to <math>a</math>, and is done by simply checking consistency of the current assignments for <math>x_1,x_i</math>, for <math>x_1,x_2,x_i</math>, for <math>x_1,x_2,x_3,x_i</math>, etc.
+[[Image:Backmarking-2.png|thumb|180px|When search reaches xi=d for the second time, part of the path is the same as the first time.]]
+The second information is changed every time ''another'' variable is evaluated. In particular, the index of the "maximal unchanged variable since the last evaluation of <math>x_i</math>" is possibly changed every time another variable <math>x_j</math> changes value. Every time an arbitrary variable <math>x_j</math> changes, all variables <math>x_i</math> with <math>i>j</math> are considered in turn. If <math>k</math> was their previous associated index, this value is changed to <math>min(k,j)</math>.
+The data collected this way is used to avoid some consistency checks. In particular, whenever backtracking would set <math>x_i=a</math>, backmarking compares the two indexes relative to <math>x_i</math> and the pair <math>x_i=a</math>. Two conditions allow to determine partial consistency or inconsistency without checking with the constraints. If <math>k</math> is the minimal index of a variable that changed since the last time <math>x_i</math> was evaluated and <math>j</math> is the minimal index such that the evaluation of <math>x_1,\ldots,x_j,x_i</math> was consistent the last time <math>x_i</math> has been evaluated to <math>a</math>, then:
+# if <math>j<k</math>, the evaluation of <math>x_1,\ldots,x_j,x_i</math> is still inconsistent as it was before, as none of these variables changed so far; as a result, no further consistency check is necessary;
+# if <math>j \geq k</math>, the evaluation <math>x_1,\ldots,x_k,x_i</math> is still consistent as it was before; this allows for skipping some consistency checks, but the assignment <math>x_1,\ldots,x_i</math> may still be inconsistent.
+Contrary to other variants to backtracking, backmarking does not reduce the search space but only possibly reduce the number of constraints that are satisfied by a partial solution.
+==References==
+*{{cite book
+| first=Rina
+| last=Dechter
+| title=Constraint Processing
+| publisher=Morgan Kaufmann
+| year=2003
+| url=http://www.ics.uci.edu/~dechter/books/index.html
+| isbn=1-55860-890-7
+}}
+[[Category:Constraint programming]]

Diode modelling: Difference between revisions

Revision as of 01:06, 4 February 2014

References

Navigation menu

Search