Model
A: (S,T)
S: 2F // power set of facts
F: {p: seq city | head p = startCity /\ last p = startCity /\
∀ c:city • c ∈ p}
T: S x S
T = {(s, s') | ∃ A→B ∈ Ext •
A ⊆ s /\ s' = (s-A) ∪ B}
Ext ⊆ {A→B | A,B ⊆ F}
Ext(A) = B where ∃i,j | i>0 /\ j>0 /\ i<|A|-2 /\
j<|A|-2 /\ i≠j • Ai = Bj /\ Aj
= Bi /\ ∀k | k≠i /\ k≠j • Ak = Bk
// swap
Process P: (A, Env, K)
Env: ({wij | wij: N∪⊥},
startCity: city) where start ∈ wij //
The environment is the mapping of the cost of travel from city i to city
j and the start city In symmetric problems, wij=wji.
Env = The set of wij Naturals for the
particular problem. See Env in the example problem for an example.
K: S x Env → S
K(s,e) = (s-A) ∪ B where
A→B ∈ Ext
A ⊆ s
∀ A'→B' ∈ Ext | A' ⊆ s ˙ fWert(A,B,e)
≤ fWert(A',B',e)
A→B = fselect({A'→B' | ∀ A''→B'' ∈
Ext | A'' ⊆ s ˙ fWert(A',B',e) ≤ fWert(A',B',e)},
e)
fWert: 2F x 2F x Env → Nat
fWert(A,B,Env) = // the total path length of B according
to Env. (We're going for the smallest fWert.)
fselect:22Fx 2Fx Env → 2Fx
2F
fselect= // choose the best .4 of A and randomly .1 from
the remainder. Apply the following fselect operators with
a probability of .3, .4, .3 respectively:
1. randomly select 2 facts, f1 and f2 from A. Randomly select a city, x
(not the start city). Concatenate the pre-x path of f1, x, and the post-x
path of f2 to create a new path f3. If there are cities, m, missing
from f3, add them by finding neighbors of m and constructing a re-route
between randomly-selected neighbours to include m.
2. randomly select a fact f, from A. If some city, c (other than the
start city) that occurs more than once in f. For one of teh
occurances of c in A, find the adjacent cities c1, and c2. If these
cities have a direct connection in Env, remove their connections to c, and
directly connect c1 to c2 in the path.
3. copy
Search Instance
Ins = (s0, G)
s0: S
s0={<A,B,C,D,A>,<A,D,C,B,A>,<A,B,D,C,B,A>}
// a randomly selected set of paths
G: s → {yes,no}
G(s) = S // in this problem, every F is a goal state by the definition of
F. We are only interested in the smalest fWert.
Env = {(wA,B, 10), (wA,D, 15), (wB,C,
7), (wB,D, 4), (wC,D, 6), (wB,A,
10), (wD,A, 15), (wC,B, 7), (wD,B, 4), (wD,C,
6)} ∪ all others are ⊥.
sgoal ? s \/ no more expansions possible
sgoal= S
Example
s0 =
{<A,B,C,D,A>=38,<A,D,C,B,A>=38,<A,B,D,C,B,A>=37}
chose: {<A,D,C,B,A>,<A,B,D,C,B,A>}
op1(<A,D,C,B,A>,<A,B,D,C,B,A>) →D
<A,D,C,B,A> //not very interesting...its the same as the first
arg.
op2(<A,B,D,C,B,A>) →B <A,D,C,B,A> // hmm..
the same as the 2nd s0.
op3(<A,B,D,C,B,A>) → <A,B,D,C,B,A>
s1 = {<A,D,C,B,A>=38, <A,D,C,B,A>=38, <A,B,D,C,B,A>=37}
...
It turns out that <A,B,D,C,B,A>
is optimal, and just happened to be in my s0...
Last updated
2013-09-01 15:45 |
|