Метод уменьшения размера задачи. Метод «уменьшай и властвуй», страница 2

Метод уменьшения размера задачи на постоянную величину применим к задачам поиска в глубину и поиска в ширину в графах и к задаче о топологической сортировке. Теперь познакомимся с примерами алгоритмов, основанных на уменьшении размера задачи на постоянный множитель. Однако мы не должны ожидать большого количества таких алгоритмов. Обычно такие алгоритмы – логарифмические и, будучи очень быстрыми, встречаются достаточно редко. Особенно большая редкость – множитель, не равный двум.

Метод уменьшения размера задачи

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

Метод уменьшения размера задачи

Наиболее естественный подход к решению данной версии задачи – разделить n монет на две кучки по n/2 монет в каждой, отложив одну монету, если n –нечетное число. Если кучки имеют одинаковый вес, то отложенная монета и является фальшивой; если нет – мы выбираем более легкую кучку и выполняем описанные действия с ней. Заметим, что, хотя мы и разделили все монеты на две кучки, после взвешивания надо решить только одну задачу половинного размера. Следовательно, в соответствии с нашей классификацией методов проектирования алгоритмов, этот алгоритм относится к алгоритмам уменьшения размера задачи (вдвое), а не к алгоритмам на основе декомпозиции.

Метод уменьшения размера задачи

Легко записать рекуррентное уравнение для количества взвешиваний W(n), необходимых алгоритму в наихудшем случае: W(n) = W(n/2) +1 при n>1, W(1) = 0. Это рекуррентное соотношение должно быть вам знакомо. В самом деле, оно практически идентично соотношению для количества сравнений в бинарном поиске в наихудшем случае (отличие только в начальном условии). Эта схожесть неудивительна, поскольку оба алгоритма основаны на одном и том же методе – уменьшении размера экземпляра задачи в два раза. Решение данного рекуррентного соотношения также очень похоже на решение соотношения для бинарного поиска W(n)=O(log2n).

Метод уменьшения размера задачи

Все это выглядит элементарно, если не просто надоедливо. Но подождите немного: самое интересное в том, что это решение – не самое эффективное. Мы можем поступить разумнее, если будем делить монеты на три кучки, примерно по n/3 монет в каждой. После взвешивания двух кучек мы можем уменьшить размер экземпляра задачи в три раза, так что следует ожидать, что необходимое количество взвешиваний будет примерно равно log3n, что меньше, чем log2n. Методом уменьшения размера задачи на постоянный множитель можно решить и хорошо Вам известную задачу Иосифа.

Метод уменьшения размера задачи

Третьим основным вариантом метода уменьшения размера задачи является уменьшение, меняющееся от итерации к итерации. Вычисление медианы и задача выбора. Задача выбора (selection problem) заключается в поиске k-го наименьшего элемента в списке из n чисел. Это число называется k-ой порядковой статистикой (order statistic). Естественно, если k = 1 или k = n можно просто сканировать весь список в поисках наименьшего или наибольшего элемента. Более интересен случай, когда k = n/2, т.е. когда надо найти элемент, больший одной половины элементов списка, и меньший – другой половины.

Метод уменьшения размера задачи