试图得到一个计划深度优先或广度优先搜索柯里功能工作

Question

我在这里是新的，我需要一个函数，我在计划书写的帮助。

基本上，它涉及一个搜索功能，可以用于广度优先搜索或深度优先搜索。我想我得到了深度优先合并和广度优先合并的工作。

但是，问题是修改主要搜索以作为“currying函数”，以便在算法特定的合并过程（例如深度优先合并或宽度优先合并）传入时作为参数，搜索使用该特定类型的搜索。退货

我有两个文件。硬币没问题，但搜索需求固定。如何修改搜索功能以作为咖喱版使用？

这是我的代码如下。第一个用于search.ss。我作为一个早期尝试进行了搜索2，但它没有奏效。我需要将搜索或搜索2作为咖喱搜索，然后删除其他搜索。我不确定，但我认为合并和两个搜索正在工作。

;;; 
;;; 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)))) 

而这是用于恭维搜索代码的Coins文件代码。他们在单独的文件中，并加载search.ss（上面的）来工作。

;; 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 '())))) 

有人可以帮我吗？我想我需要做的就是找出如何让搜索或search2代码变成一个咖喱版。

Answer 1

要咖喱一个功能装置，以重新定义它以这样的方式，它需要大量的参数小于当前定义，并返回一个新函数，它的参数的其余部分，并执行第一个的工作。举例来说，你可以咖喱以下两个参数求和函数：

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

(add 7 10) ;; => 17 

下列方式

：

(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 

因此，改造search2功能（必须扩展该功能，因为它的最后一个参数是问题实例具体之一）：

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

根据需要，你可以简单地写是这样的：

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

然后，使用正确数量的参数调用它，可以获得稍后调用的“部分”函数。例如，您可以定义一个通用的深度优先搜索为：

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

，那么你可以定义专门针对硬币问题的深度优先搜索，给予适当的定义为硬币功能：

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

最后你可以用一定量的调用它来解决这个问题：

(coin-depth-first 100)