Tema 4. Modelado de problemas

Tema 4. Modelado de problemasAnálisis y Diseño de Algoritmos

ESCUELA TÉCNICA SUPERIOR DE

INGENIERÍA INFORMÁTICA

Departamento de Lenguajes y Sistemas Informáticos

Curso 2010-2011

Análisis y Diseño de Algoritmos 2

Índice

1. Introducción1.1 Definición de tipos

1.2 La interfaz Problema

1.3 El método esSolucion

1.4 Implementación de los problemas

2. Generalización e instanciación de problemas2.1 Conjunto de problemas

3. Modelado de problemas. Ampliación3.1 Espacio de búsqueda y grafo de búsqueda

3.2 Formas Normales para Conjuntos, Multiconjutos en forma de Listas

3.3 Ejemplos

4. Detalles de implementación4.1 Tipos de propiedades, atributos, métodos getters, setters y constructores

4.2 Igualdad, Orden Natural y Copia

4.3 Ordenes

4.4 Funciones

4.5 Vistas iterables

4.6 Resumen


Introducción

A lo largo de la asignatura se presentarán técnicaspara resolver problemas que, a priori, tienensoluciones complejas o que resultan muy costosascomputacionalmente.

En la asignatura no se optará por plantear unaestructura para cada caso si no que se presenta unmodelado general que nos permitirá definir losproblemas y sus soluciones de maneraindependiente a la técnica usada.

En este tema se presentan las bases de esemodelado genérico.


IntroducciónDefinición de tipos

Cuando diseñamos un tipo nuevo indicamos suspropiedades.

Cada propiedad toma valores en rangos de un tipodado y puede depender de parámetros.

Las propiedades pueden clasificarse en base a:o Fijas, su valor se fija al crear el elemento, o Variables,

pueden cambiar su valor después del momento de lacreación del objeto.

o Simples o Derivadas. Las derivadas se pueden calculara partir de las demás.

o Individuales, cuando son propias de cada objeto de laclase, o Compartidas, cuando se comparte entre todaslas instancias.



A partir de las propiedades de un tipo diseñamos un interface. Para diseñar la interfaz debemos tener en cuenta:

Además el tipo podrá tener propiedades genéricas como Comparable o Copiable.

Igualmente tendrá los métodos equals, toString y hashCode.

A. Si tiene la propiedad A la interfaz tendrá el método

getA(),

B. Si la propiedad puede variar posteriormente, es decir,

es variable, se definirá además el método setA(…).

C. Usualmente, si la propiedad es derivada no aparece

el método setA(…) a no ser que el problema lo

requiera por aspectos concretos que se verán en

temas posteriores.



Para implementar un tipo representado como una interfaz, debemos:

A. Elegir adecuadamente los atributos privados.

B. Generar automáticamente los métodos get/set según se ha visto.

C. Generar automáticamente los métodos hashCode e equals.

D. Escribir el método toString, aunque como se verá en prácticas se

puede generar en Eclipse.

E. Escribir la implementación del método clone si el tipo es Copiable.

F. Siempre que sea posible diseñamos los nuevos tipos con orden natural

(que extiendan Comparable). En ese caso escribimos la

implementación del método compareTo.

(*) En la implementación de compareTo debemos tener en cuenta que sea compatible con la igualdad lo

cual siempre es posible. La técnica es ordenar los atributos privados involucrados en la igualdad. A partir

de este orden comparamos primero el primer atributo (usualmente con su orden natural) si el resultado

es cero continuamos con el segundo, etc. Si en algún caso el resultado es distinto de cero ese es el

valor devuelto.


IntroducciónLa interfaz Problema

Durante la asignatura se van a resolver los mismos problemas usando diferentes técnicas.

Cada uno de estos problemas debe definirse de manera independiente a la técnica que se aplique.

Pero, además, las técnicas deberían poder aplicarse a los problemas siempre de la misma manera.

Para ello, se va a definir una interfaz genérica, Problema<S>, donde S es el tipo de la solución del problema.



public interface Problema<S> {

public static enum TipoDeProblema {

UNA_SOLUCION,TODAS_LAS_SOLUCIONES,MEJOR_SOLUCION;

}

Problema.TipoDeProblema getTipoDeProblema();

}

class Problema

«interface»

Problema<S>

«static»

+ TipoDeProblema: enum

+ getTipoDeProblema() : Problema.TipoDeProblema



Problema<S> es un interface genérico donde S se

instanciará por el tipo concreto de la solución del problema.

El tipo de problema indica si lo que queremos buscar es

una solución, todas las soluciones, la mejor solución.

El orden para decidir entre las soluciones para encontrar la

mejor vendrá proporcionado por el método estático getOrden() de la clase que implemente la solución.

La opción por defecto será buscar una solución.

Otras posibilidades de tipos de problemas pueden ser:

existe solución u obtener las mejores soluciones que

modelaremos sobre las anteriores.



Ejemplo 1. Fibonacci

Se trata de calcular f(n) tal que:

f(n) = f(n-1)+f(n-2) y f(0) =0, f(1) =1

public interface ProblemaFibonacci

extends Problema<BigInteger> {

Integer getN();

}



Ejemplo 2. La potencia base entera

public interface PotenciaBaseEntera extends

Problema<Integer> {

Integer getBase();

Integer getExponente();

boolean esSolucion(Integer s);

}


IntroducciónEl método esSolucion

El método esSolucion(S s):

Decide si un valor concreto del tipo S es una solución del problema

En algunos casos es muy complejo de definir y por eso no se ha

localizado en la interfaz genérica.

Existen tres formas de orientar la elaboración de esSolucion:

CASO 1. Que exista ya una solución estándar al problema. Es decir,

