Scheme/Racket/Lisp의 중첩 목록에 대한 Minimax 연산?

Question

게임 트리를 분석하는 함수를 작성하려고합니다. 트리는 각 하위 목록이 분기를 나타내는 중첩 된 목록으로 표시됩니다. 기본적으로 알아 내고 싶은 두 가지가 있습니다.

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

Answer 1

약간 변경해야합니다. 모든 것을 만드는 하나의 기본 프로 시저를 프로그래밍하는 대신 몇 가지 유틸리티 프로 시저를 구현할 수 있습니다.

미니 맥 절차의 경우 데이터가 트리 또는 목록으로 제공되는지 여부는 중요하지 않습니다. 목록 또는 나무의 반복은 기본적으로 그래서 당신은 자신이 한

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

를 추가 읽기 Structure and Interpretation of Computer Programs하십시오. Scheme을 학습하고 일반적으로 프로그래밍하기에 좋은 책입니다.