Segona entrega de PROP (2013)

Trabajo Español
Universidad Universidad Politécnica de Cataluña (UPC)
Grado Ingeniería Informática - 3º curso
Asignatura PROP
Año del apunte 2013
Páginas 2
Fecha de subida 16/06/2014
Descargas 3

Descripción

Document de la Segona entrega PROP
2n lliurement, Documentació comuna del clúster

Vista previa del texto

2n Lliurament: Documentació Comuna del clúster Diagrama classes compartides.
Aquí teniu un uml diferent del cacoo que es pot actualitzar, poseu els atributs i funcions de les classes que heu fet: https://cacoo.com/diagrams/fFqZXnnphJxPMWC4 Repartiment de les responsabilitats de les classes compartides entre el clúster: En comú s'ha dissenyat les classes PROPGraph.java i PROPList.java i les seves funcions.
Tot i que després algun grup ha decidit que era millor cambiar-les i aquestes coses.
Especificació de les classes compartides.
Grup Problema 1: Especificació i implementació de la classe PROPGreedy.java.
La classe PROPGreedy deriva de la classe abstracta Algorithm per poder implementar l’algoritme Greedy.
L'algorisme Greedy, voraç, busca una solució força bona i ràpida, però aproximada. Començant per un node x, va recorrent tots els nodes de la següent manera: si és a x, busca el node més proper no vist y (inicialment no n'ha vist cap), llavors el camí te una durada de l'aresta de x a y; ara es situa a y i segueix amb la mateixa estratègia fins que estan tots vists i per tant ja té el camí que recorre tots els nodes demanats.
Aquest algorisme s'implementa a la classe PROPGreedy.java Cada vegada que apliquem l’algorisme a un node trobem el camí mínim que passa per tots els nodes sortint d’aquest. En el grafs s’hi poden trobar molts camins mínims així que si volem escollir la opció millorés possible i recomanable aplicar l’algorisme Greedy a cada node i d’aquesta manera obtenim quin és el cami més curt si realment no ens importa de quin node començar. Per consultar les adjacències entre nodes ens servim d’una matriu d’adjacència que ens facilita el pes entre els arcs. Anem posant en una llista els nodes visitats seguint el procediment explicat inicialment i finalment es fa la suma de tots els nodes calculant-se així el pes total del camí mímim obtingut.
Grup Problema 2: Especificació i implementació de la classe PROPAprox.java.
La classe PROPAprox.java deriva de la classe abstracta Algorithm per poder implementar l’algoritme 2-Approximation.
Utilitzant l’algorisme de Prim per tal de generar un arbre generador mínim.
Seguidament el recorrem en preordre per tal de traçar una ruta òptima a seguir.
Aquest procés es fonamenta en tres classes: - PROPAprox.java, qui a canvi d’un graf, una llista de vertexs a visitar, un vertex d’inici, un graf buit i dos llistes buides et retorna l’arbre generador mínim i un cicle que permet recorrer tots els vertexs a visitar en un temps òptim.
- Prim.java, qui a canvi d’un graf, una llista de vertexs a visitar, un vertex d’inici, una llista amb tots els vertex del graf, un graf buit i una llista buida et retorna l’arbre generador mínim.
- Edge.java, classe de dades. Representa una aresta amb pes.
Per tal d’obtindre l’arbre generador PROPAprox.java crida a Prim.java, qui a la vegada utilitza Edge.java per tal de poder funcionar. Una vegada PROPAprox.java rep l’arbre generador el recorre en preordre, trobant així un camí òptim.
Grup Problema 3: Especificació i implementació de la classe PROPHillClimbing.java.
La classe HillClimbing deriva de la classe abstracta Algorithm per poder implementar l’algoritme HillClimbing.
Aquest algoritme utilitza un array de arrays d’enters per definir les relacions entre els nodes i un vector d’integers per representar la millor solució.
Per crear una instància del HillClimbing s’especifica si es vol buscar el mínim o el màxim valor de una solució, també s’utilitza un flag per determinar si es circular(ja que nosaltres considerem que en el nostre problema ha de ser true, perque disposem d’ una prestatgeria circular, però en els altres problemes ha de ser false), i una variable que indiqui el nombre d’iteracions que es vol que executi l’algortime.
Una vegada tenim la instància creada podem aplicar l’algoritme. El mètode que ho fa té el mateix nom que la constructora però rep paràmetres diferents : un PROPGraph g, que representa les relacions entre diferents vèrtexs, una PROPList l que representa la solució inicial, i una altra PROPList que serà la nostra solució final millorada(o no si no s’ha trobat cap solució millor).
Dins d’aquest mètode s’execute l’algoritme. Aquest es basa en que de la PROPList que ha rebut com a solució inicial, es tria aleatòriament un element “i” des d’on s’iniciarà l’execució. Es calcularà el cost de la solució que es generaria si s’intercanviés aquest “ i “ amb cadascun de la resta d’elements ” j ”. Si aquest cost es millor que l’inicial, intercanviarà l’element i amb el j. Aquest procediment es fa fins que s’arribi a un nombre concret d’iteracions(determinat en la constructora) o a un temps prèviament establert. Quan acabem retornem la solució trobada que serà la millor fins a aquell moment.
...