авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 |   ...   | 13 | 14 ||

«e-maxx :: algo Вас приветствует книга, собранная по материалам сайта e-maxx.ru/algo (по состоянию на 26 Apr 2012 1:48). В этой книге Вы найдёте описание, реализации и доказательства множества ...»

-- [ Страница 15 ] --

Детали сортируются, затем распределяются по спискам (это те детали, которые были отправлены в начало очереди) и (те, что были отправлены в конец). После этого два списка объединяются (причём второй список берётся в обратном порядке), и затем по найденному порядку вычисляется искомое минимальное время: поддерживаются две переменные и — время освобождения первого и второго станка соответственно.

Литература S.M. Johnson. Optimal two- and three-stage production schedules with setup times included [1954] M.R. Garey. The Complexity of Flowshop and Jobshop Scheduling [1976] Оптимальный выбор заданий при известных временах завершения и длительностях выполнения Пусть дан набор заданий, у каждого задания известен момент времени, к которому это задание нужно завершить, и длительность выполнения этого задания. Процесс выполнения какого-либо задания нельзя прерывать до его завершения. Требуется составить такое расписание, чтобы выполнить наибольшее число заданий.

Решение Алгоритм решения — жадный (greedy). Отсортируем все задания по их крайнему сроку, и будем рассматривать их по очереди в порядке убывания крайнего срока. Также создадим очередь, в которую мы будем постепенно помещать задания, и извлекать из очереди задание с наименьшим временем выполнения (например, можно использовать set или priority_queue). Изначально пустая.

Пусть мы рассматриваем -ое задание. Сначала поместим его в. Рассмотрим отрезок времени между сроком завершения -го задания и сроком завершения -го задания — это отрезок некоторой длины.

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

По окончании этого алгоритма мы выберем оптимальное решение (или, по крайней мере, одно из нескольких решений). Асимптотика решения —.

Реализация int n;

vector pairint,int a;

// задания в виде пар (крайний срок, длительность)... чтение n и a...

sort (a.begin(), a.end());

typedef set pairint,int t_s;

t_s s;

vectorint result;

for (int i=n-1;

i=0;

--i) { int t = a[i].first - (i ? a[i-1].first : 0);

s.insert (make_pair (a[i].second, i));

while (t && !s.empty()) { t_s::iterator it = s.begin();

if (it-first = t) { t -= it-first;

result.push_back (it-second);

} else { s.insert (make_pair (it-first - t, it-second));

t = 0;

} s.erase (it);

} } for (size_t i=0;

iresult.size();

++i) cout result[i] ' ';

Задача Иосифа Условие задачи. Даны натуральные и. По кругу выписывают все натуральные числа от 1 до. Сначала отсчитывают -ое число, начиная с первого, и удаляют его. Затем от него отсчитывают чисел и -ое удаляют, и т.

д. Процесс останавливается, когда остаётся одно число. Требуется найти это число.

Задача была поставлена Иосифом Флавием (Flavius Josephus) ещё в 1 веке (правда, в несколько более узкой формулировке: при ).

Решать эту задачу можно моделированием. Простейшее моделирование будет работать. Используя Дерево отрезков, можно произвести моделирование за.

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

С помощью моделирования построим таблицу значений, например, такую:

И здесь достаточно отчётливо видна следующая закономерность:

Здесь 1-индексация несколько портит элегантность формулы, если нумеровать позиции с нуля, то получится очень наглядная формула:

Итак, мы нашли решение задачи Иосифа, работающее за операций.

Простая рекурсивная реализация (в 1-индексации):

int joseph (int n, int k) { return n1 ? (joseph (n-1, k) + k - 1) % n + 1 : 1;

} Нерекурсивная форма:

