UNIDAD V

UNIDAD V: Solución por Búsqueda exhaustiva

Justificación:

La búsqueda exhaustiva es una estrategia que se utiliza para resolver problemas en los cuales no es posible hacer una representación a partir de su enunciad.

El proceso que se sugiere en esta estrategia es una búsqueda ordenada o disciplinada, que nos permite evitar la prueba al azar con los siguientes resultados negativos y a veces frustrantes.

Existen dos caminos para manejar esta búsqueda sistemática y ordenada de una respuesta, la primera es generando respuestas tentativas a las cuales sometemos a un proceso de verificación para validar cuales son la solución o soluciones reales y la segunda es construyendo paso a paso una respuesta que cumpla con las características planteadas en el enunciado del problema.

A la primera alternativa se le denomina “Tanteo sistemático por acotación del error”, o simplemente “acotación del error”.

La segunda alternativa se le denomina “Búsqueda exhaustiva por construcción de soluciones”, o simplemente “construcción de soluciones”.

Objetivos:

1.      Aplicar las estrategias de búsqueda exhaustiva en la resolución de problemas.

2.      Reconocer los tipos de problemas que admiten el uso de esta estrategia.

3.      Comprender la utilidad de la estrategia que nos ocupa.

LECCION 1: Problemas de tanteo Sistemático por Acotación del error.

El tanteo sistemático por acotación del error consiste en definir el rango de todas las soluciones tentativas del problema, evaluamos los extremos del rango para verificar que la respuesta está en él, y luego vamos explorando soluciones tentativas en el rango hasta encontrar una que no tenga desviación respecto a los requerimientos expresados en el enunciado del problema. Esta solución tentativa es la respuesta buscada.

Ejemplo: Diez señoras entran a una librería para comprar libros y cuadernos. Cada una de las señoras compro una sola cosa. Los libros valen $8,00 y  cuadernos $2,00 ¿Cuántos  libros y cuadernos compraron las señoras si gastaron $38,00?

¿Cuál es el primer paso para resolver el problema?

Leer  el problema.

¿Qué tipos de datos se dan en el problema?

Diez  señoras entran a una librería, cada una de las señoras compro una sola cosa, los libros valen $8,00 y  cuadernos $2,00

 ¿Qué nos pide?

Encontrar cuánto dinero gastaron en los pasteles y galletas.

Representación:                              

   

Respuesta:

Las diez señoras gastaron $38,00 en librería al adquirir 3 libros y 7 cuadernos.

Estrategia binaria para el tanteo sistemático

El método seguido para encontrar cuál de las soluciones tentativas es la respuesta correcta se llama estrategia binaria. Para poder aplicar esta esta estrategia hacemos  lo siguiente:

Ordenamos el conjunto de soluciones tentativas de acuerdo a un criterio. Por ejemplo, el número de chocolates y caramelos.

Luego le aplicamos el criterio de validación (el costo de las golosinas) a los valores extremos para verificar si es uno de ellos la respuesta, o que la respuesta es una de las soluciones intermedias.

Continuamos identificando el punto intermedio que divide el rango de dos porciones y le aplicamos la validación a dicho punto. Si esa no es la solución, entonces podemos identificar en que porción del rango esta la respuesta. Como resultado de este paso terminamos con un nuevo rango que tiene la mitad de soluciones tentativas que tiene el rango original.

Repetimos el paso anterior comenzando por identificar el nuevo punto intermedio que divide el nuevo rango en dos posiciones y repetimos la validación en ese punto. Si no hemos acertado la respuesta, terminamos con otro nuevo rango que tiene la cuarta parte de las soluciones tentativas que tiene el rango del inicio del problema.

Repetimos esto hasta encontrar la respuesta al problema. Este método es muy efectivo para descartar soluciones tentativas incorrectas.

Ejemplo: Coloca signos + y x entre los números indicados para que la igualdad sea correcta. Dale prioridad a la operación de multiplicación, es decir, primero multiplica  y luego suma todos los términos al final.

a)      3    5    4    6    2 = 31

Si pongo todos +, queda 3+5+4+6+2 = 20 demasiado pequeño, tengo que multiplicar.

Si pongo todos x, queda 3x5x4x6x2 = 72, demasiado grande. Como 31 está más cerca de 20 que de 30, voy a ensayar soluciones con 3 sumas y una multiplicación. Tengo cuatro alternativas:

1.      3 + 5 + 4 + 6 x 2 = 24

2.      3 + 5 x 4 + 6 + 2 = 31

3.      3 + 5 + 4 x 6 + 2 = 34

