線形不等式の解を数える [終了]

StackOverflow https://stackoverflow.com/questions/1970507

  •  21-09-2019
  •  | 
  •  

質問

私は数を数えることに落とし込んだ問題を解決しようとしています。 整数 多くの線形不等式の解。任意の数の変数 c_1、...、c_n の解の数を数えることができる必要がありますが、n=3 の場合、方程式は次のように記述できます。

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

ここで、n と r の値が事前にわかっているので、存在する (c_1, ..., c_n) 個の解の数を見つけたいと考えています。

これを効率的に (解決策を列挙するよりも速く) 行うことはできますか?（もしそうなら：どうやって？;そうでない場合:なぜ？）

役に立ちましたか？

解決

また一部のコードをすべてのソリューション。

（パラメータ 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 を加算していきますのソリューションをすることができた.最後に、できる、性能向上のためのmemoization.

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)

一部の可能改善:

  • 場合はそ c1 ... cn 常に≤ z, その検出るとすぐに0を返バランスを再構築することが多く大規模 n.この時間雷高速O(nz).

  • されることが c1 ... cn すべてのされますが、よりよいものにする。の適切な変更 min_ck や max_ck うこOnz)小さな定数、キャッシュできる平面2次元配列の代わりに遅くハッシュテーブルました。

  • ることができるかもしれませんよりよいよキャッシュを体系的によpopulatingでの"需要"のこmemoizationコードす。最初に全体のキャッシュn=1、n=2のときです。そうすることで再帰を回避する、各段階でき捨てのキャッシュされたデータセットの必要がなくなり後の計算の結果、n=2のときも必要としない作品のためのn=1のもの

他のヒント

私はおそらく制約プログラミングの王国に行くだろう、この問題を解決するために。あなたは古典的なall different制約（N-クイーンの問題のようなビット）を持っているように思えます。下記に記載されている無料の制約ソルバの一つで行くを持っています。それは非常に効率的にあなたのソリューションを提供します。それは基本的に全探索木を生成しますが、そこに素敵なオール異なる制約の実装と、木はほとんど何に剪定されてしまうでしょう。

http://www.gecode.org/する http://minion.sourceforge.net/する http://jacop.osolpro.com/する http://research.microsoft.com/apps/pubs/default。 aspxの？ID = 64335 の

ここでは、Wikipediaのリストがあります：
http://en.wikipedia.org/wiki/Constraint_programming#Constraint_programming_libraries_for_imperative_programming_languagesする

これは本当にあなたの問題への完全な解決策ではありませんが、私はそれが役立つか、少なくともあなたにいくつかのアイデアを与えるかもしれないと思う。

ソリューションは整数であることをあなたの要件は、このNPの問題になります。我々は最初のドメインは実数であるので、問題の緩和を検討している場合は、Aは行列であり、cは未知数のあなたのベクトルである0 <= A * C <= 1、の充足可能性問題を解決するために求めています。これは、標準的な線形プログラム（些細な目的とLP）であり、（多項式時間で）効率的に解くことができます。あなたはリラックスしたLP解がない場合は、お使いの整数LPは確かに解がないので、実現可能性を判断するために、最初のパスのテストとしてこれを使用することをお勧めします。可能であれば良いLPソルバーにも実行可能な点を返され、あなたは整数解を見つけるためにベクトルのエントリを丸めることができるかもしれません。

他の人が述べたように、これらの制約に基づいて線形目的関数を最大化したい場合は、次のようになります。 整数線形計画法 この問題には、効率的な一般的な解決策が存在しません。代わりに、のポイント数を求めているようです。 実現可能領域, 、これは別の問題ですが、整数解が必要になるため、これも複雑になります。

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

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top