University of Calgary
Rob Kremer
Example Solution: Or Tree/
Traveling Salesman Problem

CPSC 433: Artifical Intelligence
Department of Computer Science
Computer
Science

Model

A: (S,T)
S: Otree
Otree: (pr, sol:{yes,?,no}, b1:Otree, ... ,bn:Otree), n>=0
pr: {r | r: seq city}
T: S x S, {(s1, s2) | s1 ∈ S /\ s2 ∈ S /\ Erw (s1, s2)}
Erw((pr, ?), (pr, yes)) \/
Erw((pr, ?), (pr, no)) \/
Erw((pr, ?), (pr, ?, (pr1, ?), ..., (prn, ?))) \/
Erw((pr, ?, b1, ..., bn), (pr, ?, b1', ..., bn')), exists1 j | j <= n . ∀ i | i /= j . Erw(bj, bj'), /\ bi = bi'
Erw((pr, ?)) = head pr = start /\ last pr = start /\ ∀ i, j . wij ∈ pr →(pr, yes) // solved if head and last are the start city and all cities are in the sequence
Erw((pr, ?)) = Erw((pr, no)) if we detect multiple same-cycles
Erw((pr, ?)) = {(pr, ?) cat b) | ∀ i | wlast pr, i ≠ ⊥ • front b = pr /\ last b = i} // add exactly one and every legal edge to the path
Erw((pr, ?, (pr1,?), ..., (prn,?))) = ∃ x:pri ∀ x':pri | x≠x' . wlast pr, last x < wlast pr, last x'  // choose the one with that adds the least to the path that we haven't visited*.

* although we want to prefer not-visited paths, it is not shown in the logic.

Process

P: (A, Env, K)
Env: ({wij | wij: N∪⊥}, start: 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.
K: See the last Erw

Search Instance

Ins = (s0, G)
s0: <<A>>
G((pr, ?)) = any child is solved \/ head pr = start /\ last pr = start /\ ∀ i, j . wij ∈ pr
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 ⊥.

Example

                                                                        <<A>>=0
                                                                        /             \
                                                    <<A,B>>=10            <<A,D>>=15
                                                /             |             \          
                       <<A,B,C>>=7      <<A,B,D>>=4     <<A,B,A>>=10
                                                 /             |                 \
                      <<A,B,D,C>>=6   <<A,B,D,A>>=15  <<A,B,D,B>>=4  <--- although it's the lowest, it has a repeat
                     /               |              \
<<A,B,D,C,A>> <<A,B,D,C,D>> <<A,B,D,C,B>>
          yes

Although we have found a solution, we would carry on in hopes of finding a better solution.
CPSC 433: Arficial Intelligence
 Department of Computer Science
Last updated 2013-09-01 15:45
Rob Kremer