StanfordAi/graphsearch
Jump to navigation
Jump to search
Unit 2
Here's my attempt:
NB. Paradigm from Unit 2
NB. A "state" of the system is the town we are now "at".
NB. s (state) -takes a 1-char value from column 0 of: map, eg 'A', 'B', ...
NB. frontier -is a set of paths, the target town at the end of the path ({:)
NB. explored -need only be a set of towns.
NB. path -is a string of towns (states), as visited in sequence.
NB. cost path -where eg path=:'ASFB' -sums the distances from Arad to Bucharest.
clear''
MAX=: 30 NB. max loops
BREADTH_FIRST=: 1
CHEAPEST_FIRST=: 2
ALGORITHM=: CHEAPEST_FIRST
initial=: 'A' NB. Start at Arad
goal=: 'B' NB. Finis at Bucharest
map=: 0 : 0 NB. A B C D E F G H I L M N O P R S T U V Z
Arad . . . . . . . . . . . . . . . c b . . a
Bucharest . . . . . f d . . . . . . e . . . g . .
Craiova . . . h . . . . . . . . . j i . . . . .
Drobeta . . h . . . . . . . k . . . . . . . . .
Eforie . . . . . . . l . . . . . . . . . . . .
Fagaras . f . . . . . . . . . . . . . m . . . .
Giurgiu . d . . . . . . . . . . . . . . . . . .
Hirsova . . . . l . . . . . . . . . . . . n . .
Iasi . . . . . . . . . . . o . . . . . . p .
Lugoj . . . . . . . . . . q . . . . . r . . .
Mehadia . . . k . . . . . q . . . . . . . . . .
Neamt . . . . . . . . o . . . . . . . . . . .
Oradea . . . . . . . . . . . . . . . t . . . s
Pitesti . e j . . . . . . . . . . . u . . . . .
Rimnicu Vilcea . . i . . . . . . . . . . u . v . . . .
Sibiu c . . . . m . . . . . . t . v . . . . .
Timisoara b . . . . . . . . r . . . . . . . . . .
Urziceni . g . . . . . n . . . . . . . . . . w .
Vaslui . . . . . . . . p . . . . . . . . w . .
Zerind a . . . . . . . . . . . s . . . . . . .
)
dist=: 0 : 0
* __
. _
a 75
b 118
c 140
d 90
e 101
f 211
g 85
h 120
i 146
j 138
k 75
l 86
m 99
n 98
o 87
p 92
q 70
r 111
s 71
t 151
u 97
v 80
w 142
)
col=: {."1
distance=: 3 : 0
NB. distance of 1-step path id: y
i=. 3 + {. I. dist E.~ LF,{.y
". LF taketo i }. dist
)
q distance 'v'
fail=: '>>> search failed.'
unknown=: '(unknown)'
INIT=: 3 : 0
NB. Initialise the data
n=: # z=: f2x }: map NB. z is map as a char-mx
m=: 16 NB. starting col# of incidence mx
name=: m col z NB. 1st m cols of z
allstates=: col name NB. list of all town-initials == states
name=: name , unknown NB. end-stop for: name_of
incid=: (m + 2*i.n){"1 z NB. every other from col 16 onwards
assert incid = |:incid NB. path mx must be symmetric
)
indx_of=: 3 : 0
NB. index in: name -of town: y
(n{. {."1 name) i. toupper y
)
name_of=: 3 : 0
NB. name of town: y
select. datatype y
case. 'literal' do. dtb name {~ indx_of y
case. 'integer' do. dtb name {~ y
case. do. unknown
end.
)
remove_choice=: 3 : 0
NB. y is frontier
NB. return: path ; (frontier minus the chosen path)
frontier=. y
select. ALGORITHM
case. BREADTH_FIRST do. i=. 0 NB. pick any entry (eg 1st)
case. CHEAPEST_FIRST do.
i=. cheapest''
end.
path=. > fx=. i { frontier NB. pick entry i
smoutput 'r_ch: chosen path=';path; ' frontier:'; (<frontier ,: costs'')
(frontier -. fx) ; path
)
cost1=: 3 : 0
NB. cost of step from {.y to {:y
NB. y is 2-string; pair of towns, eg 'AS'
i=. incid {~ (indx_of {.y)
j=. (indx_of {:y)
distance j { i
)
NB. cost1 'AS' NB. 140
cost=: 3 : 0
NB. cost of path: y
NB. y is string of towns, eg 'ASFB'
z=. 0
for_i. i.<:#y do.
z=. z + cost1 (i+0 1) { y
end.
)
NB. cost 'ASFB' NB. 140+99+211 = 450
costs=: 3 : 'cost each frontier'
cheapest=: 3 : 0
NB. choose cheapest path from frontier
min=. <./ z=. ; cost each frontier
z i. min
)
actions=: 3 : 0
NB. list of accessible towns from current state: y
z=. allstates #~ '.'~: incid {~ (indx_of y)
z [ smoutput nb 'state:' ; y ; ' actions:' ; z
)
NB. actions 'S'
add=: 4 : 0
NB. variant for TREE_SEARCH
NB. new frontier as a result of action: a in state: s
NB. Result (s,a) is a new path: (path,next_town)
NB. which must be added to: x== existing frontier
f=. x
'path a s'=. y
next_town=. {.a NB. the action spec is the successor town itself
f=. f , <path,next_town
)
addG=: 4 : 0
NB. variant for GRAPH_SEARCH
NB. new frontier as a result of action: a in state: s
NB. Result (s,a) is a new path: (path,next_town)
NB. which must be added to: x== existing frontier
NB. BUT ONLY IF it is not in: explored or: frontier_towns''
'path action state'=. y
next_town=. {.action NB. the action spec is the successor town itself
if. next_town e. (explored , frontier_towns'') do. x else. x,<path,next_town end.
)
frontier_towns=: 3 : 0
NB. towns at ends of frontier paths
~. ; {:each frontier
)
ft=: frontier_towns
GRAPH_SEARCH=: 3 : 0
smoutput 'running: GRAPH_SEARCH'
frontier=: <,initial [ explored=: '' NB. frontier = {[initial]}; explored = {}
for_i. i.MAX do. NB. loop:
if. 0=#frontier do. fail return. end. NB. if frontier is empty: return FAIL
'frontier path'=: remove_choice frontier NB. path = remove_choice (frontier)
explored=: explored , s=. {:path NB. s = path.end; add s to explored
if. s = goal do. path return. end. NB. if s is a goal: return path
for_a. actions s do. NB. for a in actions:
frontier=: frontier addG path ; a ; s NB. add [path+a --> Result (s,a)] to frontier
NB. ...unless Result (s,a) in frontier+explored
smoutput nb i;'state:';s; 'action:';a; 'path:';path; 'explored:';explored; 'frtowns:';frontier_towns''
end.
'frontier=' ; frontier NB. for maxed return
end.
)
TREE_SEARCH=: 3 : 0
smoutput 'running: TREE_SEARCH'
frontier=: <,initial NB. frontier = {[initial]}
for_i. i.MAX do. NB. loop:
if. 0=#frontier do. fail return. end. NB. if frontier is empty: return FAIL
'frontier path'=: remove_choice frontier NB. path = remove_choice (frontier)
s=. {:path NB. s = path.end
if. s = goal do. path return. end. NB. if s is a goal: return path
for_a. actions s do. NB. for a in actions:
frontier=: frontier add path ; a ; s NB. add [path+a --> Result (s,a)] to frontier
smoutput nb i;'state:';s; 'action:';a; 'path:';path; 'frtowns:';frontier_towns''
end.
'frontier=' ; frontier NB. for maxed return
end.
)
INIT''
NB. smoutput TREE_SEARCH''
smoutput GRAPH_SEARCH''
Sample output
load '/Users/ianclark/j602-user/temp/745.ijs' running: GRAPH_SEARCH ┌──────────────────┬─┬──────────┬───┐ │r_ch: chosen path=│A│ frontier:│┌─┐│ │ │ │ ││A││ │ │ │ │├─┤│ │ │ │ ││0││ │ │ │ │└─┘│ └──────────────────┴─┴──────────┴───┘ state: A actions: STZ 0 state: A action: S path: A explored: A frtowns: S 0 state: A action: T path: A explored: A frtowns: ST 0 state: A action: Z path: A explored: A frtowns: STZ ┌──────────────────┬──┬──────────┬────────────┐ │r_ch: chosen path=│AZ│ frontier:│┌───┬───┬──┐│ │ │ │ ││AS │AT │AZ││ │ │ │ │├───┼───┼──┤│ │ │ │ ││140│118│75││ │ │ │ │└───┴───┴──┘│ └──────────────────┴──┴──────────┴────────────┘ state: Z actions: AO 1 state: Z action: A path: AZ explored: AZ frtowns: ST 1 state: Z action: O path: AZ explored: AZ frtowns: STO ┌──────────────────┬──┬──────────┬─────────────┐ │r_ch: chosen path=│AT│ frontier:│┌───┬───┬───┐│ │ │ │ ││AS │AT │AZO││ │ │ │ │├───┼───┼───┤│ │ │ │ ││140│118│146││ │ │ │ │└───┴───┴───┘│ └──────────────────┴──┴──────────┴─────────────┘ state: T actions: AL 2 state: T action: A path: AT explored: AZT frtowns: SO 2 state: T action: L path: AT explored: AZT frtowns: SOL ┌──────────────────┬──┬──────────┬─────────────┐ │r_ch: chosen path=│AS│ frontier:│┌───┬───┬───┐│ │ │ │ ││AS │AZO│ATL││ │ │ │ │├───┼───┼───┤│ │ │ │ ││140│146│229││ │ │ │ │└───┴───┴───┘│ └──────────────────┴──┴──────────┴─────────────┘ state: S actions: AFOR 3 state: S action: A path: AS explored: AZTS frtowns: OL 3 state: S action: F path: AS explored: AZTS frtowns: OLF 3 state: S action: O path: AS explored: AZTS frtowns: OLF 3 state: S action: R path: AS explored: AZTS frtowns: OLFR ┌──────────────────┬───┬──────────┬─────────────────┐ │r_ch: chosen path=│AZO│ frontier:│┌───┬───┬───┬───┐│ │ │ │ ││AZO│ATL│ASF│ASR││ │ │ │ │├───┼───┼───┼───┤│ │ │ │ ││146│229│239│220││ │ │ │ │└───┴───┴───┴───┘│ └──────────────────┴───┴──────────┴─────────────────┘ state: O actions: SZ 4 state: O action: S path: AZO explored: AZTSO frtowns: LFR 4 state: O action: Z path: AZO explored: AZTSO frtowns: LFR ┌──────────────────┬───┬──────────┬─────────────┐ │r_ch: chosen path=│ASR│ frontier:│┌───┬───┬───┐│ │ │ │ ││ATL│ASF│ASR││ │ │ │ │├───┼───┼───┤│ │ │ │ ││229│239│220││ │ │ │ │└───┴───┴───┘│ └──────────────────┴───┴──────────┴─────────────┘ state: R actions: CPS 5 state: R action: C path: ASR explored: AZTSOR frtowns: LFC 5 state: R action: P path: ASR explored: AZTSOR frtowns: LFCP 5 state: R action: S path: ASR explored: AZTSOR frtowns: LFCP ┌──────────────────┬───┬──────────┬───────────────────┐ │r_ch: chosen path=│ATL│ frontier:│┌───┬───┬────┬────┐│ │ │ │ ││ATL│ASF│ASRC│ASRP││ │ │ │ │├───┼───┼────┼────┤│ │ │ │ ││229│239│366 │317 ││ │ │ │ │└───┴───┴────┴────┘│ └──────────────────┴───┴──────────┴───────────────────┘ state: L actions: MT 6 state: L action: M path: ATL explored: AZTSORL frtowns: FCPM 6 state: L action: T path: ATL explored: AZTSORL frtowns: FCPM ┌──────────────────┬───┬──────────┬────────────────────┐ │r_ch: chosen path=│ASF│ frontier:│┌───┬────┬────┬────┐│ │ │ │ ││ASF│ASRC│ASRP│ATLM││ │ │ │ │├───┼────┼────┼────┤│ │ │ │ ││239│366 │317 │299 ││ │ │ │ │└───┴────┴────┴────┘│ └──────────────────┴───┴──────────┴────────────────────┘ state: F actions: BS 7 state: F action: B path: ASF explored: AZTSORLF frtowns: CPMB 7 state: F action: S path: ASF explored: AZTSORLF frtowns: CPMB ┌──────────────────┬────┬──────────┬─────────────────────┐ │r_ch: chosen path=│ATLM│ frontier:│┌────┬────┬────┬────┐│ │ │ │ ││ASRC│ASRP│ATLM│ASFB││ │ │ │ │├────┼────┼────┼────┤│ │ │ │ ││366 │317 │299 │450 ││ │ │ │ │└────┴────┴────┴────┘│ └──────────────────┴────┴──────────┴─────────────────────┘ state: M actions: DL 8 state: M action: D path: ATLM explored: AZTSORLFM frtowns: CPBD 8 state: M action: L path: ATLM explored: AZTSORLFM frtowns: CPBD ┌──────────────────┬────┬──────────┬──────────────────────┐ │r_ch: chosen path=│ASRP│ frontier:│┌────┬────┬────┬─────┐│ │ │ │ ││ASRC│ASRP│ASFB│ATLMD││ │ │ │ │├────┼────┼────┼─────┤│ │ │ │ ││366 │317 │450 │374 ││ │ │ │ │└────┴────┴────┴─────┘│ └──────────────────┴────┴──────────┴──────────────────────┘ state: P actions: BCR 9 state: P action: B path: ASRP explored: AZTSORLFMP frtowns: CBD 9 state: P action: C path: ASRP explored: AZTSORLFMP frtowns: CBD 9 state: P action: R path: ASRP explored: AZTSORLFMP frtowns: CBD ┌──────────────────┬────┬──────────┬─────────────────┐ │r_ch: chosen path=│ASRC│ frontier:│┌────┬────┬─────┐│ │ │ │ ││ASRC│ASFB│ATLMD││ │ │ │ │├────┼────┼─────┤│ │ │ │ ││366 │450 │374 ││ │ │ │ │└────┴────┴─────┘│ └──────────────────┴────┴──────────┴─────────────────┘ state: C actions: DPR 10 state: C action: D path: ASRC explored: AZTSORLFMPC frtowns: BD 10 state: C action: P path: ASRC explored: AZTSORLFMPC frtowns: BD 10 state: C action: R path: ASRC explored: AZTSORLFMPC frtowns: BD ┌──────────────────┬─────┬──────────┬────────────┐ │r_ch: chosen path=│ATLMD│ frontier:│┌────┬─────┐│ │ │ │ ││ASFB│ATLMD││ │ │ │ │├────┼─────┤│ │ │ │ ││450 │374 ││ │ │ │ │└────┴─────┘│ └──────────────────┴─────┴──────────┴────────────┘ state: D actions: CM 11 state: D action: C path: ATLMD explored: AZTSORLFMPCD frtowns: B 11 state: D action: M path: ATLMD explored: AZTSORLFMPCD frtowns: B ┌──────────────────┬────┬──────────┬──────┐ │r_ch: chosen path=│ASFB│ frontier:│┌────┐│ │ │ │ ││ASFB││ │ │ │ │├────┤│ │ │ │ ││450 ││ │ │ │ │└────┘│ └──────────────────┴────┴──────────┴──────┘ ASFB