4.13. РАЗБИЕНИЕ

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

Наша задача состоит в том, чтобы найти такое грубейшее (с наименьшим числом блоков) разбиение множества что

1) — подразбиение разбиения (т. е. каждое множество является подмножеством некоторого блока

2) если принадлежат то принадлежат для некоторого

Будем называть грубейшим разбиением множества совместимым с

Очевидное решение состоит в повторном утончении блоков исходного разбиения следующим способом. Пусть какой-нибудь блок. Рассмотрим для каждого а из Разобьем так, чтобы два элемента а к попадали в один блок тогда и только тогда, когда оба принадлежат некоторому блоку Процесс повторяется до тех пор, пока уже нельзя будет проводить дальнейшие утончения. Этот метод дает алгоритм сложности поскольку каждое утончение занимает время а всего может

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

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

шагов. Окончательным разбиением будет для

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

Для каждого блока положим Вместо того чтобы разбивать по значениям для а разобьем относительно те блоки которые содержат хотя бы один элемент из и один элемент не из Иными словами, каждый такой блок разбивается на множества

Как только проведено разбиение относительно блока больше уже не нужно проводить разбиения относительно него, пока он сам не будет расщеплен. Если вначале для каждого элемента расщеплен на , то можно разбить относительно или и получить при этом один и тот же результат, поскольку совпадает с

Так как можно выбирать, по отношению к какому из блоков или проводить разбиение, то мы разбиваем относительно того, для которого это сделать проще. Точнее мы выбираем меньшее из множеств Алгоритм приведен на рис. 4.35.

Алгоритм 4.5. Разбиение

Вход. Множество из элементов, разбиение и функция

Выход. Грубейшее разбиение множества совместимое с

Рис. 4.35. (см. скан) Алгоритм разбиения.

Метод. К применяется программа, приведенная на рис. 4.35. В ней опущены некоторые детали, важные для ее реализации. Мы обсудим эти детали при анализе времени работы алгоритма.

Анализ алгоритма 4.5 начнем с доказательства того, что он разбивает нужным образом. Пусть — разбиение множества отображение множества на себя. Множество будем называть безопасным для , если для любого блока либо либо Например, на рис. 4.35 строки 9 и 10 гарантируют, что множество безопасно для получающегося разбиения, поскольку если для некоторого блока В, то либо и тогда включение очевидно, либо в строках 9 и 10 В разбивается на два блока, один

из которых является подмножеством множества а другой с ним не пересекается.

В доказательство корректности алгоритма 4.5 входит доказательство того, что окончательное разбиение не оказывается слишком грубым. Иными словами, надо доказать следующее.

Лемма 4.7. После окончания работы алгоритма 4.5 каждый блок В в результирующем разбиении безопасен для я.

Доказательство. На самом деле мы покажем, что для каждого блока

Интуитивно это можно изложить так: когда число I удаляется из множества ОЖИДАНИЕ, строки 6—14 делают блок безопасным для разбиения, которое получается после строки остается безопасным до тех пор, пока он не будет разбит. Когда разбивается, индекс одного подблока, назовем его помещается в ОЖИДАНИЕ. Другой подблок по-прежнему называется Очевидно, что объединение этих двух подблоков, т. е. безопасно для рассматриваемого разбиения, поскольку оно совпадает со старым блоком Дальнейшее разбиение образует такие блоки что входят в ОЖИДАНИЕ, а объединение безопасно. Когда при некотором удаляется из множества ОЖИДАНИЕ, строки 6—14 снова делают безопасными. Изложим теперь это формально. Докажем справедливость утверждения (4.6) для всех I индукцией по числу выполнений строк 4—14. Когда алгоритм заканчивает работу, множество ОЖИДАНИЕ пусто, и, значит, из (4.6) будет вытекать, что каждый блок окончательного разбиения и безопасен для .

Для доказательства базиса возьмем выполнений, тогда (4.6) тривиально, поскольку для всех

Для проведения шага индукции предположим, что после выполнения строки Если число I всегда ранее входило в ОЖИДАНИЕ, то оно имеет значение которое определялось в строке 4. Легко показать, что цикл в строках 6—14 делает безопасным для разбиения, получающегося после выполнения строки 14 Это мы уже обосновали после определения понятия "безопасный".

Если число I не входило в ОЖИДАНИЕ во время предыдущего

выполнения цикла до строки 14, то по предположению индукции найдется такой список что (4.6) было справедливо для I на предыдущем этапе. Кроме того, в строке 4 обязательно

