Octopuszle, Часть 2а - Задача о точном покрытии
Продолжаю своё рассказ о задаче "Октопаззл".
Убедившись, что представленная в прошлом посте программа перебора не может выдать даже одного решения, не говоря уже о миллионах, я несколько приуныл, но ненадолго. В конце концов, хоть практического опыта программирования у меня не так и много, но должно же моё образование хоть чего-то стоить! Неужели на всех лекциях и курсах я не почерпнул накаких знаний, которые смогут мне помочь? Недолго подумав, и проконсультировавшись с увесистым учебником по алгоритмам, я нашёл весьма перспективное решение. Точнее, не решение, а как раз задачу…
В информатике есть задачи, которые уже давно изучаются и для их решения успели разработать очень хорошие алгоритмы. Если я смогу превратить Октопаззл в одну из таких задач, я смогу воспользоваться этими алгоритмами; глядишь, они справятся лучше. Как гласит американская поговорка, если у тебя в руке молоток, любая проблема кажется гвоздём.
Конечно, почти во всех этих задачах нет гарантии успеха: почти на каждый алгоритм, даже самых известный и эффективный, можно подобрать такую кошмарную проблему, что и за миллион лет не решить. Вполне возможно, что Октопаззл станет таким "гвоздём", что никакой "молоток" не забьёт. Посмотрим. Во всяком случае, подходящую задачу я вспомнил быстро.
Задача о точном покрытии множества - одна из классических, известных задач информатики, которую преподают почти на любом курсе алгоритмов. Не буду приводить точную математическую формулировку; лучше дам несколько примеров.
Пример 1
Мы набираем астронавтов для экспедиции на Марс. Как известно, для успешной экспедиции требуются Командир, Пилот, Навигатор, Механик и Врач.
Нам нужно экономить массу, поэтому многие из наших кандидатов обладают несколькими навыками. Вот они:
Кларк: Командир, Навигатор
Марк: Пилот, Врач
Старк: Пилот, Навигатор, Механик
Парк: Механик
Изя: Командир, Врач
Нам нужно выбрать из этих кандидатов нескольких, чтобы:
Задачу можно изобразить в виде такой таблицы:
Конечно, алгоритму будет совершенно всё равно, как называются навыки или как зовут астронватов. Его интересует лишь матрица условий:
От алгоритма требуется найти несколько строк ("астронавтов"), которые вместе дают ровно одну (не больше - условие 2) единицу в каждом (условие 1) столбце ("навыке"), чтобы этих строк было как можно меньше (условие 3). Вот известное нам решение (Старк и Изя):
А вот два неправильных решения:
Скажите, почему они неправильны?
Как алгоритм, имея такую вот матрицу условий, находит правильное решение, я собираюсь объяснить в следующем посте. На данном этапе я и сам не знал, как работает алгоритм; я только надеялся, что таковой есть, и работает лучше, чем моя программа перебора. Прежде, чем разбираться с алгоритмом, я должен был превратить Октопаззл в задачу на точное покрытие, а для этого надо было познакомиться с задачей поближе.
Приведу ещё два примера, которые помогут понять, что ещё можно решить таким образом.
Выше мы видели чистую, "сферическую в вакууме" форму задачи на точное покрытие: есть какое-то количество требований и много объектов, которые на некоторые из них отвечают. Нас интересует самая маленькая группа этих объектов, которая отвечает на все требования.
Попробуем теперь что-нибудь посложнее.
Пример 2
Как известно каждому, имевшему дело с маленькими детьми, самое главное - занять их. Бездельничающий ребёнок сам себя займёт, да обычно так, что мало не покажется.
В семье краснознаменских четверо детей: Володя, Йося, Никита и Лёня. Сегодня в доме намечается генеральная уборка, и родители хотят всех их заставить помогать.
Убирать нужно всего в четырёх комнатах: гостиной, детской, ванной и кухне.
Некоторые из детей не смогут дотянуться до полок в гостиной (а Володя может, ну лучше не надо!), некоторые вместо того, чтобы убирать в детской, заиграются с игрушками, а малолетнего пиромана Йосю к кухонной плите подпускать нельзя, так что вот комнаты, в которых может убирать каждый мальчик:
Володя: Детская, Кухня
Йося: Гостиная, Детская
Никита: Ванная, Кухня
Лёня: Гостиная, Ванная, Кухня
Как распределить усилия, чтобы заняты были все?
Попробуем составить таблицу, как в прошлый раз:
Решить так, как в прошлом примере, не получится! Во-первых, в единственном решении получаются только Йося и Никита, а мы хотим занять всех детей. Во-вторых, даже если кто-то из детей может убирать в двух-трёх комнатах, он же не обязан убирать во всех. Чтобы сделать из этого примера задачу на точное покрытие придётся сделать пару финтов ушами.
Во-первых, если нам надо, чтобы все работали, то нужно добавить это в условия таблицы:
Теперь, чтобы в итоге во всех столбцах были единицы, нужно будет занять всех детей. А теперь, чтобы, скажем, Йося не был обязан убирать в детской и на кухне (и наоборот, чтобы в детской не убирали Володя и Йося), просто сделаем для каждого мальчика отдельную строку для каждой комнаты, где он может убирать:
Теперь эту таблицу уже можно решать, как обычную задачу на точное покрытие. Есть несколько возможных решений (сколько?), вот одно из них:
Володя убирает в детской, Йося - в гостиной, Никита - в ванной и Лёня - на кухне.
Конечно, эту задачу наверняка можно было решить и по-другому, без этих извращений со строками. Я только хотел показать, что через точное покрытие можно решить и такую задачу. Кто знает… если бы в задаче было не четверо детей (и столько же комнат), а тысячи работников крупной компании и тысячи же заводов, хитроумный алгоритм нахождения точного покрытия (мы до сих пор надеемся, что таковой есть!) мог бы работать быстрее "простого" решения, и затраты бы оправдались. В информатике часто приходится проделывать такие трюки.
Последний пример, который ближе всего подойдёт к моей попытке решить Октопаззл:
Пример 3
У нас есть вот такая "доска" 1х6:
Ещё у нас есть две "плитки" 1х2 и 1х4:
Мы должны обеими плитками покрыть доску полностью.
Нет-нет, я понимаю, что задача дурацкая. Но всё же - а если бы доска была побольше, а плитки были какой-нибудь заковыристой формы? Нет, очень даже стоит попробовать решить и такую задачу через точное покрытие…
Пронумеруем поля доски:
Красная плитка может покрывать поля (1,2), (2,3), (3,4), (4,5), (5,6). Синяя покрывает (1,2,3,4), (2,3,4,5) или (3,4,5,6). Составим матрицу условий:
Оба правильных решения найдутся лег… ой! Есть ещё одно решение, неправильное, которое алгоритм сможет найти:
Доску же можно замостить тремя красными плитками, не привлекая синюю*! Как в предыдущем примере, добавим в матрицу столбцы для каждой плитки, чтобы в решении использовались обе:
Теперь в решении обязаны быть обе плитки. Оба решения найдутся с лёгкостью:
* На самом деле, решение с тремя красными плитками всё равно не будет найдено, потому что оно не минимальное (три плитки против двух). Но мы всё-таки уже научимся предохраняться от таких неправильных решений, хотя бы для уверенности.
Итого, к задаче на точное покрытие можно привести много проблем, где требуется занять что-то несколькими чем-то, каждое из которых может занимать какие-то части целого. На практике с помощью этой задачи составляют расписания, распределяют грузы и задания и даже решают судоку.
Признаться, именно вспомнив про судоку, я и решил попробовать превратить Октопаззл в задачу на точное покрытие. О том, как я это сделал - в слудеющей части.
Продолжение следует…
Убедившись, что представленная в прошлом посте программа перебора не может выдать даже одного решения, не говоря уже о миллионах, я несколько приуныл, но ненадолго. В конце концов, хоть практического опыта программирования у меня не так и много, но должно же моё образование хоть чего-то стоить! Неужели на всех лекциях и курсах я не почерпнул накаких знаний, которые смогут мне помочь? Недолго подумав, и проконсультировавшись с увесистым учебником по алгоритмам, я нашёл весьма перспективное решение. Точнее, не решение, а как раз задачу…
В информатике есть задачи, которые уже давно изучаются и для их решения успели разработать очень хорошие алгоритмы. Если я смогу превратить Октопаззл в одну из таких задач, я смогу воспользоваться этими алгоритмами; глядишь, они справятся лучше. Как гласит американская поговорка, если у тебя в руке молоток, любая проблема кажется гвоздём.
Конечно, почти во всех этих задачах нет гарантии успеха: почти на каждый алгоритм, даже самых известный и эффективный, можно подобрать такую кошмарную проблему, что и за миллион лет не решить. Вполне возможно, что Октопаззл станет таким "гвоздём", что никакой "молоток" не забьёт. Посмотрим. Во всяком случае, подходящую задачу я вспомнил быстро.
Задача о точном покрытии множества - одна из классических, известных задач информатики, которую преподают почти на любом курсе алгоритмов. Не буду приводить точную математическую формулировку; лучше дам несколько примеров.
Пример 1
Мы набираем астронавтов для экспедиции на Марс. Как известно, для успешной экспедиции требуются Командир, Пилот, Навигатор, Механик и Врач.
Нам нужно экономить массу, поэтому многие из наших кандидатов обладают несколькими навыками. Вот они:
Кларк: Командир, Навигатор
Марк: Пилот, Врач
Старк: Пилот, Навигатор, Механик
Парк: Механик
Изя: Командир, Врач
Нам нужно выбрать из этих кандидатов нескольких, чтобы:
- Они имели все пять навыков
- Ни один из навыков не дублировался (зачем тратить воздух на двоих пилотов?)
- Решение было минимальным
Задачу можно изобразить в виде такой таблицы:
Конечно, алгоритму будет совершенно всё равно, как называются навыки или как зовут астронватов. Его интересует лишь матрица условий:
От алгоритма требуется найти несколько строк ("астронавтов"), которые вместе дают ровно одну (не больше - условие 2) единицу в каждом (условие 1) столбце ("навыке"), чтобы этих строк было как можно меньше (условие 3). Вот известное нам решение (Старк и Изя):
А вот два неправильных решения:
Скажите, почему они неправильны?
Как алгоритм, имея такую вот матрицу условий, находит правильное решение, я собираюсь объяснить в следующем посте. На данном этапе я и сам не знал, как работает алгоритм; я только надеялся, что таковой есть, и работает лучше, чем моя программа перебора. Прежде, чем разбираться с алгоритмом, я должен был превратить Октопаззл в задачу на точное покрытие, а для этого надо было познакомиться с задачей поближе.
Приведу ещё два примера, которые помогут понять, что ещё можно решить таким образом.
Выше мы видели чистую, "сферическую в вакууме" форму задачи на точное покрытие: есть какое-то количество требований и много объектов, которые на некоторые из них отвечают. Нас интересует самая маленькая группа этих объектов, которая отвечает на все требования.
Попробуем теперь что-нибудь посложнее.
Пример 2
Как известно каждому, имевшему дело с маленькими детьми, самое главное - занять их. Бездельничающий ребёнок сам себя займёт, да обычно так, что мало не покажется.
В семье краснознаменских четверо детей: Володя, Йося, Никита и Лёня. Сегодня в доме намечается генеральная уборка, и родители хотят всех их заставить помогать.
Убирать нужно всего в четырёх комнатах: гостиной, детской, ванной и кухне.
Некоторые из детей не смогут дотянуться до полок в гостиной (а Володя может, ну лучше не надо!), некоторые вместо того, чтобы убирать в детской, заиграются с игрушками, а малолетнего пиромана Йосю к кухонной плите подпускать нельзя, так что вот комнаты, в которых может убирать каждый мальчик:
Володя: Детская, Кухня
Йося: Гостиная, Детская
Никита: Ванная, Кухня
Лёня: Гостиная, Ванная, Кухня
Как распределить усилия, чтобы заняты были все?
Попробуем составить таблицу, как в прошлый раз:
Решить так, как в прошлом примере, не получится! Во-первых, в единственном решении получаются только Йося и Никита, а мы хотим занять всех детей. Во-вторых, даже если кто-то из детей может убирать в двух-трёх комнатах, он же не обязан убирать во всех. Чтобы сделать из этого примера задачу на точное покрытие придётся сделать пару финтов ушами.
Во-первых, если нам надо, чтобы все работали, то нужно добавить это в условия таблицы:
Теперь, чтобы в итоге во всех столбцах были единицы, нужно будет занять всех детей. А теперь, чтобы, скажем, Йося не был обязан убирать в детской и на кухне (и наоборот, чтобы в детской не убирали Володя и Йося), просто сделаем для каждого мальчика отдельную строку для каждой комнаты, где он может убирать:
Теперь эту таблицу уже можно решать, как обычную задачу на точное покрытие. Есть несколько возможных решений (сколько?), вот одно из них:
Володя убирает в детской, Йося - в гостиной, Никита - в ванной и Лёня - на кухне.
Конечно, эту задачу наверняка можно было решить и по-другому, без этих извращений со строками. Я только хотел показать, что через точное покрытие можно решить и такую задачу. Кто знает… если бы в задаче было не четверо детей (и столько же комнат), а тысячи работников крупной компании и тысячи же заводов, хитроумный алгоритм нахождения точного покрытия (мы до сих пор надеемся, что таковой есть!) мог бы работать быстрее "простого" решения, и затраты бы оправдались. В информатике часто приходится проделывать такие трюки.
Последний пример, который ближе всего подойдёт к моей попытке решить Октопаззл:
Пример 3
У нас есть вот такая "доска" 1х6:
Ещё у нас есть две "плитки" 1х2 и 1х4:
Мы должны обеими плитками покрыть доску полностью.
Нет-нет, я понимаю, что задача дурацкая. Но всё же - а если бы доска была побольше, а плитки были какой-нибудь заковыристой формы? Нет, очень даже стоит попробовать решить и такую задачу через точное покрытие…
Пронумеруем поля доски:
Красная плитка может покрывать поля (1,2), (2,3), (3,4), (4,5), (5,6). Синяя покрывает (1,2,3,4), (2,3,4,5) или (3,4,5,6). Составим матрицу условий:
Оба правильных решения найдутся лег… ой! Есть ещё одно решение, неправильное, которое алгоритм сможет найти:
Доску же можно замостить тремя красными плитками, не привлекая синюю*! Как в предыдущем примере, добавим в матрицу столбцы для каждой плитки, чтобы в решении использовались обе:
Теперь в решении обязаны быть обе плитки. Оба решения найдутся с лёгкостью:
* На самом деле, решение с тремя красными плитками всё равно не будет найдено, потому что оно не минимальное (три плитки против двух). Но мы всё-таки уже научимся предохраняться от таких неправильных решений, хотя бы для уверенности.
Итого, к задаче на точное покрытие можно привести много проблем, где требуется занять что-то несколькими чем-то, каждое из которых может занимать какие-то части целого. На практике с помощью этой задачи составляют расписания, распределяют грузы и задания и даже решают судоку.
Признаться, именно вспомнив про судоку, я и решил попробовать превратить Октопаззл в задачу на точное покрытие. О том, как я это сделал - в слудеющей части.
Продолжение следует…