Changeset 29270 in project
 Timestamp:
 06/28/13 10:03:35 (8 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

wiki/eggref/4/aima
r27477 r29270 1 == aima1 == title 2 2 3 3 AIMAsupport for Chicken Scheme … … 144 144 `(lambda () 145 145 (,%print ',object (,makeprintableobject ,object))))))))) 146 </enscript> 147 === AIMACSP 148 ==== {{aimacsp}} 149 '''[module]''' {{aimacsp}} 150 151 Solver for constraintsatisfactionproblems 152 * [[#ac3]] 153 * [[#backtrackingsearch]] 154 * [[#backtrackingenumeration]] 155 * [[#failure?]] 156 * [[#makecsp]] 157 * [[#neq?]] 158 ==== {{failure}} 159 <constant>failure â (makefailure)</constant> 160 The failure object: to distinguish ''bonafide'' solutions to a 161 CSP that are {{#f}}. 162 <enscript highlight="scheme">(define failure (makefailure)) 163 </enscript> 164 ==== {{csp}} 165 <record>csp</record> 166 A constraintsatisfactionproblem 167 ; domains : A hashtable mapping variables to possible values 168 ; constraints : A hashtable mapping pairs of variables to a dyadic lambda which returns {{#f}} if the values don't satisfy the constraint 169 ; neighbors : A hashtable adjacencylist of constraints 170 <enscript highlight="scheme">(definerecordandprinter csp domains constraints neighbors) 171 </enscript> 172 ===== Examples 173 A trivial (but inconsistent) CSP 174 (define arcinconsistentcoloring 175 (makecsp (alist>hashtable '((a white) (b white))) 176 (alist>hashtable 177 `(((a . b) unquote neq?) ((b . a) unquote neq?))) 178 (alist>hashtable '((a b) (b a))))) 179 ==== {{backtrackingsearch}} 180 <procedure>(backtrackingsearch csp) â object or {{failure}}</procedure> 181 Find a solution to the CSP or return {{failure}}. 182 ; csp : The CSP to solve 183 <enscript highlight="scheme">(define (backtrackingsearch csp) 184 (let ((enumeration (backtrackingenumeration 1 csp))) 185 (if (null? enumeration) failure (car enumeration)))) 186 </enscript> 187 ===== Examples 188 A trivial 2coloring problem 189 (define arcconsistentcoloring 190 (makecsp (alist>hashtable '((a white black) (b white black))) 191 (alist>hashtable 192 `(((a . b) unquote neq?) ((b . a) unquote neq?))) 193 (alist>hashtable '((a b) (b a))))) 194 (test "Arcconsistent coloring" 195 '((b . white) (a . black)) 196 (hashtable>alist (backtrackingsearch arcconsistentcoloring))) 197 ==== {{backtrackingenumeration}} 198 <procedure>(backtrackingenumeration csp) â list</procedure> 199 <procedure>(backtrackingenumeration n csp) â list</procedure> 200 Enumerate up to {{n}} solutions of the {{csp}}; enumerate all if {{n}} 201 is {{#f}} or unspecified. 202 ; n : Enumerate up to {{n}} solutions 203 ; csp : The CSP to solve 204 <enscript highlight="scheme">(define backtrackingenumeration 205 (caselambda 206 ((csp) (backtrackingenumeration #f csp)) 207 ((n csp) 208 (let ((enumeration (makeparameter '()))) 209 (backtrackenumerate n enumeration (makeassignment csp) csp) 210 (enumeration))))) 211 </enscript> 212 ==== {{ac3}} 213 <procedure>(ac3 csp) â unspecified</procedure> 214 Check arcconsistency of a csp; returns {{#t}} if the object is 215 arcconsistent. 216 ; csp : A constraintsatisfaction object 217 ; to : boolean 218 <enscript highlight="scheme">(define (ac3 csp) 219 (let ((queue (list>queue (hashtablekeys (cspconstraints csp))))) 220 (let iter () 221 (if (queueempty? queue) 222 #t 223 (match (queueremove! queue) 224 ((x . y) 225 (if (revise csp x y) 226 (if (zero? (length (hashtableref (cspdomains csp) x))) 227 #f 228 (begin 229 (foreach 230 (lambda (neighbor) 231 (queueadd! queue (cons neighbor x))) 232 (delete y (hashtableref (cspneighbors csp) x))) 233 (iter))) 234 (iter)))))))) 235 </enscript> 236 ==== {{neq?}} 237 <procedure>(neq? x y) â boolean</procedure> 238 The complement to {{eq?}} 239 ; x : Comparandum 240 ; y : Comparator 241 <enscript highlight="scheme">(define neq? (complement eq?)) 242 </enscript> 243 === AIMATessellation 244 ==== {{aimatessellation}} 245 '''[module]''' {{aimatessellation}} 246 247 aimatessellation has procedures for tessellating a plane into 248 disjoint, convex polygons suitable for exercise 3.7; and then plotting 249 that tessellation with a path. 250 * [[#joinanimations]] 251 * [[#makepoint]] 252 * [[#makenode]] 253 * [[#nvertices]] 254 * [[#nodestate]] 255 * [[#nodestateset!]] 256 * [[#nodeparent]] 257 * [[#nodeparentset!]] 258 * [[#nodeaction]] 259 * [[#nodeactionset!]] 260 * [[#nodepathcost]] 261 * [[#nodepathcostset!]] 262 * [[#pointdistance]] 263 * [[#plottessellation]] 264 * [[#plottessellation/animation]] 265 * [[#pointx]] 266 * [[#pointy]] 267 * [[#predecessorpath]] 268 * [[#tessellate]] 269 * [[#tessellationpoints]] 270 * [[#tessellationneighbors]] 271 * [[#tessellationstart]] 272 * [[#tessellationend]] 273 ==== {{node}} 274 <record>node</record> 275 Data structure for graphs 276 ; state : An indexable point 277 ; parent : The nodepredecessor 278 ; action : Not used 279 ; pathcost : Cost of the path up to this point 280 <enscript highlight="scheme">(definerecord node state parent action pathcost) 281 </enscript> 282 ==== {{tessellation}} 283 <record>tessellation</record> 284 tessellation contains point and adjacency information for a 285 tessellatedplane; as well as start and end nodes. 286 ; points : The points in the tessellation 287 ; neighbors : The adjacency information for points 288 ; start : The start node for the problem 289 ; end : The end node for the problem 290 <enscript highlight="scheme">(definerecordandprinter tessellation Robject points neighbors start end) 291 </enscript> 292 ==== {{tessellate}} 293 <procedure>(tessellate) â tessellation</procedure> 294 <procedure>(tessellate nvertices) â tessellation</procedure> 295 Tessellate the plane into disjoint, convex polygons. 296 ; nvertices : The numbers of vertices in the tessellation 297 <enscript highlight="scheme">(define tessellate 298 (caselambda 299 (() (tessellate (nvertices))) 300 ((nvertices) 301 (let* ((Rvoronoi (Rvoronoi nvertices)) (voronoi (voronoi Rvoronoi))) 302 (let* ((neighbors (neighbors voronoi)) (points (points neighbors))) 303 (let ((start (start points)) (end (end points))) 304 (maketessellation Rvoronoi points neighbors start end))))))) 305 </enscript> 306 ==== {{pointdistance}} 307 <procedure>(pointdistance p1 p2) â distance</procedure> 308 Calculate the distance between two points. 309 ; p1 : The first point 310 ; p2 : The second point 311 <enscript highlight="scheme">(define (pointdistance p1 p2) 312 (sqrt (+ (expt ( (pointx p1) (pointx p2)) 2) 313 (expt ( (pointy p1) (pointy p2)) 2)))) 314 </enscript> 315 ==== {{predecessorpath}} 316 <procedure>(predecessorpath node) â list</procedure> 317 List the predecessors of this node. 318 ; node : The node to predecess 319 <enscript highlight="scheme">(define (predecessorpath node) 320 (let iter ((path (list node))) 321 (let ((parent (nodeparent (car path)))) 322 (if parent (iter (cons parent path)) path)))) 323 </enscript> 324 ==== {{plottessellation}} 325 <procedure>(plottessellation tessellation path title filename) â unspecified</procedure> 326 Plot the tessellation with its start and end nodes, as well as 327 the path taken from start to end. 328 ; tessellation : The tessellation to plot 329 ; path : A list of nodes 330 ; title : Title for the graph 331 ; filename : The PNG to which to write 332 <enscript highlight="scheme">(define (plottessellation tessellation path title filename) 333 (let ((title (maketitle title (length path) (nodepathcost (car path))))) 334 (let ((start (tessellationstart tessellation)) 335 (end (tessellationend tessellation))) 336 (R (plot.voronoi 337 ,(tessellationRobject tessellation) 338 ,(list>vector (pathx path)) 339 ,(list>vector (pathy path)) 340 ,(pointx start) 341 ,(pointy start) 342 ,(pointx end) 343 ,(pointy end) 344 ,filename 345 ,title))))) 346 </enscript> 347 ==== {{plottessellation/animation}} 348 <procedure>(plottessellation/animation tessellation path title filename) â unspecified</procedure> 349 Plot the tessellation as an animation fit for YouTube. 350 ; tessellation : The tessellation to plot 351 ; path : A list of nodes 352 ; title : Title for the animation 353 ; filename : A filename for the movie (ending in e.g. `.avi') 354 <enscript highlight="scheme">(define (plottessellation/animation tessellation path title filename) 355 (let ((directory (createtemporarydirectory))) 356 (let iter ((path path) (i ( (length path) 1))) 357 (if (null? path) 358 (let* ((frames 359 (cdr (sort (glob (makepathname directory "*")) string<?))) 360 (finalframe (last frames)) 361 (epilogue (makelist 10 finalframe))) 362 (let ((framelist (createtemporaryfile))) 363 (withoutputtofile 364 framelist 365 (lambda () (foreach writeline (append frames epilogue)))) 366 (run (mencoder 367 ,(format "mf://@~a" framelist) 368 mf 369 fps=4 370 o 371 ,filename 372 ovc 373 lavc)))) 374 (let ((filename (animationfilename directory i))) 375 (format #t "~a~%" filename) 376 (plottessellation tessellation path title filename) 377 (iter (cdr path) ( i 1))))))) 378 </enscript> 379 ==== {{joinanimations}} 380 <procedure>(joinanimations output . animations) â unspecified</procedure> 381 Join the animation files into one long file. 382 ; output : The resultant file 383 ; animations : The input files 384 <enscript highlight="scheme">(define (joinanimations output . animations) 385 (run (mencoder ovc copy idx o ,output ,@animations))) 146 386 </enscript> 147 387 === AIMAVacuum … … 898 1138 ((makeanimationfinalizer compositedirectory compositefile))))))) 899 1139 </enscript> 900 === AIMATessellation901 ==== {{aimatessellation}}902 '''[module]''' {{aimatessellation}}903 904 aimatessellation has procedures for tessellating a plane into905 disjoint, convex polygons suitable for exercise 3.7; and then plotting906 that tessellation with a path.907 * [[#makenode]]908 * [[#nodestate]]909 * [[#nodestateset!]]910 * [[#nodeparent]]911 * [[#nodeparentset!]]912 * [[#nodeaction]]913 * [[#nodeactionset!]]914 * [[#nodepathcost]]915 * [[#nodepathcostset!]]916 * [[#pointdistance]]917 * [[#plottessellation]]918 * [[#plottessellation/animation]]919 * [[#pointx]]920 * [[#pointy]]921 * [[#predecessorpath]]922 * [[#tessellate]]923 * [[#tessellationpoints]]924 * [[#tessellationneighbors]]925 * [[#tessellationstart]]926 * [[#tessellationend]]927 ==== {{node}}928 <record>node</record>929 Data structure for graphs930 ; state : An indexable point931 ; parent : The nodepredecessor932 ; action : Not used933 ; pathcost : Cost of the path up to this point934 <enscript highlight="scheme">(definerecord node state parent action pathcost)935 </enscript>936 ==== {{tessellation}}937 <record>tessellation</record>938 tessellation contains point and adjacency information for a939 tessellatedplane; as well as start and end nodes.940 ; points : The points in the tessellation941 ; neighbors : The adjacency information for points942 ; start : The start node for the problem943 ; end : The end node for the problem944 <enscript highlight="scheme">(definerecordandprinter tessellation Robject points neighbors start end)945 </enscript>946 ==== {{tessellate}}947 <procedure>(tessellate) â tessellation</procedure>948 <procedure>(tessellate nvertices) â tessellation</procedure>949 Tessellate the plane into disjoint, convex polygons.950 ; nvertices : The numbers of vertices in the tessellation951 <enscript highlight="scheme">(define tessellate952 (caselambda953 (() (tessellate (nvertices)))954 ((nvertices)955 (let* ((Rvoronoi (Rvoronoi nvertices)) (voronoi (voronoi Rvoronoi)))956 (let* ((neighbors (neighbors voronoi)) (points (points neighbors)))957 (let ((start (start points)) (end (end points)))958 (maketessellation Rvoronoi points neighbors start end)))))))959 </enscript>960 ==== {{pointdistance}}961 <procedure>(pointdistance p1 p2) â distance</procedure>962 Calculate the distance between two points.963 ; p1 : The first point964 ; p2 : The second point965 <enscript highlight="scheme">(define (pointdistance p1 p2)966 (sqrt (+ (expt ( (pointx p1) (pointx p2)) 2)967 (expt ( (pointy p1) (pointy p2)) 2))))968 </enscript>969 ==== {{predecessorpath}}970 <procedure>(predecessorpath node) â list</procedure>971 List the predecessors of this node.972 ; node : The node to predecess973 <enscript highlight="scheme">(define (predecessorpath node)974 (let iter ((path (list node)))975 (let ((parent (nodeparent (car path))))976 (if parent (iter (cons parent path)) path))))977 </enscript>978 ==== {{plottessellation}}979 <procedure>(plottessellation tessellation path title filename) â unspecified</procedure>980 Plot the tessellation with its start and end nodes, as well as981 the path taken from start to end.982 ; tessellation : The tessellation to plot983 ; path : A list of nodes984 ; title : Title for the graph985 ; filename : The PNG to which to write986 <enscript highlight="scheme">(define (plottessellation tessellation path title filename)987 (let ((title (maketitle title (length path) (nodepathcost (car path)))))988 (let ((start (tessellationstart tessellation))989 (end (tessellationend tessellation)))990 (Reval991 "plot.voronoi"992 (tessellationRobject tessellation)993 (list>vector (pathx path))994 (list>vector (pathy path))995 (pointx start)996 (pointy start)997 (pointx end)998 (pointy end)999 filename1000 title))))1001 </enscript>1002 ==== {{plottessellation/animation}}1003 <procedure>(plottessellation/animation tessellation path title filename) â unspecified</procedure>1004 Plot the tessellation as an animation fit for YouTube.1005 ; tessellation : The tessellation to plot1006 ; path : A list of nodes1007 ; title : Title for the animation1008 ; filename : A base filename, unto which will be appended `.avi'1009 <enscript highlight="scheme">(define (plottessellation/animation tessellation path title filename)1010 (let ((directory (createtemporarydirectory)))1011 (let iter ((path (reverse path)) (i ( (length path) 1)))1012 (debug i)1013 (if (null? path)1014 (begin1015 (system*1016 "convert $(find ~a type f  sort k 1.~a n) $(yes $(find ~a type f  sort k 1.~a n  tail n 1)  head n 10) loop 0 ~a.gif"1017 directory1018 (+ (stringlength directory) 2)1019 directory1020 (+ (stringlength directory) 2)1021 filename)1022 (system* "mencoder ~a.gif ovc lavc o ~a.avi" filename filename))1023 (begin1024 (plottessellation1025 tessellation1026 path1027 title1028 (makepathname directory (format "~a.png" i)))1029 (iter (cdr path) ( i 1)))))))1030 </enscript>1031 1140 === About this egg 1032 1141
Note: See TracChangeset
for help on using the changeset viewer.