しかし、これについては、そして初心者のために、ゲームStill Lifeの単純な一見パズルを解くために、自分のプログラムをどのように考案したかを説明します。
パズルは5枚のリールとカードスーツで構成されているため、各リールは4つのポジションを取ることができます。
リールの1つをクリックすると、彼は自分自身と他のいくつかを回します。つまり、各ドラムには独自のパターンがあります。 さらに、回転ドラム自体は常に時計回りに回転しますが、残りは必要に応じて回転することも、まったく回転しないこともできます。
パターンは次のとおりです。
1 2 3 4 5 -------------- 1: +1 -1 +1 0 0 2: +1 +1 0 0 -1 3: 0 -1 +1 -1 0 4: -1 0 0 +1 +1 5: 0 0 -1 +1 +1
ここで、+ 1は時計回りの回転、-1は反時計回りの回転、0は回転なしです。
ドラムのステータスが0 1 2 3という数字で指定されている場合、システムの初期状態は0 2 0 3 1になります。
タスク：ドラムの回転シーケンスを見つけて、システムを状態0 0 2 0 0にします。
夕方でした。 私はあまりにも面倒でパズルをいじくり回すことができなかったので、それを解決するプログラムを書くことにしました。 しかし、私は面倒で複雑なプログラムを書くことができなかったため、ブルートフォースを使用することにしました。 明らかに、問題の解は、未知の長さの4進数として表すことができます。 この番号の各桁は、桁カテゴリに対応するステップでのリールの選択を表します。 その後、ブルートフォースは、解決策が見つかるまですべての5進数を列挙することになります。 数値の長さごとに、反復回数は5 nになります。ここで、nは数値の長さです。 最悪の場合、アルゴリズムは5 min（N）を解決します。min（N）は、問題を解決できるステップの最小数nです。 このタスクでは、この値は小さいと想定し、ブルートフォースを開始しました。 私は台所に行き、お茶を用意し、それを飲みました（私とお茶を飲むのは約20分に相当する時間です）-強引な力がn = 10のどこかに掛かっていました。自分でパズルを掘ります。 驚いたことに、私は約10分の組み合わせを選択しました。ブルートフォースはまだn = 10のどこかにかかっていました。
最初は、A *を使用して解をより速く見つけることができると考えましたが、検索空間の無声性のために、有効な先験的推定値を見つけることはそれほど簡単ではないことがわかりました。 たとえば、現在のパターンと最終パターンの不一致の数を先験的推定値とすると、解決すべきステップが1つしかない場合、そのような推定値は常に3になります。 有効なアプリオリ推定値を考え出すことは可能であると確信していますが、それが許容可能であるという証拠は、たぶん自明ではありません。 私はアプリオリ評価を思いつきませんでした（それをhabrasocietyのタスクにしましょう）が、実際にはあまりやりませんでした。同僚の助けを借りて、別の簡単な解決策を見つけたからです。
オフィスネットワークにゾーニングした後、ワークステーションでブルートフォースを開始し、就寝しました。 翌朝、オフィスで、私はCore i5が考えられないほどの反復回数で深さ14のソリューションを見つけたことがわかりました。 職場でこのゴミを処理する時間はなかったので、私は集合的な心をつなぎ、タスクをチームに送ることにしました。 チームは質問で答えました：ドラムを戻すことは可能ですか？ 問題の状況によっては不可能ですが、各ドラムの3回転が1回転に相当することを証明することは難しくありません。 したがって、ソリューションは10進数として表現でき、3つの同じ数字のシーケンスを1に置き換えます。 次数の基準を変更すると、指数が減少します。つまり、反復回数が大幅に減少します。 修正されたアルゴリズムは、Core i5で1秒間に300回の反復処理を行うソリューションを見つけました。
はい、タスクは最終的にコンピューターによってアルゴリズム的に解決されましたが、誰もが可能な速度よりも速くなりましたが、逆説があります：問題を解決しましたが、解決するアルゴリズムを定式化できませんでした。 忘れたわけではありません-ソリューションの前または最中に明確な戦略を考案したり使用したりしなかったことは確かです。つまり、入力することで問題を不合理に解決しました。
ただし、一般的なソリューションスキームは、アルゴリズムとして定式化できます。
TARGET_STATE = [0, 0, 2, 0, 0] # . intuition = Intuition.new # . solution = [] # . current_state = [0, 2, 0, 3, 1] # . while current_state != TARGET_STATE # , . if !solution.empty? && intuition.bad_state?(current_state) current_state = do_step_back(current_state, solution.pop) else # . step = intuition.get_step(current_state) solution.push(step) # , . current_state = do_step(current_state, step) end end
一般に、これは普通の人がパズルを解くための普遍的なアルゴリズムであり、このパズルはコンピューターゲームの一部であるため、プレーヤーからの離散数学の知識を必要とすることはほとんどありません。 この方法でソリューションのために設計されており、さらに、プレーヤーが数千の組み合わせをソートすることを想定していません。
これは私の個人的な経験ですが、この逆説の別の、より鮮明な例があります。
数学には、このような古典的な問題があります-アルゴリズムの可解性の問題です。 あらゆる計算プロセスはチューリングマシンによって実装できるため、問題は次のように定式化できます。問題によっては、それを解決するチューリングマシンを作成することは可能ですか。 アルゴリズムによる解決の不可能性が証明されている多くの問題があり、これらの問題の1つはチューリングマシン自体を停止する問題です。 厳密に言えば、ビットシーケンスが与えられます。これは、特定の任意のチューリングマシンとそれに入力する任意のデータの連結です（マシンとデータの間に一貫して認識可能なセパレータがあると想定されます）。 指定されたマシンがこの入力で停止した場合に1を返し、無限計算になった場合に0を返すチューリングマシンを構築する必要があります。 このようなチューリングマシンを作成することは不可能であることが証明されています。 ただし、実際には、それほど重要ではないがそれほど長くないチューリングマシンと一連の数学を与えると、ほとんどの場合、計算が停止するかどうかが決まります。 同じことは、アルゴリズム的に解決できない他の問題にも当てはまります。 それらの特別な場合は、鉛筆と紙で解決できますが、それぞれの場合で解決策は異なり、それらのすべては1つの普遍的な方法に還元できません。 全体のポイントは、一次仮説の必要性です。
科学は、どんなに正確であっても、仮説によって進歩します。 自然の法則を説明するため、または定理を証明するために、科学者はまず仮説を提唱し、それに対して直観に頼ります。 さらに、科学者は数学的形式を使用してそれを証明または反論し、仮説に反論があれば、新しい仮説を提示します。 本質的に、科学者はパズルを解く際に他の人と同じ方法を使用します。 正確な科学の科学者も同様に形式的な証明方法に精通していますが、優れた科学者は、直感によって生成された仮説がより正確であるという点で通常の科学者と異なります。 現時点では、心理学者も神経生理学者も数学者も質問に答えることはできません：仮説はどのように生じるのですか？この質問に答えることによってのみ、人工知能を作成する可能性（または不可能性）について話すことができます。