使用跟踪跳数限制的谓词函数进行图形搜索

Question

以下代码搜索图形，return根据作为参数传递的谓词函数确定真或假。

图以邻接表的形式表示。

假设图形不包含循环。

代码：

(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 函数用于查找散列 - table 和 return 其对应的路径。

搜索函数获取路径，如果发现路径不为空，则尝试使用谓词函数查找元素，如果找到 returns true，则为列表中的每个元素调用 search()。

这似乎有效。

现在我坚持要实现以下目标：

目前搜索功能遍历完整图并将谓词应用于其所有节点。

我想创建一个谓词函数，它不仅包括要搜索的元素，还包括跳数限制。

例如：如果 hop-limit 为 1 ：当且仅当搜索节点在 1 跳内时，谓词函数将为 return true，否则为 false。

我希望在不修改 search() 的情况下推广 n 的跳数限制。

到目前为止我想到的解决这个问题的方法：

1.I 可以更改搜索功能以将跳数作为参数传递并使用它来终止递归，但是我不想更改搜索功能。

2.Count 给定跳数限制可以访问的节点数，并将该信息存储在谓词函数中，对于谓词函数的每次调用，递减计数，如果计数命中0 return 每次都是假的。（但是我不确定如何实现上述（也许是闭包？），我也不认为这会起作用，因为最长的节点列表可能会用完计数）

3.If 我可以在谓词函数中找到调用者，即如果调用者是 findf 则不增加计数，如果调用者正在搜索谓词中存在的计数增量并使用它。这导致我： Detecting the caller of a function in Scheme or Racket

然而这并没有帮助。

我卡住了，没有想法任何帮助将不胜感激。

编辑:

稍微澄清一下为什么我认为方法 2 行不通。

函数搜索正在进行部门优先搜索。

我认为方法 2 行不通，原因有以下两个。

让我们假设图表

假设起始位置为 'A'，搜索元素为 'I'，跳数限制为 2。

现在计数器值 = 从 'A' 开始可以用 2 跳计数访问的节点数那是：计数 = 0（最初）

在跳数 1 内：'C' 和 'D'，count=2

在跳数 2 内：'F'、'G'、'H'、'I'，计数 = 2+4 = 6。

让我们从 'A' 开始，代码的工作方式是

访问的节点（在 findf 中）将是 'C' 和 'D'，count = 6 - 2 = 4

假设先取左半边。

现在 'C' 成为键，它的所有子子节点都被访问

访问的节点（在 findf 中）将是 'F'，'G'，'H'，count = 4-3 = 1

'F' 没有子项所以没有问题。

'G' 有一个子子，因此它访问 'K' 并且计数变为 = 1-1 = 0。

因此，从今往后，所有迭代都将 return 为假，因为如果采用方法 2，我们将计算节点的最大数量。

解决该问题的一种方法是适当调整计数，但我认为我们最终可能会在图形中进行完整搜索以查找元素以跟踪正确的计数。

Answer 1

注意这个答案：我认为这个问题是脑筋急转弯类型的谜题；我认为解决这个问题的最佳方法是通过问题中概述的方法#1。但是如果我们假设我们不允许修改 search，不管什么原因...

... 我们假设允许我们传入的 predicate? 保持状态并且调用使用的 lookup在 search（并且是我们对图表的基本表示）中，...

然后我认为可以实现您的目标，方法是让 predicate? 自行跟踪它遇到的所有节点的跳数。

然后，只要它想知道它遇到的节点是否太远，就可以查询跳数table。

这是我用来说明这一点的代码：

(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 交互中的一些示例调用 window:

> (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
>

使用跟踪跳数限制的谓词函数进行图形搜索

Graph search with a predicate function which keeps track of hop limit

lambda

scheme

functional-programming

predicate

racket