<p>Reti43的想法是正确的,但是有一个快速递归的解决方案,它可以在对不等式的限制较少的假设下工作。在</p>
<pre><code>def solve(smin, smax, coef1, coef2):
"""
Return a list of lists of non-negative integers `n` that satisfy
the inequalities,
sum([coef1[i] * n[i] for i in range(len(coef1)]) > smin
sum([coef2[i] * n[i] for i in range(len(coef1)]) < smax
where coef1 and coef2 are equal-length lists of positive integers.
"""
if smax < 0:
return []
n_max = ((smax-1) // coef2[0])
solutions = []
if len(coef1) > 1:
for n0 in range(n_max + 1):
for solution in solve(smin - n0 * coef1[0],
smax - n0 * coef2[0],
coef1[1:], coef2[1:]):
solutions.append([n0] + solution)
else:
n_min = max(0, (smin // coef1[0]) + 1)
for n0 in range(n_min, n_max + 1):
if n0 * coef1[0] > smin and n0 * coef2[0] < smax:
solutions.append([n0])
return solutions
</code></pre>
<p>你可以把这个应用到你原来的问题上</p>
^{pr2}$
<p>对于这样一个长期的问题</p>
<pre><code>smin, coef1 = 185, (97, 89, 42, 20, 16, 11, 6, 2)
smax, coef2 = 205, (98, 90, 43, 21, 17, 12, 7, 3)
solns8 = solve(smin, smax, coef1, coef2)
len(solns8)
4015
</code></pre>
<p>在我的Macbook上,这两个问题都在毫秒内解决。对于稍微大一点的问题,这应该是合理的,但从根本上说,它在系数N的数量中是O(2^N)。它实际扩展的程度取决于附加系数的大小-系数越大(与smax smin相比),可能的解越少,运行得越快。在</p>
<p><strong>更新了</strong>:从关于链接的<a href="https://math.stackexchange.com/questions/1723869/finding-all-lattice-point-in-bounded-region">M.SE post</a>的讨论中,我看到这两个不等式之间的关系是问题结构的一部分。鉴于此,可以给出一个稍微简单的解决方案。下面的代码还包括一些额外的优化,在我的笔记本电脑上,将8变量情况下的解决方案从88毫秒加速到34毫秒。我已经在22个变量的例子中尝试了这个方法,在不到一分钟的时间内就得到了结果,但是对于成百上千的变量来说,这是不可能的。在</p>
<pre><code>def solve(smin, smax, coef):
"""
Return a list of lists of non-negative integers `n` that satisfy
the inequalities,
sum([coef[i] * n[i] for i in range(len(coef)]) > smin
sum([(coef[i]+1) * n[i] for i in range(len(coef)]) < smax
where coef is a list of positive integer coefficients, ordered
from highest to lowest.
"""
if smax <= smin:
return []
if smin < 0 and smax <= coef[-1]+1:
return [[0] * len(coef)]
c0 = coef[0]
c1 = c0 + 1
n_max = ((smax-1) // c1)
solutions = []
if len(coef) > 1:
for n0 in range(n_max + 1):
for solution in solve(smin - n0 * c0,
smax - n0 * c1,
coef[1:]):
solutions.append([n0] + solution)
else:
n_min = max(0, (smin // c0) + 1)
for n0 in range(n_min, n_max + 1):
solutions.append([n0])
return solutions
</code></pre>
<p>你可以把它应用到像这样的8变量例子中</p>
<pre><code>solutions = solve(185, 205, (97, 89, 42, 20, 16, 11, 6, 2))
len(solutions)
4015
</code></pre>
<p>此解直接枚举有界区域中的点阵点。因为你想要所有这些解,得到它们所需的时间将与(至多)束缚晶格点的数量成比例(最多),而束缚晶格点的数量随维度(变量)的数量呈指数增长。在</p>