Здравствуйте, 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 (люди отсортированы по возрастанию времени).
Перекуём баги на фичи!
