To solve this problem I would probably go into the realms of constraint programming. It seems like you have a classic all different constraint (a bit like the N-Queens problem). Have a go at one of the free constraint solvers listed below. That will give you a solution quite efficiently. It'll basically generate the whole search tree but with the nice All-Different constraint implementations out there, the tree will end up being pruned almost to nothing.
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)
Suppose you had some code to produce all the solutions.
(For the parameter z here, pass 9. It's the number on the right-hand side of the inequalities. Note that this code only works when r is positive.)
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)
You can convert this into code that merely counts the solutions simply by deleting all the code that refers to c and adding up the number of solutions that would have been yielded. Finally, you can improve the performance by 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)
Some possible improvements:
If it's true that c1 ... cn are always ≤ z, then detecting that and immediately returning 0 would help a lot for large n. In fact it would reduce the running time to a lightning-fast O(nz).
If it is intended that c1 ... cn all be non-negative, that's even better. Making the appropriate changes to min_ck and max_ck would make this O(nz) with a smaller constant, and the cache could be a flat 2D array instead of the slower hash table I've got.
You might be able to do better by building the cache systematically, rather than populating it "on demand" the way this memoization code does. First build the whole cache for n=1, then for n=2, and so on. That way you could avoid recursion, and at each step you could throw away the cached data you no longer need (after calculating the results for n=2, you don't need the entries for n=1 anymore).
This is not really a full solution to your problem, but I think it may help or at least give you some ideas.
Your requirement that the solutions be integer makes this an NP problem. If we first consider the relaxation of the problem so that the domain is the real numbers, you are asking to solve the satisfiability problem of 0 <= A*c <= 1, where A is a matrix and c is your vector of unknowns. This is a standard linear program (LP with trivial objective), and can be solved efficiently (in polynomial time). You may want to use this as a first pass test to determine feasibility since if the relaxed LP has no solutions, your integer LP certainly has no solutions. A good LP solver will also return a feasible point if possible, and you may be able to round the vector's entries to find an integer solution.
As others have mentioned, if you wanted to maximize a linear objective function based on these constraints then you would have an integer linear programming problem, for which no efficient general solution exists. Instead you seem to be asking for the number of points in the feasible region, which is a different problem, but it too is complicated by having to have integer solutions.
The best idea I can come up with involves finding the points on the boundary of the feasible region, and using those to determine the number of points inside. This works well at accelerating "count the lattice points" type problems in lower dimensions, but the boundary is still just one dimension smaller than the volume in question. If your problem gets over a few dimensions then the problem will still be intractable, even if it is faster than enumerating all the solutions.
发布评论
评论（4）
为了解决这个问题，我可能会进入约束规划领域。看起来你有一个经典的
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
这是维基百科列表：
To solve this problem I would probably go into the realms of constraint programming. It seems like you have a classic
all differentconstraint (a bit like the N-Queens problem). Have a go at one of the free constraint solvers listed below. That will give you a solution quite efficiently. It'll basically generate the whole search tree but with the nice All-Different constraint implementations out there, the tree will end up being pruned almost to nothing.http://www.gecode.org/
http://minion.sourceforge.net/
http://jacop.osolpro.com/
http://research.microsoft.com/apps/pubs/default.aspx?id=64335
Here's the wikipedia list:
http://en.wikipedia.org/wiki/Constraint_programming#Constraint_programming_libraries_for_imperative_programming_languages
假设您有一些代码来生成所有解决方案。
（对于此处的参数 z，传递 9。它是不等式右侧的数字。请注意，此代码仅在 r 为正数时才有效。
）可以将其转换为仅计算解决方案的代码，只需删除所有引用
c的代码并将已产生的解决方案的数量相加即可。最后，您可以通过记忆来提高性能。一些可能的改进：
如果 c1 ... cn 始终 ≤ < em>z，然后检测到并立即返回 0 对于较大的 n 会有很大帮助。事实上，它会将运行时间减少到闪电般的 O(nz)。
如果希望 c1 ... cn 全部为非负数，那就是甚至更好。对
min_ck和max_ck进行适当的更改将使 O(nz) 具有更小的常数，并且缓存可以是平面二维数组而不是我拥有的较慢的哈希表。通过系统地构建缓存，而不是像此记忆代码那样“按需”填充缓存，您可能可以做得更好。首先为 n=1 构建整个缓存，然后为 n=2 构建整个缓存，依此类推。这样您就可以避免递归，并且在每一步中您都可以丢弃不再需要的缓存数据（计算出 n=2 的结果后，您不再需要 n=1 的条目）。
Suppose you had some code to produce all the solutions.
(For the parameter z here, pass 9. It's the number on the right-hand side of the inequalities. Note that this code only works when r is positive.)
You can convert this into code that merely counts the solutions simply by deleting all the code that refers to
cand adding up the number of solutions that would have been yielded. Finally, you can improve the performance by memoization.Some possible improvements:
If it's true that c1 ... cn are always ≤ z, then detecting that and immediately returning 0 would help a lot for large n. In fact it would reduce the running time to a lightning-fast O(nz).
If it is intended that c1 ... cn all be non-negative, that's even better. Making the appropriate changes to
min_ckandmax_ckwould make this O(nz) with a smaller constant, and the cache could be a flat 2D array instead of the slower hash table I've got.You might be able to do better by building the cache systematically, rather than populating it "on demand" the way this memoization code does. First build the whole cache for n=1, then for n=2, and so on. That way you could avoid recursion, and at each step you could throw away the cached data you no longer need (after calculating the results for n=2, you don't need the entries for n=1 anymore).
这并不是真正解决您的问题的完整解决方案，但我认为它可能会有所帮助或至少给您一些想法。
您要求解决方案为整数，这使得这是一个 NP 问题。如果我们首先考虑问题的松弛，使域是实数，那么您要求解决 0 <= A*c <= 1 的可满足性问题，其中 A 是矩阵，c 是向量未知数。这是一个标准的线性规划（具有平凡目标的LP），并且可以有效地求解（在多项式时间内）。您可能希望将此作为第一次通过测试来确定可行性，因为如果宽松的 LP 没有解，那么您的整数 LP 肯定也没有解。如果可能的话，好的 LP 求解器还会返回一个可行点，并且您可以对向量的条目进行舍入以找到整数解。
This is not really a full solution to your problem, but I think it may help or at least give you some ideas.
Your requirement that the solutions be integer makes this an NP problem. If we first consider the relaxation of the problem so that the domain is the real numbers, you are asking to solve the satisfiability problem of 0 <= A*c <= 1, where A is a matrix and c is your vector of unknowns. This is a standard linear program (LP with trivial objective), and can be solved efficiently (in polynomial time). You may want to use this as a first pass test to determine feasibility since if the relaxed LP has no solutions, your integer LP certainly has no solutions. A good LP solver will also return a feasible point if possible, and you may be able to round the vector's entries to find an integer solution.
正如其他人提到的，如果您想根据这些约束最大化线性目标函数，那么您将拥有 整数线性规划问题，不存在有效的通用解决方案。相反，您似乎要求可行区域中的点数，这是一个不同的问题，但由于必须有整数解，它也很复杂。
我能想到的最好的想法是找到可行区域边界上的点，并使用这些点来确定内部点的数量。这对于加速低维中的“计算格点”类型的问题效果很好，但边界仍然只比所讨论的体积小一维。如果你的问题超过了几个维度，那么即使它比枚举所有解决方案更快，问题仍然会很棘手。
As others have mentioned, if you wanted to maximize a linear objective function based on these constraints then you would have an integer linear programming problem, for which no efficient general solution exists. Instead you seem to be asking for the number of points in the feasible region, which is a different problem, but it too is complicated by having to have integer solutions.
The best idea I can come up with involves finding the points on the boundary of the feasible region, and using those to determine the number of points inside. This works well at accelerating "count the lattice points" type problems in lower dimensions, but the boundary is still just one dimension smaller than the volume in question. If your problem gets over a few dimensions then the problem will still be intractable, even if it is faster than enumerating all the solutions.