Model
A: (S,T)
S: Atree
Atree: (pr, sol:{yes,?}, b1:Atree, ... ,bn:Atree),
n>=0
pr: {x: seq N} // a problem is any sequence of natural numbers
pr =________
T: S x S,
T= {(s1, s2) | s1 ∈ S /\ s2
∈ S • Erw (s1, s2) \/ Erw* (s2, s1)}
Erw((pr, ?), (pr, yes)) /\ \/ // mark solved
Erw((pr, ?, (pr1, yes), (pr2, yes))) where solution =
merge(solution pr1, solution pr2) \/
Erw((pr, ?), (pr, ?, (pr1, ?), ..., (prn,
?))) \/ // expand children
Erw((pr, ?, b1, ..., bn), (pr, ?, b1', ...,
bn')), ∃1 j | j ≤ n • ∀ i | i
≠ j • Erw(bj, bj') /\ bi = bi'
// deal with a child
Erw*((pr, ?, b1, ... , bn), (pr, ?, b1',
... , bn')), ∀ i • Erw*(bi, bi')
\/ bi' = bi'
// backtrack
ErwmarkSolved((pr, ?)) → (pr, yes) if sorted pr // A
problem is solved if it's a sorted sequence
ErwexpandChildren((pr, ?)) → (pr, ?, pr', pr") where pr'
is the first half of pr and pr" is the second half of pr.
ErwdealWithAChild= <random>
Erw*= <not needed>
Process
P: (A, Env, K)
Env: <none>
K: <random>
Search Instance
Ins = (s0, G)
s0 = << 3 4 2 1 >>
G: s → {yes,no}
G(pr,?) = sorted pr
Example
<< 3 4 2 1
>>
/
\ yes, merge(<<3 4>>,<<1 2>>)=<<1 2 3
4>>
<< 3 4 >> << 2 1 >>
yes
/ \ yes,
merge(<<2>>,<<1>>)=<<1 2>>
<<2>> <<1>>
yes yes
| Last updated
2013-09-01 15:45 |
|
