задача дня-17

[falcao]

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

Comments

[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]

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

[mns2012]

Это то же самое. Худший случай, чем n * (n - 1) /2, - это backtracking search, когда нужно было бы возвращаться к предыдущему выбору и менять дверь для фиксированного замка (a variable-value assignment), а это исключается по формулировке задачи (фиксированный ключ подходит только к одной из дверей). В constraint programming это называется all different constraint. Это именно n-клика. Товарищ akm762 кмк прав.

[falcao]

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