que dispongamos de un método que ya nos dé la solución. Este sería el

caso del problema de Fibonacci.


IntroducciónEl método esSolucion

El método esSolucion(S s):

CASO 2: Que exista ya una implementación

que resuelva el problema. Este es el caso de

la Potencia Entera. Para escribir el método

esSolucion podemos comparar el resultado

obtenido con otra implementación disponible

por ejemplo la clase Math de Java.

CASO 3: Disponer de una batería de pruebas

para probar nuestras soluciones. Por ejemplo,

para Fibonacci quedaría:

N Fibonacci

0 0

1 1

2 1

3 2

4 3

5 5

6 8

7 13

8 21


IntroducciónImplementación de los problemas

Ejemplo 1. PotenciaBaseEnteraImpl (1)

public class PotenciaBaseEnteraImpl implements PotenciaBaseEntera {

private Integer base;

private Integer exponente;

public PotenciaEnteraImpl(Integer b, Integer e){

base = b;

exponente = e;

}

public Integer getBase() {

return base;

}

public Integer getExponente() {

return exponente;

}

public boolean esSolucion(Integer s) {

return s.equals(Math.pow(getBase(), getExponente()));

}

class Problema

«interface»

Problema<S>

«interface»

PotenciaBaseEntera

PotenciaBaseEnteraImpl

implements



Ejemplo 1. PotenciaBaseEnteraImpl (2)public TipoDeProblema getTipoDeProblema() {

return TipoDeProblema.UNA_SOLUCION;;

}

public int hashCode() {

return base.hashCode()+31*exponente.hashCode();

}

public boolean equals(Object obj) {

boolean r = false;

if(obj instanceof PotenciaEntera){

PotenciaEntera obj2 = (PotenciaEntera) obj;

r = getBase().equals(obj2.getBase()) &&

getExponente().equals(obj2.getExponente());

}

return r;

}

public String toString(){

return "("+getBase()+","+getExponente()+")";

}

}



Ejemplo 2. Ordenación de listas

public class OrdenaImpl<E> implements Ordena<E> {

private List<E> lista;

private Comparator<E> orden;

public OrdenaImpl(List<E> lista, Comparator<E> orden) {

super();

this.lista = lista;

this.orden = orden;

}

public OrdenaImpl(List<E> lista) {

super();

this.lista = lista;

this.orden = Ordening.natural();

}

public List<E> getLista() {

return lista;

}

public Comparator<E> getOrden() {

return orden;

}

public boolean esSolucion(List<E> s){

…

}…

}

class Problema

Problema

<List<E>>

Ordena <E>

OrdenaImpl<E>

implements


Generalización e

instanciación de problemas En el caso anterior hemos modelado el problema de la

potencia de base entera y exponente entero no negativo.

De forma muy similar podríamos haber modelado otros

problemas similares donde el exponente sigue siendo

entero pero la base podría ser real, matriz, una matriz de

tipo específico (matriz de Fibonacci), etc.

Este proceso consistente en partir de un problema y

encontrar una formulación más amplia que abarque a una

familia más general de problemas lo llamamos

generalización.


Generalización e

instanciación de problemas

Existen dos tipos de generalización:

Generalización de tipos: Cuando un tipo se sustituye por un tipo

genérico que cumpla determinadas propiedades

Generalización de parámetros: Cuando al problema de partida se

le añaden nuevas propiedades.

El proceso inverso de la generalización es la

instanciación. Se trata de instanciar un tipo genérico o fijar

los valores de algunas propiedades.


Generalización e


Ejemplo 1: Generalización de la potencia a exponente

entero. El problema de base entera y exponente entero no

negativo lo podemos generalizar al problema potencia

entera con dos propiedades: Base de tipo B y exponente

de tipo entero no negativo

public class PotenciaEnteraImpl implements PotenciaEntera {

private B base;

private Integer exponente;

public PotenciaEnteraImpl(B b, Integer e){

base = b;

exponente = e;

}

public B getBase() {

return base;

}

class Problema

Problema<S>

PotenciaEntera

PotenciaEnteraImpl

implements


Generalización e

instanciación de problemas Ejemplo 1: Generalización de la potencia a exponente entero.

public Integer getExponente() {

return exponente;

}

public TipoDeProblema getTipoDeProblema() {

return TipoDeProblema.UNA_SOLUCION;

}

public int hashCode() {

return base.hashCode()+31*exponente.hashCode();

}

public boolean equals(Object obj) {

boolean r = false;

if(obj instanceof PotenciaEntera){

PotenciaEntera<?> other = (PotenciaEntera<?>) obj;

r = base.equals(other.getBase()) &&

exponente.equals(other.getExponente());

}

return r;

}

public String toString(){

return "("+getBase()+","+getExponente()+")";

}

}


Generalización e

instanciación de problemas Ejemplo 1: Generalización de la potencia a exponente entero

El problema PotenciaEntera puede ser instanciado haciendo B Integer,

Double, BigInteger, BigDecimal, Matriz, MatrizFibonacci, etc.

En general B se puede instanciar a cualquier tipo sobre el que se pueda definir

una operación con propiedades similares a la multiplicación de enteros. De

esta forma, tendríamos que la interfaz de la transparencia 19

A este lo llamaremos BasePotenciaEntera<T>:

Y así, se exigiría a B que cumpla 

public interface BasePotenciaEntera<T>

{

T getZero();

T getOne();

T getSum(T n);

T getMultiply(T n);

T getSquare();

}

public class PotenciaEnteraImpl > implements

PotenciaEntera {…}


Generalización e

instanciación de problemas Ejemplo 1: Generalización de la potencia de base entera.

A partir del problema PotenciaEntera podemos obtener distintos

problemas concretos según el tipo concreto que instancie B.

