задача дня-17

[falcao]

Не так давно встретилась задача -- скорее всего, она известная. Слишком уж естественная у неё формулировка. В таких случаях кому-то может быть известно "авторское" решение, которое мне было бы интересно узнать

Comments

[kaktus77]

Можно рассуждать с конца.
Осталось два замка и два ключа это однозначно 1 проверка.
Нна предыдущем шаге - 3 замка и 3 ключа. Чтобы найти одну пару ключ-замок нужно 2 попытки. Это тоже однозначно. Меньше быть не может.
Таким образом получаем индукцию - каждый предыдущий шаг дает к+1 попыток.

И получаем по индукции, что это минимальное количество попыток (n(n-1)/2)

[mathreader]

Не обязательно определять сначала точно для какого замка подходит ключ номер 1. Можно сделать некоторое количество тестов (потыкав разные ключи в разные замки), и из этой информации попробовать вычислить соответствие. Поэтому индуктивный переход не работает.

[kaktus77]

Почему же, вполне работает

[mathreader]

"Так или иначе переход от n ключей к n-1 происходит через подбор одной пары."

Здесь вы используете допущение, что нам надо переходить от n ключей к n-1. Нам, вообще говоря, не надо. Надо восстановить всё соответствие, и не обязательно один ключ за одним.

[mathreader]

Не решение пока, а переформулировка. Перенумеруем замки 1..n и ключи 1..n, но соответствие, какой ключ подходит к какому замку, определяется перестановкой:

1 2 ... n

k1 ... kn

Требуется "восстановить" эту перестановку за минимальное число тестов. Каждый тест имеет два исхода: "не подходит" (0), или "подходит" (1). Каждый тест с результатом 0 исключает (n-1)! возможных перестановок, а каждый тест с результатом 1 сужает "фазовое пространство" перестановок в n раз в первый раз, в n-1 раз во второй раз и т.д.

Получается алгоритмическая задача как покрыть "пермутаэдр" всех перестановок минимальным количеством множеств вполне конкретного вида, имеющих мощность (n-1)!, так, чтобы дополнение к ним всем было одно-элементным. При этом если у нас получился тест с результатом 1, то фазовое пространство сжимается, но счетчик использованных множеств все же увеличивается на 1.

Вот картинка для n=4

[falcao]

Мысль о рассмотрении множества перестановок у меня тоже возникала, но процесс этот очень трудно контролируем. По крайней мере, я не знаю, как эту идею можно применить. Мы исключаем на одном шаге перестановки, переводящие i в j после неудачной пробы, но множества этого типа друг с другом как-то сложно пересекаются. И общая картина при этом не ясна.

[rasterjasha]

Можно рассматривать случай самого неблагоприятного "расклада" в поиске. То есть, все пробы, сделанные в процессе подбора, дали отрицательный ответ, а ключи подобрать все же удалось. Можно же? Ведь может так получиться, да? Если так получиться не может, значит, вариант не оптимальный (если из отрицательного ответа в каких-то пробах с необходимостью следует положительный в других, то "положительные" можно было и не делать)? И вот в этом случае можно уже и к индукции обратиться. Найдется ключ, с которым сделана n-1 проба. В противном случае, для каждого ключа осталось по крайней мере два непроверенных кандидата на подходящие замки. Нарисуем граф, вершинами которого будут ключи и замки, а ребрами соединим каждый ключ с его "кандидатами". Важно, что этот граф с циклами (граф двудольный, так что все циклы четной длины). Можно среди циклов выбрать простой, содержащий "правильные" пары. Любой простой цикл четной длины можно разбить на пары двумя способами, то есть, однозначности не случилось. Это, в некотором смысле, база индукции.

Заметим

[falcao]

Тут есть много общего с моим рассуждением, хотя у меня не было индукции, и граф я строил другой. Идея с циклами интересная, но я думаю, что она работает только если цикл содержит все вершины. Но при n=3 такого явления, вроде бы, не наблюдается.

[rasterjasha]

Про граф: Совершенно не обязательно все вершины цикл должен содержать. Достаточно, чтобы для двух ключей нельзя было однозначно определить подходящие замки, чтобы стало понятно, что однозначно их определить невозможно.

Вот конструкция. Берем любую пару ключ K1 и его замок L1. От ключа есть минимум еще одно ребро к замку L2, берем пару этого замка K2. Продолжаем до первого повтора замка Li=Lj. Цикл (LiKi...L{j-1}K{j-1}Li) имеет длину не меньше четырех, простой, и содержит пары ко всем входящим в него замкам и ключам. Если поменяем пары цикла (LmKm) на пары (L{m+1}Km) и еще пару (LiK{j-1}), то результаты всех проб останутся теми же, что и были, так как все ключи и замки из цикла при пробе с ключами и замками вне цикла дадут отрицательный результат, как и раньше. Вне цикла ничего не меняется. Внутри тоже. А пары подбираются теперь другие

