NOVINKA - Online rekvalifikační kurz Python programátor. Oblíbená a studenty ověřená rekvalifikace - nyní i online.
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.

Diskuze: Python - BFS s pocitadlem

Aktivity
Avatar
Petr Los
Člen
Avatar
Petr Los:26.4.2021 13:28

snazim se v pythonu naprogramovat BFS zpusobem:

graf je ve formatu dictionary, vyhledavani sousedu funguje obousmerne - tzn. umi vyhledat sousedy jak z values, tak z keys, viz kod dale

  1. vyhledam sousedy 1. bodu ve fronte
  2. pokud jsem je jeste nenavstivil, pridam je do fronty (promena "queue") + zaroven jim pridam poradove cislo vlny (promenna visited)
  3. vyhodim prvniho clena
  4. prochazim tak dlouho, dokud nenajdu cil

Zkusil jsem:

def findKeyValueTo(nodes):
    for key in graph.keys():
        if graph[key] == nodes:
            return key

def findNeighbours(starter):
    neighbours = []
    if starter in graph.keys():
        neighbours = graph[starter]
    for nodes in graph.values():
        if starter in nodes:
            newPossibleNeighbour = findKeyValueTo(nodes)
            if newPossibleNeighbour not in visited:
                neighbours.append(newPossibleNeighbour)
    return neighbours

#MAIN

with open("test2.txt", "r") as file:
    lines = file.read().splitlines()

graph = {}
for line in lines:
    pair = line.split(")")
    if pair[0] not in graph.keys():
        graph.setdefault(pair[0], [pair[1]])
    else:
        graph[pair[0]].append(pair[1])

start = "F"; end = "COM"
queue = [start]
visited = {start:0}

while end not in queue:
    newNeighbours = findNeighbours(queue[0])
    counter = max(visited.values()) + 1
    for neighbour in newNeighbours:
        if neighbour not in visited:
            visited.setdefault(neighbour, counter)
            queue.append(neighbour)
    queue.pop(0)
print(visited)
print(visited[end])

text.txt: z tohoto souboru se vytvori dictionary graph

COM)B
B)C
C)D
D)E
E)F
B)G
G)H
D)I
E)J
J)K
K)L

Chci docílit: prohledavani grafu funguje dobre, aspon myslim :D ale nefunguje mi pocitadlo.. nejsem schopny prijit na to, kdyz mi uzel najde dva sousedy, aby oba dva byli se stejnym cislem a nasledujici meli cislo o +1 vetsi atd.

bohuzel tam to pocitadlo hazi nejak divne, napr. vzdalenost COM->F je 6 a F->COM je 8 :D

zkousel jsem:

  • klasicky +1 pri kazdem pruchodu, to je evidentne nesmysl..
  • pocitat nove sousedy a snizovat pocitadlo
  • ted aktualne tu fintu s maximem v visited.values(), ale to taky nejde

dalsi napady m dosly

 
Odpovědět
26.4.2021 13:28
Avatar
Petr Los
Člen
Avatar
Petr Los:2.5.2021 20:26

tak jsem to nakonec vyresil sam, postnu sem odpoved, kdyby to nekdo hledal :)

while end not in queue:
    newNeighbours = findNeighbours(queue[0])
    for neighbour in newNeighbours:
        if neighbour not in visited:
            visited.setdefault(neighbour, visited[queue[0]]+1)
            queue.append(neighbour)
    queue.pop(0)

aby to pocitalo vzdalenost spravne, bylo potreba ukladat do dictionary visited hodnotu vzdalenosti od startu od prvku, kteremu jsem nasel sousedy, tzn. aktualne queue[0] +1..

Akceptované řešení
+5 Zkušeností
Řešení problému
 
Nahoru Odpovědět
2.5.2021 20:26
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 2 zpráv z 2.