Алгоритм планирования в Racket (ASL) - PullRequest
Новая
       52

Алгоритм планирования в Racket (ASL)

0 голосов
/ 25 марта 2020

Мне нужно смешать аспекты произвольного дерева арности с порождающей рекурсией и обратным отслеживанием, чтобы придумать простой правильный график.

До сих пор у меня есть две структуры, одна из которых идентифицирует человека с его слотами доступности и максимальным количеством слотов, с которыми она может работать: (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)))

Однако я не уверен, что это это то, что мне нужно, так как оно скорее создает все пространство для поиска в одной go вместо стратегии ветвления и сокращения, которую мне нужно реализовать. В любом случае, остальные вспомогательные функции здесь для полноты: 

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

Я также не очень доволен этими функциями фильтрации, так как они кажутся слишком «глупыми»; они просто отбрасывают то, что они находят, чтобы удовлетворить условиям.

И, наконец, у меня есть базовый случай генеративной рекурсии: 

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

, который является каким-то «глупым» «Один из всех, я думаю. В любом случае, как вы видите, я не доволен своим кодом. Но главная проблема, с которой я сталкиваюсь, опять же заключается в том, что я не думаю, что я создаю дерево с костяными отростками. Так что, если бы вы просто дали понять, как это сделать, я был бы безмерно благодарен!

NB. Это курс, который я беру, но думаю, вы можете сказать, что я действительно пытался. Пожалуйста, помогите!

...