language agnostic - Resolviendo el problema NP-complete en XKCD

language-agnostic (15)

El problema / comic en cuestión: http://xkcd.com/287/

No estoy seguro de que esta sea la mejor manera de hacerlo, pero esto es lo que se me ocurrió hasta ahora. Estoy usando CFML, pero debería ser legible por cualquiera.

<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>  <cfoutput>#arguments.currentCombo# = 15.05</cfoutput> <cfreturn true /> <cfelseif arguments.currentTotal gt 15.05> <cfoutput>#arguments.currentCombo# > 15.05 (aborting)</cfoutput> <cfreturn false /> <cfelse>  <cfoutput>#arguments.currentCombo# < 15.05 (traversing)</cfoutput> <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>

El código anterior me dice que la única combinación que suma $ 15.05 es 7 órdenes de Fruta mixta, y se necesitan 232 ejecuciones de mi función testCombo para completar.

¿Hay un algoritmo mejor para llegar a la solución correcta? ¿He llegado a la solución correcta?

En realidad, he refactorizado mi algoritmo un poco más. Hubo varias combinaciones correctas que me faltaba, y fue debido al hecho de que volvía tan pronto como el costo pasó de 15.05 - No me molestaba en consultar otros artículos (más baratos) que podía agregar. Aquí está mi nuevo algoritmo:

<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>  <cfoutput>#CC# = 15.05</cfoutput> <cfreturn true /> <cfelseif CT gt 15.05>  <cfelse>   <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> tries: #tries# combos: #combos# </cfoutput>

Salida:

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

Creo que esto puede tener todas las combinaciones correctas, pero mi pregunta sigue en pie: ¿Hay un algoritmo mejor?

Lea sobre el problema de la mochila .

¿No es más elegante con la recursión (en 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)); } } }

Salida

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

Aquí hay una solución con 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, *)

Ahora tiene todas las combinaciones correctas, pero todavía está comprobando muchas más de lo que necesita (como lo demuestran las muchas permutaciones que muestra su resultado). Además, está omitiendo el último elemento que alcanza la marca de 15.05.

Tengo una versión de PHP que hace 209 iteraciones de la llamada recursiva (2012 si obtengo todas las permutaciones). Puedes reducir tu conteo si justo antes del final de tu ciclo, sacas el ítem que acabas de marcar.

No sé la sintaxis de CF, pero será algo como esto:

<cfelse>   <cfset found = testCombo(CC, CT, arguments.apps) /> ------- remove the item from the apps array that was just checked here ------ </cfif> </cfloop>

EDITAR: como referencia, aquí está mi versión de 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; ?>

Salida

mf mf mf mf mf mf mf mf hw hw sp 209

EDICION 2:

Como explicar por qué puede eliminar los elementos llevará un poco más de lo que cabría en un comentario, lo estoy agregando aquí.

Básicamente, cada recursión encontrará todas las combinaciones que incluyen el elemento de búsqueda actual (por ejemplo, el primer paso encontrará todo, incluida al menos una fruta mixta). La forma más fácil de entenderlo es rastrear la ejecución, pero como eso ocupará mucho espacio, lo haré como si el objetivo fuera 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]

En este punto, hemos comprobado todas las combinaciones que incluyen cualquier fruta mezclada, por lo que no es necesario buscar nuevamente la fruta mezclada. También puede usar la misma lógica para podar la matriz en cada una de las recursiones más profundas.

Rastrearlo así sugirió otro ahorro de tiempo: saber que los precios están ordenados de menor a mayor significa que no necesitamos seguir revisando los artículos una vez que rebasamos el objetivo.

Aunque la mochila es NP completa, es un problema muy especial: el programa dinámico habitual es excelente ( http://en.wikipedia.org/wiki/Knapsack_problem )

Y si hace el análisis correcto, resulta que es O (nW), siendo n el número de elementos y W el número objetivo. El problema es cuando tienes que DP en una gran W, es cuando obtenemos el comportamiento NP. Pero en su mayor parte, la mochila se comporta razonablemente bien y puedes resolver instancias realmente grandes sin problemas. En lo que respecta a los problemas completos de NP, la mochila es una de las más fáciles.

Da todas las permutaciones de las soluciones, pero creo que estoy superando a todos los demás por el tamaño del código.

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).

Solución con swiprolog:

?- 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

Aquí está la solución usando constraint.py

>>> 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}]

Entonces, la solución es pedir un plato de muestras, una fruta mixta y 2 órdenes de alitas calientes, o pedir 7 frutas mixtas.

El punto acerca de un problema NP-completo no es que es complicado en un conjunto de datos pequeño, sino que la cantidad de trabajo para resolverlo crece a una velocidad mayor que el polinomio, es decir, no hay ningún algoritmo O (n ^ x).

Si la complejidad del tiempo es O (n!), Como en (creo) los dos problemas mencionados anteriormente, eso es en NP.

Haría una sugerencia sobre el diseño del algoritmo en sí (que es cómo interpreté la intención de su pregunta original). Aquí hay un fragmento de la solución que escribí:

