.

Hoy veremos en clase un problema de comparación de secuencias de caracteres (transparencias 41 a 47 de programación dinámica), concretamente el problema de la distancia de edición entre dos secuencias.

La solución de este problema (y de otros similares) tiene aplicaciones en diversos ámbitos, entre ellos la biología computacional, así como, de forma mucho más concreta, el mantenimiento de versiones de ficheros con editores de textos.

También en el ámbito de la robótica puede resultar útil la solución del problema de la distancia de edición entre cadenas. En el artículo “Solving the mobile robot localization problem using string matching algorithms“, fruto del Proyecto Fin de Carrera de una estudiante de esta Escuela (publicado en Proceedings of the 2004 IEEE/RSJ International Conference on Intelligent Robots and Systems IROS’04, Sendai, Japan, 2004, pp. 2475-2480), se presenta una solución al problema del robot secuestrado en términos de problemas de distancia de edición resueltos con algoritmos de programación dinámica.