Bitácora

Se repasan rápidamente métodos de búsqueda vistos anteriormente

Se repasa el hash

• Características
• Métodos para definir llaves
• Colisiones

Pathfindig

• Definición
• Características
• Técnicas

Apuntes

Pathfindig

Encuentra la ruta mas corte entre dos puntos

Técnicas

Depende del contexto

• Meta quieta o en movimiento

• Hay obstáculos

• La ruta mas corta es la mejor decisión

• Forma más sencilla (Sin obstáculos)

• Random

  • Si se topa un obstáculo toma una decisión random
  • Podría no encontrar el objetivo

• Obstacle tracing

  • Una decisión a la vez
  • Rodear obstáculo
  • Podría no encontrar el objetivo

• Breath-First Search (BFS)

  • Recorre los vecinos de la posición en la que estoy
  • Encuentra sí o sí
  • Puede tardar mucho

• Deph-First Search

  • Toma decisiones para saber cual es la celda siguiente a analizar y analiza la cercanas a esta
  • Se puede usar con recursividad pero puede ocasionar un Stack overflow
  • Como solución se puede hacer de manera iterativa

• Best First Search

  • Parecido al BFS, pero utiliza un heuristico
  • Busca tomar una decisión cercana a la mejor
  • Puede no dar la ruta mas cercana, pero lo da mas rapido
  • Ejemplo A*

Cómo validar que la complejidad teórica de un algoritmo se cumple en la práctica

R/ Sacar los resultados incrementando los input y comparando el incremento de los resultados cumplen con la formula