int joseph (int n, int k) { int res = 0;

for (int i=1;

i=n;

++i) res = (res + k) % i;

return res + 1;

} Решение за Для сравнительно небольших можно придумать более оптимальное решение, чем рассмотренное выше рекурсивное решение за. Если небольшое, то даже интуитивно понятно, что тот алгоритм делает много лишних действий: серьёзные изменения происходят, только когда происходит взятие по модулю, а до этого момента алгоритм просто несколько раз прибавляет к ответу число. Соответственно, можно избавиться от этих ненужных шагов, Небольшая возникающая при этом сложность заключается в том, что после удаления этих чисел у нас получится задача с меньшим, но стартовой позицией не в первом числе, а где-то в другом месте. Поэтому, вызвав рекурсивно себя от задачи с новым, мы затем должны аккуратно перевести результат в нашу систему нумерации из его собственной.

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

Реализация (для удобства в 0-индексации):

int joseph (int n, int k) { if (n == 1) return 0;

if (k == 1) return n-1;

if (k n) return (joseph (n-1, k) + k) % n;

int cnt = n / k;

int res = joseph (n - cnt, k);

res -= n % k;

if (res 0) res += n;

else res += res / (k - 1);

return res;

} Оценим асимптотику этого алгоритма. Сразу заметим, что случай разбирается у нас старым решением, которое отработает в данном случае за. Теперь рассмотрим сам алгоритм. Фактически, на каждой его итерации вместо чисел мы получаем примерно чисел, поэтому общее число итераций алгоритма примерно можно найти из уравнения:

логарифмируя его, получаем:

пользуясь разложением логарифма в ряд Тейлора, получаем приблизительную оценку:

Таким образом, асимптотика алгоритма действительно.

Аналитическое решение для В этом частном случае (в котором и была поставлена эта задача Иосифом Флавием) задача решается значительно проще.

В случае чётного получаем, что будут вычеркнуты все чётные числа, а потом останется задача для, тогда ответ для будет получаться из ответа для умножением на два и вычитанием единицы (за счёт сдвига позиций):

Аналогично, в случае нечётного будут вычеркнуты все чётные числа, затем первое число, и останется задача для, и с учётом сдвига позиций получаем вторую формулу:

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

Аналитическое решение для Несмотря на простой вид задачи и большое количество статей по этой и смежным задачам, простого аналитического представления решения задачи Иосифа до сих пор не найдено. Для небольших выведены некоторые формулы, но, по-видимому, все они трудноприменимы на практике (например, см. Halbeisen, Hungerbuhler "The Josephus Problem" и Odlyzko, Wilf "Functional iteration and the Josephus problem").

Игра Пятнашки: существование решения Напомним, что игра представляет собой поле на, на котором расположены фишек, пронумерованных числами от до, а одно поле оставлено пустым. Требуется, передвигая на каждом шаге какую-либо фишку на свободную позицию, прийти в конце концов к следующей позиции:

Игру Пятнашки ("15 puzzle") изобрёл в 1880 г. Нойес Чэпман (Noyes Chapman).

Существование решения Здесь мы рассмотрим такую задачу: по данной позиции на доске сказать, существует ли последовательность ходов, приводящая к решению, или нет.

Пусть дана некоторая позиция на доске:

где один из элементов равен нулю и обозначает пустую клетку.

Рассмотрим перестановку:

(т.е. перестановка чисел, соответствующая позиции на доске, без нулевого элемента) Обозначим через количество инверсий в этой перестановке (т.е. количество таких элементов и, что, но ).

