Revision Documental
Páginas: 3 (736 palabras)
Publicado: 4 de noviembre de 2012
Aplicación de la coloración de grafos a la telefonía móvil
Primero veamos unos conceptos del tenemos que tener conocimiento ya que nos ayudaran a entender de cómo esto es aplicativo a una red detelefonía.
Fundamento Teórico
1. Algoritmos greedy
Los algoritmos greedy son algoritmos que toman decisiones de corto alcance, basadas en información inmediatamente disponible, sin importarconsecuencias futuras. Se usan con frecuencia para resolver problemas de optimización.
Características:
* Lista de Candidatos: Es el conjunto o lista de elementos que disponemos.
* 2conjuntos: Se definen 2 conjuntos: uno de los seleccionados y considerados y otro el de seleccionados pero rechazados.
* Función es solución: Esta función es la encargada si ya se llego o no a unasolución con el conjunto de candidatos.
* Función es Factible: Esta función es la encargada de determinar si es posible o no encontrar una solución a nuestro problema al añadir algún candidato.* seleccionar Candidato: Elige el candidato más adecuado para poder llegar a la solución.
* Función Objetivo: Función que expresa el valor de la solución que se desea optimizar (minimizar omaximizar).
2. Problemas NP
Antes de definir que es una clase de tipo NP, definiremos que es una clase del tipo P, en está están todos los algoritmos eficientes y que su tiempo de ejecución esun tiempo polinómico.
Por otro lado los problemas de la clase NP, en primer lugar NP no significa “no polinómico”, más bien lo que quiere decir es de “tiempo polinómico no determinista”. Además losproblemas NP se basan en problemas de decisión, para los cuales sus respuestas son si ó no (verdadero ó falso).
Por ejemplo: “Buscar un ciclo hamiltoniano en un grafo G” no es un problema dedecisión, pero “¿Es hamiltoniano el grafo G?”si que lo es ya que su respuesta es afirmativa o negativa.
3. Algoritmos Heurísticos y Aproximados
a) Algoritmos heurísticos
Al hablar de algoritmos...
Primero veamos unos conceptos del tenemos que tener conocimiento ya que nos ayudaran a entender de cómo esto es aplicativo a una red detelefonía.
Fundamento Teórico
1. Algoritmos greedy
Los algoritmos greedy son algoritmos que toman decisiones de corto alcance, basadas en información inmediatamente disponible, sin importarconsecuencias futuras. Se usan con frecuencia para resolver problemas de optimización.
Características:
* Lista de Candidatos: Es el conjunto o lista de elementos que disponemos.
* 2conjuntos: Se definen 2 conjuntos: uno de los seleccionados y considerados y otro el de seleccionados pero rechazados.
* Función es solución: Esta función es la encargada si ya se llego o no a unasolución con el conjunto de candidatos.
* Función es Factible: Esta función es la encargada de determinar si es posible o no encontrar una solución a nuestro problema al añadir algún candidato.* seleccionar Candidato: Elige el candidato más adecuado para poder llegar a la solución.
* Función Objetivo: Función que expresa el valor de la solución que se desea optimizar (minimizar omaximizar).
2. Problemas NP
Antes de definir que es una clase de tipo NP, definiremos que es una clase del tipo P, en está están todos los algoritmos eficientes y que su tiempo de ejecución esun tiempo polinómico.
Por otro lado los problemas de la clase NP, en primer lugar NP no significa “no polinómico”, más bien lo que quiere decir es de “tiempo polinómico no determinista”. Además losproblemas NP se basan en problemas de decisión, para los cuales sus respuestas son si ó no (verdadero ó falso).
Por ejemplo: “Buscar un ciclo hamiltoniano en un grafo G” no es un problema dedecisión, pero “¿Es hamiltoniano el grafo G?”si que lo es ya que su respuesta es afirmativa o negativa.
3. Algoritmos Heurísticos y Aproximados
a) Algoritmos heurísticos
Al hablar de algoritmos...
Leer documento completo
Regístrate para leer el documento completo.