Versuch, eine Schriftstiefen-Erste oder Breitensuche-Curryfunktion zu erhalten

Question

Ich bin neu hier, und ich brauche Hilfe mit einer Funktion, die ich in Schema schreibe.

Im Grunde handelt es sich um eine Suchfunktion, die entweder für die Breiten-Erste-Suche oder Tiefen-Zuerst-Suche funktionieren kann. Ich denke, ich habe die Tiefen-Erst-Kombination und die Breite-Erste-Mischung zur Arbeit bekommen.

Das Problem besteht jedoch darin, die Hauptsuche so zu modifizieren, dass sie als "Curry-Funktion" funktioniert, wenn algorithmusspezifische Merge-Prozeduren (wie die Tiefe-zuerst-Zusammenführung oder die Breite-zuerst-Zusammenführung) übergeben werden Als Argumente verwendet die Suche diesen spezifischen Suchtyp. Die Rückkehr

Es gibt zwei Dateien, die ich damit habe. Münzen sind in Ordnung, aber die Suche muss repariert werden. Wie ändere ich die Suchfunktion hier, um als Curry-Version zu arbeiten?

Hier sind meine Codes unten. Erste für search.ss. Ich habe eine Suche2 als einen frühen Versuch gemacht, aber es hat nicht funktioniert. Ich muss Search oder search2 als die curried Suche arbeiten lassen, (dann löschen Sie das andere). Ich bin mir nicht sicher, aber ich denke, dass die Zusammenführungen und zwei Suchen funktionieren.

;;; 
;;; SEARCH: 
;;; -- Non-curried version of generic search algorithm 
;;; -- Can be customized for depth-first and breadth-first search 
;;; -- You must convert it to a curried version so that 
;;;  - the function accepts 1 algorithm specific parameter and returns a function 
;;;  - that accepts 3 problem-specific parameters and returns a function 
;;;  - that accepths 1 instance specific parameter and performs the search 
;;; -- The 5 parameters are described below 
;;; 
;;; Input: 
;;; merge-queue 
;;;  -- algorithm specific 
;;;  -- procedure that takes a list of new paths and a queue 
;;;  and returns a new queue 
;;; extend 
;;;  -- problem-specific 
;;;  -- procedure that takes a state and a list of visited states, 
;;;  and returns a list of states that are reachable in one move 
;;;  from the given state 
;;; goal? 
;;;  -- problem-specific 
;;;  -- predicate that takes a state and returns true if the 
;;;  state is a goal state, false otherwise 
;;; print-path 
;;;  -- problem-specific 
;;;  -- procedure that takes a state and prints out a state nicely 
;;; init-state 
;;;  -- problem instance-specific 
;;;  -- an initial state to start the search from 
;;; 
;;; OUTPUT: 
;;; -- When succeeded, a path from the initial state to a goal state 
;;; -- When failed, #f 
;;; 


