El ingeniero y la resolución eficiente de problemas

17 de Julio, 2009 // Tags: , , // 3 Comentarios

Hablemos del problema del vendedor viajero (Travel Salesman problem). Sin entrar demasiado en teoría computacional, digamos que es un problema NP-Completo, que ha dado muchos dolores de cabeza a matemáticos, programadores e ingenerios en general. Veamos por qué.

Supongamos que somos un comercial, que a lo largo de un mes, tiene que recorrer 50 ciudades distintas alrededor del mundo. Cada conexión entre ciudades tiene un coste (ya sea por tiempo, o por coste del billete de avión). ¿Cómo ayudamos al pobre comercial a trazar su ruta de forma óptima? Debería hacer Madrid - Londres - Nueva York - Los Ángeles - Pekin, o quizá Madrid - Nueva York - Los Ángeles - Pekin - Londres?

La solución parece evidente a simple vista, pero en realidad no es nada trivial. Y la solución de fuerza bruta es válida para 4, 5 o 6 combinaciones, pero no más (en combinatoria, sería el factorial del número de ciudades). Se puede interpretar como un problema de grafos, pero cuidado! No son algorítmos de búsqueda del camino más corto! Dijsktra no es válido aquí, ya que nuestro comercial tiene que recorrer TODOS LOS PUNTOS.

Bien, en este tipo de problemas, se suelen utilizar soluciones heurísticas. Es decir,  no será la solución óptima algorítmica al 100%, pero si una “válida” que tenga un porcentaje de error probablemente menor del 5%. No será la óptima en cuanto a resultado, pero si en cuanto a otros factores, como tiempo de computación, coste para generar la respuesta, y dolores de cabeza del ingeniero.

¿A qué viene esto?

En la empresa nos encontramos todos los días con problemas del viajero comercial. Y no me refiero a que los comerciales estén todo el día de parranda (que lo están), sino a que muchos de los problemas que nos encontramos no requieren nunca la solución perfecta. La respuesta óptima. Sino que dedicando menos tiempo, se puede llegar a una solución más rentable e igualmente válida. Muchos programadores pecan de esto. De ser extremadamente puristas, tener el algoritmo perfecto, la solución infinita, cuando en realidad, el objetivo estaba mucho más abajo que todo eso.

Así que recuerden: No busquen solo lo óptimo, sino también lo rentable y lo eficiente.

Algunos recursos: