Ніч. Четверо мають перейти вузький хиткий міст. Ліхтарик один, а без нього на міст не ступиш. Міст витримує щонайбільше двох. Один проходить міст за 1 хвилину, другий за 2, третій за 5, четвертий за 10. Пара йде разом із ліхтариком у темпі повільнішого. Кинути ліхтарик через річку не можна, хтось має принести його назад. За скільки хвилин усі четверо можуть опинитися на тому боці?
Здається, що найшвидший має провести кожного і щоразу повертатися з ліхтариком: 10 + 1 + 5 + 1 + 2 = 19. Але якщо двоє найповільніших підуть разом, п'ять хвилин одного сховаються в десяти хвилинах іншого. Ціна цього: зайвий перехід пари 1 і 2 (2 хвилини) і повернення двійки замість одиниці (ще 1 хвилина). 19 − 5 + 2 + 1 = 17.
Цю головоломку дають на співбесідах, щоб подивитися, як людина шукає найкращий план, а не перший, що спав на думку. За нею стоїть пошук найкоротшого шляху в графі станів і рекурсія, яку 2002 року довів Ґюнтер Роте.
Вузький і хиткий, витримує щонайбільше двох людей одночасно. Іншого шляху на той бік немає.
Ліхтарик один. Без нього на міст не ступиш, тож кожен перехід, і туди, і назад, хтось робить із ліхтариком у руці. Кинути його через річку не можна.
Четверо проходять міст за 1, 2, 5 і 10 хвилин. Двоє йдуть разом у темпі повільнішого: пара 2 і 10 витрачає 10 хвилин.
Яка найменша кількість хвилин, за яку всі четверо опиняться на тому боці?
«Найшвидший проводить кожного: 10 + 1 + 5 + 1 + 2 = 19 хвилин»
Логіка зрозуміла: ліхтарик щоразу повертає той, хто ходить найшвидше, тож кожне повернення коштує лише хвилину. Але так 5 і 10 ходять окремо і разом займають міст на 15 хвилин. Якщо пустити їх разом, вийде 17.
1, 2, 5 і 10 хвилин, міст на двох, один ліхтарик. Зафіксуйте найменший час, який, на вашу думку, можливий.
Тут з'явиться розбір вашої відповіді.
Важко вирішити? Відкривайте підказки по одній: спочатку легка, далі сильніша.
План «найшвидший проводить кожного» — не єдиний. Подивіться, скільки хвилин забирають 5 і 10, коли йдуть окремо.
Пустіть 5 і 10 разом, тоді 5 хвилин сховаються всередині 10. Але на тому боці вже має чекати хтось швидкий, щоб повернути ліхтарик.
Почніть так: 1 і 2 йдуть туди, 1 повертається. Хто має піти наступним, хто принесе ліхтарик назад і хто лишиться? Складіть хвилини.
Клацніть одного чи двох людей на боці з ліхтариком і натисніть «Перейти». Годинник рахує хвилини. Потім оберіть правило в правій картці: сторінка переглядає всі набори часів і шукає такий, де правило програє найкращому розкладу.
Кожна людина проходить міст за випадкову цілу кількість хвилин від 1 до 20, усі значення однаково ймовірні. Для кожного набору сторінка шукає найкращий розклад повним перебором станів (алгоритм Дейкстри) і порівнює з двома простими правилами. Стовпці показують точні частки, пораховані по всіх можливих наборах, точки показують частки в симуляції.
Правило вважаємо найкращим, якщо воно дає оптимальний час. Коли обидва правила дають однаковий оптимальний час, набір рахується для обох, тому частки можуть у сумі перевищувати 100%.
Уся різниця в тому, хто стоїть у парі з повільними і хто несе ліхтарик назад. Ось п'ять способів це побачити.
Пара йде в темпі повільнішого, тож той, хто йде з 10-хвилинним, «їде безкоштовно», якщо він сам повільний. Ставити поруч із десяткою одиницю марно: її швидкість пропадає. Найдорожче, що є в задачі, це хвилини найповільніших, і їх вигідно ховати одну в одній.
Туди за раз ідуть щонайбільше двоє, назад хтось один несе ліхтарик. Кожна пара «туди і назад» переправляє на той бік лише одну людину, тож для чотирьох потрібно щонайменше три переходи туди і два назад. Повернення неминучі, питання лише в тому, хто їх робить. Розклад на 17 хвилин платить за повернення на хвилину більше, але дорога туди коштує 2 + 10 + 2 = 14 хвилин замість 10 + 5 + 2 = 17. Разом 14 + 3 = 17 проти 17 + 2 = 19.
Різниця між двома планами для чотирьох людей дорівнює t₁ + t₃ − 2t₂. Спільний перехід двох повільних вигідний, коли два «човники», найшвидший і другий найшвидший, разом швидші, ніж найшвидший і третій.
Розклад із п'яти переходів: пара туди (6 варіантів), один назад (2), пара туди (3), один назад (3), пара туди (1). Разом 6 · 2 · 3 · 3 · 1 = 108. Сторінка щойно перебрала їх усі: найменший час 17 хвилин, і його дають лише два розклади, які відрізняються тим, хто повертається першим, 1 чи 2. Довші розклади, з сімома й більше переходами, повний перебір у раунді 3 теж охоплює: жоден не швидший за 17.
d(v) = minu → v ( d(u) + w(u, v) )
Стан переправи задає, хто на якому березі і де ліхтарик: 2⁴ · 2 = 32 варіанти, із них досяжні 30. Перехід із ціною w з'єднує два стани, і задача стає пошуком найкоротшого шляху в графі. Алгоритм Дейкстри розкриває стани в порядку зростання відстані d і гарантує оптимум. Правило «найшвидший проводить кожного» жадібне: воно робить кожне повернення найдешевшим, але не дивиться, скільки коштуватиме дорога туди. Найкоротший шлях іноді починається з дорожчого кроку.
Відсортуйте часи. Двох найповільніших переводять одним із двох способів, і задача зменшується на дві людини.
Перший доданок у min: двоє найшвидших працюють човниками, а двоє найповільніших ідуть разом. Другий: найшвидший проводить кожного з двох.
Для 1, 2, 5, 10: спершу переводимо 5 і 10, потім лишаються 1 і 2.
Ґюнтер Роте 2002 року довів, що ця рекурсія завжди дає оптимум, хоч скільки людей. На кожному кроці вибір робиться окремо: для шести людей буває, що двох найповільніших вигідно перевести разом, а наступних двох краще провести по одному. Сторінка звірила рекурсію з повним перебором у раунді 3.
Задача про міст вчить простої речі: дорогі елементи вигідно групувати разом. У математиці це рекурсія для будь-якої кількості людей. У логіці це різниця між локально розумним кроком і найкращим планом. На практиці той самий прийом скорочує час обчислень.
Математика
Для мосту на двох рекурсія Роте працює для будь-якої кількості людей: відсортуйте часи і щоразу переводьте двох найповільніших дешевшим зі способів. Таблиця ліворуч показує кожен крок. Рахунок займає лічені операції навіть для тисячі людей.
Якщо міст тримає трьох, простої формули в цій задачі вже не видно, і сторінка шукає найкоротший шлях у графі станів. Для 1, 2, 5, 10 виходить 13 хвилин: 1, 5 і 10 ідуть разом (10), 1 повертається (1), 1 і 2 переходять (2). Ідея та сама: троє найповільніших ховають свої хвилини в одному переході.
Логіка
Спершу переводимо двох по 20 хвилин, потім 4 і 5, наприкінці 1 і 3. Для кожної пари оберіть спосіб.
Кожне з двох правил розумне на своєму кроці. «Найшвидший проводить» мінімізує повернення. «Двоє найповільніших разом» мінімізує дорогу туди. Але найкращий план тут змішаний: двох по 20 хвилин краще перевести разом, а 4 і 5 провести по одному. Для шести людей із часами від 1 до 20 так буває приблизно в 29% наборів (раунд 3).
Загальний урок: оптимізуйте вузьке місце. Найдорожчі хвилини в цій задачі належать найповільнішим, і план має будуватися навколо них, а не навколо того, хто зручно бігає туди й назад. Той самий урок у задачі про отруєне вино: важить не кожен окремий крок, а вся схема.
Практика
Вісім задач по 1, 2, 3, 4, 10, 11, 12, 13 хвилин. Машина запускає їх партіями, і партія триває стільки, скільки найдовша задача в ній. Партії йдуть одна за одною.
Якщо партія триває стільки, скільки її найдовша задача, ставити коротку задачу поруч із довгою означає витратити місце: коротка все одно чекатиме. Відсортуйте задачі й розбийте на партії підряд, від найдовших: для партій по 2 це дає 13 + 11 + 4 + 2 = 30 хвилин замість 46, коли кожну швидку ставлять до повільної. Перебір усіх розбиттів підтверджує, що 30 найкраще.
Так роблять під час навчання нейромереж: речення різної довжини доповнюють до найдовшого в партії, тому їх групують за довжиною, щоб короткі не чекали на довгі. Те саме в CI: довгі тести ставлять в один прогін, а не розкидають по всіх. У мосту є ще одна деталь, якої тут немає: ліхтарик треба повертати, і тому двоє швидких стають човниками.
Головоломка трапляється щонайменше 1981 року в книжці Сола Левмора й Елізабет Кук «Super Strategies for Puzzles and Games». Там четверо чоловіків у ворожому тилу переходять міст над ущелиною з ліхтарем: 5, 10, 20 і 25 хвилин, на все година.
Найвідоміша версія зі співбесід: четверо учасників U2 (1, 2, 5 і 10 хвилин) мають перейти міст, поки він не завалився через 17 хвилин. Вільям Паундстоун описав її 2003 року в книжці «How Would You Move Mount Fuji?» про головоломки на співбесідах у Microsoft. А історія, ніби Microsoft дає її кожному кандидатові, походить із ланцюгового листа 1998 року.
Ґюнтер Роте з Вільного університету Берліна опублікував статтю «Crossing the bridge at night» у Bulletin of the EATCS (том 78, жовтень 2002) і довів, що рекурсія з двома способами переводити найповільніших завжди оптимальна. Її раніше припускав Торстен Зільке, а кількома місяцями раніше в тому самому бюлетені вийшла стаття Крістіана й Олени Калуде з хибною загальною відповіддю.
Для чотирьох людей є рівно 108 розкладів без зайвих переходів. 17 хвилин дають лише 2 з них, 19 хвилин дають 6, а найгірший триває 50 хвилин.
Едсгер Дейкстра опублікував свій алгоритм пошуку найкоротшого шляху 1959 року в статті «A note on two problems in connexion with graphs» у журналі Numerische Mathematik. Саме він перебирає стани переправи в раунді 3.
Роланд Бекгауз 2008 року розібрав загальний випадок, коли міст тримає C людей, у статті «The capacity-C torch problem» на конференції Mathematics of Program Construction (Марсель).
Поділіться своїм поясненням, запереченням чи варіантом задачі. Для коментаря потрібен акаунт GitHub.
Я поступово додаю нові задачі, інші способи їх пояснити й розбори дискусій. Залиште email, і я напишу, коли з'явиться щось нове. Без спаму, відписатися можна в один клік.
Форма підписки з'явиться тут найближчим часом.