e-maxx_algo

Задача Джонсона с двумя станками

Имеется деталей и два станка. Каждая деталь должна сначала пройти обработку на первом станке, затем — на втором. При этом -ая деталь обрабатывается на первом станке за времени, а на втором — за времени. Каждый станок в каждый момент времени может работать только с одной деталью.

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

Эта задача называется иногда задачей двухпроцессорного обслуживания задач, или задачей Джонсона (по имени S. M. Johnson, который в 1954 г. предложил алгоритм для её решения).

Стоит отметить, что когда число станков больше двух, эта задача становится NP-полной (как доказал Гэри (Garey) в 1976 г.).

Построение алгоритма

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

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

Рассмотрим порядок подачи деталей на станки, совпадающий с их входным порядком: .

Обозначим через время простоя второго станка непосредственно перед обработкой -ой детали (после обработки -ой детали). Наша цель — минимизировать суммарный простой:

Для первой детали мы имеем:

Таким образом, общий вид для выглядит так:

Посчитаем теперь суммарный простой . Утверждается, что он имеет вид:

где

(В это можно убедиться по индукции, либо последовательно находя выражения для суммы первых двух, трёх, и т.д. .)

Воспользуемся теперь перестановочным приёмом: попробуем обменять какие-либо два соседних элемента

и и посмотрим, как при этом изменится суммарный простой.

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

times included [1954]

● M.R. Garey. The Complexity of Flowshop and Jobshop Scheduling [1976]

Оптимальный выбор заданий при известных временах завершения и длительностях выполнения

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

Решение

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

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

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

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

Реализация

int n;

vector < pair<int,int> > a; // задания в виде пар (крайний срок, длительность)

... чтение n и a ...

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

typedef set < pair<int,int> > t_s; t_s s;

vector<int> 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; i<result.size(); ++i) cout << result[i] << ' ';

Задача Иосифа

Условие задачи. Даны натуральные и . По кругу выписывают все натуральные числа от 1 до . Сначала отсчитывают -ое число, начиная с первого, и удаляют его. Затем от него отсчитывают чисел и -ое удаляют, и т. д. Процесс останавливается, когда остаётся одно число. Требуется найти это число.

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

Решение за

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

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

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

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

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

int joseph (int n, int k) {

return n>1 ? (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-индексации):

алгоритма примерно можно найти из уравнения:

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

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

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

Аналитическое решение для

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

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

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

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

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

Аналитическое решение для

Несмотря на простой вид задачи и большое количество статей по этой и смежным задачам, простого аналитического представления решения задачи Иосифа до сих пор не найдено. Для небольших выведены некоторые формулы, но, по-видимому, все они трудноприменимы на практике (например, см. 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; i<16; ++i) cin >> a[i];

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

Доказательство

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

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