Минимаксные операции над вложенными списками в Scheme / Racket / Lisp? - PullRequest
Новая
       18

Минимаксные операции над вложенными списками в Scheme / Racket / Lisp?

2 голосов
/ 08 марта 2011

Я пытаюсь написать функцию для анализа деревьев игры.Деревья представлены вложенными списками, где каждый подсписок представляет ветку.По сути, я хочу выяснить две вещи:

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

1 Ответ

0 голосов
/ 12 февраля 2014

Вы должны немного изменить свой подход.Вместо программирования одной фундаментальной процедуры, которая делает все, вы можете реализовать некоторые служебные процедуры.

Для минимаксной процедуры не имеет значения, поступают ли данные в виде дерева или списка.Таким образом, вы можете написать себе процедуру, которая преобразует ваше дерево в список, подобный этому 

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

Для дальнейшего чтения Структура и интерпретация компьютерных программ .Это отличная книга для изучения Схема и программирования в целом.

...