2

我正在尝试编写一个函数来分析游戏树。树由嵌套列表表示，其中每个子列表代表一个分支。基本上，我想弄清楚两件事：

  1. 嵌套列表的最小值是多少？
  2. 该值的索引是什么？

我以为我已经基本解决了第一个问题，但是我的代码一直返回错误的值——我已经检查了所有内容，但看不到我做错了什么。

任何帮助将不胜感激，谢谢！

;MINIMAX*
(define minimax*
  (lambda (l operation hilo)
    (cond
      ((null? l) hilo)
      ((equal? operation 'max)
       (cond
         ((null? (cdr l)) (if
                           (list? (car l))
                           (minimax* (car l) 'min hilo)
                           (if
                            (> (car l) hilo)
                            (car l)
                            hilo)))
         (else (if
                (list? (car l))
                (if
                 (> (minimax* (car l) 'min hilo) hilo)
                 (minimax* (cdr l) 'max (minimax* (car l) 'min hilo))
                 (minimax* (cdr l) 'max hilo))
                (if
                 (> (car l) hilo)
                 (minimax* (cdr l) 'max (car l))
                 (minimax* (cdr l) 'max hilo))))))
      ((equal? operation 'min)
       (cond
         ((null? (cdr l)) (if
                           (list? (car l))
                           (minimax* (car l) 'max hilo)
                           (if
                            (< (car l) hilo)
                            (car l)
                            hilo)))
         (else (if
                (list? (car l))
                (if
                 (< (minimax* (car l) 'max hilo) hilo)
                 (minimax* (cdr l) 'min (minimax* (car l) 'max hilo))
                 (minimax* (cdr l) 'min hilo))
                (if
                 (< (car l) hilo)
                 (minimax* (cdr l) 'min (car l))
                 (minimax* (cdr l) 'min hilo))))))
      (else (error "Invalid operation type, must be 'max or 'min")))))
4

1 回答 1

0

你应该稍微改变你的方法。您可以实现一些实用程序，而不是编写一个基本程序来实现一切。

对于 minimax 过程，数据来自树还是列表都没有关系。所以你可以自己编写一个程序，将你的树转换成这样的列表

 (define (fringe t)
   (cond ((null? t) t)
     ((pair? (car t)) (append (fringe (car t)) 
                      (fringe (cdr t))))
     (else (cons (car t) (fringe (cdr t))))))

检查最小值或最大值基本上是对列表或树的迭代。所以你可以用fold. 见http://www.gnu.org/software/mit-scheme/documentation/mit-scheme-ref/Reduction-of-Lists.html

所以你可以这样写你的程序：

(define (minimax op t)
  (let ((flat-list (fringe t)))
    (fold op (car t) (cdr t))))

进一步阅读计算机程序的结构和解释。这是一本学习Scheme和一般编程的好书。

于 2014-02-12T18:42:31.403 回答