Главная Промышленная автоматика.

10.11.Задачу разбиения на абзацы в простейшей форме можно сформулировать следующим образом. Дана последовательность слов w-, Wz, ... , Wk длиной l, I2, ... , h, которые нужно разбить на строки длиной L. Слова разделяются пробелами, стандартная ширина которых равна Ь, но пробелы при необходимости могут удлиняться или сжиматься (но без "наползания" слов друг на друга) так, чтобы длина строки Wj w,+i ... W/ равнялась в точности L. Однако штрафом за такое удлинение или сжатие пробелов является общая величина, на которую пробелы удлиняются или сжимаются, т.е. стоимость формирования строки w,Wi+i ... WjiipH j > i равна (j - i) b - b\, где b - фактическая ширина пробелов, равная (I. - li - li+i - ... - lj)/(f- i). При j = k (речь идет о последней строке) эта стоимость равна нулю, если только Ьне окажется меньше Ь, поскольку последнюю строку растягивать не требуется. На основе метода динамического программирования разработайте алгоритм для разделения с наименьшей стоимостью последовательности слов Wi, W2, ... , Wii на строки длиной L. Совет. Для I = к, к - I, ... , 1 вычислите наименьшую стоимость формирования строк

10.12.Допустим, есть п элементов Xi,x2, ... , х„, связанных линейным порядком XI < хз < ... < х„, которое нужно представить в виде двоичного дерева поиска. Обозначим Pi вероятность запроса на поиск элемента х,. Тогда для любого заданного двоичного дерева поиска средняя стоимость поиска составит

p,(di + l) , где dj - глубина узла, содержащего л;,. При условии, что заданы ,=1

все вероятности р/, и предполагая, что х,- никогда не изменяются, можно построить двоичное дерево поиска, минимизирующее стоимость поиска. На основе метода динамического программирования разработайте алгоритм, реализующий такое двоичное дерево поиска. Каким будет время выполнения алгоритма? Совет. Вычислите для всех / я j оптимальную стоимость поиска среди всех деревьев, содержащих только элементы Xj, *,4i, ... , т.е. всего уэле-

ментов, начиная с х,.

**10.13.Для монет какого достоинства "жадный" алгоритм, описанный в разделе 10.3, обеспечивает оптимальное решение выдачи сдачи?

10.14.Составьте рекурсивный алгоритм триангуляции, обсуждавшийся в разделе 10.2. Покажите, что результатом выполнения этого рекурсивного алгоритма будут ровно 3" вызовов в случае нетривиальных задач, если начать с задачи размером s > 4.

10.15. Опишите "жадный" алгоритм для

а) задачи одномерного размещения блоков;

б) задачи разбиения на абзацы (упражнение 10.11).

Приведите пример, когда алгоритм не обеспечивает оптимального решения, или покажите, что таких случаев вообще не может быть.

10.16.Постройте нерекурсивную версию алгоритма просмотра дерева, представленного в листинге 10.3.

10.17. Рассмотрим дерево игры, в котором используются шесть шариков и игроки 1 и 2 выбирают по очереди от одного до трех шариков. Игрок, взявший последний шарик, считается проигравшим.

а) составьте полное дерево этой игры;

б) если это дерево игры просматривать с помощью метода альфа-бета отсечений, а узлы, представляющие конфигурации с наименьшим количеством шариков, просматривать первыми, какие узлы будут отсечены?

в) кто выиграет, если оба игрока будут действовать оптимальным образом?



*10.18. Разработайте алгоритм ветвей и границ для задачи коммивояжера, взяв за основу идею, что маршрут должен начинаться с вершины 1 и ответвляться на каждом уровне, исходя из того, какой узел должен быть в этом маршруте следующим (а не из того, какое конкретное ребро выбрано на рис. 10.17). Что может служить подходящим критерием оценки нижней границы ддя конфигураций, которые являются списками вершин 1, ii, V2, ... » определяющих начало маршрутов? Как будет вести себя алгоритм применительно к графу из рис. 10.16, если предположить, что вершина а является вершиной 1?

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

10.20. Если локальные преобразования состоят лишь из двойных выборов, есть ди ддя графа из рис. 10.16 какие-либо локально-оптимальные маршруты, которые не являются глобально-оптимальными?

Библиографические примечания

Существует множество приложений алгоритмов декомпозиции, включая быстрое преобразование Фурье с временем выполнения O(nlogn), описанное в [21], алгоритм умножения целых чисел с временем выполнения 0{п lograloglogra), описанный в [96], и алгоритм умножения матриц с временем 0(га), рассмотренный в [104]. Алгоритм умножения целых чисел с временем выполнения 0(л-®) описан в работе [59]. В статье [76] представлено несколько эффективных алгоритмов декомпозиции ддя модулярной арифметики, а также ддя полиномиальной интерполяции и оценивания.

С популярным изложением динамического программирования можно ознакомиться в [7]. Применение динамического программирования к триангуляции изложено в [40]. Упражнение 10.11 заимствовано из [66]. В [64] содержится решение задачи построения оптимального дерева двоичного поиска (см. упражнение 10.12).

В [68] описан эффективный эвристический алгоритм ддя задачи коммивояжера.

Обсуждение NP-полных и других задач, сложных с вычислительной точки зрения, можно найти в монографии [3], а также в работе [41].



ГЛАВА 11

Структуры данных и алгоритмы для внешней памяти

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

11.1. Модель внешних вычислений

в алгоритмах, которые мы обсуждали до сих пор, предполагалось, что объем входных данных позволяет обходиться исключительно основной (оперативной) памятью. Но как быть, если нам нужно, например, отсортировать всех государственных служащих по продолжительности их рабочего стажа или хранить информацию из налоговых деклараций всех гралсдан страны? Когда возникает необходимость решать подобные задачи, объем обрабатываемых данных намного превышает возможности основной памяти. В большинстве компьютерных систем предусмотрены устройства внешней памяти, такие как жесткие диски, или запоминающие устройства большой емкости, на которых можно хранить огромные объемы данных. Однако характеристики доступа к таким устройствам внешней памяти существенно отличаются от характеристик доступа к основной памяти. Чтобы повысить эффективность использования этих устройств, был разработан ряд структур данных и алгоритмов. В этой главе мы обсудим структуры данных и алгоритмы для сортировки и поиска информации, хранящейся на вторичных устройствах памяти.

В Pascal и некоторых других языках программирования предусмотрен файловый тип данных, предназначенный для представления данных, хранящихся во вторичной памяти. Даже если в языке, которым вы пользуетесь, файловый тип данных не предусмотрен, в операционной системе понятие "внешних" файлов, несомненно, поддерживается. О каких бы файлах мы ни говорили (файлах, предусмотренных в Pascal, или файлах, поддерживаемых непосредственно операционной системой), в любом случае нам придется действовать в рамках ограничений, касающихся способов доступа к файлам. Операционная система делит вторичную память на блоки одинакового размера. Размер блока зависит от конкретного типа операционной системы и обычно находится в пределах от 512 до 4096 байт.

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





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 [99] 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0019