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 enunciado. En este tipo de problemas generalmente se identifican características de la solución, y en base a estas características se procede en proceso de búsqueda sistemática de una respuesta.

El proceso que se sugiere en esta estrategia es una búsqueda ordenada o disciplinaria, que nos permite evitar la prueba al alzar con los consiguientes 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; 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ática por acotación del error”, o simplemente “acotación del error” por estar implícito en el tanteo al generar soluciones tentativas. Este esquema tiene dos momentos, el primero, con la construcción de una tabla se soluciones tentativas, y el segundo momento con la validación para determinar cuáles de ellas son realmente soluciones. El tanteo sistemático consiste en definir ordenadamente el conjunto de todas las soluciones tentativas del problema. Para la selección de la respuesta es importante seguir una estrategia apropiada que nos ayude a manejar los números generalmente elevados de soluciones tentativas hasta encontrar a la que se ajusta a los requerimientos del problema, que es la que llamamos respuesta definitiva o real.

La segunda alternativa s ele denomina “búsqueda exhaustiva por construcción de soluciones”, o simplemente “construcción de soluciones”. Este esquema depende las características de la solución que plantea el enunciado. Cada problema tendrá un esquema de construcción particular para él.

OBJETIVOS:

A través de la unidad se pretende que los visitantes sean capaces de

1. Aplicar las estrategias de búsqueda exhaustiva en la solución de problema.

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

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

LECCIÓN 1.- PROBLEMAS DE TANTEO SISTEMÁTICO POR ACOTACIÓN DEL ERROR

Estrategia 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 del problema. Esa solución tentativa es la respuesta buscada.

Ejemplo:
En una máquina de venta de golosinas 12 niños compraron caramelos y chocolates. Todos los niños compraron solamente una golosina. Los caramelos valen 2Um y los chocolates 4Um.¿Cuántos caramelos y cuantos chocolates compraron los niños si gastaron entre todos 40Um?

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

¿Qué tipos de datos se dan en el problema?
El número de niños , el precio de los caramelos y chocolates y por último la cantidad exacta que gastaron.

¿Qué se pide?
Saber cuántos caramelos y chocolates compraron los niños si entre todos gastaron 40Um.

¿Cuáles podrían ser las posibles soluciones? Haz una tabla de valores.





Debemos fijarnos en el par de posibilidad que nos da el total de dinero que son 40Um. y el número de niños que son 12.

¿Cuál es la respuesta?
Compraron 8 chocolates y cuatro caramelos.

¿Qué estrategia aplicamos?
Hemos aplicado la estrategia de conteo sistemático por acotación de error.

ESTRATEGIA BINARIA PARA EL TANTEO SISTEMÁTICO

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

