                      Prctica de Programacin III . Curso 1997/98

1 . Problema

En el problema de la asignacin hay que asignar n tareas a n agentes , de
forma que cada agente realice exactamente una tarea . Se dispone de una matriz
de costes C cuyos elementos Cij son enteros positivos y representan el coste
de que el agente i realice la tarea j .
El problema consiste en encontrar una distribucin de tareas entre agentes que
minimice el coste total de ejecutar las n tareas .

2 . Cuestiones

     a/  Puede aplicarse el esquema divide y vencers a la resolucin del
         problema propuesto? Por qu?
         Como se puede apreciar , se trata de un problema de optimizacin que
         es imposible descomponer en subproblemas de longitud inferior , por
         lo tanto el algoritmo de divide y vencers no es aplicable .

     b/  Se ajustan las caractersticas del problema a las del esquema voraz?
         En caso afirmativo ,existe una funcin de seleccin que nos garantice
         una solucin ptima?
         Aunque en principio se trata de un problema de optimizacin , no es
         posible emplear un algoritmo voraz porque no hay nada que nos garantice
         que no es necesario volver atrs una vez asignada una tarea a un agente.
         Con un algoritmo voraz slo conseguiramos encontar una solucin a las
         asignaciones , pero esta solucin no sera ptima .

     c/  Puede entenderse el problema en trminos de una operacin de bsqueda?
         Cul es la estructura del espacio de bsqueda en este caso ? Qu
         caractersticas tiene ?
         El problema es un problema de bsqueda ciega . El rbol consistir en un
         rbol en el que en cada nodo se ir asignando una tarea nueva a un
         agente . La raz del rbol es un nodo sin asignacin de tareas a ningn
         agente . Cada nodo generar tantos hijos como tareas se le puedan
         asignar ( sin repetir ) al siguiente agente .

     d/  De entre los algoritmos de exploracin de grafos que se contemplan en
         esta asignatura , cul es el ms adecuado para este problema ? Por
         qu?
         He empleado el algoritmo de ramificacin y poda , ya que es el ms
         eficiente , ya que disponemos de una forma de ir seleccionando la
         rama ms favorable a expandir y adems , nos permite volver sobre
         nuestros pasos en caso de que una rama que se nos ha quedado atrs ,
         pueda ser retomada en caso de que la ms favorable inicialmente deje
         de serlo en detrimento de otra anterior .

     e/  Cul es la forma ms eficiente de generar el rbol de bsqueda ?
         Existe diferencia obvia desde el punto de vista del coste asinttico
         en el caso peor?
         El recorrido en profundidad , en el caso peor , encontrara la solucin
         tras expandir todos los nodos posibles , el recorrido en anchura tambin
         necesitara recorrer todo el rbol para poder encontrar la solucin
         ms eficiente para el caso peor . En cambio un algoritmo de ramificacin
         y poda , nos permite eliminar muchas ramas que es imposible que nos
         lleven a una solucin ptima . Si en un recorrido en anchura utilizamos
         una cierta informacin heurstica ( poda ) , la solucin encontrada
         tambin es ptima y no hay que recorrer todo el rbol , pero an as
         el coste es superior a una ramificacin y poda .                                                                                                                                                                                                                                                   
         De todas formas , utilizar la estructura de datos de montculo nos
         reducir el coste.

     f/  Dado un ensayo con tareas an por asignar , cmo puede estimarse una
         cota inferior del coste de las soluciones que se generan a partir de
         l?
         La cota inferior la obtengo de sumar el coste que lleva acumulado el
         ensayo ms aquel coste que podra sumrsele si las nuevas asignaciones
         de tareas a agentes fueran las ms eficientes posible de entre las
         no asignadas ya .

     g/  Cmo podemos dar una cota superior inicial al coste mnimo de realizar
         las n tareas ?
         En mi esquema no es necesario realizar esto , ya que siempre voy a
         expandir el ensayo ms prometendor de entre todos los que hay hasta
         el momento .

     h/  Definir una estructura de datos ensayo para los nodos del rbol de
         bsqueda que contenga la siguiente informacin de forma explcita :
                * Las asignaciones realizadas .
                * La lista de tareas sin asignar .
                * El ltimo agente asignado ( o el primero sin asignar ).
                * El coste global de las asignaciones realizadas .

         TYPE TipoEnsayo=RECORD
                               Asignacion:ARRAY [1..n] OF CARDINAL;
                               UltimoAsignado:CARDINAL;
                               Coste:CARDINAL;
                               TareaAsignada:ARRAY [1..n] OF BOOLEAN;
                               Matriz:TipoMatrizCoste
                            END;

         Donde TareaAsignada nos indica si una tarea ya est asignada en este
         ensayo ; esto facilitar la obtencin de la Cota Inferior posible
         para un ensayo dado .
         La matriz de Coste es un ARRAY [1..n],[1..n] OF CARDINAL .

     i/  Las definiciones de las funciones sobre el tipo ensayo van ms adelante.
 

     j/  Solucin en pseudocdigo del algoritmo de ramificacin y poda .
         En la funcin compleciones no es necesario imponer condiciones de poda,
         ya que van implcitas al elegir en cada momento el nodo ms prometedor
         ( aqul cuya cota inferior es menor que todas las dadas ) .  

         Estructuras de datos

         TYPE TipoMatrizCoste=ARRAY [1..n],[1..n] OF CARDINAL;
                  
              TipoPunteroAMatrizCoste=POINTER TO TipoMatrizCoste;
  
              TipoEnsayo=RECORD
                               Asignacion:ARRAY [1..n] OF CARDINAL;
                               UltimoAsignado:CARDINAL;
                               Coste:CARDINAL;
                               TareaAsignada:ARRAY [1..n] OF BOOLEAN;
                               Matriz:TipoMatrizCoste
                            END;

              TipoPuntero=POINTER TO Nodo;

              Nodo=RECORD
                         Valor:TipoEnsayo;
                         Puntero:TipoPuntero
                      END;

              TipoMonticulo=RECORD
                                  T:ARRAY [1..MaxTamayo] OF TipoEnsayo;
                                  Indice:CARDINAL;
                                  Completo:BOOLEAN
                               END;
 

         El algoritmo de ramificacin y poda en pseudocdigo es :
 
                fun vuelta-atrs ( ensayo , monticulo )
                  si vlido ( ensayo )
                  entonces dev ensayo
                  si no para hijo pertenece a compleciones ( ensayo )
                        hacer sacar de cola compleciones ( ensayo )
                              aadir a monticulo ( ensayo )
                        fpara
                        sacar ensayo ms prometedor que es la cima del montculo ( ensayo )
                        vuelta-atrs ( ensayo )
                  fsi
                ffun 

         El algoritmo de compleciones es :

                fun compleciones ( ensayo ) 
                  siguiente asignacin
                  Iniciar cola
                  desde i=1 hasta n hacer 
                    si tarea no asignada ( ensayo , i ) 
                    entonces aadir asignacin a ensayo ( ensayo , i )
                             meter en cola ( ensayo )
                    fsi
                  fdesde
                  dev puntero a cola
                ffun  


         El Algoritmo para la bsqueda en anchura es :

                fun vuelta-atrs ( ensayo , cola de ensayos )
                  si cola de ensayos vaca
                  entonces dev apuntador a ensayo
                  si no 
                       si vlido ( ensayo ) y coste ( ensayo ) < coste parcial mnimo
                       entonces coste parcial mnimo= coste ( ensayo ) 
                                apuntador a ensayo
                       fsi
                       para hijo pertenece a compleciones ( ensayo )
                       hacer sacar cola compleciones ( ensayo )
                             aadir cola ensayos ( ensayo )
                       fpara
                       vuelta-atrs ( ensayo )
                   fsi
                 ffun
         
         El mdulo de la matriz de coste , consta de las siguientes funciones :

                 fun MatrizCosteVacia ( puntero a matriz de coste )
                   dev puntero a matriz de coste = NIL
                 ffun
                 
                 fun Leer ( puntero a matriz de coste )
                   inicializar puntero a matriz de coste
                   abrir fichero para lectura
                   leer fichero desde teclado y escribir en matriz
                   cerrar fichero para lectura
                   dev puntero a matriz de coste
                 ffun

                 fun Escribe ( puntero a matriz de coste )
                     escribe matriz en monitor
                 ffun

                 fun crear-matriz-coste-en-disco 
                   pedir a usuario la entrada de datos y meterlos en la matriz
                   abrir fichero para escritura
                   escribir matriz en fichero
                   cerrar fichero para escritura
                 ffun

         El mdulo de manipulacin de ensayos consta de las siguientes funciones :

                 fun crear-ensayo-inicial ( ensayo )
                   para i=1 hasta i=n
                   hacer asignacion ( i )=0
                     tarea-asignada ( i )=cierto
                   fpara
                   ultimo-asignado=0
                   coste=0
                 ffun

                 fun aadir-asignacion-a-ensayo ( ensayo,agente,tarea )
                   asignacion ( agente )=tarea
                   ultimo-asignado=agente
                   tarea-asignada ( tarea )=cierto
                   coste=coste + valor de la matriz de coste ( agente , tarea )
                 ffun 

                 fun comprobar-ensayo-valido ( ensayo ) 
                   dev ultimo-asignado=n
                 ffun

                 fun cota-inferior ( ensayo )
                   fun minimo ( matriz de coste , columna j )
                     dev mnimo coste de la columna j para los agentes no asignados                         
                   ffun
                   dev coste total de las tareas asignadas y el minimo de las no asignadas
                 ffun

             El mdulo de manipulacin de la cola consta de las siguientes funciones :

                 fun cola-vaca ( puntero a cola )
                   dev cola=NIL
                 ffun

                 fun iniciar-cola ( puntero a cola )
                   cola=NIL
                 ffun

                 fun encolar ( puntero a cola , dato )
                   crear nuevo nodo
                   valor-nuevo nodo=dato
                   puntero-nuevo nodo=NIL
                   auxiliar=cola
                   si cola=NIL
                   entonces cola=nuevo nodo
                   si no mientras puntero-auxiliar<>NIL 
                         hacer auxiliar=puntero-auxiliar
                         fmientras
                         puntero-auxiliar=nuevo nodo
                   fsi
                 ffun

                 fun desencolar ( puntero a cola , dato )
                   auxiliar=cola
                   cola=puntero-cola
                   dato=valor-auxiliar
                   borrar auxiliar
                 ffun

           El mdulo de manipulacin del montculo consta de las siguientes funciones :

                 fun monticulo-vacio ( monticulo )
                   indice=0
                 ffun

                 fun hundir ( monticulo , ensayo )
                   k=1
                   repetir
                     j=k
                     si 2j <= indice y 
                        cota-inerior(ensayo 2j de monticulo)<cota-inferior(ensayo k de monticulo)
                     entonces k=2j
                     fsi
                     si 2j+1 <i ndice y
                        cota-inferior(ensayo 2j+1 de monticulo)<cota-inferior(ensayo k de monticulo)
                     entonces k=2j+1
                     fsi
                     intercambiar ( ensayo j de monticulo , ensayo k de monticulo )
                    hasta j=k
                  ffun

                  fun flotar ( monticulo , ensayo )
                    k=indice
                    repetir
                      j=k
                      si j > 1 y 
                         cota-inferior(ensayo j DIV 2 de monticulo)>cota-inferior(ensayo k de monticulo)
                      entonces k=j DIV 2
                      fsi
                      intercambiar ( ensayo j de monticulo , ensayo k de monticulo)
                    hasta j=k
                  ffun

                  fun aadir ( monticulo , ensayo )
                    indice=indice+1
                    ensayo indice de monticulo=ensayo
                    flotar ( monticulo , ensayo )
                  ffun

                  fun borra-raz ( monticulo )
                    primer ensayo de monticulo=ultimo ensayo de monticulo
                    indice=indice-1
                    hundir ( monticulo , primer ensayo de monticulo )
                  ffun

