[Kde-devel-es] problema heurístico

[Antonio Buiza Calero]

No soy ningún experto en el tema, pero creo que un algoritmo genético se 
adaptaría bien a tu problema. Con ello alcanzarías una solución 
suficientemente buena (no la óptima) en un tiempo suficientemente corto.

Tu mensaje es un poco antiguo, llevo tiempo sin leer la lista. Si te interesa 
el tema coméntamelo y te oriento un poco más (poco porque solo tengo nociones 
genéricas de AG).

Saludos

El Jueves, 8 de Abril de 2004 13:17, Manuel Pérez López escribió:
> 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
> _______________________________________________
> Kde-devel-es mailing list
> Kde-devel-es at kde.org
> https://mail.kde.org/mailman/listinfo/kde-devel-es

-- 
Antonio Buiza Calero
	antonio at buiza.org
	abuiza at esi.us.es