Un Pipeline para Resolver el Problema de la Mochila 0-1

El problema de la mochila 0-1 se enuncia asi:

Se tiene una mochila de de capacidad $ C$ y $ N$ objetos de pesos $ w_k$ y beneficios $ p_k$ . Se trata de encontrar la combinación óptima de objetos que caben en la mochila y producen el máximo beneficio.

Denotemos por $ f_{k,c}$ el valor óptimo de la solución para el subproblema considerando los objetos $ \{1, \ldots k\}$ y capacidad $ c$ . El problema consiste en encontrar el valor de $ f_{N,C}$ . Se cumple la siguiente fórmula:

$\displaystyle f_{k,c} = \max \{ f_{k-1,c}, f_{k-1,c-w_k}+p_k \}$   $\displaystyle \mbox{ si $c > w_k$}$ (12.1)

y $ f_{\emptyset, c} = 0$ en otro caso.

Esta fórmula nos dice que la solución para el problema $ f_{k,c}$ con objetos $ \{1, \ldots k\}$ puede obtenerse a partir de las soluciones de los dos subproblemas de mochila con objetos $ \{1, \ldots k-1\}$ que resultan de tomar las decisiones de incluir o no el objeto $ k$ .

En esta sección presentamos un programa que usa $ N$ threads dispuestas en pipeline para resolver el problema.

El Fichero de Entrada

El problema se describe mediante un fichero como el que sigue:

lhp@nereida:~/Lperl/src/threads$ cat knap.dat
8
102
2
15
20
100
20
90
30
60
40
40
30
15
60
10
10
1
N=8, M = 102
weight 0
profit 0
...
N=8, M = 102
weight 0
profit 0
...
Example 2.1 pag 20 Martello and Toth
sol 280

Al ejecutar el programa se muestra la solución:

lhp@nereida:~/Lperl/src/threads$ pipeknap2.pl knap.dat
sol = 280
lhp@nereida:~/Lperl/src/threads$

El Programa Principal

El programa principal se limita a cargar las librerías y crear el pipeline de threads:

lhp@nereida:~/Lperl/src/threads$ cat -n pipeknap2.pl
 1  #!/usr/bin/perl -w
 2  use strict;
 3  use threads;
 4  use Thread::Queue;
 5  use threads::shared;
 6  use Carp;
 7  use IO::File;
 8
 9  ### main
10  my ($M, $w, $p) = ReadKnap($ARGV[0]);
11  my $N = @$w;
12
13  &pipe($N, \&knap, $M, $w, $p);
El primer argumento $N de pipe es el número de threads, el segundo la subrutina a ejecutar por la thread. En este caso una referencia a la subrutina knap. Los restantes argumentos son argumentos pasados a la subrutina que ejecuta la thread. En este caso:

Lectura del Problema

La subrutina auxiliar ReadKnap lee un fichero conteniendo una descripción del problema de la mochila:

79  sub ReadKnap {
80    my $filename = shift;
81
82    my $file = IO::File->new("< $filename");
83    croak "Can't open $filename" unless defined($file);
84    my (@w, @p);
85
86    my $N = <$file>;
87    my $M = <$file>;
88    for (0..$N-1) {
89      $w[$_] = <$file>;
90      $p[$_] = <$file>;
91    }
92    return ($M, \@w, \@p);
93  }

La Tarea Realizada por Cada Hilo

Los tres primeros argumentos son:

40  sub knap {
41    my $k = shift();
42    my $from_left = shift();
43    my $to_right = shift();
44    ##############
45    my $M = shift();
46    my @w = @{shift()};
47    my @p = @{shift()};
48
49    my $N = @w;
50    my @f;
51    my @left;
52
53    croak "Profits and Weights don't have the same size"
54                        unless scalar(@w) == scalar(@p);
55
56    for my $c (0..$M) {
57      $f[$c] = ($w[$k] <= $c)? $p[$k] : 0;
58    }
Antes de empezar el cómputo se inicia la lista @f (i.e. $ f_{k,c}$ para todo $ c$ , líneas 56-58). Si el objeto $k cabe en una mochila de capacidad $c se pondrá. En otro caso el valor inicial es cero.

La Tarea de Cada Hilo

En general, en todo pipeline hay que distinguir tres casos:

60    if ($k) {
61      for my $c (0..$M) {
62        $left[$c] = $from_left->dequeue();
63        if ($c >= $w[$k]) {
64          my $y = $left[$c-$w[$k]]+$p[$k];
65          $f[$c] = ($left[$c] < $y)? $y : $left[$c];
66        }
67        else {
68          $f[$c] = $left[$c];
69        }
70        $to_right->enqueue($f[$c]);
71      }
72    }
73    else { # thread virtual 0
74      $to_right->enqueue(@f);
75    }
76    print "sol = $f[-1]\n" if $k == ($N-1);
77  }

La Construcción del Pipeline

17  sub pipe { # crea el pipe de tamaño N
18    my $N = shift(); # número de procesadores virtuales
19    my $task = shift(); # subrutina a ejecutar
20    my @channel : shared; # array de colas
21    my @t; # array de tareas
22    # El resto de argumentos son argumentos de $task
23
24    my $id; # identificador de procesador físico
25
26    # creamos canales ...
27    for($id=0; $id <= $N; $id++) {
28      $channel[$id] = new Thread::Queue; # canal comunicando hilos $id-1 e $id
29    }
30    # creamos threads ...
31    for($id=0; $id < $N; $id++) {
32      $t[$id] = threads->new($task, $id, $channel[$id], $channel[$id+1], @_);
33    }
34    # La thread 0 no trabaja, sólo espera  ...
35    for($id=0; $id < $N; $id++) {
36      $t[$id]->join(); # join debe ser ejecutado por el padre
37    }
38  }

Ficheros Auxiliares de Entrada

Puede obtener ficheros de entrada para el ejemplo en esta sección descargando el fichero knap_dat.tgz. en la página de estos apuntes.



Subsecciones
Casiano Rodríguez León
2012-02-29