Resumen

El problema del cartero chino es un problema clásico de asignación de recursos y programación, que ha sido ampliamente utilizado en la práctica. Al tratarse de un problema polinómico no determinista clásico, la búsqueda de un algoritmo eficiente siempre ha sido objeto de investigación por parte de los académicos. En este trabajo, se propone un nuevo algoritmo bioinspirado para resolver el problema del cartero chino basado en el cálculo molecular, que tiene las ventajas de una alta eficiencia computacional, una gran capacidad de almacenamiento y una gran capacidad de cálculo paralelo. En el cálculo, se utiliza la cadena de ADN para representar adecuadamente el vértice, la arista y el peso correspondiente, y luego se generan eficazmente todas las posibles combinaciones de caminos mediante reacciones bioquímicas. El espacio de soluciones factibles se obtiene eliminando las cadenas de soluciones no factibles, y la solución óptima se resuelve mediante un algoritmo. A continuación, se demuestra la complejidad computacional y la viabilidad del algoritmo de ADN. Por comparación, se encuentra que la complejidad computacional del algoritmo de ADN es significativamente mejor que la de los algoritmos anteriores. La corrección del algoritmo se verifica mediante experimentos de simulación. Con la madurez de la tecnología de operaciones biológicas, este algoritmo tiene un amplio espacio de aplicación en la resolución de problemas de optimización combinatoria a gran escala.

• Materias:Inteligencia artificial Minería de datos Algoritmos genéticos Neurofisiología Proceso de aprendizaje
• Subjects:Artificial intelligence Data mining Genetic algorithms Neurophysiology Learning processes
• Palabras claves:problema del cartero chino, complejidad computacional, algoritmo de adn, tecnología de operaciones biológicas, asignación clásica de recursos, espacio de soluciones factibles, nuevo algoritmo bioinspirado, capacidad de computación en paralelo, combinación de caminos posibles, alta eficiencia computacional
• Keywords:chinese postman problem, computational complexity, dna algorithm, biological operations technology, classic resources allocation, feasible solutions space, new bioinspired algorithm, parallel computing ability, possible path combination, high computational efficiency