4.      3 x 5 + 4 + 6 + 2 = 27

Ahora aplicamos el criterio que nos permita si la alternativa es válida o no.

La alternativa 2 nos permite obtener la respuesta que es la suma 31.

LECCION 2: Problemas de Construcción de Soluciones.

Estrategia de búsqueda exhaustiva por construcción de soluciones

 Esta es una estrategia que tiene como objetivo la construcción de respuestas al problema mediante el desarrollo de procedimientos específicos que dependen de cada situación.

Dónde buscar la información: En este tipo de problemas donde se aplica la búsqueda de soluciones lo primero que se hace es la búsqueda de la información que vamos usar. En primer lugar se busca la información del enunciado del problema.

EJEMPLO: Coloca los dígitos del 1 al 9 en, los cuadros de la figura de abajo tal que cada fila, cada columna y cada diagonal sumen 13.

¿Cuáles son todas las ternas posibles?

139

148

157

238

247

256

¿Cómo queda la figura?

                              

                            

Ejemplo 2: Identifica los valores de números enteros que correspondan a las letras por números para que correspondan a las letras O, S y U para que la operación indicada sea correcta. Cada letra solo puede tomar un único valor.

OSO +

USO

SUU

El enunciado solo nos plantea que reemplacemos las letras por números para que la operación sea correcta. El resto de la información tiene que salir de la respuesta.

En primer término observamos que tenemos S + S = U y O + O  = U. ¿Es posible que dos números diferentes den el mismo número? Hagamos la tabla que sigue para ayudarnos.

 

Vemos que el 1 +1 da 2, el 6 + 6 da 12. Coloco el 2 y llevo 1. De esta forma S y O pueden ser los pares ( 0 y5 ), ( 1 y 6 ), ( 2 y 7 ), ( 3 y 8 ) y ( 4 y 9 ). Noten que en los pares del primer número está entre 0 y 4 y el segundo entre 5 y 9. Las sumas de los números del 5 y 9 consigo mismo llevan 1 a la columna de la derecha debe ser el número menor del par. Si colocamos el mayor llevaríamos un 1 adicional para la suma de la segunda columna, con la cual la suma de las 2 columnas no tendría el mismo resultado. También se desprende de la operación indicada en el enunciado que U debe ser un número par.

Entonces, O es un número entre 0 y 4. Con esa información podemos encontrar los valores correspondientes a la U. el valor cero hay que descartarlo porque cero más cero en la primera en la columna debería dar cero también y vemos en la suma del  enunciado que la suma de la primera columna es un numero diferente al de los términos de la suma.

   

Luego que tenemos los posibles valores de O y U, podemos determinar los valores correspondientes para S.

 

Finalmente podemos calcular el resultado de sumar O con U y el 1 que llevamos de la segunda columna a la tercera columna.

A partir de esta última tabla podemos eliminar los valores de 3 y 4 para la O porque la suma tiene un  valor superior a 9 y eso obligaría a tener un cuarto digito que no es el caso a partir del enunciado. También debemos hacer notar que debe cumplirse O + U + 1 debe ser igual a S. Eso solo se da para el valor  de 2 para O. Por lo tanto podemos descartar los valores 1, 3 y 4 de la O en la tabla.

Reemplazando los valores en la operación para verificar la respuesta nos da:

272+

472

744

Esta es una operación matemática correcta. Por lo tanto es la respuesta del ejercicio.

En esta práctica obtuvimos una respuesta única, sin embargo existen casos en los cuales puede haber más de una solución. Algunas ayudas en este tipo de problemas:

1.      Cuando se suman 2 números iguales en la primera columna de la derecha el resultado de la suma es un número par.

2.      Cuando se suman dos números iguales en otras columnas diferentes a la primera de la derecha el resultado de la suma es un número par si la suma de la columna a la derecha es menor a 10 y es un número impar si la suma de la columna a la derecha es igual o mayor que 10.

3.      Si en una columna los 2 sumandos son iguales entre si y también son iguales al resultado, hay 2 posibilidades: si no se lleva de la columna anterior, es 0 + 0 = 0; y si se lleva 1 de la columna anterior, es 1 + 9 + 9 = 9 y llevo 1 para la columna de la izquierda.

4.      Si el resultado de la suma tiene una cifra más que el número de columnas, el número de la izquierda es un 1.

5.      A medida que voy identificando los números o relaciones entre ellos puedo ir construyendo una tabla que me ayuda a descartar posibles soluciones que tengan para dos letras diferentes a un mismo valor numérico.