algorithm - 効率的な網羅的検索アルゴリズムの構築に助けが必要

Question

ボタンは10個です。これらのボタンを正しい順序で押すと、ロックを解除できます (5 回連続で押します)。ボタンを押すたびに、ロック解除チェックがトリガーされます。

例: 「パスワード」は 123456 で、ボタン 0 1 2 3 4 5 6 を押します。6 回目のボタン押しからロックを解除します。

最も効率的な方法ですべての可能な組み合わせを試すアルゴリズムを設計する必要があります (つまり、最小限のボタンを押す必要があります)。

ボタン番号を数字として解釈し、順番に押されたボタンの数を数字位置として解釈し、ロックを解除するために 99999 のすべての組み合わせを試すことができますが、それを行うためのより効率的なアルゴリズムがあると感じています。

この検索を最適化するためにできることはありますか?

Answer 1

ロックに対するブルート フォース攻撃を最適化するには、De Bruijn シーケンスを使用できます。

このシーケンスを使用して、「入力」キーを持たず、入力された最後の n 桁を受け入れる PIN のようなコード ロックに対するブルート フォース攻撃を短縮できます。たとえば、4 桁のコードを持つデジタル ドア ロックには、長さが 10,000 の B(10, 4) ソリューションがあります。したがって、ロックを開くには、最大で 10,000 + 3 = 10,003 (解が循環的であるため) のプレスのみが必要です。すべてのコードを個別に試すと、4 × 10,000 = 40,000 回のプレスが必要になります。