METODOS DE BUSQUEDA

 

 

 

 

  INSTITUTO TECNOLÓGICO DE COMITÁN

 

NOMBRE DEL ALUMNO:

Gadiela Diaz Diaz

 

NUMERO DE CONTROL:

20700214

 

SEMESTRE:

8 º (Octavo)

 

CARRERA:

Ingeniería en Sistemas Computacionales

 

 

Comitán de Domínguez Chiapas a 10 de marzo del 2024

 

  

METODOS DE BUSQUEDA

Los métodos de búsqueda son algoritmos utilizados para encontrar soluciones a problemas dentro de un espacio de búsqueda. Estos métodos son fundamentales en la informática, la inteligencia artificial, la optimización y muchas otras áreas. Aquí hay una descripción de algunos métodos de búsqueda comunes:

Búsqueda en Anchura (BFS):

En la búsqueda en anchura, también conocida como BFS (del inglés Breadth-First Search), se explora un grafo o árbol nivel por nivel. Es decir, se comienza por el nodo inicial y luego se exploran todos los nodos vecinos de ese nodo, luego se exploran los nodos vecinos de esos nodos, y así sucesivamente.

• Proceso:

  1. Se comienza en el nodo inicial y se lo marca como visitado.
  2. Se agregan todos los nodos vecinos del nodo inicial a una cola.
  3. Se saca un nodo de la cola y se marca como visitado.
  4. Se agregan todos los nodos vecinos de ese nodo a la cola (si no han sido visitados previamente).
  5. Se repiten los pasos 3 y 4 hasta que se visiten todos los nodos o hasta encontrar el objetivo.

• Características:

  • Garantiza que la solución encontrada sea la más cercana al nodo inicial.
  • Requiere una cantidad significativa de memoria, ya que se deben almacenar todos los nodos a visitar en la cola.
  • Es útil cuando se necesita encontrar la solución más cercana a un nodo inicial, como en problemas de búsqueda de rutas.

Búsqueda en Profundidad (DFS):

En la búsqueda en profundidad, también conocida como DFS (del inglés Depth-First Search), se explora un grafo o árbol descendiendo por un camino concreto tanto como sea posible antes de retroceder. Es decir, se sigue un camino hasta llegar al final y luego se retrocede para explorar otro camino.

• Proceso:

  1. Se comienza en el nodo inicial y se marca como visitado.
  2. Se elige un nodo vecino no visitado y se explora recursivamente desde ese nodo.
  3. Se repite el proceso hasta que no haya nodos vecinos no visitados, entonces se retrocede al nodo anterior y se continúa explorando otros caminos.

• Características:

  • Puede encontrar soluciones que estén más profundamente anidadas en el grafo que las encontradas por BFS.
  • Utiliza menos memoria que BFS, ya que no es necesario mantener una cola de nodos por visitar.
  • Puede entrar en bucles infinitos si no se manejan adecuadamente los ciclos o si el grafo no es acíclico.

Comparación:

• Memoria:

  • BFS generalmente requiere más memoria debido a la cola de nodos por visitar.
  • DFS requiere menos memoria ya que no mantiene una cola, sino que utiliza la pila de llamadas de la recursión.

• Velocidad:

  • BFS tiende a ser más lenta que DFS en grafos densos debido a la necesidad de mantener la cola.
  • DFS puede ser más rápido en grafos densos debido a su uso de la recursión y a la exploración más profunda de un camino antes de retroceder.

La elección entre BFS y DFS depende de las características del problema específico y de las estructuras de datos utilizadas.

1. Búsqueda Lineal (Sequential Search):

   • Este es el método más básico donde los elementos se buscan uno por uno en una secuencia hasta que se encuentra el elemento deseado o se llega al final.
   • Es simple pero puede ser ineficiente para grandes conjuntos de datos.
   • 
     

2. Búsqueda Binaria (Binary Search):

   • Es un método eficiente para buscar en listas ordenadas.
   • La lista se divide en mitades y se descarta la mitad en la que no puede estar el elemento buscado.
   • Requiere que la lista esté ordenada previamente.
   • 
     

3. Búsqueda en Profundidad (Depth-First Search, DFS):

   • Se utiliza principalmente para recorrer o buscar en estructuras de datos como árboles o grafos.
   • Explora tanto como sea posible a lo largo de un camino antes de retroceder.
   • Puede entrar en bucles infinitos si no se manejan adecuadamente los ciclos.
   • 
     

4. Búsqueda en Anchura (Breadth-First Search, BFS):

   • Otra técnica para recorrer o buscar en estructuras de datos como árboles o grafos.
   • Explora todos los nodos vecinos al mismo nivel antes de pasar al siguiente nivel.
   • Generalmente requiere más memoria que la búsqueda en profundidad.
   • 
     

5. Búsqueda Heurística (Heuristic Search):

   • Utiliza heurísticas o reglas generales para buscar soluciones en espacios de búsqueda grandes o complejos.
   • Ejemplos incluyen la búsqueda A* y la búsqueda Greedy.
   • Son especialmente útiles cuando no es posible examinar todas las soluciones posibles.
   • 
     

6. *Búsqueda A (A-star Search)**:

   • Un algoritmo de búsqueda informada que utiliza una función de costo heurística para encontrar el camino más corto entre un nodo inicial y un nodo objetivo.
   • Combina la información de costo y una estimación heurística para guiar la búsqueda hacia la solución óptima.
   • Es ampliamente utilizado en problemas de búsqueda de caminos en grafos y en inteligencia artificial.
   • 
     

7. Algoritmos Genéticos (Genetic Algorithms):

   • Inspirados en la teoría de la evolución natural, estos algoritmos se utilizan para encontrar soluciones aproximadas a problemas de optimización y búsqueda.
   • Utilizan conceptos como selección, cruce y mutación para evolucionar una población de posibles soluciones hacia una solución óptima o cercana a la óptima.

Estos son solo algunos ejemplos de métodos de búsqueda. La elección del método adecuado depende del problema específico que estés tratando de resolver, así como de las características del espacio de búsqueda y los recursos disponibles.