Browsing by Author "Cuaya Simbro, German"

Now showing 1 - 1 of 1
  • Tesis de licenciatura
    Análisis comparativo de generadores de instancias difíciles para el problema de la mochila multidimensional
    (Benemérita Universidad Autónoma de Puebla, 2005) Cuaya Simbro, German; Osorio Lama, Maria Auxilio
    El propósito principal de este trabajo es reunir ideas de ambas comunidades y aplicar los conceptos de distribución usando por la comunidad de IO para generar casos difíciles para el problema de la mochila multidimensional. En el campo de algoritmos discretos, la manera clásica de distinguir los problemas fáciles de los difíciles es estudiar su conducta en el peor caso. El objetivo Bueno para un algoritmo a llegado a ser sinónimo para un problema que esta acotado (en tiempo de ejecución) por un polinomio, en el peor de los casos de éste Edmonds. Al mismo tiempo el método de Edmonds para encontrar el complemento máximo del peso prefecto en un grafo completo con atención a los pesos de bordes, puede ser visto como un ejemplo para un algoritmo combinatorio sofisticado que resuelve un problema óptimamente. Además, encontrado un complemento óptimo en un gráfico, este puede ser usado como un primer paso para muchas heurísticas para problemas difíciles. El prototipo clásico que tan difícil es un problema es el ya conocido. Problema del agente viajero en computación. El cual consiste en encontrar la ruta más corta para pasar de un conjunto de ciudades fijas entre un total de n. Siendo esté un problema Np completo, generalmente se supone que no hay ningún algoritmo bueno en el sentido anterior, al menos P=NP no hay ningún algoritmo de tipo polinomial para el problema de agente viajero. La mejor heurística poli nominal conocida hasta la fecha usa el cómputo de un óptimo de un emparejamiento de pesos entre las ciudades.