Оптимизация queens

У Хьюго Дума ужасные трудности при решении упражнения 2.42 . Его процедура queens вроде бы работает, но невероятно медленно. (Хьюго ни разу не удается дождаться, пока она решит хотя бы задачу 6 × 6 .) Когда Хьюго просит о помощи Еву Лу Атор, она указывает, что он поменял местами порядок вложенных отображений в вызове процедуры flatmap , записав его в виде

(flatmap
 (lambda (new-row)
   (map (lambda (rest-of-queens)
          (adjoin-position new-row k rest-of-queens))
        (queen-cols (- k 1))))
 (enumerate-interval 1 board-size))

Объясните, почему из-за такой перестановки программа работает медленно. Оцените, насколько долго программа Хьюго будет решать задачу с восемью ферзями, если предположить, что программа, приведенная в упражнении 2.42 , решает ее за время T .


Комментарии отсутствуют.

Необходима авторизация

Вы должны авторизоваться для создания комментария.

Вход