10

編集：問題の明確な説明

次の問題を解決する高速なアルゴリズムはありますか? また、この問題の自然数を Z/(2^n Z) に置き換えた拡張版でもあるのでしょうか?(この問題は複雑すぎて、IMO という 1 か所に質問を追加することはできませんでした。)

問題：

{7, 20, 17, 100} のような特定の自然数のセットに対して、必要なアルゴリズムは加算、乗算、べき乗の最短シーケンスを返し、与えられたすべての数値を計算します。シーケンスの各項目は、次のパターンに一致する (正しい) 方程式です。

<number> = <number> <op> <number>

<number> は自然数、<op> は {+、*、^} のいずれかです。

シーケンスでは、<op> の各オペランドは次のうちの 1 つである必要があります。

  • 1
  • equal の左辺にすでに現れている数。

例：

Input: {7, 20, 17, 100}
Output:
2 = 1 + 1
3 = 1 + 2
6 = 2 * 3
7 = 1 + 6
10 = 3 + 7
17 = 7 + 10
20 = 2 * 10
100 = 10 ^ 2

Haskell でバックトラッキング アルゴリズムを書きました。上記のような小さな入力に対しては機能しますが、私の実際のクエリは [0,255] にランダムに分散された ~30 の数字です。実際のクエリの場合、次のコードは私の PC で 2 ~ 10 分かかります。

(実際のコード、 非常に簡単なテスト)

私の現在の（疑似）コード：

-- generate set of sets required to compute n.
-- operater (+) on set is set union.
requiredNumbers 0 = { {} }
requiredNumbers 1 = { {} }
requiredNumbers n =
      { {j, k} | j^k == n, j >= 2, k >= 2 }
    + { {j, k} | j*k == n, j >= 2, k >= 2 }
    + { {j, k} | j+k == n, j >= 1, k >= 1 }

-- remember the smallest set of "computed" number
bestSet := {i | 1 <= i <= largeNumber}

-- backtracking algorithm
-- from: input
-- to:   accumulator of "already computed" number
closure from to =
    if (from is empty)
        if (|bestSet| > |to|)
            bestSet := to
            return
    else if (|from| + |to| >= |bestSet|)
        -- cut branch
        return
    else
        m := min(from)
        from' := deleteMin(from)
        foreach (req in (requiredNumbers m))
            closure (from' + (req - to)) (to + {m}) 

-- recoverEquation is a function converts set of number to set of equation.
-- it can be done easily.
output = recoverEquation (closure input {})

追記:

のような答え

  • 高速なアルゴリズムはありません。なぜなら...
  • ヒューリスティックなアルゴリズムがあり、それは...

も大歓迎です。今、高速で正確なアルゴリズムはないと感じています...

回答＃1はヒューリスティックとして使用できると思います。

4

2 に答える 2

2

私がお勧めするのは、それをある種のグラフ最短経路アルゴリズムに変換することです。

  • 数値ごとに、操作の最短経路を計算 (および保存) します。技術的には 1 ステップで十分です。数値ごとに、演算と 2 つのオペランド (ベキ演算は可換ではないため、左と右)、および重み ( "nodes" )を格納できます。
  • 最初1はゼロの重みで登録します
  • 新しい数を登録するたびに、その数 (すべての足し算、掛け算、べき乗) を使用するすべての計算を、既に登録されているすべての数で生成する必要があります。( 「エッジ」 )
    • 計算のフィルター: 計算の結果が既に登録されている場合は、その数値を取得する簡単な方法があるため、それを保存しないでください。
    • 交換可能な操作は 1 つだけ保存します (1+2=2+1)
    • オーバーフローを引き起こす可能性があるため、電源操作を事前にフィルター処理します
  • このリストを最短の合計パス (辺の重み) に並べる必要があります。重み = (operand1 の重み) + (operand2 の重み) + (1、演算の重み)
    • 見つけなければならない最大数よりも大きいすべての結果の数値を除外できます (たとえば、既に 100 が見つかった場合、20 を超えるものは除外できます) - これを調整して、操作のメンバーも確認できるようにすることができます。 .
  • 目標数の 1 つに到達した場合、目標数の1 つを計算する最短の方法を見つけたので、世代を再起動する必要があります。
    • 目標数の最大値を再計算する
    • 現在見つかっている数字のパスに戻り、重みを 0 に設定します (コストは既に支払われているため、これから与えられます)。
    • ソース オペランドの重みが変更されている可能性があるため、生成リスト内の操作の重みを再計算します (これにより、最後に並べ替えが行われます)。ここでは、いずれかのオペランドが新しい最大値より大きいものを除外できます。
  • すべての数字がヒットしたら、検索は終了です

ターゲット番号ごとに「バックリンク」(操作、左右のオペランド) を使用して式を作成できます。

重要な点は、常に目的の機能に目を光らせていることです。つまり、操作の総数を可能な限り最小限にする必要があります。これを取得するために、特定の数への最短経路を常に計算し、その数 (および途中の他のすべての数) を与えられた数と見なして、検索を残りのターゲットに拡張します。

理論的には、このアルゴリズムは各数値を 1 回だけ処理 (登​​録) します。適切なフィルターを適用すると、不要な分岐がカットされるため、2 回計算されるものはありません (キュー内の要素の重みを除く)。

于 2013-04-23T12:48:30.733 に答える