3

私は、いくつかの線形不等式に対する整数解の数を数えることに縮小した問題を解決しようとしています。任意の数の変数 c_1、...、c_n の解の数をカウントできるようにする必要がありますが、n=3 の場合、方程式は次のように記述できます。

方程式。http://silicon.appspot.com/readdoc?id=155604

今、私は事前に n と r の値を知っており、存在する (c_1, ..., c_n) 解の数を見つけたいと考えています。

これは効率的に (ソリューションを列挙するよりも速く) 実行できますか? (もしそうなら: どのように?; そうでないなら: なぜ?)

4

4 に答える 4

1

この問題を解決するには、おそらく制約プログラミングの領域に入ります。古典的な制約があるようですall different(N-Queens 問題に少し似ています)。以下にリストされている無料の制約ソルバーのいずれかを試してみてください。これにより、非常に効率的に解決策が得られます。基本的には検索ツリー全体を生成しますが、優れた All-Different 制約の実装があれば、ツリーはほとんど何も削除されなくなります。

http://www.gecode.org/ http://minion.sourceforge.net/ http://jacop.osolpro.com/ http://research.microsoft.com/apps/pubs/default.aspx?id= 64335

ウィキペディアのリストは次のとおりです:
http://en.wikipedia.org/wiki/Constraint_programming#Constraint_programming_libraries_for_imperative_programming_languages

于 2009-12-28T17:43:28.370 に答える
0

他の人が述べたように、これらの制約に基づいて線形目的関数を最大化したい場合は、効率的な一般解が存在しない整数線形計画問題が発生します。代わりに、実行可能領域内の点の数を求めているように見えますが、これは別の問題ですが、整数の解を持たなければならないため、これも複雑です。

私が思いつく最良のアイデアは、実行可能領域の境界上の点を見つけ、それらを使用して内部の点の数を決定することです。これは、低次元での「格子点のカウント」タイプの問題を加速するのにうまく機能しますが、境界は問題のボリュームよりも 1 次元小さいままです。問題がいくつかの次元を超える場合、すべてのソリューションを列挙するよりも高速であっても、問題は依然として扱いにくいものになります。

于 2009-12-28T21:59:22.303 に答える
0

これは実際には問題の完全な解決策ではありませんが、役立つか、少なくともいくつかのアイデアが得られると思います。

解が整数であるという要件により、これは NP 問題になります。ドメインが実数になるように問題を緩和することを最初に考えると、0 <= A*c <= 1 の充足可能性問題を解くことになります。ここで、A は行列、c は未知数のベクトルです。これは標準的な線形プログラム (自明な目的を持つ LP) であり、効率的に (多項式時間で) 解くことができます。緩和された LP に解がない場合、整数 LP にも解がないことは確かであるため、実現可能性を判断するための初回通過テストとしてこれを使用することをお勧めします。優れた LP ソルバーは、可能であれば実行可能点も返し、ベクトルのエントリを丸めて整数解を見つけることができる場合があります。

于 2009-12-28T20:42:11.597 に答える
0

すべてのソリューションを生成するコードがあるとします。

(ここでパラメータzには 9 を渡します。これは不等式の右側の数値です。このコードはrが正の場合にのみ機能することに注意してください。)

from math import floor, ceil

def iter_solutions(r, n, z):
    c = [None] * n
    def iter_solutions_bounded(k, pick):
        # pick is the last pick, if any, and 0 otherwise
        assert (1 <= k < n and pick == c[k]) or (k == n and pick == 0)

        min_ck = int(ceil(-pick / r))
        max_ck = int(floor((z - pick) / r))
        if k == 1:
            for ck in range(max(min_ck, 0), min(max_ck, z) + 1):
                c[0] = ck
                yield c
        else:
            for ck in range(min_ck, max_ck + 1):
                c[k - 1] = ck
                for soln in iter_solutions_bounded(k - 1, ck):
                    yield soln
    return iter_solutions_bounded(n, 0)

これを、参照するすべてのコードを削除し、得られたソリューションの数を合計するだけで、ソリューションをカウントするだけのコードに変換できますc。最後に、メモ化によってパフォーマンスを向上させることができます。

from math import floor, ceil

def memoize(f):
    cache = {}
    def g(*args):
        if args in cache:
            return cache[args]
        tmp = cache[args] = f(*args)
        return tmp
    return g

def len_range(a, b):
    if a <= b:
        return b - a
    return 0

def count_solutions(r, n, z):
    @memoize
    def count_solutions_bounded(k, pick):
        min_ck = int(ceil(-pick / r))
        max_ck = int(floor((z - pick) / r))
        if k == 1:
            return len_range(max(min_ck, 0), min(max_ck, z) + 1)
        else:
            return sum(count_solutions_bounded(k - 1, ck) for ck in range(min_ck, max_ck + 1))
    return count_solutions_bounded(n, 0)

考えられる改善点:

  • c 1 ... c nが常に ≤ zであることが真である場合、それを検出してすぐに 0 を返すことは、大きなnに対して非常に役立ちます。実際、実行時間を超高速の O( nz ) に短縮します。

  • c 1 ... c nがすべて負でないことが意図されている場合は、さらに優れています。min_ckandに適切な変更を加えるとmax_ck、この O( nz ) はより小さな定数で作成され、キャッシュは、私が取得した低速のハッシュ テーブルではなく、フラットな 2D 配列になる可能性があります。

  • このメモ化コードのように「オンデマンド」でキャッシュを作成するのではなく、体系的にキャッシュを構築することで、より良い結果が得られる可能性があります。最初に n=1 のキャッシュ全体を構築し、次に n=2 のキャッシュを構築します。そうすれば、再帰を回避でき、各ステップで不要になったキャッシュ データを破棄できます (n=2 の結果を計算した後、n=1 のエントリはもう必要ありません)。

于 2009-12-28T20:47:54.150 に答える