3 . Comparacin entre los 2 mtodos

El mtodo de ramificacin y poda es claramente superior al de bsqueda en
anchura , ya que utiliza una heurstica vlida para encontrar el camino ideal
y desechar caminos que es imposible que lleven a una solucin mejor .
La bsqueda en anchura siempre debe explorar todos los caminos e ir anotando
el coste de llegar hasta ellos , y de todos , tomar el ms corto . Por lo tanto
, en el caso peor , los dos algoritmos tienen que expandir y comprobar del orden
de n! nodos . Pero en el caso mejor , el algoritmo de ramificacin y poda slo
tendr que expandir n nodos y en cambio el de bsqueda en anchura tendr que
expandir del orden de n! nodos . Por lo tanto , claramente es mejor el algoritmo
de ramificacin y poda .
En el caso promedio , el algoritmo de ramificacin y poda tendr que expandir
aproximadamente la mitad de nodos que en el caso peor . En cambio en el de
bsqueda en anchura tendrn que expandirse tambin del orden de n! nodos .
En el caso real de la matriz matriz4.txt , vemos que prac1 ( ramificacin y
poda ) tiene un costo temporal de 710 unidades y prac2 ( anchura ) tiene un
costo temporal de 2410 unidades , por lo que esa solucin se acerca ms al caso
mejor que al peor .

4. Bloques funcionales descripcin del funcionamiento de los programas

Se ha creado un fichero de texto , matriz4.txt que contiene la matriz 4x4.
Se han creado dos programas , uno prac1 y otro prac2 . Prac1 es la solucin
de ramificacin y poda y prac2 es la solucin en anchura .


























