Lea detenidamente el análisis que se hace a la siguiente situación:
Dilema de un Contrabandista
Un aprendiz a contrabandista se esta financiando el Máster en “Contrabando de Calidad–Superior” con los beneficios obtenidos al pasar monedas antiguas desde Asia. Para ello utiliza un compartimento secreto en su riñonera, que le permite almacenar, si no quiere que en la fron-tera descubran su “negocio”, solo 500 gramos de monedas.
Para poder realizar comparaciones, se va a completar el enunciado con dos escenarios distintos:
Primer escenario: Sus suministradores asiáticos le ofrecen 20 monedas distintas; cada una de ellas pesa 50 gramos y sus precios de venta en el mercado negro, sus valores, van desde los 100 euros hasta los 2000 euros.
Segundo escenario: Sus suministradores asiáticos le ofrecen 20 monedas distintas; cada mone-da tiene distinto peso, entre 30 y 200 gramos, y sus valores van desde 100 euros hasta 2000 eu-ros.
Evidentemente, el dilema del contrabandista consiste en como realizar una elección óptima de monedas, de forma que le permita obtener el máximo beneficio en un viaje. Y cada escenario va a suponer una estrategia distinta:
Primer escenario: Si todas las monedas pesan lo mismo, 50 gramos, puede llevar 10 monedas en la riñonera. Obviamente, le interesa elegir las 10 más valiosas, por lo que si ordena las 20 monedas por valor decreciente, le basta con elegir las 10 primeras.
Segundo escenario: Como cada moneda tiene distinto peso y valor, no es suficiente con realizar una ordenación por valor, ya que no garantiza el máximo beneficio. El contrabandista debería estudiar todas las combinaciones de monedas que pesan menos de 500 gramos y quedarse con la más ventajosa.
El costo del algoritmo del primer escenario es el costo asociado a ordenar 20 monedas por valor decreciente: aun utilizando un algoritmo tan simple como el de ordenación por selección, la com-plejidad resulta ser de O(N2/2), siendo N el numero de monedas a ordenar. En este escenario, ello viene a suponer unas 200 comparaciones, para obtener un beneficio máximo.
Pero en el segundo escenario, el costo no es tan bajo: hay 2N formas de ordenar un conjunto de N monedas; en el ejemplo concreto, N = 20, se obtienen unas 220 posibilidades a considerar (aproximadamente, un millón), ver cuales son factibles y determinar cual maximiza el beneficio.
De lo anterior, se puede sacar la impresión (correcta) de que el segundo escenario supone un pro-blema “mas difícil” de resolver que el problema asociado al primer escenario. Pero aun falta in-troducir un nuevo aspecto: en su próximo viaje, el contrabandista se encuentra con una agradable sorpresa. Sus suministradores le informan de que se acaba de descubrir una tumba pre babilónica con 100 monedas distintas. ¿Cuál es la influencia en los dos escenarios?
En el primero, el contrabandista tendrá que realizar una ordenación que le supondrá unas 5000 comparaciones, para maximizar beneficios. En el segundo, sin embargo, ahora tendrá que consi-derar 2100 posibilidades distintas, ¿cuánto tiempo le llevará la elección?
En el primer escenario, el comportamiento es polinomio: a medida que crece el tamaño del pro-blema (de 20 a 100, de 100 a 1000,...) hay que realizar mas operaciones, pero el crecimiento vie-ne dado por un factor cuadrático: de 20 a 100, será 52, de 100 a 1000, será 102...
En el segundo escenario, el comportamiento es exponencial: con añadir un único elemento, con incrementar en una unidad el tamaño del problema, el número de operaciones se multiplica por 2; cuando se pasa de 20 a 100 monedas, se pasa de 1,000,000 de posibilidades a 1,000,000,000,000,000,000,000,000.
Estos dos escenarios vienen a mostrar cual es la importancia de la escalabilidad de un problema y del comportamiento asintótico de los algoritmos resultantes. Usualmente, en Teoría de Compleji-dad se estima el comportamiento polinomio como deseable, y los problemas que pueden resol-verse con un algoritmo que presenta una función de orden polinómica se consideran tratables. Cuando no se puede encontrar un algoritmo polinómico para resolver el problema, tal y como ocurre en el segundo escenario, el problema se considera intratable.
Y esto lleva al “dilema del informático”: no hay resultados que permitan estimar cuando un pro-blema puede resolverse por medio de un algoritmo polinómico, a no ser, claro esta, que tal algo-ritmo se haya encontrado. Por lo tanto, no hay ningún resultado teórico que permita establecer que un determinado problema es, por naturaleza, intratable: solo puede afirmarse que el mejor algoritmo conocido hasta el momento tiene una complejidad superior a la polinómica. Una forma de atacar este “dilema” consiste en establecer clases de problemas, de forma que problemas con la misma dificultad estén en la misma clase. Esta clasificación, además, dota al informático de una herramienta interesante en su objetivo de encontrar algoritmos eficientes: si todos los pro-blemas de una determinada clase son de la misma dificultad que un problema que es representan-te de esa clase, cualquier resultado o mejora que se obtenga para dicho problema, podrá aplicarse a todos los demás de su misma clase.
gracias
