<p><strong>索赔</strong></p>
<p>此问题可以在25秒内解决,而不是在11小时内解决,如下所示</p>
<ol>
<li>使用回溯搜索F11^15或4五百万搜索空间</li>
<li>回溯提供了一种机制,用于丢弃不满足约束(即权重和约束)的部分搜索空间</li>
</ol>
<p><strong>代码</strong></p>
<pre><code>class BackTrack:
max_n = 15 # Max number of weights (i.e. 15)
max_sum = 10 # sum of integer weights
normalization = 0.1 # factor to multiply integer weights to make them between 0 and 1
def solve(self, sum_ = 0, weights = [], solutions = []):
"""Find weights that sum to 1 by finding weights that sum to 10 then multiply by 0.1
Integer weights are used during backtracking to avoid issues of rounding errors in computations"""
if len(weights) > BackTrack.max_n or sum_ > BackTrack.max_sum:
# Backtrack since no solution since either
# too many weights or sum of current weights is too large
return
if len(weights) == BackTrack.max_n and sum_ == BackTrack.max_sum:
# Found solution
# Add weights normalized to range 0 to 1 by multiplyfing by
# normalization constant
solutions.append([weight*BackTrack.normalization for weight in weights])
return solutions
# Add additional weights
for weight in range(BackTrack.max_sum + 1):
if weight + sum_ > BackTrack.max_sum:
# No more solutions for this or higher weight
break
else:
# Recursively find solutions for this weight
self.solve(sum_ + weight, weights + [weight], solutions)
return solutions
</code></pre>
<p><strong>测试</strong></p>
<pre><code># start timer
import time
t0 = time.time()
# Solve for weigt combinations
b = BackTrack()
weights = b.solve(0, [], [])
# Show results
print('Elapsed Time {:.2f} seconds'.format(time.time() - t0))
print("Number of Solutions: {:,}".format(len(weights)))
print('Head of Solutions (first 4): ', *weights[:5], sep = '\n')
print('Tail of Solutions (last 4): ', *weights[-5:], sep = '\n')
</code></pre>
<p><strong>输出</strong></p>
<pre><code>Elapsed Time 23.78 seconds
Number of Solutions: 1,961,256
Head of Solutions (first 4):
[0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0]
[0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.1, 0.9]
[0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.2, 0.8]
[0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.30000000000000004, 0.7000000000000001]
[0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.4, 0.6000000000000001]
Tail of Solutions (last 4):
[0.9, 0.0, 0.0, 0.0, 0.1, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
[0.9, 0.0, 0.0, 0.1, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
[0.9, 0.0, 0.1, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
[0.9, 0.1, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
[1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
</code></pre>
<p><strong>发电机版本</strong></p>
<p>在这种情况下,我们为权重创建了一个生成器,它消除了存储所有1.9M权重向量的必要性,如下所示</p>
<pre><code>class BackTrack:
max_n = 15 # Max number of weights (i.e. 15)
max_sum = 10 # sum of integer weights
normalization = 0.1 # factor to multiply integer weights to make them between 0 and 1
def solve(self, sum_ = 0, weights = []):
"""Find weights that sum to 1 by finding weights that sum to 10 then multiply by 0.1
Integer weights are used during backtracking to avoid issues of rounding errors in computations"""
if len(weights) > BackTrack.max_n or sum_ > BackTrack.max_sum:
# No solution since too many weights or sum is too large
return
if len(weights) == BackTrack.max_n and sum_ == BackTrack.max_sum:
# Add path normalized to range 0 to 1 by multiplyfing by
# normalization constant
yield [weight*BackTrack.normalization for weight in weights]
# Check for new solutions
for weight in range(BackTrack.max_sum + 1):
if weight + sum_ > BackTrack.max_sum:
# No more solutions for this or higher weight
break
else:
# Recursively find solutions for this weight
yield from self.solve(sum_ + weight, weights + [weight])
</code></pre>
<p><strong>用法</strong></p>
<pre><code>b = BackTrack()
for weights in b.solve(0, []):
do_something(weights) # current w1, w2, ... w15
</code></pre>