Por ejemplo, podemos usarlo para el problema de Fibonacci. El problema

de Fibonacci puede ser escrito de manera matricial:

Vemos que el número n de Fibonacci puede ser obtenido si calculamos las

potencias de la matriz A (n = 0,1,2,…).

Así podríamos resolver el problema con la clase

PotenciaEntera<MatrizFibonacci> donde B ha sido instanciado por

MatrizFibonacci. Los valores de este tipo son las matrices 2x2 de BigInteger

con la forma general:

Que puede

escribirse como


Generalización e


Ejemplo 2: Generalización del problema de la ordenación

de listas.

En este caso la generalización de parámetros, es la ordenación de

listas. Ahora añadimos dos nuevas propiedades de tipo entero: Inf,

Sup. El problema generalizado será ordenar la sublista de la lista

definida por el límite inferior Inf (incluido) y el límite superior Sup

(excluido)


Generalización e


public class Ordena2<E> implements Ordena<E> {

private List<E> lista;

private Comparator<E> orden;

private Integer inf;

private Integer sup;

public Ordena2(List<E> lista, Comparator<E> orden,

Integer inf, Integer sup) {

super();

if(sup < inf || inf < 0 || inf >= lista.size() || sup < 0 ||

sup >= lista.size()){

throw new IllegalArgumentException("Limites no permitidos");

}

this.lista = lista;

this.orden = orden;

this.inf = inf;

this.sup = sup;

}

public boolean esSolucion(List<E> s){

…

}

..

}


Generalización…Conjunto de problemas

Llamaremos conjuntos de problemas asociados a una generalización al conjunto de problemas concretos que pueden obtenerse instanciando, de todas las formas posibles, algunas propiedades escogidas de un problema general dado

Por ejemplo, en el caso concreto de Ordena2 si escogemos las

propiedades Inf y Sup y las instanciamos en todos sus valores posibles

obtenemos todos los problemas consistentes en ordenar una sublista

cualquiera de una lista dada con un orden dado

El conjunto de problemas está definido por una generalización y una o

varias propiedades escogidas que se instancian en todos los valores

posibles.

El concepto de conjunto de problemas es importante porque algunas

propiedades del conjunto de problemas pueden ser compartidas por

todos los problemas del conjunto.


Generalización…Conjunto de problemas

Dentro de un conjunto de problemas podemos escoger dos formas para

identificar a cada uno de los problemas en concreto:

Asociar un objeto a cada problema.

Asociar a cada problema un conjunto de parámetros


Ampliación

Hay muchos problemas de interés cuyas propiedades pueden

modelarse mediante agregados como colecciones, listas, conjuntos,

multiconjuntos, grafos, etc.

Son problemas que requieren en muchos casos usar las técnicas del

modelado proporcionadas por la orientación a objetos.

En concreto tendremos que identificar el tipo de la solución, que puede

ser complejo, el tipo de los elementos que pueden ser integrados en un

agregado, los tipos de los agregados y en general los tipos de las

propiedades del problema

En general llamaremos E al tipo genérico de los elementos que forman

cada uno de los agregados.

A este tipo en algunos contextos se le exigirá unas propiedades:

iterable, tener orden natural, actualizable, etc.


Ampliación Espacio de búsqueda y grafo de búsqueda

En este espacio los valores suelen tener ligaduras entre ellos, bien

dado por el problema en sí o por la técnica.

Estos problemas vendrán representado por un grafo, donde cada uno

de los vértices del grafo es un valor posible del tipo S (solución del

problema) y la aristas son la ligaduras entre ellos.

A este grafo lo llamaremos grafo de búsqueda.

Aunque todos los vértices del grafo de búsqueda son valores del tipo de

la solución del problema solamente algunos (los que cumplen el predicado esSolucion(v)) son las soluciones buscadas.

Resolver el problema es encontrar, en ese grafo o en ese espacio de

búsqueda, los vértices que son solución.

Llamaremos espacio de búsqueda al conjunto de valores posibles del tipo

de la solución del problema.


Ampliación Formas Normales para Conjuntos, Multiconjutos en forma de Listas

La igualdad definida sobre un tipo clasifica los valores del mismo en

clases de equivalencia.

En muchos casos es interesante escoger un representante canónico de

cada una de las clases de equivalencia anteriores.

Por ejemplo, dos racionales son iguales si uno puede ser obtenido deotro multiplicando numerador y denominador por un entero. De cadaclase de racionales iguales podemos escoger una forma normal:aquel racional que esté simplificado

La forma normal de un tipo es una elección concreta para esos representantes canónicos.



Para escoger la forma normal de un conjunto pensemos que dos

conjuntos son iguales si tienen los mismos elementos.

Si fijamos un orden de manera arbitraria entre los elementos de un

conjunto entonces una forma normal para el tipo conjunto es la una lista

ordenada que contenga los mismos elementos que el conjunto.

La forma normal de un conjunto puede ser escogida como una lista ordenada (con un orden arbitrario) y sin repeticiones..



De forma similar para un multiconjunto podemos escoger como forma

normal una lista ordenada de pares.

Cada par contiene un elemento y un entero que indica el número de

veces en que el elemento está contenido en el multiconjunto.

La lista está ordenada por un orden arbitrario sobre los primeros

componentes de los pares: los elementos del multiconjunto. Esta idea se

puede concretar haciendo que los elementos del multiconjunto ofrezcan la

propiedad de tipo entero positivo Count (consultable y modificable) y por lo

tanto los métodos Integer getCount(), void setCount(Integer c).

La forma normal de un multiconjunto puede ser escogida como una lista ordenada (con un orden arbitrario) y sin repeticiones donde cada objeto tiene la propiedad adicional Count.



