Teoría de búsqueda garantizada

La teoría de búsqueda garantizada (o teoría de búsqueda , abreviada como TGP ) es una rama de las matemáticas que estudia las propiedades de búsqueda en grafos y espacios topológicos .

En términos generales, una de las principales tareas de TGP se formula de la siguiente manera. Hay perseguidores en el campo de búsqueda , a quienes se les debe garantizar que atraparán al llamado evasor , cuya información de velocidad y ubicación falta. Todo el mundo se mueve continuamente por el campo de búsqueda . Estamos obligados a encontrar el número mínimo de perseguidores que están garantizados para poder atrapar al evasor. Una característica numérica que describe el número mínimo de perseguidores necesarios para atrapar a un evasor se llama número de búsqueda de arena . [una]

Por ejemplo, el número de búsqueda del segmento es igual a : basta con poner al perseguidor en uno de los extremos del segmento, desde donde irá al otro extremo, donde tiene la garantía de atrapar al evasor. Y en el círculo, un perseguidor ya no es suficiente, ya que el evasivo se mantendrá en un punto diametralmente opuesto a este perseguidor. En un gráfico con la forma de la letra "T", un perseguidor tampoco es suficiente, porque al llegar a la "bifurcación", no podrá adivinar con certeza cuál de las dos partes restantes es el evasor. Pero dos perseguidores serán suficientes, por lo tanto, el número de búsqueda de este gráfico es igual a .

En el caso de un gráfico arbitrario, el problema de encontrar el número de búsqueda permanece abierto . [una]

Historia

Es curioso que por primera vez el espeleólogo Breish planteó la cuestión del menor número de perseguidores. Imagina que en alguna cueva, compuesta de pasajes y pozos de acceso, se perdió un desafortunado explorador, a quien debemos salvar. Tenemos un mapa de la cueva (gráfico) a nuestra disposición, pero el número de rescatistas es limitado. El hecho de que un espeleólogo perdido quiera reunirse con los rescatadores no facilita nuestra tarea cuando se trata de una salvación garantizada. Puede correr sin rumbo fijo por la cueva a una velocidad desconocida. Se requiere desarrollar un plan de búsqueda que garantice el rescate del espeleólogo, es decir, excluyendo cualquier posibilidad de rebasarlo. [2]

El problema de encontrar el número de búsqueda fue planteado por primera vez de forma independiente por los matemáticos Torrance Parsons [3] y Nikolai Petrov [4] en la década de 1980. Sus artículos contenían una solución al problema de búsqueda de árboles . Después de algún tiempo, se demostró [5] que el problema de encontrar el número de búsqueda es NP-completo . En el mismo artículo, se caracterizaron todos los gráficos con un número de búsqueda inferior a 4. En 1989, P. A. Golovach demostró [6] que las formulaciones topológica y combinatoria del problema de búsqueda son equivalentes. Más tarde (en una formulación ligeramente diferente) se demostró [7] que entre todas las búsquedas óptimas en un gráfico se puede destacar una búsqueda monótona. En los trabajos enumerados anteriormente, nos ocupamos de la búsqueda en gráficos. En 2022, D. A. Grishmanovsky planteó y estudió el problema de la búsqueda en un espacio topológico.

Secciones de teoría de búsqueda garantizada

Teoría de búsqueda finita garantizada

La Teoría de búsqueda garantizada finita (TFG), o la teoría de búsqueda garantizada en gráficos, es una sección de la teoría de búsqueda garantizada, en la que cualquier búsqueda utiliza un número finito de perseguidores, se dedica a encontrar los números de búsqueda de gráficos y estudiar el propiedades de búsqueda en grafos combinatorios .

Teoría analítica de la búsqueda garantizada

Teoría analítica de la búsqueda garantizada (ATGP): se ocupa del estudio de las búsquedas utilizando un conjunto infinito de perseguidores. En ATGP, es importante que los conjuntos, de una forma u otra relacionados con el área en estudio, sean siempre medibles .

Aplicaciones

Una de las primeras aplicaciones de TGP fue en los sistemas de control de misiles . Las tareas para estos sistemas fueron formuladas por Rufus Isaacs de RAND Corporation [8] . Algunos científicos creen que THP se puede utilizar para crear programas antivirus. Esta es la opinión del conocido experto Bienstock [9] :

Considere el comportamiento de un virus informático en una red. Suponiendo lo peor, debemos sospechar que toda la red está infectada, por lo que los nodos deben limpiarse. Supongamos que tenemos varias copias de programas de vacunas y hacer más copias no es práctico. Por otro lado, una estrategia mal diseñada puede conducir a la reinfección del huésped. Por lo tanto, el desafío es desarrollar una estrategia de limpieza que utilice la menor cantidad de copias de los programas de vacunas.

Además, TGP tiene aplicaciones [1] en áreas de actividad científica tales como

y muchos otros.

Véase también

Notas

  1. ↑ 1 2 3 Abramovskaya, Petrov, 2013 .
  2. ↑ Breish, 1967 .
  3. ↑ Parsons, 1976 .
  4. ↑ Petrov, 1982 .
  5. ↑ Meguido, Hakimi, Garey, 1988 .
  6. ↑ Golovach, 1989 .
  7. ↑ Lapaugh, 1993 .
  8. ↑ Isaacs, 1965 .
  9. ↑ Bienstock, 1991 .

Literatura