翻訳と辞書 Words near each other ・ Backlight (film) ・ Backlighting (lighting design) ・ Backline ・ Backline (stage) ・ Backlink ・ Backlist ・ Backlog ・ Backlog (album) ・ Backlog of unexamined patent applications ・ Backlot ・ Backlot Stunt Coaster ・ Backlund ・ Backlund (crater) ・ Backlundtoppen ・ Backman ・ Backmarking ・ Backmasking ・ Backmuir Wood ・ Backnang ・ Backnang Abbey ・ Backnang station ・ Backnang–Ludwigsburg railway ・ Backney Halt railway station ・ Backoffice ・ BackOffice Associates ・ Backoo, North Dakota ・ Backpack ・ Backpack (disambiguation) ・ Backpack helicopter ・ Backpack journalism Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Backmarking ： ウィキペディア英語版 Backmarking 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,\backslash 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: # 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 # 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 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. 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,\backslash ldots,x\_j,x\_i$ was consistent the last time $x\_i$ has been evaluated to $a$, then: # if # if $j\; \backslash geq\; k$, the evaluation $x\_1,\backslash ldots,x\_k,x\_i$ is still consistent as it was before; this allows for skipping some consistency checks, but the assignment $x\_1,\backslash 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== * 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Backmarking」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.