UNIDAD 5

SOLUCIÓN POR BÚSQUEDA EXHAUSTIVA

JUSTIFICACIÓN 


La búqueda 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. 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.

Existen dos caminos para manejar esta búsqueda sistemática y ordenada; La primera se denomina como"Tanteo sistemático por acotación del error" o "acotación del error" donde se generan respuestas tentativas a las cuales sometemos a un proceso de verificación para validar cuales son la solución o soluciones reales.

La segunda alternativa se la conoce como "Búsqueda exhaustiva por búsqueda de soluciones", o simplemente "Construcción de Soluciones". Este esquema depende de las características de solución que plantea el enunciado. Cada problema tendrá un esquema de construcción particular para el.

De acuerdo a lo dicho, la estrategia general "Búsqueda Exhaustiva", se aqplica a travás de dos estrategias particulares descritas en los párrafos anteriores.


                                                             OBJETIVOS
1. Aplicar las estrategias de búsqueda exhaustiva en la resolución de los problemas.
2. Reconocer los tipos de problemas que admiten el uso de esta estrategia.
3. comprender la utilidad de la estrategia que nos ocupa.




LECCIÓN 11 PROBLEMAS DE TANTEO SISTEMÁTICO POR ACOTACIÓN DEL ERROR


      Estrategia de tanteo sistemático por acotación de error

El tanteo sistemático por acotación de error consiste en definir el rango de todas las soluciones tentativas del problema, evaluamos los extremos del rangopara verificar que las respuestas están en él, y luego vamos explorando las 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.

EJERCICIO 1: En una máquina de venta de juguetes 12 niños compraron pelotas y carros. todos los niños compraron solamente un juquete. Las pelotas valen 2 um y los carros valen 4um. ¿Cuántas pelotas y carros compraron en total si gastaron 40um entre todo?



¿Cuál es el primer paso para resolver el problema?
Leer el enunciado, encontrar los datos 

¿Qué tipos de datos se dan en el problema?
Variables cualitativas y cuantitativas

¿Qué se pide?
 ¿Cuántas pelotas y carros compraron en total si gastaron 40um entre todo?

Hacer la tabla de valores



Pelotas
1
2
3
4
5
6
7
8
9
10
11
Carros
11
10
9
8
7
6
5
4
3
2
1
total
26




36

40


46
 

 Respuesta:

12 niños cogieron 8 pelotas  y 4 carros
 

Estrategia binaria para el tanteo sistemático

El método seguido para encontrar cual es las soluciones tentativas es la respuestas correctas 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 número de conejos. o el número de chocolatesm o caramelos.
Luego le aplicamos el criterio de validación (el número 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 puntointermedio que divide el rango en dos porciones y le aplicamos una validación a dicho punto. Si esa no es la solución, entonces podemos identificar en que porción está la respuesta. Como resultado de esta respuesta terminamos con otro nuevo rango que tiene la mitad de las soluciones tentativas que tiene el rango original.

Repetimos el paso anterior comenzando por identificar el nuevo punto medio que divide el nuevo rango en dos porciones y repetimos la validación en este punto. si no hemos acertado la respuesta, terminamos con otro rango que tiene la cuarta parte de la soluciones tentativas que tiene el rango del inicio del problema.
Repetimos esto hasta encontrar la respuesta del problema.


Número de soluciones tentativas
2
4
8
16
32
64
128
256
1024
Número de evaluaciones para obtener la respuesta.
1
2
3
4
5
6
7
8
10

PRÁCTICA 1 . Coloca + y x entre los números indicados para que la igualdad sea correcta.


9 x 6 +3 +7 = 46


LECCIÓN 12   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.


EJERCICIO 1. Coloca los dígitos del 1 al 9 en los cuadros de la figura de abajo, de forma tal que cada una de las cuatro direcciones indicadas sume 13.

Datos:
·Números del 1 al 9
· La suma = 13.
Posibles Ternas:
1 + 3 + 9 = 13
1 + 4 + 8 = 13
1 + 5 + 7 = 13
2 + 3 + 8 = 13
2 + 4 + 7 = 13
2 + 5 + 6 = 13
3 + 4 + 6 = 13

Respuestas:

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

 

                                            ¿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 del problema. 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.




EJERCICIO.3
Identifica los valores de números enteros que corresponden a las letras O. S y U para que la operación identificada sea correcta. Cada letra solo puede tomar un único valor.
O
S
O
+ U
S
O
S
U
U
El enunciado solo se 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.


primer número
0
1
2
3
4
5
6
7
8
9
segundo numero
0
1
2
3
4
5
6
7
8
9
suma de los dos números(el 1 se lleva a la columna de la izquierda)
0
2
4
6
8
10
12
14
16
18


Veamos que el 1+1 da 2, pero el 6+6 da 12. Coloco el 2 y llevo 1. De esta formas S y O pueden ser los pares (0 y 5), (1 y 6), (2 y 7), (3y y (4 y 9). Noten que en los pares el primer número esta entre 0 y 4 y el segundo entre 5y 9. Las sumas de los números del 5 y9 consigo mismo llevan 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 número 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 cero hay que descartarlo porque cero más cero 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 numero diferente al de los términos de la suma.

O
0
1
2
3
4
U
0
2
4
6
8













Luego que tenemos los posibles valores de O y U, podemos determinar los valores correspondientes para la S.
O
0
1
2
3
4
U
0
2
4
6
8
S

6
7
8
9







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

O
0
1
2
3
4
U
0
2
4
6
8
S

6
7
8
9
O+U +1
4
7
10
13

A partir de esta última tabla podemos eliminar los valores de 3 y 4 para 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 que O+ U + R
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:


2
7
2
4
7
2
7
4
4

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. Algunas ayudas en este tipo de problemas:

  • Cuando se suman dos números iguales en la primera columna de la derecha el resultado de la suma es un número par, como se muestra n la tabla en la tabla que hicimos en el ejercicio 3.
  • Cuando se suman dos números iguales en otras columnas diferentes a la primera de la derecha el resultado de la suma es un numero par si la suma de la columna a la derecha es menor de 10, y es un número impar si la suma de la columna a la derecha es igual o mayor a 10.
  • Si en una columna los dos sumados son iguales entre si y también son iguales al resultado, hay dos 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.
  • Si el resultado de la suma tiene una cifra más que el número de columnas, el número de la izquierda es un1.
  • A medida que voy identificando números o relaciones entre ellos puedo ir construyendo una tabla que me ayuda a descartar posibles soluciones que tengan para dos letras diferentes un mismo valor numérico.





No hay comentarios:

Publicar un comentario

Suscribirse a: Entradas (Atom)