Las formas normales anteriores nos sugieren que cuando el tipo S, en

un problema dado, sea de tipo Set<E> modelemos la solución con la

forma normal correspondiente es decir List<E> pero siendo esta lista sin

repeticiones y ordenada con respecto a un orden arbitrario.

En el caso de que la solución sea del tipo Multiset<E>. En este caso

modelamos las solución como una lista ordenada y sin repeticiones y

ampliamos el tipo E con la propiedad Count.

Cuando la solución de un problema es de tipo Set<E> o Multiset<E> la

igualdad entre valores del tipo nos permite elegir su forma normal como

representación del conjunto de valores iguales.


Ampliación Ejemplos. El problema de la Mochila

Tenemos un conjunto de objetos con un

determinado peso y valor que nos gustaría

guardar en una mochila. Por cada objeto

podemos guardar varias copias. El

inconveniente es que la mochila sólo puede

llevar un peso máximo y por cada objeto se

indica el número máximo de copias que se

pueden guardar en la mochila. Para resolver el

problema se debe encontrar qué objetos (y el

número de copias de cada uno) que, sin

sobrepasar el peso de la mochila y sin

sobrepasar el número de copias máximo

permitido para ese objeto en particular,

maximiza la suma de los valores de los objetos

almacenados.



class Problema

«interface»

Comparable

«interface»

SolucionMochila

«interface»

Copiable«interface»

Iterable

«interface»

ObjetoMochila

«interface»

Problema

«interface»

ProblemaMochila



ObjetoMochila: representa los objetos que se guardan en la Mochila.

public interface ObjetoMochila extends Copiable<ObjetoMochila>,

Iterable<ObjetoMochila>,

Comparable<ObjetoMochila> {

Integer getCodigo();

Integer getCount();

void setCount(Integer n);

Integer getCountMax();

Integer getPeso();

Integer getValor();

Integer getPesoTotal();

Double getValorUnitario();

}

• Codigo: Entero, Consultable. Identificador del objeto

• Count: Entero, Consultable y modificable. Número de copias

del objeto

• CountMax: Entero, Consultable, Número máximo de copias

del objeto

• Peso: Entero, Consultable. Peso de una unidad del objeto

• Valor: Entero, Consultable. Valor de una unidad del objeto

• PesoTotal: Entero, Consultable. Peso de todas las unidades

del objeto

• ValorUnitario, consultable. Calcula el valor del objeto por

unidad



Igualdad: Dos objetos son iguales si tienen iguales las propiedades Codigo y

Count.

Ordenes: La implementación proporcionará un orden a partir de la propiedad

derivada de tipo Double Valor/Peso. El orden se proporcionará en la

implementación con el método estático Comparator<ObjetoMochila> getOrden

Iteración: El tipo es iterable y debe generar copias del objeto con todos los

valores posibles de la propiedad Count de mayor a menor.

Funciones: La implementación proporcionará una función capaz de convertir un

String en un ObjetoMochila. La función se proporcionará en la implementación

con el método estático Expresion<String,ObjetoMochila> getExpresion().



SolucionMochila: representa la solución del problema de la mochila

public interface SolucionMochila extends Copiable<SolucionMochila>,

Comparable<SolucionMochila>{

List<ObjetoMochila> getObjetosEnMochila();

Integer getPeso();

Integer getValor();

int getSize();

boolean isEmpty();

ObjetoMochila getLast();

}

• ObjetosEnMochila: Lista de ObjetoMochila ordenada y sin

repeticiones, Consultable. El orden con el que se mantiene

ordenada la lista es arbitrario pero por defecto escogemos el orden

que se indica abajo.

• Peso: Entero, Consultable. Peso todos los objetos en la mochila

teniendo en cuenta el número de copias de cada uno.

• Valor: Entero, Consultable. Valor de todos los objetos en la

mochila teniendo en cuenta el número de unidades de cada uno.

• Size: Entero, Consultable. Número de objetos diferentes en la

mochila

• Empty: boolean. Verdadero si la mochila está vacía.

• Last: ObjetoMochila. El último objeto añadido a la mochila si no

está vacía.

Igualdad: Dos objetos son iguales si tienen igual la

propiedad ObjetosEnMochila.

Ordenes: La implementación proporcionará un

orden a partir de la propiedad Valor.



ProblemaMochila: representa el problema de la mochila

public interface ProblemaMochila extends Problema<SolucionMochila> {

List<ObjetoMochila> getObjetosDisponibles();

Integer getCapacidad();

boolean esSolucion(SolucionMochila s);

}

• ObjetosDisponibles: Lista de ObjetoMochila, Consultable. El orden

con el que se mantiene ordenada la lista es arbitrario. Escogemos

el orden que proporciona la implementación del tipo ObjetoMochila.

•Capacidad: Entero, Consultable. Peso máximo que soporta la

mochila.

•Métodos:

•esSolucion(s): El valor s es una solución del problema si su Peso

es menor o igual que la Capacidad de la mochila y los

ObjetosEnMochila están en los ObjetosDisponibles.

Igualdad: Dos problemas son iguales si tienen igual las

propiedades ObjetosDisponibles y Capacidad.

Tipo de Problema: Obtener la mejor solución con

respecto a la propiedad Valor de la solución.



El problema puede generalizarse de varias maneras. Por ejemplo,

considerando sólo un subconjunto de los objetos disponibles para llenar la

mochila.

El paso final, sería implementar el tipo.


Ampliación Ejemplos. El problema de las n reinas

El problema de las n reinas consiste en colocar n reinas en un tablero

de ajedrez (n×n) de manera tal que ninguna de ellas amenace a

ninguna de las demás. Una reina amenaza a los cuadrados de la

