解决XKCD中的NP完全问题
时间：2020-03-06 14:48:25 来源:igfitidea点击:
有问题的问题/漫画：http：//xkcd.com/287/
我不确定这是否是最好的方法，但是到目前为止，这是我要提出的。我正在使用CFML，但任何人都应该可以读取。
<cffunction name="testCombo" returntype="boolean">
<cfargument name="currentCombo" type="string" required="true" />
<cfargument name="currentTotal" type="numeric" required="true" />
<cfargument name="apps" type="array" required="true" />
<cfset var a = 0 />
<cfset var found = false />
<cfloop from="1" to="#arrayLen(arguments.apps)#" index="a">
<cfset arguments.currentCombo = listAppend(arguments.currentCombo, arguments.apps[a].name) />
<cfset arguments.currentTotal = arguments.currentTotal + arguments.apps[a].cost />
<cfif arguments.currentTotal eq 15.05>
<!--- print current combo --->
<cfoutput><strong>#arguments.currentCombo# = 15.05</strong></cfoutput><br />
<cfreturn true />
<cfelseif arguments.currentTotal gt 15.05>
<cfoutput>#arguments.currentCombo# > 15.05 (aborting)</cfoutput><br />
<cfreturn false />
<cfelse>
<!--- less than 15.05 --->
<cfoutput>#arguments.currentCombo# < 15.05 (traversing)</cfoutput><br />
<cfset found = testCombo(arguments.currentCombo, arguments.currentTotal, arguments.apps) />
</cfif>
</cfloop>
</cffunction>
<cfset mf = {name="Mixed Fruit", cost=2.15} />
<cfset ff = {name="French Fries", cost=2.75} />
<cfset ss = {name="side salad", cost=3.35} />
<cfset hw = {name="hot wings", cost=3.55} />
<cfset ms = {name="moz sticks", cost=4.20} />
<cfset sp = {name="sampler plate", cost=5.80} />
<cfset apps = [ mf, ff, ss, hw, ms, sp ] />
<cfloop from="1" to="6" index="b">
<cfoutput>#testCombo(apps[b].name, apps[b].cost, apps)#</cfoutput>
</cfloop>
上面的代码告诉我，唯一加起来为$ 15.05的组合是7个混合水果订单，并且需要232次testCombo函数的执行才能完成。
是否有更好的算法可以得出正确的解决方案？我找到正确的解决方案了吗？
解决方案
阅读背包问题。
实际上，我已经对算法进行了一些重构。我错过了几个正确的组合，这是由于这样的事实，当费用超过15.05时我就立即返回-我不费心检查我可以添加的其他(便宜的)物品。这是我的新算法：
<cffunction name="testCombo" returntype="numeric">
<cfargument name="currentCombo" type="string" required="true" />
<cfargument name="currentTotal" type="numeric" required="true" />
<cfargument name="apps" type="array" required="true" />
<cfset var a = 0 />
<cfset var found = false />
<cfset var CC = "" />
<cfset var CT = 0 />
<cfset tries = tries + 1 />
<cfloop from="1" to="#arrayLen(arguments.apps)#" index="a">
<cfset combos = combos + 1 />
<cfset CC = listAppend(arguments.currentCombo, arguments.apps[a].name) />
<cfset CT = arguments.currentTotal + arguments.apps[a].cost />
<cfif CT eq 15.05>
<!--- print current combo --->
<cfoutput><strong>#CC# = 15.05</strong></cfoutput><br />
<cfreturn true />
<cfelseif CT gt 15.05>
<!--<cfoutput>#arguments.currentCombo# > 15.05 (aborting)</cfoutput><br />-->
<cfelse>
<!--- less than 15.50 --->
<!--<cfoutput>#arguments.currentCombo# < 15.05 (traversing)</cfoutput><br />-->
<cfset found = testCombo(CC, CT, arguments.apps) />
</cfif>
</cfloop>
<cfreturn found />
</cffunction>
<cfset mf = {name="Mixed Fruit", cost=2.15} />
<cfset ff = {name="French Fries", cost=2.75} />
<cfset ss = {name="side salad", cost=3.35} />
<cfset hw = {name="hot wings", cost=3.55} />
<cfset ms = {name="moz sticks", cost=4.20} />
<cfset sp = {name="sampler plate", cost=5.80} />
<cfset apps = [ mf, ff, ss, hw, ms, sp ] />
<cfset tries = 0 />
<cfset combos = 0 />
<cfoutput>
<cfloop from="1" to="6" index="b">
#testCombo(apps[b].name, apps[b].cost, apps)#
</cfloop>
<br />
tries: #tries#<br />
combos: #combos#
</cfoutput>
输出：
Mixed Fruit,Mixed Fruit,Mixed Fruit,Mixed Fruit,Mixed Fruit,Mixed Fruit,Mixed Fruit = 15.05 Mixed Fruit,hot wings,hot wings,sampler plate = 15.05 Mixed Fruit,hot wings,sampler plate,hot wings = 15.05 Mixed Fruit,sampler plate,hot wings,hot wings = 15.05 false false false hot wings,Mixed Fruit,hot wings,sampler plate = 15.05 hot wings,Mixed Fruit,sampler plate,hot wings = 15.05 hot wings,hot wings,Mixed Fruit,sampler plate = 15.05 hot wings,sampler plate,Mixed Fruit,hot wings = 15.05 false false sampler plate,Mixed Fruit,hot wings,hot wings = 15.05 sampler plate,hot wings,Mixed Fruit,hot wings = 15.05 false tries: 2014 combos: 12067
我认为这可能具有所有正确的组合，但我的问题仍然存在：是否有更好的算法？
现在我们已经拥有了所有正确的组合，但是我们仍然需要检查的内容比需要的要多(结果显示的许多排列证明了这一点)。另外，我们将省略最后一个达到15.05标记的项目。
我有一个PHP版本，可以进行209次递归调用的迭代(如果得到所有排列，则可以在2012年实现)。如果恰好在循环结束之前拔出刚刚检查的项目，则可以减少计数。
我不知道CF语法，但是会是这样的：
<cfelse>
<!--- less than 15.50 --->
<!--<cfoutput>#arguments.currentCombo# < 15.05 (traversing)</cfoutput><br />-->
<cfset found = testCombo(CC, CT, arguments.apps) />
------- remove the item from the apps array that was just checked here ------
</cfif>
</cfloop>
编辑：供参考，这是我的PHP版本：
<?
function rc($total, $string, $m) {
global $c;
$m2 = $m;
$c++;
foreach($m as $i=>$p) {
if ($total-$p == 0) {
print "$string $i\n";
return;
}
if ($total-$p > 0) {
rc($total-$p, $string . " " . $i, $m2);
}
unset($m2[$i]);
}
}
$c = 0;
$m = array("mf"=>215, "ff"=>275, "ss"=>335, "hw"=>355, "ms"=>420, "sp"=>580);
rc(1505, "", $m);
print $c;
?>
输出
mf mf mf mf mf mf mf mf hw hw sp 209
编辑2：
由于要解释为什么可以删除元素将花费比我在注释中多得多的内容，因此在此处添加它。
基本上，每次递归都会找到包含当前搜索元素的所有组合(例如，第一步将找到包含至少一个混合水果的所有内容)。理解它的最简单方法是跟踪执行，但是由于这将占用大量空间，因此我将其视为目标为6.45.
MF (2.15)
MF (4.30)
MF (6.45) *
FF (7.05) X
SS (7.65) X
...
[MF removed for depth 2]
FF (4.90)
[checking MF now would be redundant since we checked MF/MF/FF previously]
FF (7.65) X
...
[FF removed for depth 2]
SS (5.50)
...
[MF removed for depth 1]
至此，我们已经检查了包含任何混合水果的每个组合，因此无需再次检查混合水果。我们还可以使用相同的逻辑在每个更深层次的递归中修剪数组。
像这样跟踪它实际上暗示了另一个节省时间的方法-知道价格是从低到高排序的，这意味着一旦超过目标，我们就无需继续检查商品。
这是F＃的解决方案：
#light
type Appetizer = { name : string; cost : int }
let menu = [
{name="fruit"; cost=215}
{name="fries"; cost=275}
{name="salad"; cost=335}
{name="wings"; cost=355}
{name="moz sticks"; cost=420}
{name="sampler"; cost=580}
]
// Choose: list<Appetizer> -> list<Appetizer> -> int -> list<list<Appetizer>>
let rec Choose allowedMenu pickedSoFar remainingMoney =
if remainingMoney = 0 then
// solved it, return this solution
[ pickedSoFar ]
else
// there's more to spend
[match allowedMenu with
| [] -> yield! [] // no more items to choose, no solutions this branch
| item :: rest ->
if item.cost <= remainingMoney then
// if first allowed is within budget, pick it and recurse
yield! Choose allowedMenu (item :: pickedSoFar) (remainingMoney - item.cost)
// regardless, also skip ever picking more of that first item and recurse
yield! Choose rest pickedSoFar remainingMoney]
let solutions = Choose menu [] 1505
printfn "%d solutions:" solutions.Length
solutions |> List.iter (fun solution ->
solution |> List.iter (fun item -> printf "%s, " item.name)
printfn ""
)
(*
2 solutions:
fruit, fruit, fruit, fruit, fruit, fruit, fruit,
sampler, wings, wings, fruit,
*)
递归(在Perl中)是否更优雅？
#!/usr/bin/perl
use strict;
use warnings;
my @weights = (2.15, 2.75, 3.35, 3.55, 4.20, 5.80);
my $total = 0;
my @order = ();
iterate($total, @order);
sub iterate
{
my ($total, @order) = @_;
foreach my $w (@weights)
{
if ($total+$w == 15.05)
{
print join (', ', (@order, $w)), "\n";
}
if ($total+$w < 15.05)
{
iterate($total+$w, (@order, $w));
}
}
}
输出
`marco @ unimatrix-01：〜$ ./xkcd-knapsack.pl
2.15、2.15、2.15、2.15、2.15、2.15、2.15
2.15、3.55、3.55、5.8
2.15、3.55、5.8、3.55
2.15、5.8、3.55、3.55
3.55、2.15、3.55、5.8
3.55、2.15、5.8、3.55
3.55、3.55、2.15、5.8
3.55、5.8、2.15、3.55
5.8、2.15、3.55、3.55
5.8、3.55、2.15、3.55
`
关于NP完全问题的意义不在于在一个小的数据集上是棘手的，而是解决它的工作量以大于多项式的速率增长，即没有O(n ^ x)算法。
如果时间复杂度为O(n！)，如(我相信)上面提到的两个问题，那就是NP。
从@rcar的答案中学习，并在以后进行另一次重构，我得到了以下内容。
与我编写的许多代码一样，我已经从CFML重构为CFScript，但是代码基本上是相同的。
我添加了他关于数组动态起点的建议(而不是通过值传递数组并更改其值以用于将来的递归)，这使我获得了与他得到的相同的统计信息(209个递归，571个组合价格检查(循环迭代) ))，然后对此进行了改进，即假设该数组将按成本进行排序-因为它是-且一旦超过目标价格便立即中断。有了休息，我们减少到209个递归和376个循环迭代。
function testCombo(minIndex, currentCombo, currentTotal){
var a = 0;
var CC = "";
var CT = 0;
var found = false;
tries += 1;
for (a=arguments.minIndex; a <= arrayLen(apps); a++){
combos += 1;
CC = listAppend(arguments.currentCombo, apps[a].name);
CT = arguments.currentTotal + apps[a].cost;
if (CT eq 15.05){
//print current combo
WriteOutput("<strong>#CC# = 15.05</strong><br />");
return(true);
}else if (CT gt 15.05){
//since we know the array is sorted by cost (asc),
//and we've already gone over the price limit,
//we can ignore anything else in the array
break;
}else{
//less than 15.50, try adding something else
found = testCombo(a, CC, CT);
}
}
return(found);
}
mf = {name="mixed fruit", cost=2.15};
ff = {name="french fries", cost=2.75};
ss = {name="side salad", cost=3.35};
hw = {name="hot wings", cost=3.55};
ms = {name="mozarella sticks", cost=4.20};
sp = {name="sampler plate", cost=5.80};
apps = [ mf, ff, ss, hw, ms, sp ];
tries = 0;
combos = 0;
testCombo(1, "", 0);
WriteOutput("<br />tries: #tries#<br />combos: #combos#");
可以对算法进行哪些其他改进？
即使背包是NP完整版，它也是一个非常特殊的问题：常用的动态程序实际上非常出色(http://en.wikipedia.org/wiki/Knapsack_problem)
并且，如果我们进行了正确的分析，结果将是O(nW)，n是项的of，W是目标数。问题是当我们必须在较大的W上进行DP运算时，这就是我们得到NP行为的时候。但是，在大多数情况下，背包的行为都相当合理，我们可以毫无问题地解决背包中的很多问题。就NP完全问题而言，背包是最简单的问题之一。
item(X) :- member(X,[215, 275, 335, 355, 420, 580]). solution([X|Y], Z) :- item(X), plus(S, X, Z), Z >= 0, solution(Y, S). solution([], 0).
它提供了解决方案的所有排列方式，但是我认为我在代码大小方面击败了其他所有人。
?- solution(X, 1505). X = [215, 215, 215, 215, 215, 215, 215] ; X = [215, 355, 355, 580] ; X = [215, 355, 580, 355] ; X = [215, 580, 355, 355] ; X = [355, 215, 355, 580] ; X = [355, 215, 580, 355] ; X = [355, 355, 215, 580] ; X = [355, 355, 580, 215] ; X = [355, 580, 215, 355] ; X = [355, 580, 355, 215] ; X = [580, 215, 355, 355] ; X = [580, 355, 215, 355] ; X = [580, 355, 355, 215] ; No
swiprolog解决方案：
>>> from constraint import *
>>> problem = Problem()
>>> menu = {'mixed-fruit': 2.15,
... 'french-fries': 2.75,
... 'side-salad': 3.35,
... 'hot-wings': 3.55,
... 'mozarella-sticks': 4.20,
... 'sampler-plate': 5.80}
>>> for appetizer in menu:
... problem.addVariable( appetizer, [ menu[appetizer] * i for i in range( 8 )] )
>>> problem.addConstraint(ExactSumConstraint(15.05))
>>> problem.getSolutions()
[{'side-salad': 0.0, 'french-fries': 0.0, 'sampler-plate': 5.7999999999999998, 'mixed-fruit': 2.1499999999999999, 'mozarella-sticks': 0.0, 'hot-wings': 7.0999999999999996},
{'side-salad': 0.0, 'french-fries': 0.0, 'sampler-plate': 0.0, 'mixed-fruit': 15.049999999999999, 'mozarella-sticks': 0.0, 'hot-wings': 0.0}]
这是使用constraint.py的解决方案
因此，解决方案是订购一个采样盘，一个混合水果和2个热翅，或者订购7个混合水果。
....
private void findAndReportSolutions(
int target, // goal to be achieved
int balance, // amount of goal remaining
int index // menu item to try next
) {
++calls;
if (balance == 0) {
reportSolution(target);
return; // no addition to perfect order is possible
}
if (index == items.length) {
++falls;
return; // ran out of menu items without finding solution
}
final int price = items[index].price;
if (balance < price) {
return; // all remaining items cost too much
}
int maxCount = balance / price; // max uses for this item
for (int n = maxCount; 0 <= n; --n) { // loop for this item, recur for others
++loops;
counts[index] = n;
findAndReportSolutions(
target, balance - n * price, index + 1
);
}
}
public void reportSolutionsFor(int target) {
counts = new int[items.length];
calls = loops = falls = 0;
findAndReportSolutions(target, target, 0);
ps.printf("%d calls, %d loops, %d falls%n", calls, loops, falls);
}
public static void main(String[] args) {
MenuItem[] items = {
new MenuItem("mixed fruit", 215),
new MenuItem("french fries", 275),
new MenuItem("side salad", 335),
new MenuItem("hot wings", 355),
new MenuItem("mozzarella sticks", 420),
new MenuItem("sampler plate", 580),
};
Solver solver = new Solver(items);
solver.reportSolutionsFor(1505);
}
...
我会对算法本身的设计提出一个建议(这就是我如何解释原始问题的意图)。这是我编写的解决方案的一部分：
(请注意，构造函数会按价格递增对菜单项进行排序，以在剩余余额小于任何剩余菜单项时启用固定时间提前终止。)
7 mixed fruit (1505) = 1505 1 mixed fruit (215) + 2 hot wings (710) + 1 sampler plate (580) = 1505 348 calls, 347 loops, 79 falls
样本运行的输出为：
我要强调的设计建议是，在上面的代码中，每个findAndReportSolution(...)嵌套(递归)调用都处理一个菜单项的数量，该数量由" index"参数标识。换句话说，递归嵌套与一组嵌套循环的行为并行。最外层计算第一个菜单项的可能用途，下一个计数第二个菜单项的用途，依此类推。(当然，递归的使用使代码摆脱了对特定数量菜单项的依赖！)
我建议这样做可以使代码设计更容易，并且更容易理解每次调用的功能(考虑到特定项目的所有可能使用，将菜单的其余部分委派给下级调用)。这也避免了产生多项目解决方案的所有安排的组合爆炸(如上述输出的第二行，仅发生一次，而不是以项目的不同顺序重复发生)。
我试图最大化代码的"显而易见性"，而不是试图最小化某些特定方法的调用次数。例如，上面的设计让委派的调用确定是否已达到解决方案，而不是将检查结果包装在调用点周围，这样可以减少调用次数，但会使代码混乱。
嗯，你知道这很奇怪。解决方案是菜单上第一项中的七个。
既然这显然是要在短时间内用纸和笔解决的，为什么不将订单总数除以每件商品的价格，以查看是否有机会订购了一件商品的倍数？
例如，
15.05 / 2.15 = 7种混合水果
15.05 / 2.75 = 5.5炸薯条。
然后继续简单的组合...
15 /(2.15 + 2.75)= 3.06122449混合水果和炸薯条。
换句话说，假设该解决方案被认为是简单且可解决的，而无需访问计算机。然后测试最简单，最明显(因此隐藏在视线中)的解决方案是否有效。
我发誓我会在这个周末在当地的购物街上拉这个，当我在俱乐部关门后的4:30 AM订购价值$ 4.77的开胃菜(含税)。
这是Clojure中的并发实现。要计算"(价格为15.05的商品)"，大约需要进行14次组合生成的递归，并进行大约10次可能性检查。花了我大约6分钟的时间，才能在我的Intel Q9300上计算出"(含价格的商品100)"。
;; np-complete.clj
;; A Clojure solution to XKCD #287 "NP-Complete"
;; By Sam Fredrickson
;;
;; The function "items-with-price" returns a sequence of items whose sum price
;; is equal to the given price, or nil.
(defstruct item :name :price)
(def *items* #{(struct item "Mixed Fruit" 2.15)
(struct item "French Fries" 2.75)
(struct item "Side Salad" 3.35)
(struct item "Hot Wings" 3.55)
(struct item "Mozzarella Sticks" 4.20)
(struct item "Sampler Plate" 5.80)})
(defn items-with-price [price]
(let [check-count (atom 0)
recur-count (atom 0)
result (atom nil)
checker (agent nil)
; gets the total price of a seq of items.
items-price (fn [items] (apply + (map #(:price %) items)))
; checks if the price of the seq of items matches the sought price.
; if so, it changes the result atom. if the result atom is already
; non-nil, nothing is done.
check-items (fn [unused items]
(swap! check-count inc)
(if (and (nil? @result)
(= (items-price items) price))
(reset! result items)))
; lazily generates a list of combinations of the given seq s.
; haven't tested well...
combinations (fn combinations [cur s]
(swap! recur-count inc)
(if (or (empty? s)
(> (items-price cur) price))
'()
(cons cur
(lazy-cat (combinations (cons (first s) cur) s)
(combinations (cons (first s) cur) (rest s))
(combinations cur (rest s))))))]
; loops through the combinations of items, checking each one in a thread
; pool until there are no more combinations or the result atom is non-nil.
(loop [items-comb (combinations '() (seq *items*))]
(if (and (nil? @result)
(not-empty items-comb))
(do (send checker check-items (first items-comb))
(recur (rest items-comb)))))
(await checker)
(println "No. of recursions:" @recur-count)
(println "No. of checks:" @check-count)
@result))
这只会给出第一个找到的答案，如果没有答案，则为nil，因为这就是所有问题的要求。为什么要求我们做更多的工作;)？
class Solver(object):
def __init__(self):
self.solved = False
self.total = 0
def solve(s, p, pl, curList = []):
poss = [i for i in sorted(pl, reverse = True) if i <= p]
if len(poss) == 0 or s.solved:
s.total += 1
return curList
if abs(poss[0]-p) < 0.00001:
s.solved = True # Solved it!!!
s.total += 1
return curList + [poss[0]]
ml,md = [], 10**8
for j in [s.solve(p-i, pl, [i]) for i in poss]:
if abs(sum(j)-p)<md: ml,md = j, abs(sum(j)-p)
s.total += 1
return ml + curList
priceList = [5.8, 4.2, 3.55, 3.35, 2.75, 2.15]
appetizers = ['Sampler Plate', 'Mozzarella Sticks', \
'Hot wings', 'Side salad', 'French Fries', 'Mixed Fruit']
menu = zip(priceList, appetizers)
sol = Solver()
q = sol.solve(15.05, priceList)
print 'Total time it runned: ', sol.total
print '-'*30
order = [(m, q.count(m[0])) for m in menu if m[0] in q]
for o in order:
print '%d x %s \t\t\t (%.2f)' % (o[1],o[0][1],o[0][0])
print '-'*30
ts = 'Total: %.2f' % sum(q)
print ' '*(30-len(ts)-1),ts
在python中。
我在使用"全局变量"时遇到了一些问题，因此我将函数作为对象的方法。它是递归的，它会在漫画中自问29次问题，并在第一次成功比赛后停止
Total time it runned: 29
------------------------------
1 x Sampler Plate (5.80)
2 x Hot wings (3.55)
1 x Mixed Fruit (2.15)
------------------------------
Total: 15.05
输出：
如果我们需要优化的算法，则最好按降序尝试价格。这样一来，我们可以先用尽所有剩余的金额，然后查看如何填充剩余的金额。
此外，我们可以使用数学方法来计算每次开始的每种食品的最大数量，因此我们不会尝试超过15.05美元目标的组合。
public class NPComplete {
private static final int[] FOOD = { 580, 420, 355, 335, 275, 215 };
private static int tries;
public static void main(String[] ignore) {
tries = 0;
addFood(1505, "", 0);
System.out.println("Combinations tried: " + tries);
}
private static void addFood(int goal, String result, int index) {
// If no more food to add, see if this is a solution
if (index >= FOOD.length) {
tries++;
if (goal == 0)
System.out.println(tries + " tries: " + result.substring(3));
return;
}
// Try all possible quantities of this food
// If this is the last food item, only try the max quantity
int qty = goal / FOOD[index];
do {
addFood(goal - qty * FOOD[index],
result + " + " + qty + " * " + FOOD[index], index + 1);
} while (index < FOOD.length - 1 && --qty >= 0);
}
}
该算法只需尝试88种组合即可获得完整答案，这看起来是迄今为止发布的最低答案：
9 tries: 1 * 580 + 0 * 420 + 2 * 355 + 0 * 335 + 0 * 275 + 1 * 215 88 tries: 0 * 580 + 0 * 420 + 0 * 355 + 0 * 335 + 0 * 275 + 7 * 215 Combinations tried: 88
段落数量不匹配
