ProblemSolving
Jump to navigation
Jump to search
I cleaned the code considerably, and posted at rosettacode.
NB. verbs and adverb
parse_table=: ;:@:(LF&= [;._2 -.&CR)
mp=: $:~ :(+/ .*) NB. matrix product
min=: <./ NB. minimum
Index=: (i.`)(`:6) NB. Index adverb
dijkstra=: dyad define
'LINK WEIGHT'=. , (0 _ ,. 2) <;.3 y
'SOURCE SINK'=. |: LINK
FRONTIER=. , < {. x
GOAL=. {: x
enumerate=. 2&([\)&.>
while. FRONTIER do.
PATH_MASK=. FRONTIER (+./@:(-:"1/)&:>"0 _~ enumerate)~ LINK
I=. PATH_MASK min Index@:mp WEIGHTS
PATH=. I >@{ FRONTIER
STATE=. {: PATH
if. STATE -: GOAL do. PATH return. end.
FRONTIER=. (<<< I) { FRONTIER NB. elision
ADJACENCIES=. (STATE = SOURCE) # SINK
FRONTIER=. FRONTIER , PATH <@,"1 0 ADJACENCIES
end.
EMPTY
)
NB. The specific problem
INPUT=: noun define
a b 7
a c 9
a f 14
b c 10
b d 15
c d 11
c f 2
d e 6
e f 9
)
T=: parse_table INPUT
NAMED_LINKS=: _ 2 {. T
NODES=: ~. , NAMED_LINKS NB. vector of boxed names
NUMBERED_LINKS=: NODES i. NAMED_LINKS
WEIGHTS=: _ ".&> _ _1 {. T
GRAPH=: NUMBERED_LINKS ,. WEIGHTS NB. GRAPH is the numerical representation
TERMINALS=: NODES (i. ;:) 'a e'
NODES {~ TERMINALS dijkstra GRAPH
Note 'Output'
┌─┬─┬─┬─┐
│a│c│d│e│
└─┴─┴─┴─┘
)
NB. to do: store frontier both as priority queue and as a set.
Note 'tree_search'
Dyadic adverbs "treeSearch" and "graphSearch" are the essence of this code.
The dyads are designed to take the universe as y and
as x, whatever may be appropriate.
The adverbs construct a verb from a gerund.
The verbs of the gerund need to be self consistent
with the universe. I haven't tried other variations.
comments lie, this note isn't current
(initialState;goal) gerund treeSearch problemSpace
gerund m shall be
isEmpty`isGoal`removeChoice`followPath
isEmpty problemSpace Boolean determines if the problem space is empty
isGoal
removeChoice frontier returns a (carefully selected) choice from the frontier and removes it from the frontier.
)
RomanianCities=: ;:'Arad Zerind Oradea Sibiu Fagaras Timisoara Lugoj Mehadia Drobeta Craiova RimnicuVilcea Pitesti Bucharest Giurgiu Urziceni Hirsova Eforie Vaslui Iasi Neamt'
NB. node node road_length
RomanianRoads=: ".;._2]0 :0
0 1 75
0 3 140
0 5 118
1 2 71
2 3 151
5 6 111
6 7 70
7 8 75
8 9 120
9 10 146
9 11 138
3 10 80
3 4 99
4 12 211
10 11 97
11 9 138
11 12 101
12 13 90
12 14 85
14 15 98
15 16 86
14 17 142
17 18 92
18 19 87
)
RomanianRoads=: ~.(, 1 0 2 {"1 ])RomanianRoads
Universe=: RomanianCities;RomanianRoads
NB. An admissible heuristic does not overestimate the distance to the goal.
h=: 0 : 0 NB. crow's distance heuristic from named city to Bucharest.
Arad 366
Zerind 374
Oradea 380
Sibiu 253
Fagaras 176
Timisoara 329
Lugoj 244
Mehadia 241
Drobeta 242
Craiova 160
RimnicuVilcea 193
Pitesti 100
Bucharest 0
Giurgiu 77
Urziceni 80
Hirsova 151
Eforie 161
Vaslui 199
Iasi 226
Neamt 234
)
Crow=: _2({.,".&.>@{:)\;:(LF=h)}h,:' ' NB. noun, n by string;integer
NB. city Crow Heuristic Universe
NB. node heuristic_noun heuristically Universe
heuristically=: 1 : '(((] >@{:@{~ (i.~ _ 1&(,@{.)))&m)@<@toString) :: 0:'
extractCities=: 0&{::
extractPaths=: 1&{::
links=: 2&(]\>) NB. nodes 0 3 4 12
NB. cost function
weigh=: [: +/ links@:>@[ ((i.~ _ 2&{.) { 2&{"1@]) extractPaths@] NB. path weigh Universe
steps=: #@>@[ NB. path steps Universe
AStar=: weigh + Crow heuristically
Choice=:2 : '{.@I.@(= u)@:(v"0 _)' NB. frontier (<./)Cost steps Universe
IndexShortest=: <./ Choice steps NB. frontier IndexShortest Universe
IndexLongest=: >./ Choice steps NB. needs all paths, works not
IndexCheapest=: <./ Choice weigh
IndexAStar=: <./ Choice (weigh + AStar)
NB. conversions to index from index or string
toString=: >@(({~ 0&+)~ :: [) extractCities NB. 1 toString Universe
toIndex=: (0+[) :: (]i.<@:>@[) extractCities NB. 1 toIndex Universe
Display=: smoutput@toString
ExtractFrontier=: toIndex ((I.@e.~ _ 1 ,@{. ]) { ]) extractPaths@] NB. 'Arad'ExtractFrontier Universe
Transition=: 1&{"1@ExtractFrontier
NB. frontier is a list of boxed paths
NB. frontier Choose universe returns index of next path to follow
IsEmpty=: 0 = #
IsGoal=: 1 : (':'; 'x m&-:@toString y')
treeSearch=: adverb define
:
'`display isEmpty choose isGoal transition'=. m
'initial goal'=. x
universe=. y
frontier=. ,<initial toIndex universe
while. 0=isEmpty frontier do.
i=. frontier choose universe
path=. i >@{ frontier
state=. {: path
if. state isGoal universe do. path return. end.
frontier=. (<<<i){frontier NB. elision
adjacencies=. state transition universe
frontier=. frontier , path <@,"1 0 adjacencies
end.
EMPTY
)
g=: Display`IsEmpty`0:`('Bucharest'IsGoal)`Transition
(;:'Arad Bucharest')g treeSearch Universe
graphSearch=: adverb define
:
'`display isEmpty choose isGoal transition'=. m
'initial goal'=. x
universe=. y
explored=. ''
frontier=. ,<initial toIndex universe
while. 0=isEmpty frontier do.
i=. frontier choose universe
path=. i >@{ frontier
state=. {: path
if. state isGoal universe do. path return. end.
frontier=. (<<<i){frontier NB. elision
explored=. explored , state
adjacencies=. state transition universe
unseenAdjacencies=. adjacencies -. explored NB. , {:@>frontier
frontier=. frontier , path <@,"1 0 unseenAdjacencies
end.
EMPTY
)
(;:'Arad Bucharest')g graphSearch Universe
Note 'Examples'
NB. Choose cheapest from the frontier
Universe toString~ (;:'Arad Bucharest')(Display`IsEmpty`IndexCheapest`('Bucharest'IsGoal)`Transition) graphSearch Universe
Arad
Sibiu
RimnicuVilcea
Pitesti
Bucharest
NB. Choose longest from the frontier
Universe toString~ (;:'Arad Bucharest')(Display`IsEmpty`IndexLongest`('Bucharest'IsGoal)`Transition) graphSearch Universe
Arad
Zerind
Oradea
Sibiu
RimnicuVilcea
Pitesti
Bucharest
NB. Choose shortest from the frontier
Universe toString~ (;:'Arad Bucharest')(Display`IsEmpty`IndexShortest`('Bucharest'IsGoal)`Transition) graphSearch Universe
Arad
Sibiu
Fagaras
Bucharest
NB. A* search, choose minimal estimated distance to goal + distance covered so far
Universe toString~ (;:'Arad Bucharest')(Display`IsEmpty`IndexAStar`('Bucharest'IsGoal)`Transition) graphSearch Universe
Arad
Sibiu
RimnicuVilcea
Pitesti
Bucharest
)