Далее, пусть — номер строки, в которой находится пустой элемент (т.е. в наших обозначениях.

Тогда, решение существует тогда и только тогда, когда чётно.

Реализация Проиллюстрируем указанный выше алгоритм с помощью программного кода:

int a[16];

for (int i=0;

i16;

++i) cin a[i];

int inv = 0;

for (int i=0;

i16;

++i) if (a[i]) for (int j=0;

ji;

++j) if (a[j] a[i]) ++inv;

for (int i=0;

i16;

++i) if (a[i] == 0) inv += 1 + i / 4;

puts ((inv & 1) ? "No Solution" : "Solution Exists");

Доказательство Джонсон (Johnson) в 1879 г. доказал, что если нечётно, то решения не существует, а Стори (Story) в том же году доказал, что все позиции, для которых чётно, имеют решение.

Однако оба эти доказательства были достаточно сложны.

В 1999 г. Арчер (Archer) предложил значительно более простое доказательство (скачать его статью можно здесь).

Дерево Штерна-Броко. Ряд Фарея Дерево Штерна-Броко Дерево Штерна-Броко — это изящная конструкция, позволяющая построить множество всех неотрицательных дробей.

Она была независимо открыта немецким математиком Морицем Штерном (Moritz Stern) в 1858 г. и французским часовщиком Ахиллом Броко (Achille Brocot) в 1861 г. Впрочем, по некоторым данным, эта конструкция была открыта ещё древнегреческим учёным Эратосфеном (Eratosthenes).

На нулевой итерации у нас есть две дроби:

(вторая величина, строго говоря, дробью не является;

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

Так, на первой итерации текущее множество будет таким:

На второй:

На третьей:

Продолжая этот процесс до бесконечности, утверждается, можно получить множество всех неотрицательных дробей. Более того, все получаемые дроби будут различными (т.е. в текущем множестве каждая дробь встречается не более одного раза), несократимыми (числители и знаменатели будут получаться взаимно простыми). Наконец, все дроби будут автоматически упорядоченными по возрастанию. Доказательство всех этих замечательных свойств дерева Штерна-Броко будет приведено чуть ниже.

Осталось только привести изображение самого дерева Штерна-Броко (пока мы описывали его с помощью меняющегося множества). В корне этого бесконечного дерева находится дробь, а слева и справа от дерева находятся дроби и. Любая вершина дерева имеет двух сыновей, каждый из которых получается как медианта своего левого предка и правого предка:

Доказательство Упорядоченность. Она доказывается очень просто: заметим, что медианта двух дробей всегда находится между ними, т.е.:

при условии, что Доказывается это просто приведением трёх дробей к общему знаменателю.

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

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

Действительно, вспоминая Диофантовы уравнения с двумя неизвестными ( ), получаем из этого утверждения, что, что нам и требуется.

Итак, нам надо доказать истинность утверждения на любой итерации. Докажем его также по индукции.

На нулевой итерации это свойство выполнялось (в чём нетрудно убедиться). Теперь пусть оно было выполнено на предыдущей итерации, покажем, что оно выполнено на текущей итерации. Для этого надо рассмотреть тройку дробей-соседей в новом списке:

Для них условия принимают вид:

Однако истинность этих условий очевидна, при условии истинности. Таким образом, действительно, это свойство выполнено и на текущей итерации, что и требовалось доказать.

Наличие всех дробей. Доказательство этого свойства тесно связано с алгоритмом нахождения дроби в дереве Штерна-Броко. Учитывая, что в дереве Штерна-Броко все дроби упорядочены, получаем, что для любой вершины дерева в её левом поддереве находятся дроби, меньшие её, а в правом — большие её. Отсюда получаем и очевидный алгоритм поиска какой-либо дроби в дереве Штерна-Броко: вначале мы находимся в корне;

сравниваем нашу дробь с дробью, записанной в текущей вершине: если наша дробь меньше, то переходим в левое поддерево, если наша дробь больше — переходим в правое, а если совпадает — нашли дробь, поиск завершён.

Чтобы доказать, что бесконечное дерево Штерна-Броко содержит все дроби, достаточно показать, что этот алгоритм поиска дроби завершится за конечное число шагов для любой заданной дроби. Этот алгоритм можно понимать так: у нас есть текущий отрезок, в котором мы ищем нашу дробь. Изначально,.

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

Но их можно переписать в таком виде:

(здесь использовалось то, что они целочисленны, поэтому из следует ) Тогда, умножая первое на, а второе — на, и складывая их, получаем:

Раскрывая скобки слева и учитывая, что (см. доказательство предыдущего свойства), окончательно получаем:

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

Алгоритм построения дерева Чтобы построить любое поддерево дерева Штерна-Броко, достаточно знать только левого и правого предков.

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

Псевдокод этой процедуры, пытающийся построить всё бесконечное дерево:

void build (int a = 0, int b = 1, int c = 1, int d = 0, int level = 1) { int x = a+c, y = b+d;

... вывод текущей дроби x/y на уровне дерева level build (a, b, x, y, level + 1);

build (x, y, c, d, level + 1);

} Алгоритм поиска дроби Алгоритм поиска дроби был уже описан при доказательства того, что дерево Штерна-Броко содержит все дроби, повторим его здесь. Этот алгоритм — фактически алгоритм бинарного поиска, или алгоритм поиска заданного значения в бинарном дереве поиска. Изначально мы стоим в корне дерева. Стоя в текущей вершине, мы сравниваем нашу дробь с дробью в текущей вершине. Если они совпадают, то процесс останавливаем — мы нашли дробь в дереве. Иначе, если наша дробь меньше дроби в текущей вершине, то переходим в левого сына, иначе — в правого.

Как было доказано в свойстве о том, что дерево Штерна-Броко содержит все неотрицательные дроби, при поиске дроби алгоритм совершит не более итераций.

Приведём реализацию, которая возвращает путь до вершины, содержащей заданную дробь, возвращая его в виде последовательности символов 'L'/'R': если текущий символ равен 'L', то это обозначает переход в дереве в левого сына, а иначе — в правого (изначально мы стоим в корне дерева, т.е. в вершине с дробью ). На самом деле, такая последовательность символов, существующая и однозначно определяющая любую неотрицательную дробь, называется системой счисления Штерна-Броко.

string find (int x, int y, int a = 0, int b = 1, int c = 1, int d = 0) { int m = a+c, n = b+d;

if (x == m && y == n) return "";

if (x * n y * m) return 'L' + find (x, y, a, b, m, n);

else return 'R' + find (x, y, m, n, c, d);

} Иррациональным числам в системе счисления Штерна-Броко будут соответствовать бесконечные последовательности символов;

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

Последовательность Фарея Последовательностью Фарея порядка называется множество всех несократимых дробей между 0 и 1, знаменатели которых не превосходят, причём дроби упорядочены в порядке возрастания.

Эта последовательность названа в честь английского геолога Джона Фарея (John Farey), который попытался в г. доказать, что в ряде Фарея любая дробь является медиантой двух соседних. Насколько известно, его доказательство было неверным, а правильное доказательство предложил несколько позже Коши (Cauchy). Впрочем, ещё в 1802 г. математик Харос (Haros) в одной из своих работ пришёл практически к тем же результатам.

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

Из алгоритма построения дерева Штерна-Броко следует и аналогичный алгоритм для последовательностей Фарея.

На нулевой итерации включим в множество только дроби и. На каждой следующей итерации мы между каждыми двумя соседним дробями вставляем их медианту, если её знаменатель не превосходит. Рано или поздно в множестве перестанут происходить какие-либо изменения, и процесс можно останавливать — мы нашли искомую последовательность Фарея.

Вычислим длину последовательности Фарея. Последовательность Фарея порядка содержит все элементы последовательности Фарея порядка, а также все несократимые дроби со знаменателями, равными, но это количество, как известно, равно. Таким образом, длина последовательности Фарея порядка выражается по формуле:

или, раскрывая рекурсию:

Литература Роналд Грэхем, Дональд Кнут, Орен Паташник. Конкретная математика. Основание информатики [1998] Поиск подотрезка массива с максимальной/минимальной суммой Здесь мы рассмотрим задачу о поиске подотрезка массива с максимальной суммой ("maximum subarray problem" на английском), а также некоторые её вариации (в том числе алгоритм решения варианта этой задачи в режиме онлайн — описанный автором алгоритма — KADR (Ярослав Твердохлеб)).

Постановка задачи Дан массив чисел. Требуется найти такой его подотрезок, что сумма на нём максимальна:

Например, если бы все числа массива были бы неотрицательными, то в качестве ответа можно было бы взять весь массив. Решение нетривиально, когда массив может содержать как положительные, так и отрицательные числа.

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

Алгоритм Здесь мы рассмотрим практически очевидный алгоритм. (Дальше мы рассмотрим другой алгоритм, который чуть сложнее придумать, однако его реализация получается ещё короче.) Описание алгоритма Алгоритм весьма прост.

Введём для удобства обозначение:. Т.е. массив — это массив частичных сумм массива. Также положим значение.

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

Формально это означает, что нам надо для текущего найти такое (не превосходящее ), чтобы величина была максимальной. После тривиального преобразования мы получаем, что нам надо найти минимальное значение в массиве минимум на отрезке.

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

Очевидно, этот алгоритм работает за и асимптотически оптимален.

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

Реализация приводится в 0-индексированных массивах, а не в 1-нумерации, как было описано выше.

Приведём сначала решение, которое находит просто численный ответ, не находя индексы искомого отрезка:

int ans = a[0], sum = 0, min_sum = 0;

for (int r=0;

rn;

++r) { sum += a[r];

ans = max (ans, sum - min_sum);

min_sum = min (min_sum, sum);

} Теперь приведём полный вариант решения, который параллельно с числовым решением находит границы искомого отрезка:

int ans = a[0], ans_l = 0, ans_r = 0, sum = 0, min_sum = 0, min_pos = -1;

for (int r=0;

rn;

++r) { sum += a[r];

int cur = sum - min_sum;

if (cur ans) { ans = cur;

ans_l = min_pos + 1;

ans_r = r;

} if (sum min_sum) { min_sum = sum;

min_pos = r;

} } Алгоритм Здесь мы рассмотрим другой алгоритм. Его чуть сложнее понять, но зато он более элегантен, чем приведённый выше, и реализуется чуть-чуть короче. Этот алгоритм был предложен Джеем Каданом (Jay Kadane) в 1984 г.

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


Докажем этот алгоритм.

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

Однако этого недостаточно для доказательства алгоритма. В алгоритме мы, фактически, ограничиваемся в поиске ответа только такими отрезками, которые начинаются непосредственно после мест, когда случалось.

Но, в самом деле, рассмотрим произвольный отрезок, причём не находится в такой "критической" позиции (т.

е., где — последняя такая позиция, в которой ). Поскольку последняя критическая позиция находится строго раньше, чем в, то получается, что сумма неотрицательна.

Это означает, что, сдвинув в позицию, мы увеличим ответ или, в крайнем случае, не изменим его.

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

Реализация Как и в алгоритме 1, приведём сначала упрощённую реализацию, которая ищет только числовой ответ, не находя границ искомого отрезка:

int ans = a[0], sum = 0;

for (int r=0;

rn;

++r) { sum += a[r];

ans = max (ans, sum);

sum = max (sum, 0);

} Полный вариант решения, с поддержанием индексов-границ искомого отрезка:

int ans = a[0], ans_l = 0, ans_r = 0, sum = 0, minus_pos = -1;

for (int r=0;

rn;

++r) { sum += a[r];

if (sum ans) { ans = sum;

ans_l = minus_pos + 1;

ans_r = r;

} if (sum 0) { sum = 0;

minus_pos = r;

} } Смежные задачи Поиск максимального/минимального подотрезка с ограничениями Если в условии задачи на искомый отрезок накладываются дополнительные ограничения (например, что длина отрезка должна находиться в заданных пределах), то описанный алгоритм скорее всего легко обобщается на эти случаи — так или иначе, задача будет по-прежнему заключаться в поиске минимума в массиве при заданных дополнительных ограничениях.

Двумерный случай задачи: поиск максимальной/ минимальной подматрицы Описанная в данной статье задача естественно обобщается на большие размерности. Например, в двумерном случае она превращается в поиск такой подматрицы заданной матрицы, которая имеет максимальную сумму чисел в ней.

Из описанного выше решения для одномерного случая легко получить решение за : переберём и, и посчитаем массив сумм с по в каждой строке матрицы;

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

Более быстрые алгоритмы решения этой задачи хотя и известны, однако они не сильно быстрее,и при этом весьма сложны (настолько сложны, что по скрытой константе многие из них уступают тривиальному алгоритму при всех разумных ограничениях). По всей видимости, лучший из известных алгоритмов работает за (T. Chan 2007 "More algorithms for all-pairs shortest paths in weighted graphs").

Этот алгоритм Chan, а также многие другие результаты в данной области на самом деле описывают быстрое умножение матриц (где под умножением матриц подразумевается модифицированное умножение: вместо сложения используется минимум, а вместо умножения — сложение). Дело в том, что задача о поиске подматрицы с наибольшей суммой сводится к задаче о поиске кратчайших путей между всеми парами вершин, а эта задача, в свою очередь — сводится к такому умножению матриц.

Поиск подотрезка с максимальной/минимальной средней суммой Эта задача заключается в том, что надо найти такой отрезок, чтобы среднее значение на нём было максимальным:

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

В таком случае применим стандартный приём при работе с задачами о среднем значении: будем подбирать искомую максимальную среднюю величину двоичным поиском.

Для этого нам надо научиться решать такую подзадачу: дано число, и надо проверить, есть ли подотрезок массива (конечно, удовлетворяющий всем дополнительным ограничениям задачи), на котором среднее значение больше.


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

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

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

Алгоритм решения этой задачи достаточно сложен. Автор данного алгоритма — KADR (Ярослав Твердохлеб) — описал данный алгоритм в своём сообщении на форуме.

Литература С++ Visual C++, MFC Круглински, Уингоу, Шеферд. Программирование на Microsoft Visual C++ 6. для профессионалов (PDF[in RAR], 54.4 МБ) С++ ANSI. C++ International Standard (second edition, 2003-10-15) (PDF, 2.3 МБ) Эккель. Философия C++. Введение в стандартный C++ (2-е изд.) (DJVU, 6.4 МБ) Эккель, Эллисон. Философия C++. Практическое программирование (DJVU, 6.5 МБ) Саттер. Решение сложных задач на C++. 87 головоломных примеров с решениями (DJVU, 3.8 МБ) Саттер. Новые сложные задачи на C++. 40 новых головоломных примеров с решениями (DJVU, 3.6 МБ) Страуструп. Язык программирования C++ (2-е, дополненное изд.) (PDF, 2.9 МБ) Stroustrup. The C++ Programming Language (3rd edition) (PDF, 3.4 МБ) Abrahams, Gurtovoy. C++ Template Metaprogramming: Concepts, Tools, and Techniques from Boost and Beyond (CHM, 0.62 МБ) Джосьютис. C++. Стандартная библиотека. Для профессионалов (DJVU, 4.8 МБ) Джосьютис. C++. Стандартная библиотека. Для профессионалов (CD к книге) (ZIP, 0.14 МБ) Vandervoorde, Josuttis. C++ Templates: The Complete Guide (CHM, 0.72 МБ) Sutter, Alexandrescu. C++ Coding Standards: 101 Rules, Guidelines, and Best Practices (CHM, 0.51 МБ) Голуб. Веревка достаточной длины, чтобы выстрелить себе в ногу.

Правила программирования на C и C++ (PDF, 1.29 МБ) Meyers. Effective C++. More effective C++ (CHM, 2.0 МБ) Дьюхэрст. Скользкие места C++. Как избежать проблем при проектировании и компиляции ваших программ (DJVU, 9.3 МБ) Дьюхэрст. C++. Священные знания (DJVU, 6.7 МБ) Алгоритмы Фундаментальные пособия Кормен, Лейзерсон, Ривест, Штайн. Алгоритмы. Построение и анализ (2-е зд.) (DJVU, 18.3 МБ) Knuth. The Art of Computer Programming. Volume 1 (3rd edition) (DJVU, 6.0 МБ) Knuth. The Art of Computer Programming. Volume 2 (3rd edition) (DJVU, 7.6 МБ) Knuth. The Art of Computer Programming. Volume 3 (2nd edition) (DJVU, 7.7 МБ) Кормен, Лейзерсон, Ривест, Штайн. Алгоритмы. Построение и анализ (1-е изд.?) (PDF, 4.5 МБ) Седжвик. Фундаментальные алгоритмы (3-я ред.). Части 1-4 (DJVU, 15.0 МБ) Седжвик. Фундаментальные алгоритмы (3-я ред.). Часть 5 (DJVU, 16.7 МБ) Кнут. Искусство программирования. Том 1 (DJVU, 5.6 МБ) Кнут. Искусство программирования. Том 2 (DJVU, 6.1 МБ) Кнут. Искусство программирования. Том 3 (DJVU, 6.4 МБ) Грэхэм, Кнут, Паташник. Конкретная математика (DJVU, 8.9 МБ) Пападимитриу, Стайглиц. Комбинаторная оптимизация: алгоритмы и сложность (DJVU, 5.6 МБ) Motwani, Raghavan. Randomized Algorithms (DJVU, 4.4 МБ) Tucker. Computer Science Handbook (PDF, 27.0 МБ) Mehlhorn, Sanders. Algorithms and Data Structures: The Basic Toolbox (PDF, 2.0 МБ) Олимпиадные задачи Меньшиков. Олимпиадные задачи по программированию (DJVU, 4.4 МБ) Меньшиков. Олимпиадные задачи по программированию (CD к книге) (ZIP, 4.0 МБ) Окулов. Программирование в алгоритмах (DJVU, 3.6 МБ) Долинский. Решение сложных и олимпиадных задач по программированию (DJVU, 2.9 МБ) Скиена, Ревилла. Олимпиадные задачи по программированию (DJVU, 5.3 МБ) Строки Гасфилд. Строки, деревья и последовательности в алгоритмах (DJVU, 12.1 МБ) Smyth. Computing patterns in strings (DJVU, 26.4 МБ) Crochemore, Rytter. Jewels of Stringology (DJVU, 2.6 МБ) Crochemore, Hancart. Automata for matching patterns (pdf, 0.44 МБ) Компиляция, интерпретация Aho, Lam, Sethi, Ullman. Compilers: Principles, Techniques and Tools (DJVU, 5.

7 МБ) Mogensen. Basics of Compiler Design (PDF, 0.81 МБ) Пратт, Зелковиц. Языки программирования: разработка и реализация (4-е изд., 2002) (DJVU, 5.7 МБ) Теория игр Conway. On Numbers and Games (DJVU, 2.1 МБ) Алгебра, теория чисел Ribenboim. The New Book of Prime Number Records (DJVU, 11.0 МБ) Shoup. A Computational Introduction to Number Theory and Algebra (version 2) (PDF, 3.5 МБ) William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. Numerical Recipes: The Art of Scientific Computing (PDF, 20.4 МБ) Вычислительная геометрия Препарата, Шеймос. Вычислительная геометрия. Введение (DJVU, 4.5 МБ) Андреева, Егоров. Вычислительная геометрия на плоскости (DPF, 0.61 МБ) Mount. Lecture notes for the course Computational Geometry (PDF, 0.77 МБ) de Berg, van Kreveld, Overmars, Schwarzkopf. Computational Geometry: Algorithms and Applications (2nd, revised edition) (DJVU, 3.7 МБ) Chen. Computational Geometry: Methods and Applications (PDF, 1.14 МБ) Скворцов. Триангуляция Делоне и её применение (PDF, 2.5 МБ) Miu. Voronoi Diagrams: lecture slides (PDF, 0.14 МБ) Held. Voronoi Diagram: slides (PDF, 1.35 МБ) Графы Ahuja, Magnanti, Orlin. Network flows (DJVU, 13.8 МБ) Приезжев. Задача о димерах и теорема Кирхгофа (PDF, 1.18 МБ) Thorup. Unidirected Single-Source Shortest Paths with Positive Integer Weights in Linear Time (PPT, 1.10 МБ) Eppstein. Finding the K Shortest Paths (PDF, 0.18 МБ) Sokkalingham, Ahuja, Orlin. Inverse Spanning Tree Problems: Formulations and Algorithms (PDF, 0.07 МБ) Ahuja, Orlin. A Faster Algorithm for the Inverse Spanning Tree Problem (PDF, 0.10 МБ) Brander, Sinclair. A Comparative Study of K-Shortest Path Algorithms (PDF, 0.16 МБ) Gabow. An Efficient Implementation of Edmonds Maximum-Matching Algorithm (PDF, 2.7 МБ) Bender, Farach-Colton. The LCA Problem Revisited (PDF, 0.08 МБ) Майника. Алгоритмы оптимизации на сетях и графах (DJVU, 4.0 МБ) Mehlhorn, Uhrig. The minimum cut algorithm of Stoer and Wagner (PDF, 0.12 МБ) Оре. Теория графов (DJVU, 4.3 МБ) Харари. Теория графов (DJVU, 8.7 МБ) Stoer, Wagner. A Simple Min-Cut Algorithm (PDF, 0.20 МБ) Lovasz, Plummer. Matching theory (PDF, 9.9 МБ) Tutte. The Factorization of Linear Graphs (PDF, 0.47 МБ) Комбинаторика Степанов. Лемма Бернсайда и задачи о раскрасках (DPF, 0.18 МБ) Харари. Перечисление графов (DJVU, 4.1 МБ) Теория сложности Гэри, Джонсон. Вычислительные машины и труднорешаемые задачи (DJVU, 11.5 МБ) Математика Aitken. Determinants and Matrices (PDF, 10.2 МБ) Структуры данных Tarjan. Efficiency of a Good But Not Linear Set Union Algorithm (PDF, 0.63 МБ) Tarjan, Leeuwen. Worst-Case Analysis of Set Union Algorithms (PDF, 1.55 МБ) Оптимизация Kaspersky. Code Optimization: Effective Memory Usage (CHM, 10.4 МБ) Kaspersky. Code Optimization: Effective Memory Usage (CD к книге) (ZIP, 4.6 МБ) Fog. Optimization Manuals (Optimizing software in C++, in assembly, processors microarchitecture) (last edited - 2008) (PDF[in ZIP], 2.9 МБ) Intel. Intel Architecture Optimization Manual (1997) (PDF, 0.49 МБ) Java Java Эккель. Философия Java (4-е изд.) (DJVU, 5.4 МБ) Хорстманн, Корнелл. Java 2. Библиотека профессионала. Том 1 (Основы) (7-е изд.) (DJVU, 10.5 МБ) Хорстманн, Корнелл. Java 2. Библиотека профессионала. Том (Тонкости программирования) (7-е изд.) (DJVU, 13.2 МБ) Хорстманн, Корнелл. Java 2. Библиотека профессионала (7-е изд.) (CD к книге) (ZIP, 0.66 МБ) TeX TeX Кнут. Всё про TeX (DJVU, 17.1 МБ) Abrahams, Hargreaves, Berry. TeX for the Impatient (PDF, 1.36 МБ) LaTeX Gratzer. Math into LaTeX. An Introduction to LaTeX and AMS-LaTeX (DJVU, 0.34 МБ) Oetiker. The Not So Short Introduction to LaTeX (version 4.26, 2008-Sep-25) (PDF, 2.3 МБ) Об авторе Бессменным автором сайта e-maxx.ru и всех статей по алгоритмам являюсь я, e-maxx, также известный как Максим Иванов :) Все материалы сайта, в том числе и эта книга, выложены под лицензией Public Domain, т.е.

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

Кроме меня в создании, корректировке и улучшении статей принимали участие множество людей, — спасибо Вам за бесчисленные замечания, предложения по улучшению, указания на неточности, и т.д. К сожалению, пока никто из сообщества не решился на написание полноценной статьи с описанием какого-либо алгоритма. Если пожелаете быть первым — добро пожаловать ;

) Связаться со мной можно по электронной почте: e-maxx@inbox.ru, или на форуме сайта e-maxx.



Pages:     | 1 |   ...   | 13 | 14 ||
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.