[Kde-devel-es] problema heurístico

[Manuel Pérez López]

Buenas:

Estoy haciendo una aplicación en la que me he 'atrancado'. Así, que si alguien 
me echa una mano, se lo agradecería. 

La cosa es que tengo que repartir unos 25 puntos entre unos 300 posibles 
lugares de una determinada región de un plano. Para que nos 
hagamos una idea, podría ser algo así como un juego en el que el tablero 
tiene 300 escaques y tengo que colocar 25 fichas *diferentes* sobre él. Mi 
problema es que ni siguiera puedo calcular el número de posibles soluciones, 
ya que en el hipotético caso de reducir a 25 escaques, tendría la friolera de 
25!, lo que en otras palabras son 1.551121004 * 10 elevado a 25 
posibilidades.

El problema no termina ahí, porque tengo que valorar cada una de las 
posibilidades resultantes y quedarme con la mejor bajo unos determinados 
criterios de valoración, por lo que el tiempo de ejecución del programa sería 
prácticamente infinito.

Como veo que por ahí no pueden ir los tiros (a no ser que me equivoque, y 
estaría gustoso de que alguien me ayudara), he visto solo una posible 
solución:


Quedarme con sólo, digamos unas 5000 ó 10000 de esas posiciones posibles, 
elegidas al azar, y valorar cual es la mejor. Esto ya lo he implementado, con 
tiempo de respuesta del algoritmo dentro de la normalidad, pero con 
resultados muy pobres :-(


Comento el asunto con más detalles sobre cómo he implementado esta solución 
con resultados no muy aceptables:

- La distribución de los puntos no es totalmente al azar, sino que ya desde el 
principio voy colocando restricciones. Concretamente los puntos representan 
personas de diferente sexo y el área donde van los puntos son tres círculos 
concéntricos. Cada persona tiene asignado a qué círcuclo va. Esto lo llamo 
zona asignada. Además, hago un reparto del circulo total en dos sectores 
circulares, uno para hombres y otro para mujeres. Adicionalmente no permito 
que los puntos se puedan colocar en cualquier lugar, sino que establezco unas 
posibles posiciones discretas, lo que me da la ventaja de antemano de no 
tener puntos demasiado cerca unos de otros.

- A partir de este punto, y bajo estas condiciones, comienzo las interacciones 
para ir colocando los sujetos al azar (teniendo en cuenta la zona, el sector 
circular y las posibles posiciones discretas).

- En cada una de las interacciones hago una valoraciones de la posición 
resultante, dando puntos: los sujetos representados por puntos tienen unas 
relaciones entre sí, que se establecen con flechas. Para poder visualizar 
correctamente el conjunto, valoro más aquellos resultatos en los que los 
puntos relacionados (con flechas) están cercanos (no todos los puntos tienen 
relaciones entre sí), y sobre todo, la fechas no pueden pasar por encima de 
otros puntos (o sus cercanías).


En el proceso de las interacciones voy maximizando el resultado, es decir, voy 
almacenado el resultado con mejor puntuación. En el fondo, lo que pretendo es 
una visión clara de los puntos y las flechas, con los sujetos relacionados 
cercanos entre sí, y con el mínimo de solapamiento de los elementos.


No se si me he explicado bien, porque el asunto es algo complejo para los que 
nunca han visto algo de este tema (concretamente es una representación 
gráfica de sujetos y sus interacciones sociológicas como grupo, que se llama 
sociograma).

Lo dicho, cualquier sugerencias sobre el tema estaría muy agradecido.

Saludos
Manuel Perez