帶謂詞函數的圖搜索，跟蹤跳數限制

Question

以下代碼搜索圖並根據作爲參數傳遞的謂詞函數返回true或false。

該圖以鄰接表的形式表示。

假設圖形不包含循環。

代碼：

(define (search predicate? key) 
    (define value-list (lookup key)) 
    (if (not (empty? value-list)) 
     (if (findf predicate? value-list) 
      #t 
      (ormap (curry search predicate?) value-list)) 
     #f)) 

的loopup功能用來做一個哈希表的查找，並返回其相應的路徑。

搜索函數獲取路徑，如果發現爲非空，則嘗試使用謂詞函數查找元素，如果找到，則返回true，否則調用list（）中的每個元素的search（）。

這似乎工作。

現在卡住搭售實現如下：

目前搜索功能遍歷完全圖和謂語適用於所有的節點。

我希望創建一個謂詞函數，它不僅包含要搜索的元素，還包含跳躍限制。

例如： 如果跳數限制爲1：當且僅當搜索節點在1跳內時謂詞函數才返回true，否則返回false。

我希望在不修改搜索（）的情況下概括n的跳數限制。

事情，我認爲到現在解決這個：

1.I可以改變搜索功能，通過跳數作爲參數，並用它來終止了遞歸的，但是我不希望改變搜索功能。

2.計算可用給定跳躍限制訪問的節點數並將該信息存儲在謂詞函數中，並且對於謂詞函數的每次調用，遞減計數並且如果計數命中0返回錯誤每次。 （但我不知道如何實現上述（也許關閉？），也不認爲這將工作，因爲計數可能會用盡最長的節點列表）

3.如果我能找到調用者在謂詞函數中，即如果調用者是findf，則不增加計數，如果調用者搜索謂詞中存在的計數並使用它。 這導致我： Detecting the caller of a function in Scheme or Racket

但這並沒有幫助。

我卡住了，想出任何幫助，將不勝感激。

編輯：

一點澄清，爲什麼我覺得這種方法2是行不通的。

功能搜索正在進行部門首次搜索。

我認爲方法2不適用於以下2個原因。

假設圖

說開始位置是「A」和搜索元素是「我」與跳數限制爲2

現在計數器值=節點NUM其可以與2跳計數從 'A' 即開始被訪問： 計數= 0（intially）

在跳數1： 'C' 和 'd'，計數= 2

在跳數2： 'F'， 'G'， 'H'， '我'，數= 2 + 4 = 6

讓我們以 'A' 的方式啓動代碼將工作是

節點訪問（在findf）將是 'C' 和 'd'，計數= 6 - 2 = 4

讓我們假設左半首先服用。

現在 'C' 成爲項和所有其子兒童的的被訪問

節點訪問（在findf）將是 'F'， 'G'， 'H'，計數= 4-3 = 1

'F'沒有subclild，所以沒有probs。

「G」有一個subchild所以參觀「K」和計數變成= 1-1 = 0

所以今後所有的迭代會因爲我們計算節點的最大數返回false，如果方法2時緊隨其後。

解決這個問題的一種方法是正確調整計數，但是我覺得我們最終可能會對元素的圖形進行完整的搜索以跟蹤正確的計數。

Answer 1

注意這個答案：我把這個問題看作是腦筋急轉彎類型的難題;我認爲最好的解決方法是通過問題中提到的方法1。但是，如果我們假設我們不允許修改search，無論出於何種原因...

...我們認爲，我們通過在predicate?被允許保持狀態和做出的lookup調用，用於search（並且是我們圖表的基本表示），...

然後我認爲你可以通過讓predicate?自己記錄所有節點的跳數來實現你的目標它遇到過。

然後，只要想知道它所遇到的節點是否太遠，它就可以查詢該跳數表。

這裏是我做了說明這個代碼：

(define (is-parent-of? maybe-parent maybe-child) 
    (member maybe-child (lookup maybe-parent))) 

(define (hist-capturing-pred root pred?) 
    (let ((hop-counts (list (list root (box 0))))) 
    (lambda (n) 
     (let* ((parents (filter (lambda (entry) (is-parent-of? (car entry) n)) 
           hop-counts)) 
      (min-count (apply min (map unbox (map cadr parents))))) 
      ;; the `min-count` above represents a distance given what we 
      ;; know so far. Its possible that we actually encountered `n` 
      ;; *previously* via a *longer* path, in which case not only 
      ;; will there already be an entry for `n` in the `hop-counts` 
      ;; table, but it will have recorded a non-globally-minimum 
      ;; hop-count. 
      ;; 
      ;; So, check if there is an entry for `n`, and if so, make 
      ;; sure it holds the currently known minimum value. 
     (cond ((assoc n hop-counts) 
       => (lambda (entry) 
        (set-box! (cadr entry) 
           (min min-count (unbox (cadr entry)))))) 
       (else 
       ;; otherwise, add a new entry for `n` to the table 
       (set! hop-counts (cons (list n (box (+ 1 min-count))) 
             hop-counts)))) 
     (pred? (map (lambda (entry) (list (car entry) (unbox (cadr entry)))) 
        hop-counts) 
       n))))) 

這裏是在DrRacket互動窗口中的一些樣品電話：

> (search (hist-capturing-pred 'A (lambda (h n) (display `(,h ,n)) (newline) (eq? n 'I))) 'A) 
(((C 1) (A 0)) C) 
(((D 1) (C 1) (A 0)) D) 
(((F 2) (D 1) (C 1) (A 0)) F) 
(((G 2) (F 2) (D 1) (C 1) (A 0)) G) 
(((H 2) (G 2) (F 2) (D 1) (C 1) (A 0)) H) 
(((K 3) (H 2) (G 2) (F 2) (D 1) (C 1) (A 0)) K) 
(((K 2) (H 2) (G 2) (F 2) (D 1) (C 1) (A 0)) K) 
(((I 2) (K 2) (H 2) (G 2) (F 2) (D 1) (C 1) (A 0)) I) 
#t 
> (search (hist-capturing-pred 'A (lambda (h n) (and (eq? n 'I) (< (cadr (assoc 'I h)) 3)))) 'A) 
#t 
> (search (hist-capturing-pred 'A (lambda (h n) (and (eq? n 'I) (< (cadr (assoc 'I h)) 2)))) 'A) 
#f 
>