Случай нет в В строках 9, 10 могло произойти разбиение нескольких блоков. Для каждого такого блока (т. е. добавим в индекс блока, образованного в строке 8. Благодаря строке И список по-прежнему будет состоять только из индексов, входящих в ОЖИДАНИЕ. Если сам блок не разбит, то и множество блоков с индексами из все еще образуют множество, безопасное для текущего разбиения, так что (4.6) удовлетворяется. Если же блок разбит, надо также добавить в индекс выбранный в строке 8, когда Следовательно, множество будет безопасно для текущего разбиения.

Случай находится в Без потери общности будем считать, что Рассуждение проводится почти так же, как в случае 1, но в конце рассматриваемой итерации строк 4—14 может не входить в ОЖИДАНИЕ. Мы знаем, что каждый блок В текущего разбиения будет либо подмножеством множества либо не будет с ним пересекаться. Пусть где список модифицирован, как в случае 1. Если то, разумеется, Если то аналогично случаю 1 можно доказать, что или

Наконец, когда алгоритм 4.5 заканчивает работу, множество ОЖИДАНИЕ должно быть пусто. Следовательно, из (4.6) вытекает, что для каждого I блок безопасен для окончательного разбиения.

Теорема 4.8. Алгоритм 4.5 правильно вычисляет грубейшее разбиение множества совместимое с

Доказательство. Лемма 4.7 показывает, что выход алгоритма 4.5 совместим с Надо доказать, что разбиение грубо, насколько возможно. Простая индукция по числу блоков, разбиваемых в строках 9, 10, показывает, что каждое такое разбиение, сделанное алгоритмом, необходимо для совместимости. Оставляем эту индукцию в качестве упражнения.

Теперь мы должны детально исследовать реализацию алгоритма 4.5, чтобы показать, что время его работы составляет где Основным при оценке времени работы будет демонстрация того, что цикл в строках 6—14 можно выполнить за время, пропорциональное Наша первая задача — эффективно найти подходящее множество чисел в строке 6. Нам понадобится такой массив что индекс блока, содержащего Начальное состояние массива БЛОК можно

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

С помощью массива БЛОК легко построить список чисел необходимых в строке 6, за шагов. Для каждого элемента а, входящего в индекс блока, содержащего а, добавляем в если его там еще нет. Для каждого хранится счетчик числа элементов, входящих в которые входят также и в Если этот счетчик достигнет величины то и удаляется из списка

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

Строки 9 и 10 требуют шагов. Для данного выполнения -цикла суммарное время, затрачиваемое на нахождение подходящих чисел и на выполнение строк 7—10, составляет Кроме того, легко видеть, что тест в строках 12—14, если его выполнять должным образом, занимает времени, так что общее время есть

Осталось рассмотреть строку 11. Чтобы быстро сказать, входит ли в ОЖИДАНИЕ, образуем другой массив Начальное состояние можно построить за шагов и без труда корректировать его в строках 11—14. Таким образом, мы доказали следующую лемму.

Лемма -цикл в строках 6—14 на рис. 4.35 можно реализовать за шагов.

Доказательство. В силу изложенного выше.

Теорема 4.9. Алгоритм 4.5 можно реализовать за время

Доказательство. Рассмотрим условия, при которых блок, содержащий целое число и не представленный в множестве ОЖИДАНИЕ, может попасть туда. В строке 1 это может случиться лишь один раз. В строке 11 это произойти не может; даже если поскольку тогда было бы в еще раньше, а индекс уже входил в ОЖИДАНИЕ. Если это случилось в строках 13 и 14, то число находится в блоке, размер которого не больше половины размера того блока, куда оно входило в тот предыдущий момент, когда индекс множества, содержащего попал в

Отсюда можно заключить, что индекс множества, содержащего попадает в ОЖИДАНИЕ не больше раз. Следовательно, не может быть в блоке который выбирался в строке 4 более чем раз.

Допустим, что на каждый элемент из каждый раз налагается штраф, пропорциональный так что сумма всех штрафов равна сложности выполнения цикла в строках 6—14. Тогда существует такая постоянная с, что за одно выполнение цикла элемент штрафуется не более чем на Как мы уже показали, элемент не может попасть в выбираемый список более чем раз, так что суммарный штраф, налагаемый на него, составляет Так как сумма должна равняться то общая сложность всех выполнений -цикла есть Легко видеть, что сложность остальной части алгоритма 4.5 есть теорема доказана.

Алгоритм 4.5 имеет несколько приложений. Одно из важных приложений — минимизация числа состояний конечного автомата. Дан конечный автомат и требуется найти эквивалентный ему автомат с наименьшим числом состояний. Для каждого состояния и входного символа а обозначим через очередное состояние автомата. Вначале все состояния автомата можно разбить на множество допускающих состояний и множество недопускающих состояний. Задача минимизации числа состояний автомата эквивалентна нахождению грубейшего разбиения множества совместимого с начальным разбиением и такого, что если состояния находятся в одном блоке разбиения , то состояния и также находятся в одном блоке автомата для каждого входного символа а.

Единственное отличие этой задачи от задачи, решаемой алгоритмом 4.5, состоит в том, что отображение из а не из Однако можно трактовать как множество функций на где сужение функции на а.

Алгоритм 4.5 легко модифицировать так, что он справится с этой более общей задачей, помещая в множество ОЖИДАНИЕ пары Каждая пара состоит из индекса некоторого блока разбиения и функции по которой проводится разбиение. Вначале или поскольку начальное разбиение состоит из двух блоков. Всякий раз, когда блок разбивается на и каждая допустимая функция 8а спаривается с Остальные детали оставляем в качестве упражнения.