0

私は一日中インターネットを閲覧して、指定されたターゲット番号の数値と演算子のリストから方程式を作成する既存のソリューションを探していました。

多くの 24 ゲーム ソルバー、カウントダウン ソルバーなどに出くわしましたが、それらはすべて、答えに括弧を使用できるようにするというコンセプトに基づいて構築されています。

たとえば、ターゲット 42 の場合、数値 1 2 3 4 5 6 を使用すると、解は次のようになります。

6 * 5 = 30
4 * 3 = 12
30 + 12 = 42

アルゴリズムがサブ方程式の結果を記憶し、後でそれを再利用して解 (この場合は 30 と 12) を形成する方法に注意してください。基本的には括弧を使用して解を形成します(6 * 5) + (4 * 3) = 42。

たとえば、左から右に解決される括弧を使用しないソリューションが必要ですが6 - 1 + 5 * 4 + 2 = 42、それを書き出すと、次のようになります。

6 - 1 = 5
5 + 5 = 10
10 * 4 = 40
40 + 2 = 42

約 55 の数値 (2 から 12 の範囲の乱数)、9 つの演算子 (各基本演算子 2 つ + ランダム演算子 1 つ)、およびターゲット値 (0 から 1000 の間の乱数) のリストがあります。目標値が解けるかどうかをチェックするアルゴリズムが必要です (解けない場合は、実際の値にどれだけ近づくことができるか)。各数値と演算子は 1 回しか使用できません。つまり、目標値を得るために使用できる数値は最大 10 個です。

私は自分がやりたいことをするために簡単に調整できるブルートフォースアルゴリズムを見つけました (カウントダウンスタイルの数学数パズルを計算するアルゴリズムを設計する方法)、それは機能しますが、より洗練された「ソリューション」を生成するものを見つけたいと思っていました。 、このページのように: http://incoherency.co.uk/countdown/

4

2 に答える 2

4

あなたが投稿の最後に言及したソルバーを書きましたが、コードがあまり読みにくいことを前もってお詫びします。

この種の問題に対するソルバーのコードは、本質的には深さ優先検索であり、既に機能していることを意味します。

「左から右に解決される括弧を使用しないソリューション」を使用する場合、解決できない入力セットがあることに注意してください。たとえば、ターゲットが 144 の 11,11,11,11,11,11 です。解は ((11/11)+11)*((11/11)+11) です。私のソルバーは、括弧を別の行に分割することで人間が理解しやすくしていますが、左から右に評価するのではなく、効果的に括弧を使用しています。

「括弧を使用する」方法は、操作を入力の 1 つとアキュムレータに適用するのではなく、入力に操作を適用して結果を入力バッグに戻すことです。たとえば、入力バッグが 1,2,3,4,5,6 で、3 と 4 を乗算すると、バッグは 1,2,12,5,6 になります。このように、再帰する場合、そのステップは前のステップの結果を使用できます。これを出力用に準備するのは、操作の履歴を各番号とともにバッグに格納する場合にすぎません。

より「洗練された」ソリューションについてあなたが何を意味しているのかは、私のjavascriptソルバーで使用されているシンプルなヒューリスティックに過ぎないと思います。ソルバーは、検索空間全体の深さ優先検索を実行し、最も少ないステップを使用するソリューションだけでなく、「最適な」ソリューションを選択することによって機能します。

解がターゲットに近い場合、その解は以前の解よりも「優れている」と見なされます (つまり、それを「答え」解として置き換えます) (ソルバー内の任意の状態が候補解であることに注意してください。それは、ほとんどがより離れているということです)。ターゲットからの距離が等しく、ヒューリスティック スコアが低い場合。

ヒューリスティック スコアは、末尾の 0 が削除された「中間値」(つまり、「=」記号の右側の値) の合計です。たとえば、中間値が 1、4、10、150 の場合、ヒューリスティック スコアは 1+4+1+15 です。10 と 150 は、ゼロで終わるため、1 と 15 としてのみカウントされます。これは、人間は 10 で割り切れる数を扱う方が簡単であると判断し、解決策が「より単純」に見えるためです。

「洗練された」と見なすことができるもう1つの部分は、いくつかの行が一緒に結合される方法です. これは単に「5 + 3 = 8」と「8 + 2 = 10」の結果を「5 + 3 + 2 = 10」に結合するだけです。これを行うコードは絶対に恐ろしいものですが、興味がある場合は、すべてhttps://github.com/jes/cntdn/blob/master/js/cntdn.jsのJavascriptにあります。配列形式で格納されているソリューション (各数値がどのように作成されたかに関する情報を含む) では、一連の後処理が行われます。だいたい：

  • DFS から生成された「ソリューション リスト」を (初歩的な、ネストされた配列ベースの) 式ツリーに変換します。これは、複数引数の場合に対処するためです (つまり、「5 + 3 + 2」は 2 つの加算演算ではなく、 3 つの引数を持つ 1 つの加算のみ)
  • 式ツリーをステップの配列に変換します。これには、引数がより一貫して表示されるようにソートすることも含まれます
  • ステップの配列を文字列表現に変換して、ユーザーに表示します。結果が等しくない場合は、結果がターゲット番号からどれだけ離れているかの説明が含まれます

その長さについてお詫び申し上げます。うまくいけば、それのいくつかは役に立ちます。

ジェームズ

編集: カウントダウン ソルバー全般に興味がある場合は、数字の 1 よりもはるかにエレガントな私の文字ソルバーをご覧になることをお勧めします。これはhttps://github.com/jes/cntdn/blob/master/js/cntdn.jsの上位 2 つの関数です。文字列と一致するすべての単語に対して呼び出される関数を使用して、solve_letters() の呼び出しを使用します。このソルバーは、ディクショナリを表すトライ ( https://github.com/jes/cntdn/blob/master/js/mk-js-dictによって生成) をトラバースし、すべてのエンド ノードでコールバックを呼び出すことによって機能します。

于 2013-05-12T23:27:52.817 に答える