Teoría de la Información: Búsqueda Binaria

Búsqueda Binaria

Este post inaugura una serie de 5 pequeños artículos sobre Teoría de la Información. Se trata de dar un breve repaso a esta rama de las matemáticas mediante un ejemplo aplicado.

Los cinco artículos son: Búsqueda Binaria, Búsqueda Jerárquica, Shannon-Fano, Huffman y Entropía.

Pueden leerlos ya o esperar a que se vayan publicando diariamente durante esta semana.

El problema

Imaginen que tenemos que adivinar una letra de entre las siguientes: A, B, C, D, E, F, G y H. Imaginen además que tan sólo podemos hacer preguntas que se puedan responder con un “Si“ o un “No“. ¿Qué método usarían?

Bien, es de suponer que si tenemos que repetir el experimento muchas veces nos interesa un método que de media haga que el número de preguntas que tendremos que realizar hasta encontrar la letra correcta sea lo más pequeño posible. ¿Cuál será ese método?

Una solución sencilla

Si no sabemos nada más acerca de la probabilidad concreta que tiene cada letra de ser la correcta lo más normal es suponer que todas son equiprobables. Es decir, que todas salen (de media) el mismo numero de veces conforme realicemos más y más experimentos. En ese caso lo mejor es aplicar la búsqueda binaria.

La búsqueda binaria consiste en partir el conjunto en dos mitades y realizar una pregunta del estilo: ¿Está en la primera mitad? En caso afirmativo volvemos a aplicar el algoritmo sobre la primera mitad, en caso negativo lo aplicaríamos sobre la segunda.

En nuestro caso vamos a suponer que la letra correcta es la F, la secuencia de preguntas y respuestas seria la que sigue:

  • ¿Es la A, la B, la C o la D? No
  • ¿Es la E o la F? Si
  • ¿Es la E? No
  • Luego ya sabemos que es la F.

Como ven estamos reduciendo rápidamente el conjunto de posibles respuestas con cada pregunta. Cosa que nos hace adivinar muy rápidamente cual es la letra correcta.

En concreto y debido a la simetría del problema en este caso hacen falta exactamente 3 preguntas de media para saber cual es la letra correcta. Usaremos esta unidad, las preguntas de media, para comparar métodos entre sí.

Resumiendo

Teníamos un problema y hemos propuesto un método que tiene muy buena pinta para solucionarlo pero quizás podamos mejorar el resultado en aquellos casos en los que tengamos más datos sobre la solución del problema.

BOLAEXTRA: ¿Podemos hacerlo mejor? No se pierdan el próximo capítulo.

Escrito en 08/12/08 09:35 por Carlos Luna en las categorías:

Comentarios

Gravatar.com se ha roto

Esto me recuerda a cuando se busca al mejor dentro de un conjunto de jugadores (de algo) y se juega un torneo.

Jorge | 11/12/08 12:42 | #
Gravatar.com se ha roto

La búsqueda binaria es un problema de complejidad logarítmica… ¿realmente puede haber un interés (práctico) en mejorar eso?

Sergio Alvaré | 14/06/09 15:23 | #
Gravatar.com se ha roto

@Sergio Alvaré: Sí, si, por ejemplo, un elemento es mucho más probable que el resto. La búsqueda binaria es óptima cuando todos los elementos son equiprobables pero tremendamente ineficiente cuando hay grandes asimetrías.

Además estamos hablando de compresión de datos. No te niego que una longitud de palabra fija (el ASCII es el equivalente a la búsqueda binaria en codificación de textos) sea práctica para la mayoría de casos pero si quieres comprimirlos tienes que exprimir al máximo las asimetrías de las que hablo.

En imágenes, donde hay muchos datos y mucha redundancia es una burrada aplicar codificar en BMP (que, de nuevo, sería el equivalente a la búsqueda binaria en este contexto) y se opta con formatos que aprovechan esa redundancia para comprimirlas sin perder información (como el PNG).

Por último el algoritmo de Huffman, que encuentra la codificación óptima, es sencillo y eficiente. Parece claro que hay pocos motivos para no usarlo.

Los otros 4 posts de esta serie lo explican un poquito mejor ;-)

Carlos Luna | 14/06/09 17:37 | #
Gravatar.com se ha roto

MMM

Tengo una duda. A este tipo de búsqueda en que se reparte en dos mitades las posibles respuestas, ¿no se llama también “búsqueda dicotómica”?

Creo que se utiliza en listas ordenadas, donde la posición también aporta información, pero no estoy seguro. ¿Alguien puede confirmarlo? Gracias.

Pablo | 15/06/09 12:42 | #
Gravatar.com se ha roto

@Pablo: Efectivamente, Búsqueda Dicotómica es una manera bastante común de referirse a ese tipo de búsquedas.

Carlos Luna | 15/06/09 14:56 | #
Gravatar.com se ha roto

esta explicacion esta muy clara pero quisiera saber mas tengo que hacer un trabajo referente a este tema para explicarlo en clase con un algoritmo me puedes ayudar

lucybel blanco | 21/11/09 16:58 | #

Deja un Comentario

Quizás quieras usar textile para dar formato a tu comentario.

"linktext":http://       _em_       *strong*       -strike-       ^sup^       ~sub~
bq. Blockquote       # Lista numerada       * Lista no-numerada       ==html crudo, sin textile==

(no será mostrado) (http://...)