*L3.4.11. Проверка. Примените программу из упр. 3.4.10 для экспериментальной проверки качества алгоритма коммивояжера, изученного в этом разделе. Ограничьтесь случаями n<.20 городов.

***L3.4.12. Задача о рюкзаке (полное построение). Имеется рюкзак объема V и неограниченный запас каждого из n разных видов предметов. Для г=1, ... , n один предмет вида i имеет известный оем vi и известную стоимость /л,-. В рюкзак можно положить целое число различных предметов. Нужно упаковать рюкзак так, чтобы общая стоимость упаковапиых предметов была как можно большей, при условии, чтобы их общий объем пе превосходил V. Форма предметов в задаче не играет роли. Постройте полностью алгоритм ветвей и границ для задачи о рюкзаке.

***L3.4.13. Составление расписания для паралмльных процессоров (полное тстрое-ние). Три одинаковых центральных процессора могут выполнять М заданий. Каждое задание может быть выполнено на любом процессоре, и, если задание загружено в процессор, оно находится в нем до полного завершения (т. е. задания не могут пре-

рьшаться или разделяться между двумя или более процессорами). При t=l.....М

задание i требует времени ti для выполнения. Для любого линейного порядка заданий следующее задание из списка выполняется на первом освободившемся процессоре. Задания могут быть перечислены в любом порядке.

Полностью постройте алгоритм ветвей и границ для поиска оптимального списка, т. е. такого, который дает возможность завершить все задания в кратчайшее время. Рассмотрим в качестве примера четыре задания: с i=3, 4=3, <з=3 и t=Q. Взятые в порядке (1, 2, 3, 4), все задания полностью завершатся за время Г=9. Для порядка (4, 1, 2, 3) Г=6, и ясно, что это наилучшее возможное расписание.

*L3.4.14. Оценка алгоритма GTS2 (проверка). Это упражнение может быть выполнено, только если у вас есть программы как для алгоритма GTS2, так и для алгоритма ветвей и границ, построенного раньше. Экспериментально проверьте качество алгоритма GTS2 по сравнению с точными решениями, полученными алгоритмом ветвей и границ, для случайно генерируемых задач не более чем с 20 городами. Используйте алгоритм GTS2 в качестве начального этапа для алгоритма ветвей и границ, как описано в этом разделе. Каковы результаты сравнения экспериментальных величин математического ожидания и дисперсии времени работы алгоритмов?

3.5. Рекурсия

В математике и программировании рекурсия - это метод определения или выражения функции, процедуры, языковой конструкции или решения задачи посредством той же функции, процедуры и т. д. Несколько примеров придадут этой идее более конкретный характер.

Факториалы и числа Фибоначчи

Факториальная функция определяется рекурсивно следующим образом:

0! = 1,

m=Nx (N-l)], если Л>0,

или в виде фрагмента программы:

FAC(0)=1, (1)

FAC(iV)=A*FAC(A-1), если Л>0. (2)

Областью определения функции FAC является множество неотрицательных целых чисел.

Уравнение (2) - это пример рекуррентного соотношения. Рекуррентные соотношения выражают значения функции при помощи дру-

гих значенир!, вычисленных для меньших аргументов. Уравнение (1) - нерекурсивно определенное начальное значение функции. Для каждой рекурсивной функции нужно хотя бы одно такое начальное значение, в противном случае ее нельзя вычислить в явном виде.

Аналогично числа Фибоначчи определяются следующей бесконечной последовательностью целых чисел: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... . Проверка показывает, что М-й элемент этой последовательности равен сумме двух непосредственно предшествующих элементов. Таким образом, если FIB(A) обозначает Л-е число Фибоначчи, то значение FIB (N) может быть определено из рекуррентного соотношения:

FIB (A)=FIB (Л-1)+FIB (Л-2).

Так как FIB (N) определено через два разных значения для меньших аргументов, необходимы два начальных значения. Ими служат

FIB(1)=1, FIB(2)=1.

Определенные здесь числа Фибоначчи ) являются рекурсивным решением следующей задачи:

Каждый месяц самка из пары кроликов приносит двух кроликов (самца и самку). Через два месяца новая самка сама приносит пару кроликов. Нужно найти число кроликов в конце года, если в начале года была одна новорожденная пара кроликов и в течение этого года кролики не умирали.

Посмотрим, какую работу надо проделать, чтобы вычислить FAC (Л) для произвольного натурального числа N. Для вычисления FAC(N) мы должны произвести рекурсивное обращение и вычислить FAC{N-1). Это в свою очередь требует другого рекурсивного обращения для вычисления FAC{N-2) и т. д. Таким образом, для того чтобы вычислить FAC(A/), нужно произвести рекурсивных обращений, последнее из которых выполняется для FAC(0)=1. Принято говорить, что глубина рекурсии, требуемой для вычисления ¥kC{N), равна Л. В машинных программах глубина рекурсии соответствует самой длинной последовательности обращений к процедуре, требуемой для вычисления функции. Поэтому глубина рекурсии - это мера вычислительной сложности рекурсивно определенной функции.

Для вычисления значения FIB(A/) функции Фибоначчи нужно вычислить два значения функции [FIB(A-1) и FIB(A/-2)]. Каждое из этих вычислений в свою очередь требует двух вычислений - два для FIB(A-1) и еще два для FIB(A-2) и т. д. Это подсказывает, что глубрша рекурсии, требуемая для вычисления FIB(A), равна приблизительно 2~. Однако после недолгого размышления мы

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

видим, что такой подход дает сильно завышенную оценку. Ясно, что если известны Л-1 значений, FIB(l), FIB (2), . . ., FIB(iV-1), то можно вьнислить FIB(A). Более того, поскольку сразу были заданы FIB(I) и FIB (2), потребуется только Л-3 вычислений для FIB(3), . . ., FIB(#-I). Таким образом, -2 вычислений функции будет достаточно для вычисления FIB(Af).

Функция Аккермана

Две рекурсивные функции, рассмотренные до сих пор, были достаточно простьми. Поэтому, чтобы не сложилось неправильное впечатление о том, насколько сложны рекурсивные функции, представим следующую, довольно простую на первый взгляд, дважды рекурсивную функцию, известную как функция Аккермана. Функция дважды рекурсивна, если сама функция и один из ее аргументов определены через самих себя.

iV + 1, если М=0;

А{М, N) = - -1, 1), если ЛА = 0;

,А[М-1, А(М, N - I)] в остальных случаях.

Беглый просмотр рис. 3.5.1 показывает, как трудно вычислить эту функцию даже для таких малых аргументов, как М=4 и N=2. Заметьте, например, что Л (4, 1)=Л(3, 13).

Разбиения целого

Разбиение положительного целого числа М - это представление М в виде суммы целых чисел. Классическая счетная задача - определение количества Р{М) разбиений числа М.

Для /14=6 разбиениями являются

4+2, 4+1+1 3+3, 3+2+1, 3+1+1+1 2+2+2, 2+2+1 + 1, 2+1 + 1 + 1+1 1 + 1+1 + 1+1 + 1.

Интересен способ выражения функции Р (М) через другую функцию Q(M, N), которая определяется как число разбиений целого М со слагаемьми, не превышающими N. Несложные рекурсивные рассуждения приводят к следующему:

1. Q{M, 1)=1. Это значит, что существует только одно разбиение целого числа М, в котором наибольшее слагаемое есть единица, а именно М=1+1+. . .+1.

2. Q(l, N)=l. Очевидно, существует только одно разбиение целого числа 1 независимо от величины N наибольшего слагаемого.