Ordenamos el conjunto de soluciones tentativas de acuerdo a un criterio. Por ejemplo, el numero de conejos, o el numero chocolates o caramelos. Luego aplicamos el criterio de validación (el numero de patas o 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 en 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 qu 

Repetimos el paso anterior comenzando por identificar el nuevo punto intermedio que divide el un rango en dos porciones 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. El número de evaluaciones necesarias con este método es como sigue.

Ejemplo:

Esta práctica consiste en un juego. Seleccionar dos alumnos. Uno piensa su número entre 1 y 128 ambos incluidos que lo va a escribir en un papel que mantiene guardado. el otro alumno trata de adivinar el número, para esto solo puede hacer preguntas cuya respuesta sea un "si" o un "no".Anota el número de preguntas que hizo cada uno de los alumnos que adivinaba el número. Discutir los resultados.

Si la persona responde en menos de 7 preguntas hay dos alternativas, o el número es muy "fácil" o la persona tiene mucha suerte adivinando.
Si la persona gastó 8 o más preguntas es que no aplicó correctamente la estrategia binaria.


LECCIÓN 2: PROBLEMAS DE CONSTRUCCIÓN DE SOLUCIONES.

ESTRATEGIA DE BÚSQUEDA EXHAUSTIVA POR CONSTRUCCIÓN DE SOLUCIONES

La búsqueda exhaustiva por construcción de soluciones 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. La ejecución de esta estrategia generalmente permite establecer no solo una respuesta, sino que permite visualizar la globalidad de soluciones que se ajustan al problema.

Ejemplo:
Coloca los dígitos del 1 al 9 en los cuadros de la figura de abajo, de forma tal que cada columna y cada diagonal sumen 15.
¿Cuáles son todas las ternas posibles?

8+1+6=15
3+5+7=15
4+9+2=15
8+3+4=15
1+5+9=15
6+7+2=15
6+5+4=15
8+5+2=15

¿Cuáles grupos de 3 ternas sirven para construir la solución?
1+5+9=15
6+7+2=15
8+3+4=15
¿Cómo quedan las figuras?
Práctica 2: .Coloca los dígitos del 1 al 9 en los cuadros de la figura de abajo , de forma tal que todos los grupos de tres recuadros que indican sumen 12
¿Cuáles son las todas ternas posibles? Nota que las ternas de este caso son diferentes a las anteriores . Ahora son los números del 1 al 9 y las ternas deben sumar 12.
4+2+6= 12
8+3+1=12
4+3+5=12
9+1+2=12
7+4+1=12
3+7+2=12
¿Cómo podemos distribuir las ternas en los cuadros?Nota que hay unos cuadros que participan en más sumas que otros; hay un cuadro que participa en 4 sumas; es decir, el número que va ahí debe estar incluido en cuatro ternas . Puedes hacer una tabla de veces que aparece en ternas cada número del 1 al 9.
5+3+4=12
4+2+6=12
4+7+1=12
3+1+8=12
¿Cómo queda la figura?                                                Podemos buscar información en el enunciado del problema, también podemos encontrar la a partir de la solución que se pide en el problema como lo he podido comprobar en el ejercicio anterior.

¿DÓNDE BUSCAR LA INFORMACIÓN?

En este tipo de problemas donde se aplica la búsqueda de soluciones (por acotación o por construcción de soluciones) lo primero que se hace es la búsqueda de la información que vamos a usar. En primer lugar se busca la información en el enunciado de los problemas. En las prácticas anteriores la forma de la figura, los números que vamos a usar y la condición que se le impone están todos en el enunciado.

Sin embargo, también podemos extraer información a partir de la solución que se pide en el problema. Por ejemplo, en el ejemplo 2 de esta lección la información de que hay número participando en 4 ternas diferentes de la figura es extraída de la solución.

Podemos buscar información en el enunciado del problema, también podemos encontrar la a partir de la solución que se pide en el problema como lo he podido comprobar en el ejercicio anterior.

Ejemplo:

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

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 1+1 da 2, pero el 6+6 da 12. Coloco el 2 y llevo1. De esta forma S y O pueden ser los pares (0 y 5), (1 y 6), (2 y 7), (3 y 8) y (4 y 9). Noten que en los pares el 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 lleva 1 a la columna de la izquierda. Esto nos obliga a que el número a colocar en la primera columna de la derecha debe ser el menor del par. Si colocamos el mayor llevaríamos un 1 adicional para la suma de la segunda columna, con lo cual las sumas de las dos columnas no tendrían 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 numero entre 0 y 4. Con esa información podemos encontrar los valores correspondientes a la U. El valor de cero hay que descartarlo porque cero mas cera en la primera columna debería dar cero también y vemos en la suma del enunciado que la suma de la primera columna es un número 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 a la tercera columna.

hacer notar que debe cumplirse que O+U+1 debe ser igual a S. eso solo se da para el valor de 2 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 del partir enunciado. También debemos para O. por lo tanto podemos descartar valores 1,3 y 4 de la O en la tabla.

Reemplazando los valores matemática correcta para verificar la respuesta nos da:

272+472= 744

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

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

LECCIÓN 3: PROBLEMAS DE BÚSQUEDA EXHAUSTIVA. EJERCICIOS DE CONSOLIDACIÓN.

Ejemplo: 

El señor Pedro le pide a un compañero, que adivine la edad de sus tres hijas. Le da como información que el producto de las edades es 36, y que la suma de las edades es igual al número de empleados de la empresa. El compañero le dice que no tiene suficiente información, y Pedro le dice que tuvo tres hijas porque no quería tener una única hija. ¿Cuáles son las edades de cada una de las hijas de Pedro?

¿Qué información puedes obtener del enunciado?

El producto de las edades de las hijas es 36.

Que la suma de las edades es igual al número de los empleados de la empresa.

Tuvo tres hija porque no quería tener hija única.

¿Cuáles son las ocho posibles tres edades cuyo producto sea 36?(Factores de 36=3*3*2*2*1).

¿Qué significa lo que Pedro le dice “que tuvo tres hijas porque no quería tener una hija única”.

que Pedro tuvo primero una hija y después quería tener una hija más pero le salieron gemelas.

Respuesta:

Las hijas de Pedro tienen las edades de nueve años y las dos últimas de dos años (gemelas).

Ejemplo:

El diagrama está formado por 10 círculos , cada uno de ellos contiene una letra . A cada letra le corresponde un dígito del 1 al 9 .Los números colocados en las intersecciones de los círculos corresponden a la suma de los números asignados a los dos círculos que se encuentran (por ejemplo, B y C deben de ser dos números que sumados dan 12). Que número corresponde a cada letra?

¿Qué relaciones puedes sacar de la figura?

A+B=7 F+H=7

B+C=12 G+H=11

D+C=6 I+H=9

E+C=14 A+H=5

¿Cómo derivamos la relación siguiente?

A+B+D+E+F+G+I+4C+4H+A=7+12+6+14+7+11+9+5

¿Cuánto es la suma de A+B+C+D+E+F+G+H+I = 45?

¿Puedo saber si C es par o impar?

La C es número impar porque está representada por el 5

¿Qué valores pueden tener A Y C?

A=2 y C=5

¿Qué valores pueden tener A y H?

A= 2 y H=3.