Foros aprenderaprogramar.com
Aprender a programar => Aprender a programar desde cero => Mensaje iniciado por: vince15 en 19 de Mayo 2015, 17:06
-
Muy buenas, estudiando Algoritmos Genéticos, he encontrado una duda que no soy capaz de resolver, les agradecería mucho su ayuda.
"A graph with n vertices will be colored by k colors. How many bits are needed for representing an individual for solving the problem with Genetic Algorithm."
Este es el problema que encontre, y no encuentro la solución. Con un grafo de n vertices y k colores, cuantos bits necesito para representar un individuo, usando algoritmos genéticos?
Gracias
-
Hola, yo lo que entiendo es que cada posible individuo tienes que representarlo con un array o arreglo de bits (de ceros y unos).
La pregunta es cuántos bits necesitas para representar los individuos presentes en un grafo de n vértices que va a ser coloreado con k colores.
Supón que el grafo fuera compuesto por dos puntos. Aquí parece que lo que se necesita es un bit. Basta indicar que un nodo se representa con un 1 y el otro con un 0. Lo que no tengo claro es el significado de los colores. Por ejemplo si los dos nodos tienen el mismo color no tengo claro si se representarían ambos como un 1 ¿?
Saludos
-
Gracias Alex por la contestacion, ya resolví mi duda.
Cuando tienes 1 bit, puedes representas dos posibilidades, con 2(4)... 2^n=numero de posibilidades
Entonces en el caso de los k colores... k=[log base2 bits] ... bits=[2^k]
Para el caso de los nodos también depende del numero de posibilidades
bits= [2^k] * n(bits necesarios)
creo que seria así
Gracias