ich bin neu im Forum und hoffe, dass ihr mir helfen könnt. Ich kenne mich leider nicht sonderlich mit Graphen aus (hab aber Vorkenntnisse) und hab daher nur etwas aus dem Internet kopiert und etwas editiert.
------------------------------------------------------------
Code: Alles auswählen
class Graph(object): #eine Graphenklasse
class Knoten(object): #Knotenobjekt im Graph
def __init__(self, name, connections=None):
self.name = name
self.connections = {}
if connections is not None:
self.connections.update(connections)
def __init__(self, *args):
self.Knotens = set(args) #Graph besteht aus den gegebenen Knoten
def shortest_path(self, from_, to): #Algorithmus zum kürzesten Wege Problem
P = self._algorithmus(from_)
path, Knoten = [], to
while not (Knoten == from_):
if path.count(Knoten): break
path.append(Knoten)
Knoten = P[Knoten]
return [from_] + list(reversed(path))
def _algorithmus(self, start): #D ist der kürzeste gefundene Weg, P die Liste von den bekannten Knoten
D, P = {},{}
for Knoten in self.Knotens:
D[Knoten.name], P[Knoten.name] = float("inf"), None
D[start] = 0
unseen_Knotens = list(self.Knotens)
while unseen_Knotens:
shortest = min(unseen_Knotens, key=lambda Knoten: D[Knoten.name]) """lambda zur Berechnung der Längen (hab das noch nicht ganz verstanden xD)"""
unseen_Knotens.remove(shortest)
for neighbour, distance in shortest.connections.items():
if neighbour not in [Knoten.name for Knoten in unseen_Knotens]:
continue
if D[shortest.name] + distance < D[neighbour]:
D[neighbour] = D[shortest.name] + distance
P[neighbour] = shortest.name
return P
# def find_all_paths(self, from_, to, path=[]):
# paths = []
# Knotenliste = list(self.Knoten)
# for Knoten in Knotenliste:
# if Knoten not in path:
# extended_paths = self.find_all_paths(Knoten, to, path)
# for p in extended_paths:
# paths.append(p)
# return paths
graph = Graph(
Graph.Knoten('A', {'B': 3, 'G': 1, 'I': 2}),
Graph.Knoten('B', {'C': 4, 'G': 5, 'A': 3}),
Graph.Knoten('C', {'D': 5, 'F': 9, 'B': 4}),
Graph.Knoten('D', {'E': 6, 'F': 3, 'C': 5}),
Graph.Knoten('E', {'F': 2, 'H': 4, 'D': 6}),
Graph.Knoten('F', {'G': 3, 'H': 5, 'D': 3, 'E': 2, 'C': 9}),
Graph.Knoten('G', {'H': 6, 'B': 5, 'A': 1, 'F': 3}),
Graph.Knoten('H', {'I': 4, 'J': 2, 'E': 4, 'F': 5, 'G': 6}),
Graph.Knoten('I', {'J': 1, 'A': 2, 'H': 4}),
Graph.Knoten('J', {'H': 2, 'J': 1}),
)
x = graph.shortest_path('A', 'D')
So, jetzt möchte ich eine Art Bogo-Sort machen, weil ich später einen Graphen erstelle, der so 400 Objekte hat und einen bestimmten Algorithmus habe (aber dann festgestellt, dass die Laufzeit expotentiell ist). Also möchte ich nun zwischen zwei Knoten alle bzw. eine nach obenbegrenzte Anzahl an Pfaden generieren (nach Zufallsprinzip und dann den Algorithmus anwenden). Ich hab leider nicht so viel Ahnung und hab das kurz probiert in der auskommentierten Funktion, aber die funktioniert nicht. Vielleicht kennt ihr auch ein bessere Darstellung für einen Graphen (die Weglängen sind leider unverzichtbar).
Kurz zusammengefasst: Zwischen zwei Knoten in einem Graphen sollen zufällig Pfade generiert werden (gleiche nicht wiederholen).
Danke im Voraus
Auch sollten Kommentare nicht als Ersatz für aussagekräftige Namen herhalten müssen. Statt einbuchstabiger Namen die irgendwo in einem Kommentar erklärt werden, sollte man Namen wählen die selbsterklärend sind, so dass man beim Lesen des Codes weiss welche Bedeutung ein Namen hat, ohne den dazugehörigen Kommentar suchen zu müssen.