Contents

LAB 09 Recorridos sobre grafos

!wget --no-cache -O init.py -q https://raw.githubusercontent.com/rramosp/20192.L3/master/init.py
import init; init.init(force_download=False); init.get_weblink()

import init
from local.lib.rlxmoocapi import submit, session
import inspect
student = session.Session(init.endpoint).login( course_id=init.course_id, 
                                                session_id="UDEA", 
                                                lab_id="lab_09" )

LAB 09 Recorridos sobre grafos

Ejercicio 1

completa al siguiente función para que dada una especificación de un laberinto como en las notas devuelva las coordenadas de la casilla T. Por ejemplo:

my_grid = [".....X",
           "XX...X",
           "...X..",
           ".XX..X",
           ".X...T"]
              
find_target(my_grid)
(4,5)

observa que en la coordenada resultante el primer elemento es la columna y el segundo la fila.

el resultado ha de ser del tipo tupla

sugerencia: usa la función np.argwhere

def find_target(grid):
    import numpy as np
    target = # tu codigo aqui
    return target

comprueba tu código

my_grid = [".....X",
        "XX...X",
        "...X..",
        ".XX..X",
        ".X...T"]

find_target(my_grid)

registra tu solución en línea

student.submit_task(globals(), task_id="task_01");

Ejercicio 2

completa la siguiente clase para que implemente una cola con prioridades de forma que:

  • el método put añada elemnetos asociados a una prioridad

  • cada vez que se invoque el método get devuelva el elemento con la prioridad más baja y lo elimine de la cola.

  • si la cola no tiene elementos el método get ha de devolver None

  • el método empty ha de devolver True si la cola no tiene elementos y False si tiene alguno

def PriorityQueue(*args, **kwargs):
    
    class PriorityQueue_class:
        
        def __init__(self):
            self.elements = []

        def empty(self):
            return ### tu codigo aqui

        def put(self, item, priority):
            ### tu codigo aqui

        def get(self):
            return ### tu codigo aqui

    return PriorityQueue_class(*args,**kwargs)

verifica tu código. el siguiente ejemplo debe de recuperar los elementos en el siguiente orden:

    c 
    a
    b 
    None

q = PriorityQueue()

q.put("a", 20)
q.put("b", 30)
q.put("c", 15)

print (q.get())
print (q.get())
print (q.get())
print (q.get())

registra tu solución en línea

student.submit_task(globals(), task_id="task_02");

Ejercicio 3

observa el algoritmo de búsqueda cost_search que devuelve dos estructuras:

  • paths: un diccionario en el que, para cada posición, indica desde qué posición anterior se llegó con el menor coste desde la posición inicial (0,0).

  • costs: un diccionario en el que, para cada posición, indica cual es el menor coste de los posibles caminos para llegar a dicha posición.

Definición: el coste de un camino es la longitud del mismo

Observa como, desde paths, se puede recuperar el camino de menor coste a cualquier posición empezando desde un target dado un caminando hacia atrás.

P.ej. desde al target (2,4) (esquina inferior derecha), se llega desde el (2,3), y a este desde el (2,2), y a este desde el (1,2), y a este desde el (0,2) y a este desde el (0,1) y a este desde el (0,0). Con lo que el camino completo desde el (0,0) es el siguiente:

(0,0), (0,1), (0,2), (1,2), (2,2), (2,3), (2,4)

con un coste de 6.

import pandas as pd
import numpy as np
EMPTY, WALL, TARGET, USED = ".","X","T","o"
c  = pd.Series({"EMPTY": ".", "WALL":"X", "TARGET":"T", "USED":"o"})
ci = pd.Series({".": 0, "X": 255, "T":100, "o":200})


def possible_moves(grid, y,x):
    moves = [ [y,x+1], [y-1,x], [y,x-1], [y+1,x]]

    moves = [(my,mx) for my,mx in moves if mx>=0 and mx<len(grid[0]) and \
                                           my>=0 and my<len(grid) and grid[my][mx]!=c.WALL]
    return moves

def cost_search(grid):
    
    start = (0,0)
    step_cost = 1
    frontier = PriorityQueue()
    frontier.put(start, 0)
    came_from   = {}
    cost_so_far = {}
    came_from[start]   = None
    cost_so_far[start] = 0

    while not frontier.empty():
        current = frontier.get()
        y,x = current
        if grid[y][x] == c.TARGET:
            break

        for next in possible_moves(grid,y,x):
            new_cost = cost_so_far[current] + step_cost
            if next not in cost_so_far or new_cost < cost_so_far[next]:
                cost_so_far[next] = new_cost
                priority = new_cost
                frontier.put(next, priority)
                came_from[next] = current

    return came_from, cost_so_far

Completa la función recover_path más abajo para que dado paths, costs y una tupla representando una posición target devuelva

  • el camino especificado en paths para llegar a target

  • el coste del mismo

por ejemplo, con los valores del ejemplo anterior:

> camino, coste = recover_path(path, cost, (2,4))
> print camino
> print coste

[(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (2, 3), (2, 4)]
6

my_grid = ["....X",
           "XX.XX",
           ".X..T"]

path, cost = cost_search(my_grid)

path

cost

Completa esta función ” recover_path “

def recover_path(path, cost, target):
    # tu codigo aqui
    camino = ...
    coste  = ...
    return camino, coste

prueba tu código

camino, coste = recover_path(path, cost, (2,4))
print (camino)
print (coste)

registra tu solución en línea

student.submit_task(globals(), task_id="task_03");

previous

LAB 08 Grafos

next

LAB 10 Algoritmos sobre grafos