試圖得到一個計劃深度優先或廣度優先搜索柯里功能工作

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)