задача дня-17

[falcao]

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

Comments

[lj_frank_bot]

Hello!
LiveJournal categorization system detected that your entry belongs to the following categories: Архитектура, Путешествия.
If you think that this choice was wrong please reply this comment. Your feedback will help us improve system.
Frank,
LJ Team

[falcao]

Дорогой Фрэнк!

Научите, пожалуйста, вашего русскоговорящего робота различать такие слова как зАмок и замОк! :)

[xgrbml]

:)))

[greygreengo]

n!

[falcao]

Это общее число разных вариантов, а проб нужно существенно меньше, так как одна проба отсекает сразу много таких вариантов.

[dumart]

Что сразу приходит на ум: n проб для одного ключа, (n-1) для второго и т.д., так что n(n-1)/2 всего.

[falcao]

Для первого ключа достаточно n-1 пробы, потом n-2, и так далее, что даёт 1+2+...+(n-1), то есть получается n(n-1)/2. И задача фактически состоит в том, что надо доказать оптимальность этого значения.

[mns2012]

Это число ребер в клике с n вершинами.

Как я понял задачу, надо показать, что выполняется условие для поиска без отката (backtrack free search). Это фактически достигается при максимально возможном constraint propagation. А оно таково для данной задачи при условии клики. ч.т.д.

[falcao]

См. комментарий ниже.

[f137]

Сумма от n-1 (если перебраны все, кроме одного, последний заведомо подойдет) до 1.

[falcao]

Да, для n(n-1)/2 имеется пример, и суть задачи в получении оценки, то есть надо доказать, что меньшего числа проб в общем случае не хватает.

[akm762]

Стесняюсь спросить: а что-ж тут доказывать, когда "гарантированно" означает, что реализуется наихудший вариант, к-рый уже озвучен?..

[falcao]

Есть план, как гарантированно всё выяснить за n(n-1)/2. Доказывать надо то, что не существует более хитрого плана, позволяющего добиться цели за меньшее число проб. Это обычная для такого рода задач ситуация.

[ptushnik]

Мне кажется, если допустить, что есть способ сопоставить замки и ключи за меньшее, чем n(n-1)/2 число попыток, то можно показать, что после всех проб останутся два замка и два ключа, которые между собой не проверялись.

[falcao]

В принципе, идея правильная.