ダイクストラ パールは、1970 年代初頭に Edsger Dijkstra が『Communications of the ACM』で述べた、プログラミングにおけるバックトラッキングの問題です。
この問題への関心は、 GO TO命令なしでプログラムするのが難しいという事実から来ていますが、そのような命令を使用してプログラムすると、間違いを犯し、プログラムが非常に難しくなる可能性が高くなります。修正するために。
また、単純な数学的発展も生まれました。
問題
3 色のビーズを通す糸を考えてみましょう。ダイクストラは、オランダ国旗の色である青、白、赤を提案していますが、より中立的な定式化では、それらを 0、1、2 と呼ぶことができます。
制約が 1 つだけ存在します。それは、ワイヤ上に 2 つの同一の隣接シーケンスがあってはなりません。
質問:
- ビーズを何個つなげることができますか？
- 可能な限り最長のシーケンスを生成するアルゴリズム、または必要に応じて無期限に継続できるシーケンスを作成します。
分析
もっともらしさ
まず、少し考えることから始まります。各ビーズの選択は 3 つのうちの 1 つです。構造の自由度は3 N程度です。 N 3/2では制約がむしろ減少するように見えます。これにより、特定の点を超えると、無限に継続するための十分な操作余地が得られると言えます。しかし、印象はデモンストレーションではありません。
簡単な慣れ
次に、手動による小さなシミュレーションが含まれています。
- 0が正しいです
- 00は間違いです
- 01が正解です
- 010が正しいです
- 0100 と 0101 は正しくありません
- 0102が正しいです
- …
- 0102010が正しいです
次に、追加の真珠を配置する際に問題が発生します。
- 01020100は適切ではありません ( 0の繰り返し)
- 01020101は適切ではありません ( 01の繰り返し)
- 01020102も適切ではありません ( 0102の繰り返し)
これは検索された最長のチェーンですか?いいえ。私たちは、これまでの（任意の）選択の 1 つをいつでも疑問視して、状況のブロックが解除されないかどうかを確認できます。そして実際:
010201 2 はブロックを解除し、続行できるようにします。この手順はバックトラッキングと呼ばれます。
あなたがしなければならないのはプログラムだけです。
プログラミング
しかし、不注意なプログラマは注意してください。プログラムが同じ位置からの連続したバックトラッキングが何度も発生する可能性を予測していない場合、深刻な問題に直面することになります。 GO TO命令も使用すると、プログラムの各時点で有効な不変式を簡単に予測できなくなる問題が、すぐに解決できなくなります。
数学的手法
このような任意の長さのチェーンを構築できます。射を考えると