Решение упражнения 2.43 из SICP

3 February, 2008 (14:21) | Решения упражнений

Переставив фрагменты программы, Хьюго внес рекурсивный вызов queen-cols внутрь итерации по номерам строк, то есть если ранее при решении задачи для доски NxN решение задачи для доски (N-1)x(N-1) вычислялось один раз, то теперь это происходит N раз. Таким образом здесь пахнет экспоненциальным ухудшением производительности.

Примем упрощенно, что обработка очередной позиции (добавление одного ферзя и проверка на безопасность) на каждом шаге отнимает одинаковое время P (на самом деле это не так, ведь время работы проверки на безопасность зависит от количества ферзей, но это не влияет особенно на результат, так как на каждом шаге число ферзей мало по сравнению с числом позиций). Тогда время T(N) решения задачи для доски NxN складывается из времени решения задачи для доски (N-1)x(N-1) и времени обработки каждой из позиций помноженного на количество позиций для обработки (количества решений L(N-1) для доски (N-1)x(N-1) помноженного на N).

Тогда для исходного решения получаем:

T(N) = P * N * L(N-1) + T(N-1), или, что то же

T(N) = P * N * (L(N-1) + L(N-2) + … + L(1)),

а для решения Хьюго:

Th(N) = P * N * L(N-1) + N * T(N-1) или

Th(N) = P * N * (L(N-1) + N * L(N-2) + … + NN-2 * L(1)).

Для задачи с 8 ферзями, то есть доски 8×8
Воспользуемся вычисленными в прошлом упражнении значениями L(N):

L(1)=L(2)=L(3)=0, L(4)=2, L(5)=10, L(6)=4, L(7)=40.

Тогда

T(8) = P * 8 * (L(7) + L(6) + … + L(1)) = P * 8 * 56 = 448*P,

Th(8) = P * 8 * (L(7) + 8*L(6) + … +86*L(1)) = P * 8 * (40+32+640+1024) = 13888*P.

То есть Th(8) = 31 * T(8), и программа Хьюго отработает в 31 раз медленнее для задачи с восемью ферзями. Причем разница в эффективности будет расти экспоненциально с ростом размерности задачи.

Меня по-прежнему не покидает чувство, что приведенное решение упражнения не идеально. Думаю, со временем я смогу его улучшить.

Comments

Comment from Dima
Date: August 21, 2008, 1:25 pm

Ваше чувство вас не подводит 🙂 Пользуясь вашим методом, то есть подщотом количества вызовов процедуры safe?, правильный ответ 2171. То есть медленнее в 2171 раз. Ваша ошибка в том, что там где нужно рассматривать (N-1)xN, (N-2)xN, etc, вы рассматриваете (N-1)x(N-1), (N-2)x(N-2), etc. На бумаге этот подщот помойму сделать невозможно, а код который даёт правильный ответ вот:

(define (valid-layouts board-size columns)
  (define (queen-cols k) ; unchanged from queens procedure
    (if (= k 0)
        (list empty-board)
        (filter safe?
                (flatmap
                 (lambda (rest-of-queens)
                   (map (lambda (new-row)
                          (cons new-row rest-of-queens))
                        (enumerate-interval 1 board-size))) 
                 (queen-cols (- k 1)))))) 
  (if (= columns 0) 
      0 ; we don't want 1, which is technically the length of (())
      (length (queen-cols columns))))

(define (safe?-calls board-size column) ; in a given column
  (* board-size (valid-layouts board-size (- column 1))))

(define (safe?-calls-original board-size)
  (accumulate + 0
   (map (lambda (x) (safe?-calls board-size x))
        (enumerate-interval 1 board-size))))

(define (safe?-calls-louis board-size)
  (accumulate + 0
   (map (lambda (x) (* (safe?-calls board-size x)
                       (expt board-size (- board-size x))))
        (enumerate-interval 1 board-size))))

(/ (safe?-calls-louis 8 ) (safe?-calls-original 8 ))

Write a comment