Задача про мост

[Sparky]

Добрый день! Есть задача про мост и фонарь. Вот например: В спешке не пропустить начало нового сериала, семья ночью подошла к мосту. Папа может перейти его за 1 минуту, мама — за 2, сынишка — за 5, а бабушка — за 10 минут. У них есть один фонарик, а мост выдерживает только двоих. За сколько минут все они смогут его перейти при лучшей организации своего движения?
Условия для особо придирчивых: Если переходят двое, то они идут с меньшей из скоростей. Идти по мосту без фонарика нельзя. Светить издали нельзя. Носить друг друга на руках нельзя. Бросать фонарик нельзя.

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

[Serge_Bliznykov]

А мне кажется, что алгоритм очевиден: фонарик должен носить самый быстрый. Порядок остальных неважен.
Кстати, длительность перехода очевидно вычисляется по формуле.
Пусть N - количество членов семьи (при этом N>1), и T1 T2 .. Tn - длительность перехода каждого члена семьи, при этом минимальное время обозначим через Tmin
тогда

ВремяПерехода = T1 + T2 + .. Tn  - Tmin +  (n-2)*Tmin

[Sparky]

эм пробовала так. Но если данные такие 1 2 10 10 15 то будет правильнее медленных вести вместе.

[Serge_Bliznykov]

то будет правильнее медленных вести вместе.

не понял. поясните. В какой последовательности и за сколько Вы собираетесь перевести?

по моему алгоритму, фонарик носит обратно тот у кого время прохождения минимально, в данном случае — одна минута.
Общее время прохождения 2 + 10 + 10 + 15 + 3*1 = 40 минут.

[Alex Cones]

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

[Sparky]

правильнее будет увести сначала 1,2. 1 возвращается передет фонарь и идут 10 и 15
затем 2 возвращается и идут 1 и 10 затем 1 возвращается берет 2 и идет и выходит 31

может быть кто-нибудь помнит?

[Vago]

http://archive.ite.journal.informs.o...rimbergHurley/
Если просто нужен алгоритм - п.4. Если нужно разобраться - пп.3-4. Если нужно глубоко покопать, тогда - книги по динамическому программированию и принципу Беллмана в частности.

[Tronix]

Могу забрутфорсить все варианты и написать какой будет оптимальный по времени )))

[Serge_Bliznykov]

Ого. Признаю. Был неправ.

1 2 10 10 15
правильнее будет увести сначала 1,2. 1 возвращается передет фонарь и идут 10 и 15
затем 2 возвращается и идут 1 и 10 затем 1 возвращается берет 2 и идет и выходит 31

Вы правы в алгоритме, но чуть ошиблись в расчётах.
идут 1 и 2 = 2 мин
1 возвращается = 1 мин
10 и 15 идут = 15 минут
2 возвращается = 2 мин
идут 1 и 2 = 2 мин
1 возвращается = 1 мин
1 и 10 идут = 10 минут
итого: 33 минуты

Vago, снимаю шляпу. Спасибо за науку!
не поленюсь запостить перевод финального алгоритма из пункта 4 (взятый по ссылке выше):

Шаг 1 - Взять двух самых быстрых членов группы (скажем, номера 1 и 2) и перевести их на нужный берег. После самый быстрый из них возвращает фонарик на исходный берег.

Шаг 2 - Из остальных членов на исходной стороне, отправить двух самых медленных на нужный берег, второй быстрый член группы (число 2) возвращает фонарик на исходный берег.

Шаг 3 - Вернитесь к шагу 1 и повторяйте процесс, пока кто-нибудь остаётся на исходном берегу.

[Vago]

Самое смешное, что чуть ниже в этом самом п.4 приведен пример, когда этот алгоритм оптимального решения не даёт! Там в ссылках упоминается работа Роте, в ней есть универсальный алгоритм.