9

可能重复：
在构建有效的穷举搜索算法方面需要帮助

想象一下，您必须通过在键盘上输入正确的 4 位密码来打开一扇上锁的门。每次按键后，锁都会评估输入的最后 4 位数字的顺序，即通过输入123456您已经评估了 3 个代码1234：2345和3456。

  • 10^4评估所有不同组合的最短按键序列是什么？
  • 是否有一种方法可以轻松地穿越整个空间以供人类遵循？

我不时思考这个问题，因为我的一个朋友不得不蛮力这样锁，冬天不必在户外过夜。

我微弱的尝试将我的头缠绕在它周围

使用长度L=4数字的代码和大小数字的“字母表”，D=10最佳序列的长度不能短于D^L + L - 1. 在比[L,D] = [4,10]我更小的模拟中，通过半随机搜索空间获得了最佳结果。但是，我不知道是否存在任意[L,D]对的解决方案，并且如果我不得不使用它，我将无法记住该解决方案。

迄今为止的经验教训

当计划在另一个城镇的朋友家过夜时，如果那个人要出去参加聚会并且听不到她的手机，请确保不要在凌晨 1 点到达。

4

2 回答 2

5

我认为您想要一个http://en.wikipedia.org/wiki/De_Bruijn_sequence -“给定字母 A 的循环序列，大小为 k，其中 A 中长度为 n 的每个可能子序列都恰好出现一次连续字符序列。”

于 2012-11-05T18:03:05.663 回答
3

Evgeny 提供的链接应该可以回答您的两个问题。这个答案有点离题，但是您要求为人类提供解决方案。

在现实世界中，您可能应该更多地依赖社会工程或启发式算法，然后再依赖数学。我举一个现实生活的案例：

我去参观一个公寓，我发现我的手机没电了。现在联系进行访问的人的方式。我正要回去的时候看到门用的是键盘0 - 9和A B. 我做了几个假设：

  1. 代码长度为 5 位。长度非常标准，具体取决于您所在的地区。我基于我之前访问过的建筑物（合法：D）做出了这个假设。
  2. 代码以数字开头，然后是A或B（基于我自己的建筑）。
  3. 键盘不是全新的。结论，代码中使用的数字有点损坏。我确定哪些数字不在代码中，以及代码中四个数字中的三个（根据我之前的假设）
  4. 根据损坏的按键数量，我假设代码不包含重复的按键（7 个已损坏，很明显A已使用，B未使用）

最后，我肯定有 3 个号码在代码中，最后一个号码有 2 个候选人，我确信A在最后。与其他人相比，On key 只是轻微损坏。

我只需要从看起来更受损的候选人开始列举排列，这给了我4! + 4! = 48尝试。相信我，在第 5 次尝试时，门被打开了。如果我能给我的 2 美分，旧put a key and open the door的仍然是限制进入建筑物的最可靠的方法。

于 2012-11-05T15:36:12.293 回答