Análisis comparativo de generadores de instancias difíciles para el problema de la mochila multidimensional
| dc.audience | generalPublic | |
| dc.contributor.advisor | Osorio Lama, Maria Auxilio | |
| dc.contributor.author | Cuaya Simbro, German | |
| dc.coverage.place | Biblioteca Central 3er. piso | |
| dc.date.accessioned | 2026-01-12T17:23:39Z | |
| dc.date.available | 2026-01-12T17:23:39Z | |
| dc.date.issued | 2005 | |
| dc.description.abstract | 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. | |
| dc.identifier.uri | https://hdl.handle.net/20.500.12371/30841 | |
| dc.language.iso | spa | |
| dc.publisher | Benemérita Universidad Autónoma de Puebla | |
| dc.rights.acces | restrictedAccess | |
| dc.subject.lcc | Operadores polinomicos | |
| dc.subject.lcc | Condicionamiento operante--Programas de computadora--Algoritmo eficiente | |
| dc.subject.lcc | Herramienta edmodo--Es una red social--Educativa global | |
| dc.thesis.career | Licenciatura en Ciencias de la Computación | |
| dc.thesis.degreediscipline | Área de Ingeniería y Ciencias Exactas | |
| dc.thesis.degreegrantor | Facultad de Ciencias de la Computación | |
| dc.thesis.degreetoobtain | Licenciado (a) en Ciencias de la Computación | |
| dc.title | Análisis comparativo de generadores de instancias difíciles para el problema de la mochila multidimensional | |
| dc.type | Tesis de licenciatura | |
| dc.type.degree | Licenciatura |