misma fila, de la misma columna y de las mismas diagonales.



class Problema

«interface»

Comparable

«interface»

Copiable

«interface»

Iterable

«interface»

Problema

«interface»

Reina«interface»

SolucionReina

«interfaz»

ProblemaReina



Reina: representa cada una de las reinas a colocar en el tablero

public interface Reina extends Iterable<Reina>, Copiable<Reina> {

Integer getColumna();

Integer getFila();

void setFila(Integer f);

Integer getDiagonalPrincipal();

Integer getDiagonalSecundaria();

Integer gerNumeroDeReinas();

}• Columna: Entero, Consultable. Columna donde está la

reina

•Fila: Entero, Consultable y modificable. Fila donde está

la reina

•DiagonalPrincipal: Entero, Consultable. Diagonal

principal donde está la reina. Esta propiedad es derivada

mediante la expresión Fila-Columna.

•DiagonalSecundaria: Entero, Consultable. Diagonal

secundaria donde está la reina. Esta propiedad es

derivada mediante la expresión Fila+Columna.

•NumeroDeReinas: Entero, Consultable, Modificable,

Compartida por toda la población. Numero de Reinas.

Igualdad: Dos reinas son iguales si tienen iguales las

propiedades Columna y Fila.

Iteración: El tipo es iterable y debe generar copias del

objeto con todos los valores posibles de la propiedad

Fila.

Ojo a métodos calculados



SolucionReina: representa la solución del problema

public interface SolucionReina extends Copiable<SolucionReina>,

Comparable<SolucionReina> {

List<Reina> getReinas();

Set<Integer> getFilasOcupadas();

Set<Integer> getDiagonalesPrincipalesOcupadas();

Set<Integer> getDiagonalesSecundariasOcupadas();

int getSize();

boolean isEmpty();

Reina getLast();}

• Reinas: Lista de Reina ordenada por columna de la

reina, sin repeticiones, Consultable.

•FilasOcupadas: Conjunto de Enteros, Consultable.

Conjunto de los enteros que identifican las filas ocupadas

por las reinas de la solución.

•DiagonalesPrincipalesOcupadas: Entero, Consultable.

Conjunto de los enteros que identifican las diagonales

principales ocupadas por las reinas de la solución.

•DiagonalesSecundariasOcupadas: Entero, Consultable.

Conjunto de los enteros que identifican las diagonales

secundarias ocupadas por las reinas de la solución.

•Size, Empty y Last tienen el significado habitual.

Igualdad: Dos objetos son iguales si tienen igual la

propiedad Reinas.

Ordenes: La implementación proporcionará un orden

basado en el orden natural.



ProblemaReina: representa el problema de las reinas

public interface ProblemaReinas extends Problema<SolucionReina> {

Integer getNumeroDeReinas();

boolean esSolucion(SolucionReina s);

}•NumeroDeReinas: Entero, Consultable. Número de

Reinas igual al número de filas y de columnas del tablero.

•esSolucion(s): El valor s es una solución del problema si

los cardinales de las propiedades Reinas, FilasOcupadas,

DiagonalesPrincipalesOcupadas,

DiagonalesSecundariasOcupadas son todos iguales e

iguales al NumeroDeReinasIgualdad: Dos problemas son iguales si tienen igual la

propiedad NumeroDeReinas.

Tipo de Problema: Obtener todas las soluciones.


Ampliación Ejemplos. Problemas sobre mapas

Dado un mapa con ciudades y carreteras que la unen hay un conjunto de

problemas relacionados que pueden plantearse:

El Problema del Camino Mínimo:

Dado un mapa de carreteras una ciudad origen y una ciudad destino un camino mínimo de

la primera a la segunda. Un camino mínimo es una secuencia de ciudades conectadas por

carreteras que no pase dos veces por la misma ciudad y sea de longitud mínima.

El Problema de los Caminos Mínimos:

Dado un mapa de carreteras y una ciudad origen encontrar el camino mínimo de cada una

de las ciudades del mapa a la ciudad origen.

El Problema de Todos los Caminos Mínimos :

Dado un mapa de carreteras encontrar los caminos mínimos de cada una de las ciudades a

las restantes.

El Problema del Viajante de Comercio :

Un viajante de comercio, partiendo de una ciudad origen, desea encontrar la ruta que le

permita hacer el recorrido por todas las ciudades del mapa pasando sólo una vez por cada

una de ellas, de manera que la distancia final recorrida sea mínima, y finalice en la ciudad

de partida.



Todos estos problemas pueden modelarse de una manera similar,

aunque cada uno tenga luego sus características propias.

Modelaremos el mapa mediante un grafo donde las ciudades son los

vértices (Tipo Ciudad) y las aristas las carreteras que los unen.

SolucionCaminoMinimo representará la solución para este problemas

es una secuencia de ciudades del grafo, que podemos modelar mediante

una lista, cada una conectada con la siguiente mediante una carretera del

mapa.



class Problema

«interface»

Problema<SolucionCaminoMinimo>

«interface»

Comparable

«interface»

Ciudad«interface»

SolucionCaminoMinimo

«interface»

ProblemaCaminoMinimo



Ciudad: representa cada una de las ciudades en el mapa

public interface Ciudad extends Comparable<Ciudad> {


String getNombre();

}•Codigo: Entero, Consultable. Código de la ciudad

•Nombre: String, Consultable. Nombre de la ciudad

Igualdad: Dos ciudades son iguales si tienen el mismo

Codigo.



SolucionCamino: representa la solución del problema

public interface SolucionCaminoMinimo extends

