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

这并不是您问题的完整解决方案，但我认为它可能会有所帮助或至少给您一些想法。

您要求解决方案是整数使得这是一个 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_ck对and进行适当的更改max_ck将使这个 O( nz ) 具有更小的常数，并且缓存可以是一个平面 2D 数组，而不是我得到的较慢的哈希表。

  • 您可以通过系统地构建缓存来做得更好，而不是像这个记忆代码那样“按需”填充它。首先为 n=1 构建整个缓存，然后为 n=2 构建整个缓存，依此类推。这样您就可以避免递归，并且在每一步都可以丢弃不再需要的缓存数据（在计算 n=2 的结果之后，您不再需要 n=1 的条目）。

于 2009-12-28T20:47:54.150 回答
0

正如其他人所提到的，如果您想根据这些约束最大化线性目标函数，那么您将遇到整数线性规划问题，对此不存在有效的一般解决方案。相反，您似乎在询问可行区域中的点数，这是一个不同的问题，但由于必须有整数解，它也很复杂。

我能想出的最好办法是找到可行区域边界上的点，并使用这些点来确定内部点的数量。这对于加速低维中的“计算晶格点”类型的问题非常有效，但边界仍然只比所讨论的体积小一维。如果你的问题超过了几个维度，那么问题仍然是棘手的，即使它比枚举所有解决方案要快。

于 2009-12-28T21:59:22.303 回答