ui-cviko1/notebook/cviko3.ipynb

Queue / Fronta¶

In [1]:

queue = ["a", "b", "c", "d"]

In [2]:

queue.pop()

Out[2]:

'd'

In [3]:

queue

Out[3]:

['a', 'b', 'c']

Reprezentácia grafu¶

In [4]:

from typing import Optional

In [66]:

my_graph = {
    'A': ['B', 'C'],
    'B': ['A','D','E'],
    'C': ['A','F'],
    'D': ['B','G'],
    'E': ['B','G'],
    'F': ['C','G'],
    'G': ['D','E','F']
}

In [67]:

my_graph["A"]

Out[67]:

['B', 'C']

In [68]:

for neighbor in my_graph["A"]:
    print(neighbor)

B
C

In [69]:

start_node = "A"
goal_node = "G"

In [70]:

def search(graph: dict[str, list[str]], start: str, goal: str) -> Optional[dict[str, str]]:
    fifo = [start]
    visited = {start: None}

    while fifo:
        current_node = fifo.pop(0)

        if current_node == goal:    
            return visited
        
        for neighbor in graph[current_node]:
            if neighbor not in visited:
                visited[neighbor] = current_node
                fifo.append(neighbor)

    return None

In [71]:

search(my_graph, start_node, goal_node)

Out[71]:

{'A': None, 'B': 'A', 'C': 'A', 'D': 'B', 'E': 'B', 'F': 'C', 'G': 'D'}

In [72]:

def search(graph: dict[str, list[str]], start: str, goal: str) -> Optional[dict[str, str]]:
    fifo = [start]
    visited = {start: None}

    while fifo:
        current_node = fifo.pop(0)

        if current_node == goal:    
            return visited
        
        for neighbor in graph[current_node]:
            if neighbor not in visited:
                visited[neighbor] = current_node
                print(visited)
                fifo.append(neighbor)

    return None

In [73]:

result = search(my_graph, start_node, goal_node)

{'A': None, 'B': 'A'}
{'A': None, 'B': 'A', 'C': 'A'}
{'A': None, 'B': 'A', 'C': 'A', 'D': 'B'}
{'A': None, 'B': 'A', 'C': 'A', 'D': 'B', 'E': 'B'}
{'A': None, 'B': 'A', 'C': 'A', 'D': 'B', 'E': 'B', 'F': 'C'}
{'A': None, 'B': 'A', 'C': 'A', 'D': 'B', 'E': 'B', 'F': 'C', 'G': 'D'}

In [74]:

def reconstruct_path(visited: dict[str, str], start: str, goal: str) -> tuple[int, str]:
    steps = 0
    path = ""
    current = goal

    while current is not None:
        path = current + " -> " + path
        current = visited[current]
        steps += 1
    
    path = path.removesuffix(" -> ")
    return steps, path

In [75]:

steps, path = reconstruct_path(result, start_node, goal_node)

In [76]:

steps

Out[76]:

4

In [77]:

path

Out[77]:

'A -> B -> D -> G'

Prehľadávanie do šírky + nájdenie najkratšej cesty¶

In [88]:

import heapq

In [89]:

a = [3, 5, 1, 2, 6, 8, 7]

In [90]:

heapq.heapify(a)

In [91]:

a

Out[91]:

[1, 2, 3, 5, 6, 8, 7]

In [92]:

a = [2, 5, 3, 7, 6, 8]
heapq.heappush(a, 4)

In [93]:

a

Out[93]:

[2, 5, 3, 7, 6, 8, 4]

In [94]:

heapq.heappop(a)

Out[94]:

2

In [95]:

heapq.heappop(a)

Out[95]:

3

Uniform cost search¶

flowchart LR
    A<-->|4|C;
    A<-->|1|B;
    B<-->|1|D;
    B<-->|3|E;
    D<-->|4|G;
    E<-->|1|G;
    C<-->|2|F;
    G<-->|2|F;

In [98]:

my_graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('A',1), ('D', 1), ('E', 3)],
    'C': [('A', 4), ('F', 2)],
    'D': [('B', 1), ('G', 4)],
    'E': [('B', 3), ('G', 1)],
    'F': [('C', 2), ('G', 2)],
    'G': [('D', 4), ('E', 1), ('F', 2)]
}

In [109]:

def reconstruct_path(visited: dict[str, tuple[int, str]], start: str, goal: str) -> str:
    path = []
    current = goal
    while current is not None:
        path.append(current)
        current = visited[current][1]
    path.reverse()
    return path

In [115]:

def uniform_cost_search(graph: dict[str, list[tuple[str, int]]], start: str, goal: str) -> Optional[str]:
    priority_queue = [(0, start)]
    visited = {start: (0, None)}

    while priority_queue:
        current_cost, current_node = heapq.heappop(priority_queue)

        if current_node == goal:
            return current_cost, reconstruct_path(visited, start, goal)
        
        for neighbor, cost in graph[current_node]:
            total_cost = current_cost + cost

            if neighbor not in visited or total_cost < visited[neighbor][0]:
                visited[neighbor] = (total_cost, current_node)
                heapq.heappush(priority_queue, (total_cost, neighbor))

    return None

In [116]:

result = uniform_cost_search(my_graph, start_node, goal_node)

In [117]:

if result:
    total_cost, path = result
    print(f"Least cost path from {start_node} to {goal_node}: {' -> '.join(path)} with total cost {total_cost}")
else:
    print(f"No path found from {start_node} to {goal_node}")

Least cost path from A to G: A -> B -> E -> G with total cost 5