4

プロジェクト オイラー数219を実行しようとしていますが、それを把握できていません。プロジェクトオイラーによると、Pythonを使用しようとしていますが、1分以内に実行できるはずです! これは、Pythonでは遅すぎるため、個々のビット文字列を計算することをおそらく望んでいないと考えるようになります.sub O(n)アルゴリズムが必要です。

新しいビット文字列をすばやく選択し、それらをグループで考慮することさえできるように、ビット文字列の可能なプレフィックスを格納する再帰的なソリューションを見てきました。これは、10 を少し超える値までのブルート フォース値でのみ機能します。

cost(1) = 1
cost(2) = 5
cost(3) = 11
cost(4) = 18
cost(5) = 26
cost(6) = 35
cost(7) = 44
cost(8) = 54
cost(9) = 64
cost(10)= 74
cost(11)= 85
cost(12)= 96

これを過ぎると、問題を軽減する方法を理解するのに苦労しています。次のようなパターンを作成することは常に可能です。

1
01
001
0001
00001
00000

ただし、ビット文字列が 7 つを超える場合は最適ではありません。私が考慮すべきことについて誰かが私を導くことができますか？

4

6 に答える 6

9

ブルートフォースは正しい方法ではありません。これは、あることを知っていればそれほど難しくない問題の 1 つですが、そのことを聞いたことがない場合は事実上不可能です。それがハフマン木です。

[編集] さらに調べてみると、文字列のコスト関数は 4*(1 の数) + (0 の数) であるため、特定の頻度の N ノードでハフマン ツリーを完全に構築できないようです。コスト関数が文字列の長さ (またはその倍数) である場合、ハフマン木を作成できます。

プレフィックスのないコード セットは、ハフマンのようなバイナリ ツリーとして表すことができます。この場合、各ノードには 0 または 2 つの子があり、リーフ ノードはコードを表します。N 個のノードを持つツリーが与えられた場合、次のように N+1 個のノードを持つツリーを構築できます。

  1. リーフ ノードのコストが 4*(ルートからリーフへのパス上の 1 の数) + (パス上の 0 の数) である、最小のコストを持つリーフ ノードを選択します。
    • そのノードに 2 つの子を追加します

したがって、ノードのコードが以前に xxxx だった場合、そのコードをコード セットから削除し (葉ではないため)、2 つのコード xxxx0 と xxxx1 を追加します。コード セットの総コストは、

`cost(xxxx0) + cost(xxxx1) - cost(xxxx) = cost(0) + cost(1) + cost(xxxx) = 5 + cost(xxxx)

したがって、mincost(N+1) <= mincost(N) + 5 + cost(N の最適解における最も安価なコード) となります。私の理論では、その不等式は等式であるはずですが、まだ証明できていません。力ずくでリストしたすべての値について、このステートメントは実際には等価です。

それが等しい場合、問題を解決するには、次のようにします。

  1. 総コストゼロで空のコードセットから始める
    • 1 から 10 9まで繰り返し、次のようにします。
      1. コードセットで最も安いコードを見つける
    • 0 と 1 を追加して、そのコードを 2 つに分割します
    • そのコードのコスト + 5 を総コストに追加します

プライオリティ キューを使用すると、O(N log N) 時間でこれを実行できるはずです。上限が 10 9であることを考えると、これは実行可能である場合とそうでない場合があります。

于 2008-12-06T20:16:36.287 に答える
1

Adam: たくさんのリンクをありがとう -とても有望ですね! ウィキペディアの記事を読んだ後でよくわからないのは、係数 4 がどのように考慮されるかです。Project Eulerの問題をアルゴリズムに「マッピング」するのに苦労しています。アルファベットは 10^9 アイテムの長さである必要がありますが、重みはどのくらいになるでしょうか?

私を悩ませているもう1つのことは、上で述べたように、ハフマンコーディングはせいぜいO(n)が確かに遅すぎるということです...

マティアスト: あなたの再発はうまくいかないと思います (または私はそれを誤解しています!)。私の解釈は次のとおりです。

def cost(n):
    if n == 1: return 1

    m = None
    for k in range(1, n):
        v = cost(k)+cost(n-k)+k+4*(n-k)
        if not m or v < m: m = v

    return m

print(cost(6))

返される値は、35 になるはずのときに 41 です。それでも、私の値が正しい場合、ATT の Integer Sequences Encyclopedia で違いを見つけることができません。

于 2008-12-06T22:59:15.273 に答える
1

N = 10**9

t = [0]

for c in xrange(N) : m = min(t) t.remove(m) t.append(m+1) t.append(m+4) print sum(t), t

于 2009-01-05T15:29:32.653 に答える
0

私がそれをどのように解決したかは、n = 1000までのCost（n）を計算し、そこからどのように進行するかを推測することでした。連続する値の違いを見て、整数列の百科事典（およ​​びいくつかの想像力）を使用すると、ルールを推測できます。

繰り返しを使用して、一種の動的計画法で小さな（<= 1000）例を計算できますCost(n) = min {Cost(k)+Cost(n-k)+k+4*(n-k) | 0 < k < n}。

于 2008-12-06T20:51:08.637 に答える
0

O[n*log(n)] は遅すぎるわけではありませんが、メモリの複雑さはおおよそ O(n) です。ただし、上記で提案されたアルゴリズムは、O(n) 時間の複雑さと低いメモリの複雑さにさらに減らすことができます。これを行うには、x[a] = コスト a の数値の数である配列 x を使用できます。

行われた仮定は 10^9 に対して正しい結果を与えるので、正しいと思います。

于 2008-12-07T18:15:50.447 に答える
0

Adam Rosenfield の解決策はうまくいく可能性が非常に高いようです。ここはもう遅い（真夜中くらい！）ので、朝まで置いておきます。私は C でプライオリティ キューを効率的に実装しているので、明日はそれを使用して解決策を見つけようとします。

アルゴリズムの成功についてはまた報告しますが、その理由は私には適切であり、データと密接に一致しています (上記のとおり)。しかし、私がつぶやくように、sub O(n) アルゴリズムがあるに違いありません! ;-)

于 2008-12-07T00:06:44.433 に答える