Comparable<SolucionCaminoMinimo> {

List<Ciudad> getCamino();

Integer getLongitudDelCamino();

int getSize();

Ciudad getLast();

Ciudad getFirst();

boolean isEmpty();

Graph<Integer, Ciudad> getGrafo();

}•Camino: List<Ciudad>, Consultable. Camino tal que

entre cada ciudad y la ciudad siguiente de la lista hay una

carretera en el mapa del problema.

•LongitudDelCamino: Entero, Consultable. Conjunto de

los enteros que identifican las filas ocupadas por las

reinas de la solución.

•Size, Empty, Last y First tienen el significado habitual en

relación a la propiedad Camino.

•Grafo: Graph<Integer,Ciudad>, Consultable, Compartida

por toda la población. Mapa de ciudades y carreteras.

Igualdad: Dos objetos son iguales si tienen la misma

propiedad Camino.

Ordenes: La implementación proporcionará un orden

basado en la propiedad LongitudDelCamino (de menor

a mayor).



ProblemaCamino: representa el problema sobre mapas más genérico

public interface ProblemaCaminoMinimo extends

Problema<SolucionCaminoMinimo> {

Ciudad getCiudadOrigen();

Ciudad getCiudadDestino();

Graph<Integer,Ciudad> getGrafoDeCiudades();

boolean esSolucion(SolucionCaminoMinimo s);

List<Ciudad> getCiudades();

} •CiudadOrigen: Ciudad, Consultable. Ciudad origen del

camino.

•CiudadDestino: Ciudad, Consultable. Ciudad destino del

camino.

•GrafoDeCiudades: Graph<Integer,Ciudad>, Consultable.

Mapa de ciudades.

•Ciudades: List<Ciudad>, Consultable. Lista formada por

las ciudades del mapa ordenadas por su código.

•esSolucion(s): El valor s es una solución del problema si

la propiedad First es igual a CiudadOrigen, la propiedad

Last es igual a CiudadDestino y cada ciudad está

conectada con la siguiente por una carretera del mapa.

Igualdad: Dos problemas son iguales si tienen igual las

propiedades GrafoDeCiudades, CiudadOrigen y

CiudadDestino.

Tipo de Problema: Obtener la mejor solución teniendo

en cuenta la propiedad LongitudDelCamino (menor

valor de la misma).


El problema puede generalizarse de varias maneras. Por ejemplo,

considerando sólo un subconjunto de las ciudades para resolver el

problema. Esto se puede concretar añadiendo la propiedad K de tipo

entero. El problema generalizado es resolver el problema del Camino

Mínimo con una CiudadOrigen y CiudadDestino y usando sólo las

ciudades que están en la lista Ciudades en las posiciones desde 0 a K-1.

El paso final, sería implementar el tipo.



public class ProblemaCaminoMinimoImpl implements ProblemaCaminoMinimo {

...

public ProblemaCaminoMinimoImpl(String datos,int origen, int destino){

grafo = GraphsFactory.<Integer,Ciudad>creaGraph(

datos, CiudadImpl.getExpresion(), new StringAInteger());

ciudades = CollectionsFactory.creaList(grafo.getVertices());

Collections.sort(ciudades);

this.origen = origen;

this.destino = destino;

SolucionCaminoMinimoImpl.setGrafo(grafo);

}

public boolean esSolucion(SolucionCaminoMinimo s){

boolean r = false;

if(!s.isEmpty()){

r = s.getFirst().equals(getCiudadOrigen()) &&

s.getLast().equals(getCiudadDestino());

}

if(r){

for (int i = 0; i < s.getCamino().size()-1; i++) {

r = r && grafo.isEdge(s.getCamino().get(i),

s.getCamino().get(i+1));

}

}

return r;

}

...

}



Un primer test sobre el problema del camino mínimo sería:

public class TestCaminoMinimo extends Test {

public static void main(String[] args) {

ProblemaCaminoMinimo p = new

ProblemaCaminoMinimoImpl("mapa.txt",10,11);

mostrar(p.getCiudades());

SolucionCaminoMinimo s = new

SolucionCaminoMinimoImpl();

s.add(p.getCiudades().get(10));

s.add(p.getCiudades().get(11));

mostrar("La solución es "+s);

mostrar("El problema es "+p);

mostrar("Es solución "+p.esSolucion(s));

}

}



El problema del viajante puede utilizar los mismos tipos que en el

ejemplo de Camino Mínimo anterior con pequeños cambios. El problema

del Viajante no tiene la propiedad CiudadDestino y la implementación del

método esSolución es:

...

public boolean esSolucion(SolucionCaminoMinimo s){

boolean r;

r = (s.getSize() == ciudades.size());

if(!s.isEmpty()){

r = r && s.getFirst().equals(getCiudadOrigen());

}

if(r){

for (int i = 0; i < s.getCamino().size()-1; i++) {

r = r && grafo.isEdge(s.getCamino().get(i),

s.getCamino().get(i+1));

}

}

if(r){

r = r && grafo.isEdge(s.getLast(), s.getFirst());

}

return r;

}

...



Vemos que los requisitos adicionales para que un valor del tipo

SolucionViajante (exactamente igual en sus propiedades al tipo

SolucionCaminoMinimo) son:

El número de ciudades en la solución debe ser igual al número de

ciudades.

Debe existir una carretera desde la última ciudad en la solución a la

primera (puesto que hemos modelado el recorrido por todas las

ciudades como una lista sin repetición).



Para los otros dos tipos de problemas los cambios también son

mínimos.

En el problema de Caminos Mínimos decidimos (una de las posibles

alternativas) que cada ciudad sea la responsable de conocer el camino

mínimo desde la ciudad origen. Quedando:


