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