StanfordAi/graphsearch

From J Wiki
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