1. Четыре человека разных лет подошли ночью с лампочкой к мосту.
Мост узкий, т.е. пройти по нему могут не более двух человек с лампой.
На прохождение моста каждому из путешественников нужно соотв. 1, 2, 5 и 10 мин. Пара двигается со скоростью более медленного.
Как пересечь мост по-быстрее?
2. Обобщить задачу для N-путников с t[1;N]. Найти эффективное решение или показать NP-полноту.
В жизни кaждoгo челoвекa бывaют приятные мoменты, кoгдa oн чувствует себя пoлным идиoтoм. Приятнoсть этих мoментoв в пoстижении истины.
Здравствуйте, sugarde, Вы писали:
S>1. Четыре человека разных лет подошли ночью с лампочкой к мосту. S>Мост узкий, т.е. пройти по нему могут не более двух человек с лампой.
S>На прохождение моста каждому из путешественников нужно соотв. 1, 2, 5 и 10 мин. Пара двигается со скоростью более медленного. S>Как пересечь мост по-быстрее?
Мои перешли за 17 мин. Хочется увидеть другие решения, пока свое придержу...
S>2. Обобщить задачу для N-путников с t[1;N]. Найти эффективное решение или показать NP-полноту.
Ой лениво... Но NP полноты не будет.
Здравствуйте, samius, Вы писали:
S>>2. Обобщить задачу для N-путников с t[1;N]. Найти эффективное решение или показать NP-полноту. S>Ой лениво... Но NP полноты не будет.
С одной стороны, чувтвуется, что есть какое-то дин.прог решение, с другой подозрительная задачка.
Тоже думаю.
В жизни кaждoгo челoвекa бывaют приятные мoменты, кoгдa oн чувствует себя пoлным идиoтoм. Приятнoсть этих мoментoв в пoстижении истины.
Здравствуйте, sugarde, Вы писали:
S>1. Четыре человека разных лет подошли ночью с лампочкой к мосту. S>Мост узкий, т.е. пройти по нему могут не более двух человек с лампой.
S>На прохождение моста каждому из путешественников нужно соотв. 1, 2, 5 и 10 мин. Пара двигается со скоростью более медленного. S>Как пересечь мост по-быстрее?
S>2. Обобщить задачу для N-путников с t[1;N]. Найти эффективное решение или показать NP-полноту.
Сначала идут номера
1,2 — проходят за 2 минуты
потом
5,10 проходят за 10 минут
Здравствуйте, codelord, Вы писали:
C>Здравствуйте, sugarde, Вы писали:
S>>1. Четыре человека разных лет подошли ночью с лампочкой к мосту. S>>Мост узкий, т.е. пройти по нему могут не более двух человек с лампой.
S>>На прохождение моста каждому из путешественников нужно соотв. 1, 2, 5 и 10 мин. Пара двигается со скоростью более медленного. S>>Как пересечь мост по-быстрее?
S>>2. Обобщить задачу для N-путников с t[1;N]. Найти эффективное решение или показать NP-полноту.
C>Сначала идут номера C>1,2 — проходят за 2 минуты C>потом C>5,10 проходят за 10 минут
C>итого 12 минут.
или я не понял условие или для любого количества решением будет:
сортировка по времени и выход по парам начиная с конца сортированного списка т/е
имеем время проходов 20 60 80 1 2 555 30 21
сначала сортируем
1 2 20 21 30 60 80 555
и выпускаем
80 — 555
30 — 60
20 — 21
1 — 2
если остается последний ( нечетный список значит идет последним один )
получаем минимальное время прохода пар
Здравствуйте, sugarde, Вы писали:
S>1. Четыре человека разных лет подошли ночью с лампочкой к мосту. S>Мост узкий, т.е. пройти по нему могут не более двух человек с лампой.
S>На прохождение моста каждому из путешественников нужно соотв. 1, 2, 5 и 10 мин. Пара двигается со скоростью более медленного. S>Как пересечь мост по-быстрее?
S>2. Обобщить задачу для N-путников с t[1;N]. Найти эффективное решение или показать NP-полноту.
Ну я так и думал, видимо лампу надо вернуть и она у них одна,
Но про это никто не сказал
Здравствуйте, sugarde, Вы писали:
S>1. Четыре человека разных лет подошли ночью с лампочкой к мосту. S>Мост узкий, т.е. пройти по нему могут не более двух человек с лампой.
S>На прохождение моста каждому из путешественников нужно соотв. 1, 2, 5 и 10 мин. Пара двигается со скоростью более медленного. S>Как пересечь мост по-быстрее?
Самый быстрый бегает по мосту взад-вперед и переводит всех.
S>2. Обобщить задачу для N-путников с t[1;N]. Найти эффективное решение или показать NP-полноту.
Здравствуйте, Socrat, Вы писали:
S>Самый быстрый бегает по мосту взад-вперед и переводит всех.
Это, очевидно, неправильно. Таким образом даже задача 1 не решается (получится больше 17 минут).
S>>Самый быстрый бегает по мосту взад-вперед и переводит всех. RT>Это, очевидно, неправильно. Таким образом даже задача 1 не решается (получится больше 17 минут).
Действительно, погорячился. Надо двух самых быстрых использовать, чтобы лампу относить назад, а самых медленных группировать парами...
Здравствуйте, Socrat, Вы писали:
S>Здравствуйте, RomikT, Вы писали:
S>>>Самый быстрый бегает по мосту взад-вперед и переводит всех. RT>>Это, очевидно, неправильно. Таким образом даже задача 1 не решается (получится больше 17 минут).
S>Действительно, погорячился. Надо двух самых быстрых использовать, чтобы лампу относить назад, а самых медленных группировать парами...
Здравствуйте, sugarde, Вы писали:
S>1. Четыре человека разных лет подошли ночью с лампочкой к мосту. S>Мост узкий, т.е. пройти по нему могут не более двух человек с лампой.
S>На прохождение моста каждому из путешественников нужно соотв. 1, 2, 5 и 10 мин. Пара двигается со скоростью более медленного. S>Как пересечь мост по-быстрее?
17 минут (задача от MS):
-> — туда
<- — назад
->1+2 (2)
<-2 (2) ->10+5 (10)
<-1 (1) ->1+2 (2)
S>2. Обобщить задачу для N-путников с t[1;N]. Найти эффективное решение или показать NP-полноту.
Здравствуйте, samius, Вы писали:
S>>2. Обобщить задачу для N-путников с t[1;N]. Найти эффективное решение или показать NP-полноту. S>Ой лениво... Но NP полноты не будет.
Обобщить как раз довольно таки просто...
сортируем всех N путников по времени прохождения.
Первые два ... т.е. пара самых быстрых будут т.н. перевозчиками. Их задача переносить лампу с одного конца на другой за минимальное возможное время.
Алгоритм перевозки такой.
0. i=0.
1. Перевозчики переходят мост.
2. Самый быстрый из перевозчиков идет обратно.
3. Мост переходит пара N-2i, N-(2i+1).
4. Оставшийся перевозчик идет обратно с лампой.
5. i=i+1.
6. Если остались пары не перевозчиков, идем на шаг 1.
7. Если осталася непарный "тормоз". Самый быстрый из перевозчиков переходит с ним мост и возвращается обратно.
8. Пара перевозчиков переходит мост. Конец.
[..]
S>2. Обобщить задачу для N-путников с t[1;N]. Найти эффективное решение или показать NP-полноту.
ИМХО всё сводится к тому как лучше перевести двух самых медленных из оставшихся. Есть 2 разумных подхода:
1) Самый быстрый последовательно переводит обоих самых медленных и возвращается назад с лампой.
2) Двое самых быстрых переходят с лампой, потом один возвращает лампу назад, с этой лампой переходят двое самых медленных после чего второй быстрый возвращает лампу назад.
На каждом шаге определяется, какой из вариантов эффективнее.
---
The optimist proclaims that we live in the best of all possible worlds; and the pessimist fears this is true
Здравствуйте, RomikT, Вы писали:
RT>Здравствуйте, gbear, Вы писали:
G>>Алгоритм перевозки такой... RT>Алгоритм, видимо, неправильный, так как не работает для [102, 104, 105, 108]
1. 102 и 104 переходять мост.
2. 102 возращается.
3. 105 и 108 переходят мост.
4. 104 возвращается.
5. 102 и 104 переходят мост.
Здравствуйте, wallaby, Вы писали:
W>ИМХО всё сводится к тому как лучше перевести двух самых медленных из оставшихся. Есть 2 разумных подхода:
W>1) Самый быстрый последовательно переводит обоих самых медленных и возвращается назад с лампой. W>2) Двое самых быстрых переходят с лампой, потом один возвращает лампу назад, с этой лампой переходят двое самых медленных после чего второй быстрый возвращает лампу назад.
W>На каждом шаге определяется, какой из вариантов эффективнее.
Кстати да... например при [1, 10, 10, 10] первый способ эффективней.
Здравствуйте, wallaby, Вы писали:
W>ИМХО всё сводится к тому как лучше перевести двух самых медленных из оставшихся. Есть 2 разумных подхода:
W>1) Самый быстрый последовательно переводит обоих самых медленных и возвращается назад с лампой. W>2) Двое самых быстрых переходят с лампой, потом один возвращает лампу назад, с этой лампой переходят двое самых медленных после чего второй быстрый возвращает лампу назад.
W>На каждом шаге определяется, какой из вариантов эффективнее.
Более точно так:
цикл
если эффективнее первый вариант, самый быстрый переводит одного самого медленного и возвращается
если эффективнее второй вариант, переводятся двое самых медленных по второму варианту
конец цикла
но гарантии что в итоге мы получим наименьшее время нет — не исключено, что даже если второй вариант эффективнее в итоге если проанализировать всё до конца окажется лучше сначала перевести самого медленного. Ситуация напоминает известную проблему в алгоритме сжатия LZ77 (eg, Deflate), когда приходится искать компромисс между скоростью работы и качеством сжатия.
---
The optimist proclaims that we live in the best of all possible worlds; and the pessimist fears this is true
Здравствуйте, gbear, Вы писали:
G>Здравствуйте, RomikT, Вы писали:
RT>>Здравствуйте, gbear, Вы писали:
G>>>Алгоритм перевозки такой... RT>>Алгоритм, видимо, неправильный, так как не работает для [102, 104, 105, 108]
Здравствуйте, wallaby, Вы писали:
W>Здравствуйте, sugarde, Вы писали:
W>[..]
S>>2. Обобщить задачу для N-путников с t[1;N]. Найти эффективное решение или показать NP-полноту.
W>ИМХО всё сводится к тому как лучше перевести двух самых медленных из оставшихся. Есть 2 разумных подхода:
W>1) Самый быстрый последовательно переводит обоих самых медленных и возвращается назад с лампой. W>2) Двое самых быстрых переходят с лампой, потом один возвращает лампу назад, с этой лампой переходят двое самых медленных после чего второй быстрый возвращает лампу назад.
W>На каждом шаге определяется, какой из вариантов эффективнее.
выделим двух самых шустрых. (T1, T2)
они будут переводить людей на другую сторону. (T3, T4)
1ый способ эффективнее если T2 + T2 > T1 + T3
но как оптимально бить на пары?
к тому же людей может быть нечетное кол-во
Здравствуйте, sugarde, Вы писали:
S>1. Четыре человека разных лет подошли ночью с лампочкой к мосту. S>Мост узкий, т.е. пройти по нему могут не более двух человек с лампой.
Здравствуйте, sugarde, Вы писали:
S>2. Обобщить задачу для N-путников с t[1;N]. Найти эффективное решение или показать NP-полноту.
Пробуем обощить...
Выделим из всей совокупности путников дух самых быстрых... x и у. При чем t(x) <= t(y).
Очевидно, что решение всегда будет начинаться с того, что выполняется переход x и y. После чего, х возращается с лампой обратно.
Время такого шага t(y) + t(x).
Опишем следующий за первым переходом выбор:
Необходимо решить, пойдет ли сейчас через мост пара самых медленных, или самый быстрый поведет одного самого медленного. При этом очевидно, что с той стороны моста лампу принесет самый быстрый. В первом случае это будет y, а во втором x.
Выделим из множетва не перешедших мост двух самых медленных i и j. При этом t(i) => t(j).
Очевидно, t(x) <= t(y) <= t(j) <= t(i).
В случае перехода i и j время перехода будет выражаться как:
переход пары + возврат лампы + очевидный переход x и y /*/ + возврат лампы.
Т.е. t(i) + t(y) + t(y) + t(x).
В случае перехода x и i время перехода i и j будет выражаться как:
переход x и i + возврат лампы + переход x и j /**/ + возврат лампы.
t(i) + t(x) + t(j) + t(x).
Т.е. если t(x) + t(j) > 2t(y) выгодней первый вариант, иначе — второй.
*
После того как y перенес лампу, на той стороне моста остались путники время перехода которых выше чем t(x) и t(y).
Очевидно t(y) + t(x) — минимальное время добиться минимального времени последующего возврата лампы.
**
На самом деле этот переход не очевиден, и будет осуществлен только в том случае если для него выполняется
t(x) + t(k) <= 2t(y), где k следующий за j по медленности времени перехода путник.
Перебор нашел решение: (1,5)(1)(1,30)(1)(60,120)(5)(1,5)
С результатом 167.
Т.е. наводит на мысль о смешении решений (толстые парочками, шустрики носят лампу) и (шустрик водит толстяков).
В жизни кaждoгo челoвекa бывaют приятные мoменты, кoгдa oн чувствует себя пoлным идиoтoм. Приятнoсть этих мoментoв в пoстижении истины.
Здравствуйте, sugarde, Вы писали:
S>2. Обобщить задачу для N-путников с t[1;N]. Найти эффективное решение или показать NP-полноту.
пока N >= 4
туда t[1],t[2]
обратно t[1] -- или t[2], без разницы
туда t[N-1],t[N]
обратно t[2] -- или t[1], соответственно
N := N-2
если N == 3
туда t[1],t[3]
обратно t[1]
N := 2
если N == 2
туда t[1],t[2]
N := 0
если N == 1
туда t[1]
N := 0
К>пока N >= 4
К> туда t[1],t[2]
К> обратно t[1] -- или t[2], без разницы
К> туда t[N-1],t[N]
К> обратно t[2] -- или t[1], соответственно
К> N := N-2
К>
Опаньки! Оказывается, здесь возможны варианты.
t1,t2 ->
t1 <-
t3,t4 ->
t2 <-
либо
t1,t4 ->
t1 <-
t1,t3 ->
t1 <-
разница: t2+t2 против t1+t3
Таким образом, нужно делать проверку и принимать решение.
К>>пока N >= 4
К>> туда t[1],t[2]
К>> обратно t[1] -- или t[2], без разницы
К>> туда t[N-1],t[N]
К>> обратно t[2] -- или t[1], соответственно
К>> N := N-2
К>>
К>Опаньки! Оказывается, здесь возможны варианты.
К>t1,t2 -> К>t1 <- К>t3,t4 -> К>t2 <-
К>либо
К>t1,t4 -> К>t1 <- К>t1,t3 -> К>t1 <-
К>разница: t2+t2 против t1+t3
К>Таким образом, нужно делать проверку и принимать решение.
А как разбивать на пары???
Может быть более грамотное разбиение(чем банальные пары соседей в отсортированном массиве) приведет к другому выбору.
Вообще 2ой случай t1 + t3 можно рассмотреть как отдельный перевод 2 независимых тихоней самым шустрым чуваком.
И после этого может быть снова стоит задуматься о новом разбиении на пары.
Здравствуйте, sugarde, Вы писали:
S>1. Четыре человека разных лет подошли ночью с лампочкой к мосту. S>Мост узкий, т.е. пройти по нему могут не более двух человек с лампой.
S>На прохождение моста каждому из путешественников нужно соотв. 1, 2, 5 и 10 мин. Пара двигается со скоростью более медленного. S>Как пересечь мост по-быстрее?
S>2. Обобщить задачу для N-путников с t[1;N]. Найти эффективное решение или показать NP-полноту.
Минимальное время перехода даст такая функция, рекурсивно перебирающая все возможные сочетания 2-х основных примитивов:
function FindTime(const Times: array of Cardinal): Cardinal;
var
Time1: Cardinal;
Time2: Cardinal;
NextTimes: array of Cardinal;
begin
case Length(Times) of
0: Result:= 0;
1: Result:= Times[0];
2: Result:= Times[1];
3: Result:= Times[0] + Times[1] + Times[2];
else// шустрый переводит тормоза
SetLength(NextTimes, Length(Times) - 1);
Move(Times[0], NextTimes[0], (Length(Times) - 1) * SizeOf(Cardinal));
Time1:= Times[0] + Times[Length(Times) - 1] + FindTime(NextTimes);
// переходит пара тормозов
SetLength(NextTimes, Length(Times) - 2);
Move(Times[0], NextTimes[0], (Length(Times) - 2) * SizeOf(Cardinal));
Time2:= Times[0] + 2 * Times[1] + Times[Length(Times) - 1]
+ FindTime(NextTimes);
if Time1 < Time2
then Result:= Time1
else Result:= Time2;
end;
end;
В частности, FindTime([1, 2, 5, 10]) = 17.
---
The optimist proclaims that we live in the best of all possible worlds; and the pessimist fears this is true
1. Аля метод грубой силы.
На 100000 то поди уже загнется
2. Не совсем понятно почему эти примитивы обеспечивают полноту решений.
3. Если не ошибаюсь то следующий алгоритм будет работать на порядок быстрее и будет выдавать тот же результат.
считаем что массивчик уже отсортирован.
делим его на 2 части по времени.
Ti > 2*T2 — T1. (тормоза)
Ti <= 2*T2 — T1. (шустрики)
T1, T2 мегашустрики
делим тормозов на пары начиная с конца. если останется 1 без пары приравниваем его к шустрикам.
переводим тормозов с помощью мегашустриков.
затем обычных шустриков первый переводит лично.
похоже на минимум надо чуть подумать.
W>Здравствуйте, sugarde, Вы писали:
S>>1. Четыре человека разных лет подошли ночью с лампочкой к мосту. S>>Мост узкий, т.е. пройти по нему могут не более двух человек с лампой.
S>>На прохождение моста каждому из путешественников нужно соотв. 1, 2, 5 и 10 мин. Пара двигается со скоростью более медленного. S>>Как пересечь мост по-быстрее?
S>>2. Обобщить задачу для N-путников с t[1;N]. Найти эффективное решение или показать NP-полноту.
W>Минимальное время перехода даст такая функция, рекурсивно перебирающая все возможные сочетания 2-х основных примитивов:
W>
Здравствуйте, ghost92, Вы писали:
G>1. Аля метод грубой силы.
Наверняка можно усовершенствовать, не в этом дело — главное действительно ли он даёт минимальное время.
G>2. Не совсем понятно почему эти примитивы обеспечивают полноту решений.
Предложите контрпример.
ИМХО, быстрее чем с помощью этих примитивов перейти нельзя (максимум что возможно — за то же время).
---
The optimist proclaims that we live in the best of all possible worlds; and the pessimist fears this is true
Здравствуйте, ghost92, Вы писали:
G>А как разбивать на пары??? G>Может быть более грамотное разбиение(чем банальные пары соседей в отсортированном массиве) приведет к другому выбору. G>Вообще 2ой случай t1 + t3 можно рассмотреть как отдельный перевод 2 независимых тихоней самым шустрым чуваком. G>И после этого может быть снова стоит задуматься о новом разбиении на пары.
Мысли неспешно текут в сторону кода Хаффмана... Но очень неспешно...
Здравствуйте, wallaby, Вы писали:
К>>Мысли неспешно текут в сторону кода Хаффмана... Но очень неспешно...
W>Мимо. Как связать код Хаффмана с переводом тормоза шустриком?
Там тоже операции на самых толстых
Тут весь вопрос, работает ли greedy или нет.
В жизни кaждoгo челoвекa бывaют приятные мoменты, кoгдa oн чувствует себя пoлным идиoтoм. Приятнoсть этих мoментoв в пoстижении истины.
Здравствуйте, sugarde, Вы писали:
S>Тут весь вопрос, работает ли greedy или нет.
Да нет, greedy/lazy — это из LZ77. В коде Хаффмана символы собираются в пары по толщине (частоте появления в тексте), а связи худых с толстыми не просматривается.
---
The optimist proclaims that we live in the best of all possible worlds; and the pessimist fears this is true
G>>2. Не совсем понятно почему эти примитивы обеспечивают полноту решений.
W>Предложите контрпример. W>ИМХО, быстрее чем с помощью этих примитивов перейти нельзя (максимум что возможно — за то же время).
Ну, если можно доказать, что туда-сюда ходит все время конечное число человек, то решение динамикой, вроде бы очевидно. Под конечным числом имеется в виду, что существует M, такое, что для любого N макисмальный номер возвращающегося человека не больше M (люди отсортированы по возрастанию времени).
Листаю список NPC с идеей добавить супер-шустриков с нуль-переходом и решить, скажем BIN PACKING.
А как в твоей динамике доказать, что тормоза гарантированные невозвращенцы?
т.е. ага нам нужно послать назад кого-то с лампочкой. Этот кто-то ещё вернётся.
Он перенесёт лампу и затратит своё время. На возвращение ему понадобится как-минимум своё время. Итог — пусть назад бежит всегда самый шустрый с правой стороны. Один факториал ушел!
В жизни кaждoгo челoвекa бывaют приятные мoменты, кoгдa oн чувствует себя пoлным идиoтoм. Приятнoсть этих мoментoв в пoстижении истины.
Здравствуйте, sugarde, Вы писали:
S>Он перенесёт лампу и затратит своё время. На возвращение ему понадобится как-минимум своё время.
Это достаточно очевидный факт. То есть всегда существует i такое что все aj (j<=i) возвращаются, а aj (j>i) нет. Вопрос заключается в том, зависит ли это i от N или нет. Если не зависит, то решаем динамикой за O(N*2^i), а если зависит, то надо думать.
Здравствуйте, ghost92, Вы писали:
G>А как разбивать на пары??? G>Может быть более грамотное разбиение(чем банальные пары соседей в отсортированном массиве) приведет к другому выбору. G>Вообще 2ой случай t1 + t3 можно рассмотреть как отдельный перевод 2 независимых тихоней самым шустрым чуваком. G>И после этого может быть снова стоит задуматься о новом разбиении на пары.
Маленькая эврика. Динамическое программирование и линейная сложность.
Сперва примем лемму, что общее направление работ — всё-таки в порядке убывания, а не вперемешку.
Действительно, если есть операция "туда t[N-k], t[N]", то предпочтительнее выбрать k=1 — это приведёт как минимум к не худшему состоянию.
Но сейчас я её доказывать не буду, чтоб не закопаться.
Итак.
Имеем операции:
— одноходовку "туда t[1],t[N]; обратно t[1]"
— двухходовку "туда t[1],t[2]; обратно t[1]" + "туда t[N-1],t[N]; обратно t[2]"
— завершающий ход "туда t[1],t[2]" либо "туда t[1],t[3]"
Обозначим их кодами 'mov', 'push'+'pop', 'ret0', 'ret1'.
Программа действий — это строка из команд, вот в такой автоматной грамматике
Применяя программу к нашему набору t[N],t[N-1],..., в момент, когда на левом берегу остались t[K] и младше, наша программа
— потратила какое-то суммарное время
— находится в одном из двух состояний: либо "вне двухходовки", либо "внутри двухходовки".
Таким образом, для каждого значения K и обоих состояний мы можем найти наилучшее время и соответсвующую наилучшую головную часть программы.
Дальнейшее очевидно
Держим вектор наилучших результатов для текущего K и из него получаем вектор наилучших результатов для K-1.
Начинаем с вектора для N (outside -> T=0,P=''; inside -> T=+oo,P='')
Приходим к вектору для 2 (outside,inside)
И из него приходим к точке (1,finish)
Поскольку двухходовки делать вложенными (на нулевом уровне бегают t[1],t[2]; на первом — t[1],t[3]; и т.д.)
то автомат у нас уже получается стековый, а число состояний — до N-2.
А это уже квадратичная сложность.
Но всяко не экспонента.
Здравствуйте, Vintik_69, Вы писали:
V_>Ну, если можно доказать, что туда-сюда ходит все время конечное число человек...
А что тут доказывать? Туда-сюда имеет смысл ходить только двум самым шустрым — любое возвращение более медленного приведёт к увеличению общего времени перехода. Если же есть ещё столь же шустрые как и второй, то они не улучшат результат — поэтому можно считать что возвращаются не более 2 человек.
---
The optimist proclaims that we live in the best of all possible worlds; and the pessimist fears this is true
Здравствуйте, Cider, Вы писали:
C>Здравствуйте, sugarde, Вы писали:
S>>1. Четыре человека разных лет подошли ночью с лампочкой к мосту. S>>Мост узкий, т.е. пройти по нему могут не более двух человек с лампой.
C>Опять гора Фудзи
Интуитивно это понятно, а вот как доказать?
Вообще не понятно может быть иногда выгодно вернуться нескольким шустрикам обратно.
Но похоже жадный алгоритм будет не хуже.
Предлагаю рассмотреть 2 частных случая.
1) 2 мегашустрика со скоростью 0 (ну если необходимо >0, то можно сделать скорость 1/(4N) этого точно хватит на то чтоб покрыть все лишние проходы)
жадный алгоритм доказывается тривиально.
2) 1 мегашустрик со скоростью 0.
тут надо думать.
3) общий случай.
вычитаем из каждого времени прохода время первого.
говорим что проходов по мосту как минимум 2*N — 1. (в жадном алгоритме ровно столько)
мы свели задачу ко 2ому пункту.
К>Здравствуйте, ghost92, Вы писали:
G>>А как разбивать на пары??? G>>Может быть более грамотное разбиение(чем банальные пары соседей в отсортированном массиве) приведет к другому выбору. G>>Вообще 2ой случай t1 + t3 можно рассмотреть как отдельный перевод 2 независимых тихоней самым шустрым чуваком. G>>И после этого может быть снова стоит задуматься о новом разбиении на пары.
К>Маленькая эврика. Динамическое программирование и линейная сложность.
К>Сперва примем лемму, что общее направление работ — всё-таки в порядке убывания, а не вперемешку. К>Действительно, если есть операция "туда t[N-k], t[N]", то предпочтительнее выбрать k=1 — это приведёт как минимум к не худшему состоянию. К>Но сейчас я её доказывать не буду, чтоб не закопаться.
К>Итак. К>Имеем операции: К>- одноходовку "туда t[1],t[N]; обратно t[1]" К>- двухходовку "туда t[1],t[2]; обратно t[1]" + "туда t[N-1],t[N]; обратно t[2]" К>- завершающий ход "туда t[1],t[2]" либо "туда t[1],t[3]" К>Обозначим их кодами 'mov', 'push'+'pop', 'ret0', 'ret1'.
К>Программа действий — это строка из команд, вот в такой автоматной грамматике К>
К>Применяя программу к нашему набору t[N],t[N-1],..., в момент, когда на левом берегу остались t[K] и младше, наша программа К>- потратила какое-то суммарное время К>- находится в одном из двух состояний: либо "вне двухходовки", либо "внутри двухходовки".
К>Таким образом, для каждого значения K и обоих состояний мы можем найти наилучшее время и соответсвующую наилучшую головную часть программы. К>Дальнейшее очевидно К>Держим вектор наилучших результатов для текущего K и из него получаем вектор наилучших результатов для K-1. К>Начинаем с вектора для N (outside -> T=0,P=''; inside -> T=+oo,P='') К>Приходим к вектору для 2 (outside,inside) К>И из него приходим к точке (1,finish)
К> К>Поскольку двухходовки делать вложенными (на нулевом уровне бегают t[1],t[2]; на первом — t[1],t[3]; и т.д.) К>то автомат у нас уже получается стековый, а число состояний — до N-2.
К>А это уже квадратичная сложность. К>Но всяко не экспонента.
Здравствуйте, sugarde, Вы писали:
S>1. Четыре человека разных лет подошли ночью с лампочкой к мосту. S>Мост узкий, т.е. пройти по нему могут не более двух человек с лампой.
S>На прохождение моста каждому из путешественников нужно соотв. 1, 2, 5 и 10 мин. Пара двигается со скоростью более медленного. S>Как пересечь мост по-быстрее?
Я прочел Ваше сообщение три раза, и мой хомячок сломал клетку, отрастил кожистые крылья и сейчас демонически попискивая носится вокруг люстры. Это нормально?
В жизни кaждoгo челoвекa бывaют приятные мoменты, кoгдa oн чувствует себя пoлным идиoтoм. Приятнoсть этих мoментoв в пoстижении истины.
Здравствуйте, ghost92, Вы писали:
G>Предлагаю рассмотреть 2 частных случая. G>1) 2 мегашустрика со скоростью 0 (ну если необходимо >0, то можно сделать скорость 1/(4N) этого точно хватит на то чтоб покрыть все лишние проходы) G> жадный алгоритм доказывается тривиально. G>2) 1 мегашустрик со скоростью 0. G> тут надо думать.
Угу. Возникают невозможные переходы. Типа, мегашустрик один сбегал на другой берег лампу принес.
В случае с конечным мегашустриком в таких переходах нет смысла.
G>3) общий случай. G> вычитаем из каждого времени прохода время первого. G> говорим что проходов по мосту как минимум 2*N — 1. (в жадном алгоритме ровно столько) G> мы свели задачу ко 2ому пункту.
Кажется, не свели. 1-й не обязан участвовать в каждом переходе.
В жизни кaждoгo челoвекa бывaют приятные мoменты, кoгдa oн чувствует себя пoлным идиoтoм. Приятнoсть этих мoментoв в пoстижении истины.
Здравствуйте, Кодт, Вы писали:
К>Поскольку двухходовки делать вложенными (на нулевом уровне бегают t[1],t[2]; на первом — t[1],t[3]; и т.д.) К>то автомат у нас уже получается стековый, а число состояний — до N-2.
А вот это уже лишнее.
Действительно,
1,2-> 1<- 1,3-> 1<- Y,Z-> 3<- W,X-> 2<-
можно переставить
1,2-> 1<- Y,Z-> 2<- 1,2-> 1<- W,X-> 2<-
и это будет дешевле.
Здравствуйте, sugarde, Вы писали:
S>Здравствуйте, ghost92, Вы писали:
G>>Предлагаю рассмотреть 2 частных случая. G>>1) 2 мегашустрика со скоростью 0 (ну если необходимо >0, то можно сделать скорость 1/(4N) этого точно хватит на то чтоб покрыть все лишние проходы) G>> жадный алгоритм доказывается тривиально. G>>2) 1 мегашустрик со скоростью 0. G>> тут надо думать. S>Угу. Возникают невозможные переходы. Типа, мегашустрик один сбегал на другой берег лампу принес. S>В случае с конечным мегашустриком в таких переходах нет смысла.
Данный переход и правда невозможен. без лампы за лампой не побежишь
А вообще почему бы ему не побегать туда-сюда несколько раз? Может так быстрее будет.
G>>3) общий случай. G>> вычитаем из каждого времени прохода время первого. G>> говорим что проходов по мосту как минимум 2*N — 1. (в жадном алгоритме ровно столько) G>> мы свели задачу ко 2ому пункту.
S>Кажется, не свели. 1-й не обязан участвовать в каждом переходе.
А вот этого нигде не утверждается. До сих пор остается схема когда 1ый переводит 2ого чтоб затем отправить 2х тормозов, а 2ой вернет лампу.
Общая идея упрощения в том что показать что жадный алгоритм в данных условиях минимален. При таких условиях проще делать какие-либо утверждения а так же модифицировать алгоритм перевода всех на другой берег.
) и вторым вопросом пока думаю.
Перекуём баги на фичи!
