Changeset 29270 in project


Ignore:
Timestamp:
06/28/13 10:03:35 (8 years ago)
Author:
Peter Danenberg
Message:

Add docs for CSPs; generally re-arrange.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • wiki/eggref/4/aima

    r27477 r29270  
    1 == aima
     1== title
    22
    33AIMA-support for Chicken Scheme
     
    144144                `(lambda ()
    145145                   (,%print ',object (,make-printable-object ,object)))))))))
     146</enscript>
     147=== AIMA-CSP
     148==== {{aima-csp}}
     149'''[module]''' {{aima-csp}}
     150
     151Solver for constraint-satisfaction-problems
     152* [[#ac-3]]
     153* [[#backtracking-search]]
     154* [[#backtracking-enumeration]]
     155* [[#failure?]]
     156* [[#make-csp]]
     157* [[#neq?]]
     158==== {{failure}}
     159<constant>failure → (make-failure)</constant>
     160The failure object: to distinguish ''bona-fide'' solutions to a
     161CSP that are {{#f}}.
     162<enscript highlight="scheme">(define failure (make-failure))
     163</enscript>
     164==== {{csp}}
     165<record>csp</record>
     166A constraint-satisfaction-problem
     167; domains : A hash-table mapping variables to possible values
     168; constraints : A hash-table mapping pairs of variables to a dyadic lambda which returns {{#f}} if the values don't satisfy the constraint
     169; neighbors : A hash-table adjacency-list of constraints
     170<enscript highlight="scheme">(define-record-and-printer csp domains constraints neighbors)
     171</enscript>
     172===== Examples
     173A trivial (but inconsistent) CSP
     174 (define arc-inconsistent-coloring
     175   (make-csp (alist->hash-table '((a white) (b white)))
     176             (alist->hash-table
     177              `(((a . b) unquote neq?) ((b . a) unquote neq?)))
     178             (alist->hash-table '((a b) (b a)))))
     179==== {{backtracking-search}}
     180<procedure>(backtracking-search csp) → object or {{failure}}</procedure>
     181Find a solution to the CSP or return {{failure}}.
     182; csp : The CSP to solve
     183<enscript highlight="scheme">(define (backtracking-search csp)
     184  (let ((enumeration (backtracking-enumeration 1 csp)))
     185    (if (null? enumeration) failure (car enumeration))))
     186</enscript>
     187===== Examples
     188A trivial 2-coloring problem
     189 (define arc-consistent-coloring
     190   (make-csp (alist->hash-table '((a white black) (b white black)))
     191             (alist->hash-table
     192              `(((a . b) unquote neq?) ((b . a) unquote neq?)))
     193             (alist->hash-table '((a b) (b a)))))
     194 (test "Arc-consistent coloring"
     195   '((b . white) (a . black))
     196   (hash-table->alist (backtracking-search arc-consistent-coloring)))
     197==== {{backtracking-enumeration}}
     198<procedure>(backtracking-enumeration csp) → list</procedure>
     199<procedure>(backtracking-enumeration n csp) → list</procedure>
     200Enumerate up to {{n}} solutions of the {{csp}}; enumerate all if {{n}}
     201is {{#f}} or unspecified.
     202; n : Enumerate up to {{n}} solutions
     203; csp : The CSP to solve
     204<enscript highlight="scheme">(define backtracking-enumeration
     205  (case-lambda
     206    ((csp) (backtracking-enumeration #f csp))
     207    ((n csp)
     208     (let ((enumeration (make-parameter '())))
     209       (backtrack-enumerate n enumeration (make-assignment csp) csp)
     210       (enumeration)))))
     211</enscript>
     212==== {{ac-3}}
     213<procedure>(ac-3 csp) → unspecified</procedure>
     214Check arc-consistency of a csp; returns {{#t}} if the object is
     215arc-consistent.
     216; csp : A constraint-satisfaction object
     217; to : boolean
     218<enscript highlight="scheme">(define (ac-3 csp)
     219  (let ((queue (list->queue (hash-table-keys (csp-constraints csp)))))
     220    (let iter ()
     221      (if (queue-empty? queue)
     222        #t
     223        (match (queue-remove! queue)
     224               ((x . y)
     225                (if (revise csp x y)
     226                  (if (zero? (length (hash-table-ref (csp-domains csp) x)))
     227                    #f
     228                    (begin
     229                      (for-each
     230                        (lambda (neighbor)
     231                          (queue-add! queue (cons neighbor x)))
     232                        (delete y (hash-table-ref (csp-neighbors csp) x)))
     233                      (iter)))
     234                  (iter))))))))
     235</enscript>
     236==== {{neq?}}
     237<procedure>(neq? x y) → boolean</procedure>
     238The complement to {{eq?}}
     239; x : Comparandum
     240; y : Comparator
     241<enscript highlight="scheme">(define neq? (complement eq?))
     242</enscript>
     243=== AIMA-Tessellation
     244==== {{aima-tessellation}}
     245'''[module]''' {{aima-tessellation}}
     246
     247aima-tessellation has procedures for tessellating a plane into
     248disjoint, convex polygons suitable for exercise 3.7; and then plotting
     249that tessellation with a path.
     250* [[#join-animations]]
     251* [[#make-point]]
     252* [[#make-node]]
     253* [[#n-vertices]]
     254* [[#node-state]]
     255* [[#node-state-set!]]
     256* [[#node-parent]]
     257* [[#node-parent-set!]]
     258* [[#node-action]]
     259* [[#node-action-set!]]
     260* [[#node-path-cost]]
     261* [[#node-path-cost-set!]]
     262* [[#point-distance]]
     263* [[#plot-tessellation]]
     264* [[#plot-tessellation/animation]]
     265* [[#point-x]]
     266* [[#point-y]]
     267* [[#predecessor-path]]
     268* [[#tessellate]]
     269* [[#tessellation-points]]
     270* [[#tessellation-neighbors]]
     271* [[#tessellation-start]]
     272* [[#tessellation-end]]
     273==== {{node}}
     274<record>node</record>
     275Data structure for graphs
     276; state : An indexable point
     277; parent : The node-predecessor
     278; action : Not used
     279; path-cost : Cost of the path up to this point
     280<enscript highlight="scheme">(define-record node state parent action path-cost)
     281</enscript>
     282==== {{tessellation}}
     283<record>tessellation</record>
     284tessellation contains point and adjacency information for a
     285tessellated-plane; 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">(define-record-and-printer tessellation R-object points neighbors start end)
     291</enscript>
     292==== {{tessellate}}
     293<procedure>(tessellate) → tessellation</procedure>
     294<procedure>(tessellate n-vertices) → tessellation</procedure>
     295Tessellate the plane into disjoint, convex polygons.
     296; n-vertices : The numbers of vertices in the tessellation
     297<enscript highlight="scheme">(define tessellate
     298  (case-lambda
     299    (() (tessellate (n-vertices)))
     300    ((n-vertices)
     301     (let* ((R-voronoi (R-voronoi n-vertices)) (voronoi (voronoi R-voronoi)))
     302       (let* ((neighbors (neighbors voronoi)) (points (points neighbors)))
     303         (let ((start (start points)) (end (end points)))
     304           (make-tessellation R-voronoi points neighbors start end)))))))
     305</enscript>
     306==== {{point-distance}}
     307<procedure>(point-distance p1 p2) → distance</procedure>
     308Calculate the distance between two points.
     309; p1 : The first point
     310; p2 : The second point
     311<enscript highlight="scheme">(define (point-distance p1 p2)
     312  (sqrt (+ (expt (- (point-x p1) (point-x p2)) 2)
     313           (expt (- (point-y p1) (point-y p2)) 2))))
     314</enscript>
     315==== {{predecessor-path}}
     316<procedure>(predecessor-path node) → list</procedure>
     317List the predecessors of this node.
     318; node : The node to predecess
     319<enscript highlight="scheme">(define (predecessor-path node)
     320  (let iter ((path (list node)))
     321    (let ((parent (node-parent (car path))))
     322      (if parent (iter (cons parent path)) path))))
     323</enscript>
     324==== {{plot-tessellation}}
     325<procedure>(plot-tessellation tessellation path title filename) → unspecified</procedure>
     326Plot the tessellation with its start and end nodes, as well as
     327the 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 (plot-tessellation tessellation path title filename)
     333  (let ((title (make-title title (length path) (node-path-cost (car path)))))
     334    (let ((start (tessellation-start tessellation))
     335          (end (tessellation-end tessellation)))
     336      (R (plot.voronoi
     337           ,(tessellation-R-object tessellation)
     338           ,(list->vector (path-x path))
     339           ,(list->vector (path-y path))
     340           ,(point-x start)
     341           ,(point-y start)
     342           ,(point-x end)
     343           ,(point-y end)
     344           ,filename
     345           ,title)))))
     346</enscript>
     347==== {{plot-tessellation/animation}}
     348<procedure>(plot-tessellation/animation tessellation path title filename) → unspecified</procedure>
     349Plot 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 (plot-tessellation/animation tessellation path title filename)
     355  (let ((directory (create-temporary-directory)))
     356    (let iter ((path path) (i (- (length path) 1)))
     357      (if (null? path)
     358        (let* ((frames
     359                 (cdr (sort (glob (make-pathname directory "*")) string<?)))
     360               (final-frame (last frames))
     361               (epilogue (make-list 10 final-frame)))
     362          (let ((frame-list (create-temporary-file)))
     363            (with-output-to-file
     364              frame-list
     365              (lambda () (for-each write-line (append frames epilogue))))
     366            (run (mencoder
     367                   ,(format "mf://@~a" frame-list)
     368                   -mf
     369                   fps=4
     370                   -o
     371                   ,filename
     372                   -ovc
     373                   lavc))))
     374        (let ((filename (animation-filename directory i)))
     375          (format #t "~a~%" filename)
     376          (plot-tessellation tessellation path title filename)
     377          (iter (cdr path) (- i 1)))))))
     378</enscript>
     379==== {{join-animations}}
     380<procedure>(join-animations output . animations) → unspecified</procedure>
     381Join the animation files into one long file.
     382; output : The resultant file
     383; animations : The input files
     384<enscript highlight="scheme">(define (join-animations output . animations)
     385  (run (mencoder -ovc copy -idx -o ,output ,@animations)))
    146386</enscript>
    147387=== AIMA-Vacuum
     
    8981138         ((make-animation-finalizer composite-directory composite-file)))))))
    8991139</enscript>
    900 === AIMA-Tessellation
    901 ==== {{aima-tessellation}}
    902 '''[module]''' {{aima-tessellation}}
    903 
    904 aima-tessellation has procedures for tessellating a plane into
    905 disjoint, convex polygons suitable for exercise 3.7; and then plotting
    906 that tessellation with a path.
    907 * [[#make-node]]
    908 * [[#node-state]]
    909 * [[#node-state-set!]]
    910 * [[#node-parent]]
    911 * [[#node-parent-set!]]
    912 * [[#node-action]]
    913 * [[#node-action-set!]]
    914 * [[#node-path-cost]]
    915 * [[#node-path-cost-set!]]
    916 * [[#point-distance]]
    917 * [[#plot-tessellation]]
    918 * [[#plot-tessellation/animation]]
    919 * [[#point-x]]
    920 * [[#point-y]]
    921 * [[#predecessor-path]]
    922 * [[#tessellate]]
    923 * [[#tessellation-points]]
    924 * [[#tessellation-neighbors]]
    925 * [[#tessellation-start]]
    926 * [[#tessellation-end]]
    927 ==== {{node}}
    928 <record>node</record>
    929 Data structure for graphs
    930 ; state : An indexable point
    931 ; parent : The node-predecessor
    932 ; action : Not used
    933 ; path-cost : Cost of the path up to this point
    934 <enscript highlight="scheme">(define-record node state parent action path-cost)
    935 </enscript>
    936 ==== {{tessellation}}
    937 <record>tessellation</record>
    938 tessellation contains point and adjacency information for a
    939 tessellated-plane; as well as start and end nodes.
    940 ; points : The points in the tessellation
    941 ; neighbors : The adjacency information for points
    942 ; start : The start node for the problem
    943 ; end : The end node for the problem
    944 <enscript highlight="scheme">(define-record-and-printer tessellation R-object points neighbors start end)
    945 </enscript>
    946 ==== {{tessellate}}
    947 <procedure>(tessellate) → tessellation</procedure>
    948 <procedure>(tessellate n-vertices) → tessellation</procedure>
    949 Tessellate the plane into disjoint, convex polygons.
    950 ; n-vertices : The numbers of vertices in the tessellation
    951 <enscript highlight="scheme">(define tessellate
    952   (case-lambda
    953     (() (tessellate (n-vertices)))
    954     ((n-vertices)
    955      (let* ((R-voronoi (R-voronoi n-vertices)) (voronoi (voronoi R-voronoi)))
    956        (let* ((neighbors (neighbors voronoi)) (points (points neighbors)))
    957          (let ((start (start points)) (end (end points)))
    958            (make-tessellation R-voronoi points neighbors start end)))))))
    959 </enscript>
    960 ==== {{point-distance}}
    961 <procedure>(point-distance p1 p2) → distance</procedure>
    962 Calculate the distance between two points.
    963 ; p1 : The first point
    964 ; p2 : The second point
    965 <enscript highlight="scheme">(define (point-distance p1 p2)
    966   (sqrt (+ (expt (- (point-x p1) (point-x p2)) 2)
    967            (expt (- (point-y p1) (point-y p2)) 2))))
    968 </enscript>
    969 ==== {{predecessor-path}}
    970 <procedure>(predecessor-path node) → list</procedure>
    971 List the predecessors of this node.
    972 ; node : The node to predecess
    973 <enscript highlight="scheme">(define (predecessor-path node)
    974   (let iter ((path (list node)))
    975     (let ((parent (node-parent (car path))))
    976       (if parent (iter (cons parent path)) path))))
    977 </enscript>
    978 ==== {{plot-tessellation}}
    979 <procedure>(plot-tessellation tessellation path title filename) → unspecified</procedure>
    980 Plot the tessellation with its start and end nodes, as well as
    981 the path taken from start to end.
    982 ; tessellation : The tessellation to plot
    983 ; path : A list of nodes
    984 ; title : Title for the graph
    985 ; filename : The PNG to which to write
    986 <enscript highlight="scheme">(define (plot-tessellation tessellation path title filename)
    987   (let ((title (make-title title (length path) (node-path-cost (car path)))))
    988     (let ((start (tessellation-start tessellation))
    989           (end (tessellation-end tessellation)))
    990       (R-eval
    991         "plot.voronoi"
    992         (tessellation-R-object tessellation)
    993         (list->vector (path-x path))
    994         (list->vector (path-y path))
    995         (point-x start)
    996         (point-y start)
    997         (point-x end)
    998         (point-y end)
    999         filename
    1000         title))))
    1001 </enscript>
    1002 ==== {{plot-tessellation/animation}}
    1003 <procedure>(plot-tessellation/animation tessellation path title filename) → unspecified</procedure>
    1004 Plot the tessellation as an animation fit for YouTube.
    1005 ; tessellation : The tessellation to plot
    1006 ; path : A list of nodes
    1007 ; title : Title for the animation
    1008 ; filename : A base filename, unto which will be appended `.avi'
    1009 <enscript highlight="scheme">(define (plot-tessellation/animation tessellation path title filename)
    1010   (let ((directory (create-temporary-directory)))
    1011     (let iter ((path (reverse path)) (i (- (length path) 1)))
    1012       (debug i)
    1013       (if (null? path)
    1014         (begin
    1015           (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             directory
    1018             (+ (string-length directory) 2)
    1019             directory
    1020             (+ (string-length directory) 2)
    1021             filename)
    1022           (system* "mencoder ~a.gif -ovc lavc -o ~a.avi" filename filename))
    1023         (begin
    1024           (plot-tessellation
    1025             tessellation
    1026             path
    1027             title
    1028             (make-pathname directory (format "~a.png" i)))
    1029           (iter (cdr path) (- i 1)))))))
    1030 </enscript>
    10311140=== About this egg
    10321141
Note: See TracChangeset for help on using the changeset viewer.