Scribd
Cargar
12 vistas2 páginas

Rutas Óptimas: Viajero y Robot en Laberintos

El documento describe dos problemas de búsqueda: el Problema del Viajero entre Ciudades y el Robot en el Laberinto. En el primero, se utiliza el algoritmo de Dijkstra para encontrar la ruta más corta de A a G, que es A -> C -> G con una distancia total de 17 km. En el segundo, se aplica BFS para que el robot se mueva desde (1, 1) hasta (4, 4) en 6 movimientos, evitando obstáculos.

Cargado por

aleshdesigncompanyweb
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd
12 vistas2 páginas

Rutas Óptimas: Viajero y Robot en Laberintos

El documento describe dos problemas de búsqueda: el Problema del Viajero entre Ciudades y el Robot en el Laberinto. En el primero, se utiliza el algoritmo de Dijkstra para encontrar la ruta más corta de A a G, que es A -> C -> G con una distancia total de 17 km. En el segundo, se aplica BFS para que el robot se mueva desde (1, 1) hasta (4, 4) en 6 movimientos, evitando obstáculos.

Cargado por

aleshdesigncompanyweb
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd

Problema 1: El Problema del Viajero entre Ciudades

1. Definir el problema en términos de búsqueda.

• Estado inicial: Ciudad A

• Estados finales: Ciudad G

• Acciones disponibles: El agente puede viajar de una ciudad a otra siguiendo las
carreteras. Cada acción tiene un costo (distancia en kilómetros).

• Modelo de transición: Viajar de una ciudad a otra.

• Función de costo: La suma de las distancias de las carreteras recorridas.

2. Aplicar un algoritmo de búsqueda.

Usaremos el algoritmo de búsqueda de costo uniforme (o Dijkstra) para encontrar la ruta


más corta. Este algoritmo garantiza que la primera vez que se expande un nodo, se ha
encontrado la ruta más corta hasta ese nodo.

3. Solución óptima:

La ruta más corta de A a G es:

A -> C -> G con una distancia total de 17 km.


Problema 2: El Robot en el Laberinto

1 2 3 4
1 R _ X _

2 _ X _ _

3 _ _ X _

4 _ _ _ O

R: Robot (posición inicial en (1,1))

O: Objetivo (posición final en (4,4))

X: Obstáculos (el robot no puede moverse a estas celdas)

-: Camino libre

Conjunto de estados: Las celdas que el robot puede visitar, excluyendo los obstáculos (celdas
X).

Estado inicial: El robot comienza en la celda (1, 1).

Estado final: El objetivo es alcanzar la celda (4, 4).

Acciones disponibles: El robot puede moverse a las celdas adyacentes (arriba, abajo,
izquierda, derecha), siempre que no haya un obstáculo y no salga de la cuadrícula.

Modelo de transición: Cada acción mueve al robot de una celda a otra, si está libre.

Función de costo: El número de movimientos realizados.

Utilizaremos BFS porque expande los nodos nivel por nivel y asegura que cuando se alcanza el
objetivo, se ha recorrido la menor cantidad de movimientos.

La ruta más corta desde (1, 1) hasta (4, 4) es:

(1,1) → (2,1) → (3,1) → (3,2) → (4,2) → (4,3) → (4,4)

Número de movimientos:

El robot necesita realizar 6 movimientos para llegar al objetivo.

También podría gustarte