.... 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); } ...

(Tenga en cuenta que el constructor clasifica los elementos del menú aumentando el precio, para permitir la terminación anticipada a tiempo constante cuando el saldo restante es más pequeño que cualquier otro elemento del menú).

El resultado de una ejecución de muestra es:

7 mixed fruit (1505) = 1505 1 mixed fruit (215) + 2 hot wings (710) + 1 sampler plate (580) = 1505 348 calls, 347 loops, 79 falls

La sugerencia de diseño que quiero resaltar es que en el código anterior, cada llamada anidada (recursiva) de findAndReportSolution(...) trata de la cantidad de exactamente un ítem del menú, identificado por el argumento del index . En otras palabras, el agrupamiento recursivo es paralelo al comportamiento de un conjunto en línea de bucles anidados; el más externo cuenta posibles usos del primer elemento del menú, el siguiente en cuenta los usos del segundo elemento del menú, etc. (Excepto, por supuesto, el uso de la recursión libera el código de la dependencia de un número específico de elementos de menú!)

Sugiero que esto hace que sea más fácil diseñar el código, y más fácil de entender lo que hace cada invocación (teniendo en cuenta todos los usos posibles de un elemento específico, delegando el resto del menú a las llamadas subordinadas). También evita la explosión combinatoria de producir todas las disposiciones de una solución de múltiples elementos (como en la segunda línea de la salida anterior, que solo se produce una vez, en lugar de repetidamente con diferentes ordenamientos de los elementos).

Intento maximizar la "obviedad" del código, en lugar de intentar minimizar el número de llamadas de algún método específico. Por ejemplo, el diseño anterior permite que una llamada delegada determine si se ha alcanzado una solución, en lugar de ajustar esa verificación en el punto de la llamada, lo que reduciría el número de llamadas a costa de saturar el código.

Hmm, sabes lo que es extraño. La solución es siete del primer elemento en el menú.

Dado que esto estaba obviamente destinado a ser resuelto con papel y lápiz en un corto período de tiempo, ¿por qué no dividir el total de la orden por el precio de cada artículo para ver si por casualidad ordenaban múltiplos de un artículo?

Por ejemplo,

15.05 / 2.15 = 7 frutas mezcladas 15.05 / 2.75 = 5.5 papas fritas.

Y luego pasar a combinaciones simples ...

15 / (2.15 + 2.75) = 3.06122449 frutas mezcladas con papas fritas.

En otras palabras, suponga que se supone que la solución es simple y puede ser solucionada por un humano sin acceso a una computadora. Luego prueba si funciona (n) la (s) solución (es) más simple (s) y más obvia (y por lo tanto oculta a la vista).

Juro que voy a sacar esto en el coney local este fin de semana cuando pido $ 4.77 en aperitivos (impuestos incluidos) a las 4:30 a.m. después de que el club cierre.

Aquí hay una implementación concurrente en Clojure. Para calcular (items-with-price 15.05) necesitan aproximadamente 14 recursiones de generación de combinación, y aproximadamente 10 cheques de posibilidad. Me llevó unos 6 minutos calcular (items-with-price 100) en mi Intel Q9300.

Esto solo da la primera respuesta encontrada, o nil si no hay ninguna, ya que eso es todo lo que el problema requiere. ¿Por qué hacer más trabajo que te han dicho que hagas?)?

;; 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))

En python.
Tuve algunos problemas con "vars globales", así que puse la función como método de un objeto. Es recursivo y se llama a sí mismo 29 veces para la pregunta en el cómic, deteniéndose en el primer partido exitoso

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

Salida:

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

Si desea un algoritmo optimizado, es mejor probar los precios en orden descendente. Eso le permite usar la mayor parte de la cantidad restante primero y luego ver cómo se puede completar el resto.

Además, puede usar las matemáticas para calcular la cantidad máxima de cada artículo de comida para comenzar cada vez, de modo que no pruebe combinaciones que superarían la meta de $ 15.05.

Este algoritmo solo necesita probar 88 combinaciones para obtener una respuesta completa y que se ve como la más baja que se ha publicado hasta el momento:

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); } }

Aquí está el resultado que muestra las dos soluciones:

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

Aprendiendo de la respuesta de @ rcar , y otra refactorización posterior, tengo lo siguiente.

Al igual que con tantas cosas que codigo, he refabricado de CFML a CFScript, pero el código es básicamente el mismo.

Añadí su sugerencia de un punto de inicio dinámico en la matriz (en lugar de pasar la matriz por valor y cambiar su valor para futuras recurrencias), lo que me llevó a las mismas estadísticas que él (209 recursiones, 571 comprobaciones de precios de combinación (iteraciones de bucle) )), y luego mejoró al suponer que la matriz se ordenará por costo, porque lo es, y se interrumpirá tan pronto como superemos el precio objetivo. Con el descanso, tenemos 209 recursiones y 376 iteraciones de bucle.

¿Qué otras mejoras podrían hacerse al algoritmo?