racket - Racket (ASL) 中的调度算法

Question

我需要将任意数量树的各个方面与生成递归和回溯相结合，以便提出一个简单有效的时间表。

到目前为止，我有两个结构，一个用她的可用槽和她可以工作的最大槽数来标识个人：(define-struct ta [name max avail])以及一个作为有序对的分配结构：(define-struct assignment [ta slot])其中槽只是一个自然数。因此，例如，我对以下虚拟对象进行了以下单元测试：

(define SOBA (make-ta "Soba" 2 (list 1 3)))
(define UDON (make-ta "Udon" 1 (list 3 4)))
(define RAMEN (make-ta "Ramen" 1 (list 2)))

(define NOODLE-TAs (list SOBA UDON RAMEN))

(check-expect (schedule-tas empty empty) empty)
(check-expect (schedule-tas empty (list 1 2)) false)
(check-expect (schedule-tas (list SOBA) empty) empty) 
(check-expect (schedule-tas NOODLE-TAs (list 1 2 3 4)) 
              (list
               (make-assignment UDON 4)
               (make-assignment SOBA 3)
               (make-assignment RAMEN 2)
               (make-assignment SOBA 1)))

所以我现在的主要功能是这样的：

;; (listof TA) (listof Slot) -> Schedule or false
;; produces valid schedule given TAs and Slots; false if impossible;
;; Schedule is (listof Assignment), Assigment is (make-assignment TA Slot)
(define (schedule-tas tas slots)
  (local [(define (fn-for-tas tas)
            (cond [(empty? slots) empty]
                  [(and (empty? tas)(cons? slots)) #f]                    ;From two 'One-Of' type analysis
                  [else
                   (if (all-assigned? (next-assignments tas slots) slots) ;Generative-recursion through 'next-assignments'   
                       (next-assignments tas slots)                       ;I know about the duplication of the computation here.
                       (fn-for-loa (next-assignments tas slots)))]))      ;just waiting to have a working version before I make it less readable

          (define (fn-for-loa loa)
            (cond [(empty? loa) #f]
                  [else
                   (local [(define try (fn-for-tas (first loa)))]
                     (if (not (false? try))
                         try
                         (fn-for-loa (rest loa))))]))]
    (fn-for-tas tas)))

因此，要通过生成递归生成数据，我希望将(next-assignments tas slots)其作为我需要的组合：进行所有分配并按可用性和最大可用插槽数进行过滤：

;; (listof TA) (listof Slot) -> (listof Assignment)
;; creates next list of possible valid assignments
(define (next-assignments tas slots)
  (filter-by-max (filter-by-availability (all-assignments tas slots))))

(define (all-assignments tas slots)
  (local [(define (assign-ta ta)
            (map (λ (s) (make-assignment ta s)) slots))

          (define (all-assignments tas)
            (cond [(empty? tas) empty]
                  [else
                   (append (assign-ta (first tas))
                           (all-assignments (rest tas)))]))]
    (all-assignments tas)))

但是我不相信这是我需要的，因为它宁愿一次性创建整个可搜索空间，而不是我需要实施的分支和修剪策略。无论如何，为了完整起见，其余的辅助功能都在这里：

(define (filter-by-availability loa)
  (cond [(empty? loa) empty]
        [else
         (if (member? (assignment-slot (first loa))
                      (ta-avail (assignment-ta (first loa))))
             (cons (first loa) (filter-by-availability (rest loa)))    
             (filter-by-availability (rest loa)))]))

(define (filter-by-max loa)
  (cond [(empty? loa) empty]
        [else
         (if (> (length loa) (ta-max (assignment-ta (first loa))))
             (filter-by-max (rest loa))
             loa)]))

我对这些过滤功能也不是很满意，因为它们似乎太“愚蠢”了；他们只是放弃他们碰巧找到的任何 ta 以满足条件。

最后，我有生成递归的基本情况：

(define (all-assigned? loa slots)
  (= (length loa)
     (length slots)))

我认为这在某种程度上是最“愚蠢”的。无论如何，如您所见，我对我的代码不满意。但是我看到的主要问题是，我不认为我正在生成一棵真正的树。因此，如果您能告诉我该怎么做，我将不胜感激！

注意这是我正在上的一门课程，但我想你可以看出我真的试过了。请帮忙！

标签： racketrecursive-backtrackingmutual-recursion