[falcao]

По-моему, это не работает. Давайте проверим для случая n=3. Я сначала проверяю ключ 1 для замков 2, 3. Не походят. Я делаю вывод, что K1 открывает L1. Теперь проверяю ключ 2 для замка 3. Тоже не подходит. Получаем однозначную картину: K2 открывает L2, K3 открывает L3.

Теперь посмотрим на граф дополнения. Есть 6 пар, про которые мы не спрашивали. Это (1,1), (2,1), (2,2), (3,1), (3,2), (3,3). В этом графе есть цикл K2 - L1 - K3 - L2 - K2. Но мы по нему не можем построить никакое альтернативное сочетание ключей и замков.

Тут есть принципиальное несоответствие по мощностям. Всего рёбер в полном двудольном графе n^2, и допустим, что мы сделали n(n-1)/2 проб. Осталось n(n+1)/2 рёбер, то есть много. В дереве же рёбер всего 2n-1. Поэтому при n>=3 первая величина превышает вторую, и циклы есть даже при n(n-1)/2 вопросах.

[relf]

Можно рассмотреть игру как выявление "скрытого" полного паросочетания в двудольном графе K_{n,n} (одна доля - ключи, другая - замки), где каждая неудачная попытка удаляет одно ребро из графа.
Кроме того, можно считать, что скрытое паросочетание нефиксированно, а некто играющий против нас может его варьировать, пока есть такая возможность.

Предположим, что мы сделали m неудачных попыток, те. удалили m ребер, и в оставшемся графе без вариантов есть только одно единственное полное паросочетание. Для любой пары ребер (x,y) и (u,v) из этого паросочетания, по крайней мере одно из ребер (x,v), (u,y) должно было быть нами удалено. Поэтому m >= n*(n-1)/2.

[mathreader]

А как получается последнее неравенство?

Если мы стремимся избавиться от возможных подграфов типа K_22, то у меня получается такая оценка: всего подграфов типа K_22 в графе K_nn, есть (n(n-1)/2)^2 = n^2 (n-1)^2 /4. Каждое ребро участвует в (n-1)^2 подграфах типа K_22. Поэтому чтобы их устранить все, нужно удалить как минимум, n^2 (n-1)^2/4 / (n-1)^2 = n^2/4 ребер. А как у вас получилось n(n-1)/2 ?

Но похоже, что отсутствие подграфов типа K_{2,2} не является ни необходимым, ни достаточным для того, чтобы паросочетание было единственным:

Если мы удалим n(n-1)/2 ребер как обрисовал автор журнала (т.е. n-1 от первой вершины, n-2 от второй, и т.д.), в оставшемся графе все равно будет подграф K_22, как нетрудно проверить. Но паросочетание при этом будет единственным!

С другой стороны, возможна ситуация, когда K_22 подграфов нет, но присутствуют два паросочетания (например, подграф в K_33 с ребрами (1,1), (1,2), (2,2),(2,3), (3,3),(3,1) ).

[relf]

Ну так все эти кандидаты на удаление различны для различных пар рёбер из паросояетания, поэтому m не меньше чем количество пар рёбер в паросочетаеии, те. n*(n-1)/2.

[falcao]

Это очень похоже на моё рассуждение, только я самый последний вывод пока не понял.

[unreal_undead]

Грубый программистский подход - за проверку получаем максимум бит информации, всего надо log2(n!), O(n^2) - асимптотику лучше квадратичной не получим, так что ресурсы на оптимизацию первоначального алгоритма выделять не будем )

[falcao]

Логарифм факториала - это оценка снизу, она слишком слабая. Здесь нужно доказать, что оценка n(n-1)/2 точная. С точки зрения программирования тут изначально всё ясно, то есть речь не об улучшении алгоритма.

[unreal_undead]

И ещё никто за это время не ткнул, что я второпях написал лажу - логарифм факториала даёт n log n, как для сортировки. Интересно, можно ли получить просто квадратичную оценку для данной задачи малой кровью.

[falcao]

Так я отметил в комментарии, что это оценка снизу. Она верная сама по себе, но значительно слабее оптимальной. Похожие оценки возникают при сравнении n пакетов по весу.

Здесь точную оценку n(n-1)/2 уже получили. См. ответы relf. Я вскоре сделаю добавление и изложу своё решение. Оно во многом похожее.