public interface Ciudad extends Comparable<Ciudad> {


String getNombre();

Ciudad getCiudadAnteriorDesdeOrigen();

void setCiudadAnteriorDesdeOrigen(Ciudad ciudadAnterior);

boolean isCaminoDesdeOrigen();

Integer getLongitudDelCaminoDesdeOrigen();

public List<Ciudad> getCaminoDesdeOrigen();

Ciudad getCiudadOrigen();


}

CiudadAnteriorDesdeOrigen: Ciudad, Consultable y

Modificable. Ciudad anterior en el camino mínimo desde el

origen hasta la ciudad actual

LongitudDelCaminoDesdeOrigen: Entero, Consultable.

Longitud del camino desde el origen.

CaminoDesdeOrigen: boolean, Consultable. Verdadero si

hay camino desde el origen.

CaminoDesdeOrigen: List<Ciudad>, Consultable. Camino

mínimo desde el origen.

CiudadOrigen: Ciudad, Consultable, Compartida por todo la

población. Ciudad origen.

•Grafo: Graph<Integer,Ciudad>, Consultable, Compartida

por toda la población. Mapa de ciudades.



SolucionCaminosMinimos: quedaría como

public interface SolucionCaminosMinimos {


List<Ciudad> getCamino(Ciudad c);

Integer getLongitudDelCamino(Ciudad c);

boolean isCamino(Ciudad c1);

}•Ciudades: List<Ciudad>, Consultable, Compartida por

toda la población. Ciudades del mapa.

•LongitudDelCamino: Entero, Consultable. Longitud del

camino desde el origen hasta la ciudad c.

•Camino: boolean, Consultable. Verdadero si hay camino

desde el origen hasta la ciudad c.

•Camino: List<Ciudad>, Consultable. Camino desde el

origen hasta c.


En el problema de Todos los Caminos Mínimos decidimos (una de las

posibles alternativas) que cada ciudad sea la responsable de conocer el

camino mínimo desde todas las demás. La solución, como antes, es

simplemente la lista de ciudades.


public interface Ciudad extends Comparable<Ciudad>{


String getNombre();

Ciudad getCiudadAnteriorDesde(Ciudad c);

void setCiudadAnteriorDesde(Ciudad c, Ciudad ciudadAnterior);

boolean isCaminoDesde(Ciudad c);

Integer getLongitudDelCaminoDesde(Ciudad c);

public List<Ciudad> getCaminoDesde(Ciudad c);


}

public interface SolucionTodosLosCaminosMinimos {


List<Ciudad> getCamino(Ciudad c1, Ciudad c2);

boolean isCamino(Ciudad c1, Ciudad c2);

Integer getLongitudDelCamino(Ciudad c1, Ciudad c2);

}


Detalles de implementación Tipos de propiedades

Un tipo tiene una serie de propiedades con un tipo y con una serie de

características que pueden ser clasificadas en:

A. MODIFICABILIDAD: Según esta característica una propiedad puede

ser consultable o consultable y modificable.

B. DERIVABILIDAD: Según esta caracterísitca una propiedad puede ser

básica o derivada.

C. INDIVIDUABILIDAD: Denominamos población de un tipo al conjunto

de objetos creados de ese tipo. Desde el punto de vista de la

individualidad las propiedades pueden ser: individuales de cada

objeto creado o compartidas por todos los miembros de la población

del tipo. Las propiedades individuales son específicas de cada objeto.

Las compartidas son comunes a toda la población del tipo

En base a estas características, veremos una serie de pasos para

implementar un tipo.



Una vez definido el tipo Tipo mediante una interfaz con su nombre, es

necesario decidir sus propiedades. Por cada propiedad N:

Paso 1. Damos un nombre a la propiedad comenzando con mayúsculas. Ej.

Cantidad, Peso, etc.

Paso 2. Estudio de la MODIFICABILIDAD:

2.1 En cualquier caso se crea un método para consultar la

propiedad N.

2.1.1 Si N es un booleando, se definirá el método boolean isN()

2.1.2 En otro caso, se definirá el método TipoDeN getN().

2.1 Si la propiedad es, además, modificable, se definirá el método void setN(TipoDeN n)

61


Paso 3. Estudio de la DERIVABILIDAD. Pasamos a implementar la interfaz en la clase TipoImpl. Por cada propiedad básica se definirá un

atributo privado con el mismo nombre.

Paso 4. Estudio de la INDIVIDUALIDAD cumpliendo los siguientes

aspectos

4.1 Si una propiedad es compartida y básica entonces tiene asociado un atributo que está cualificado como static. Pero el

correspondiente método get no tiene porqué ser static.

4.2 Las propiedades básicas se inicializan dando valor a los

correspondientes atributos ya sea este un valor nuevo o un valor

por defecto.

4.3 Las propiedades básicas individuales se inicializan en los

constructores.

62


Paso 5. Creación de los constructores. Eclipse proporciona una forma

cuasi automática de implementar los constructores a partir de los atributos y de las propiedades de la superclase (super).

Una vez implementados los constructores es conveniente usar las

técnicas de refactorización proporcionadas por el entorno Eclipse para

crear métodos de factoría.

En resumen esta técnica consiste en hacer privado el constructor e introducir un nuevo método público cualificado con static, con los

mismos parámetros que el constructor y de nombre create.

63

Detalles de implementación Igualdad, Orden Natural y Copia

Definir la igualdad de un tipo significa elegir un subconjunto de sus

propiedades.

Elegir esas propiedades implica definir que dos objetos de ese tipo son

iguales si tienen iguales esas propiedades elegidas. Normalmente las

propiedades elegidas son propiedades básicas y por lo tanto tienen

atributos asociados.

La igualdad se implementa en el método equals que, según hemos

visto en temas anteriores, tiene que ser coherente con la implementación

de los métodos hashCode y toString, y si tiene orden natural definido,