;;Either this or search2 needs to be rewritten into a curried version 
;;To accept either depth-first-merge or breadth-first merge as merge procedures into merge-queue 
(define search 
    (lambda (merge-queue init-config extend goal? print-state) 
    (letrec 
     ((helper 
    (lambda (queue) 
    (newline) 
    (for-each 
    (lambda (p) (print-path p print-state)) 
    queue) 
     (cond ((null? queue) #f) 
      ((goal? (caar queue)) 
     (print-state (caar queue)) 
     (newline) 
     (let ((ans (reverse (car queue)))) 
     (for-each (lambda (x) (print-state x) (newline)) ans) 
     ans)) 
      (else 
       (let ((successors (extend (caar queue)))) 
     (print-state (caar queue)) (newline) 
       (cond ((null? successors) 
         (helper (cdr queue))) 
         (else 
      (for-each (lambda (x) (print-state x) (newline)) 
       successors) 
      (helper 
      (merge-queue (cdr queue) 
       (extend-path successors (car queue)))))))))))) 
    (helper 
    (list (list (config->state init-config)))))) 



(define search2 
    (lambda (merge-queue extend goal? print-path init-state) 
(letrec 
    ((search-helper 
     (lambda (queue visited) 
     (cond 
      ((null? queue) #f) 
      ((goal? (caar queue)) 
      (begin 
       (print-path (car queue)) 
       (car queue))) 
      (else 
      (let ((successors (extend (caar queue) visited))) 
       (cond 
       ((null? successors) 
        (search-helper (cdr queue) visited)) 
       (else 
        (let ((new-paths (extend-path successors (car queue)))) 
        (search-helper 
      (merge-queue queue new-paths) 
      (cond 
      (merge-queue)) 
         (append successors visited))))))))))) 
    (search-helper 
    (list (list init-state)) ; initial queue 
    (list init-state)))))  ; initial visited 


(define extend-path 
    (lambda (successors path) 
    (if (null? successors) 
    '() 
    (cons (cons (car successors) path) 
     (extend-path (cdr successors) path))))) 



;; merge new extended paths to queue for depth first search 
;; - uncomment and define your merge for depth first search 

(define depth-first-merge 
    (lambda (queue paths) 
    (append! paths queue))) 

;; merge new extended paths to queue for breadth first search 
;; - uncomment and define your merge for breadth first search 

(define breadth-first-merge 
    (lambda (queue paths) 
    (append! queue paths))) 


;; customize the generic search for depth first search 
;; - uncomment and define your depth-first-search in terms of your 
;; curried version of search and depth-first-merge 
;; Curry Methods are helpful to this. 

(define depth-first-search (search depth-first-merge)) 
    (lambda (extend goal? print-path) 
    (search (depth-first-merge extend goal? print-path)))) 



;; customize the generic search for breadth first search 
;; - uncomment and define your breadth-first-search in terms of your 
;; curried version of search and breadth-first-merge 

(define breadth-first-search (search breadth-first-merge)) 
    (lambda (extend goal? print-path) 
    (search (breadth-first-merge extend goal? print-path)))) 

Und dies ist der Coins-Dateicode, der den Suchcode ergänzt. Sie befinden sich in separaten Dateien und laden search.ss (das oben genannte).

;; load algorithm specific code for search 
(load "search.ss") 

;;; Problem specific code for solving the old British coin problems 
;;; using the curried version of the simple search procedure. 
;;; The old British coin problem was discussed in the lecture. 
;;; 
;;; To solve the problem, load this file and run 
;;; (coin-depth-first amount) 
;;; or 
;;; (coin-breadth-first amount) 
;;; where, amount is replaced with some number, e.g., 48. 
;;; 
;;; Here, a state is represented as follows: 
;;;  (amount (coin1 coin2 ...)) 
;;; 
;;; The car of the state represents how much change you need to pay further. 
;;; The cadr of the state represents the combination of coins you used 
;;; to pay so far. For example, 
;;;  (48()) 
;;; is the initial state for the amount of 48 cents and 
;;;  (0 (24 24) 
;;; can be one of the goal states using two 24-cent coins. 


;; There are 7 kinds of old British coins 
(define old-british-coins '(120 30 24 12 6 3 1)) 

;; Or, you can do the same for US coins 
(define us-coins '(100 50 25 10 5 1)) 

;; Here, we will do the old British coins 
(define *coins* old-british-coins) 


;; Is a state the goal state? 
(define goal? 
    (lambda (state) 
    (zero? (car state)))) 


;; returns children of a state 
(define extend 
    (lambda (state visited) 
    (let ((coins (applicable-coins state visited *coins*))) 
    (map 
    (lambda (coin) 
     (list (- (car state) coin) 
     (append (cadr state) (list coin)))) 
    coins)))) 


;; find all applicable coins from a state 
(define applicable-coins 
    (lambda (state visited coins) 
    (cond 
    ((null? coins) '()) 
    ((<= (car coins) (car state)) 
     (if (visited? state visited (car coins)) 
     (applicable-coins state visited (cdr coins)) 
     (cons (car coins) (applicable-coins state visited (cdr coins))))) 
    (else (applicable-coins state visited (cdr coins)))))) 


;; see if a state has been visited before 
(define visited? 
    (lambda (state visited coin) 
    (cond 
    ((null? visited) #f) 
    ((= (- (car state) coin) (caar visited)) #t) 
    (else (visited? state (cdr visited) coin))))) 


;; pretty-print a state 
(define pretty-print-path 
    (lambda (path) 
    (pretty-print-state (car path)))) 

(define pretty-print-state 
    (lambda (state) 
    (let ((change (car state)) 
     (coins (cadr state)) 
     (total (apply + (cadr state)))) 
    (printf 
    "===> Total of ~a paid with ~a, with remainder of ~a <===~%" 
    total coins change)))) 


;; customize the generic depth-first-search for coin problem 
(define coin-depth-first-search 
    (depth-first-search extend goal? pretty-print-path)) 

;; instance of a coin problem using depth-first search 
(define coin-depth-first 
    (lambda (amount) 
    (coin-depth-first-search (list amount '())))) 



;; customize the generic breadth-first-search for coin problem 
(define coin-breadth-first-search 
    (breadth-first-search extend goal? pretty-print-path)) 


;; instance of a coin problem with breadth-first search 
(define coin-breadth-first 
    (lambda (amount) 
    (coin-breadth-first-search (list amount '())))) 

Kann jemand mir bitte helfen? Ich denke, alles, was ich brauche, um es zum Laufen zu bringen, ist herauszufinden, wie man den Code search oder search2 zu einer Curry-Version macht.

Answer 1

eine Funktion Curry bedeutet es, in einer solchen Weise neu zu definieren, dass es eine Anzahl von Parametern geringer als die aktuelle Definition nimmt und gibt eine neue Funktion, die den Rest der Parameter und durchzuführen, um die Arbeit der ersten dauert . Zum Beispiel können Sie die folgenden zwei Parameter Summierfunktion Curry:

(define add 
    (lambda (a b) 
    (+ a b))) 

(add 7 10) ;; => 17 

auf folgende Weise:

(define add-to 
    (lambda (a) 
    (lambda (b) 
     (+ a b)))) 

((add-to 7) 10) ;; => 17 

(define add-to-7 (add-to 7)) ;; we give a name to the function that add 7 to its argument 

(add-to-7 8) ;; => 15 

(add-to-7 9) ;; => 16 

Also, die search2 Funktion zu transformieren (müssen Sie diese Funktion seit dem letzten Parameter erweitern ist das Problem Instanz spezifische):

:

(define search2 
    (lambda (merge-queue extend goal? print-path init-state) 
    ...body of search2... 

nach Bedarf, können Sie einfach so etwas schreiben könnte

(define search2 
    (lambda (merge-queue) 
    (lambda (extend goal? print-path) 
     (lambda (init-state) 
     ...body of search2... 

und dann mit der richtigen Anzahl von Parametern aufgerufen werden, können Sie "teilweise" Funktionen erhalten, die später aufgerufen werden.Zum Beispiel können Sie eine generische Tiefensuche definieren als:

(define depth-first-search (search2 depth-first-merge)) 

dann können Sie die Tiefensuche für die Münze Problem bei entsprechenden Definitionen für die Münze Funktionen spezialisiert definieren:

(define coin-depth-first (depth-first-search coin-extend coin-goal? coin-print-path)) 

und schließlich Sie können es mit einer bestimmten Menge anrufen, um das Problem zu lösen: