Aktuálně: Postihly zákazy tvou profesi? Poptávka po ajťácích prudce roste, využij slevové akce 50% výuky zdarma!
Pouze tento týden sleva až 80 % na e-learning týkající se Javy
Avatar
Petr Los
Člen
Avatar
Petr Los:26. dubna 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. dubna 13:28
Tento výukový obsah pomáhají rozvíjet následující firmy, které dost možná hledají právě tebe!
Avatar
Petr Los
Člen
Avatar
Petr Los:2. května 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. května 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.