también debe ser coherente a compareTo().

La primera sugerencia es que siempre que sea posible dotemos a

todos los tipos nuevos de una igualdad (equals, hashCode, toString) y un

orden natural (compareTo) compatibles entre sí y generados lo más

automáticamente que sea posible.

64

Detalles de implementación Igualdad, Orden Natural y Copia

Para generar el orden natural elegimos que primero que se orden por la

propiedad Codigo y luego por la propiedad Count. Para estos métodos

(clone, toString, compareTo) diseñamos plantillas adecuadas. entre sí y

generados lo más automáticamente que sea posible.

@Override

public ObjetoMochila clone(){

ObjetoMochila copia=null;

try{

copia=(ObjetoMochila)super.clone();

}catch(CloneNotSupportedException e){e.printStackTrace();}

return copia;

}

@Override

public String toString() {

String s;

s = codigo + "," + count;

return s;

}

@Override

public int compareTo(ObjetoMochila other) {

int result;

if (this == null || other == null) {

if (this == null && other == null)

result = 0;

else if (this == null)

result = +1;

else

result = -1;

} else {

result =

getCodigo().compareTo(other.getCodigo());

if(result == 0)

result =

getCount().compareTo(other.getCount());

}return result;}

65

Detalles de implementación Órdenes

Es muy frecuente que necesitemos un orden que ordene los objetos de

un tipo según los valores de una propiedad dada.

Debe cumplirse el requisito adicional de que sean compatibles con la

igualdad definida para ese tipo.

Eso puede ser programado cuasi automáticamente si el tipo tiene

previamente definido un orden natural compatible con la igualdad.

Para conseguir la compatibilidad con la igualdad la idea central es

ordenar los objetos por la propiedad escogida y posteriormente según su

orden natural.

Es necesario implementar una clase interna con estas ideas y un

método público cualificado con static.

La implementación dispone, después de esa implementación, delmétodo public static Comparator<ObjetoMochila> getOrden().

66

Detalles de implementación Órdenes

private static Comparator<ObjetoMochila> ordenObjetoMochila =

new OrdenObjetoMochila();

public static Comparator<ObjetoMochila> getOrden(){

return ordenObjetoMochila;

}

private static class OrdenObjetoMochila implements

Comparator<ObjetoMochila>{

public OrdenObjetoMochila(){

}

public int compare(ObjetoMochila o1, ObjetoMochila o2){

Double d2 = ((double)o2.getValor())/o2.getPeso();

Double d1 = ((double)o1.getValor())/o1.getPeso();

int r = d2.compareTo(d1);

if(r==0)

r = o1.compareTo(o2);

return r;

}

}

67

Detalles de implementación Funciones

En muchos casos es útil que el tipo ofrezca algunas funciones. Una de

uso frecuente es una expresión que convierte hileras de caracteres, en un

formato dado, a objetos del tipo. En ese caso la implementación disponedel método public static Funcion <String, ObjetoMochila>

getExpresion().private static Function<String, ObjetoMochila> expresion = new StringAObjetoMochila();

public static Function<String, ObjetoMochila> getExpresion() {

return expresion;

}

private static class StringAObjetoMochila implements

Function<String, ObjetoMochila> {

public StringAObjetoMochila() {

}

@Override

public ObjetoMochila apply(String s) {

return new ObjetoMochilaImpl(s);

}

}

68

Detalles de implementación Vistas Iterables

Algunos tipos ofrecen una vista iterable, es decir, pueden usarse en un

for extendido.

Para ello, haremos que el objeto extienda a Iterable y a Iterator.public interface ObjetoMochila extends …, Iterable<ObjetoMochila>,…{

…

}

public class ObjetoMochilaImpl implements ObjetoMochila,

Iterator<ObjetoMochila> {

public Iterator<ObjetoMochila> iterator() {

countIterator = getCount();

return this;

}

private Integer countIterator;

public oolean hasNext() {

return countIterator >= 0;

}

public ObjetoMochila next() {

setCount(countIterator);

countIterator--;

return this;

}

public void remove() {

}

…

}

69

Detalles de implementación Resumen

Como resumen final, puede verse que la implementación de un tipo

puede, automatizarse en gran medida:

En primer lugar, Por el procedimiento explicado los métodos públicos de la clase NImpl que implementa el tipo N son los métodos static create

(que sirven para crear objetos), los métodos static con prefijo set (que

inicializan propiedades básicas compartidas) y los métodos setters y getters

obtenidos de las propiedades del tipo. En segundo lugar los métodos relacionados con la igualdad (equals,

hashCode, toString, clone, compareTo) todos coherentes.

En tercer lugar los métodos getOrden(), getExpresion() que

proporcionan un orden basado en una propiedad y una expresión que

construye objetos a partir de hileras de caracteres.

Por último hemos visto la forma de implementar una vista iterable que

genera copias con todos los valores posibles de una propiedad El resto de métodos, como por ejemplo esSolucion, se realizarán de

manera manual.

70

Modificaciones respecto versión 1.0

TRANSPARENCIA 2. EL punto 4.4 se llama Funciones

TRANSPARENCIA 6. Aclaración de la generación de String

TRANSPARENCIA 16. Inclusión de la interfaz Ordena y cambio del

nombre de la clase a OrdenaImpl. Incorporación del diagrama. Cambio de

referencia a Ordening. Cambio en el método es solucion

TRANSPARENCIA 19. Añadido diagrama

TRANSPARENCIA 21. Añadir restricción sobre el uso de

PotenciaEnteraBase

TRANSPARENCIA 34. Cambios en el diagrama

TRANSPARENCIA 35. El método getValorUnitario devuelve un Double

y se ha añadido su descripción

Documents

Tema 4. Modelado de problemas