Der wohl berühmteste zelluläre Automat ist vermutlich Conway’s Game of Life.
Er und nahe Verwandte sind geradezu lächerlich gut untersucht. Das LifeWiki
gibt einen ganz guten Überblick.
Die Regeln sind einfach: Jede Zelle hat 8 Nachbarn, wenn genau 3 Nachbarn leben,
erwacht sie auch zum Leben, bei weniger als 2 oder mehr als 3 stirbt sie (23/3).
Wenn man die Regeln des Automaten ändert, kann man mit 12345/3 labyrinthartige
Strukturen erzeugen.
Zu jedem Zeitpunkt ist im obigen Video ein Relative Neighborhood Graph (RNG) zu
sehen. Der RNG verbindet Knoten miteinander, die nahe beieinander sind.
Für die Knotenmenge \(V\) muss also eine Metrik definiert sein, sodass eine
Distanz \(d_{ij}\) zwischen zwei Knoten definiert ist. Dann verbindet der RNG
alle Knoten, die die Bedingung
Dementsprechend simpel kann man einen RNG erzeugen.
importrandomimportnetworkxasnximportmatplotlib.pyplotaspltdefdist(n1,n2):"""Euclidean distance"""return((n1[0]-n2[0])**2+(n1[1]-n2[1])**2)**0.5defrng(G):"""Insert edges according to the RNG rules into the graph G"""forc1inG.nodes():forc2inG.nodes():d=dist(c1,c2)forpossible_blockerinG.nodes():distToC1=dist(possible_blocker,c1)distToC2=dist(possible_blocker,c2)ifdistToC1<danddistToC2<d:# this node is in the lune and blocksbreakelse:G.add_edge(c1,c2)if__name__=="__main__":# generate some random coordinatescoordinates=[(random.random(),random.random())for_inrange(100)]G=nx.Graph()forx,yincoordinates:G.add_node((x,y),x=x,y=y)rng(G)# draw the graph Gpos={n:(n[0],n[1])forninG.nodes()}nx.draw_networkx_nodes(G,pos=pos,node_shape="o")nx.draw_networkx_edges(G,pos=pos)plt.show()
Interessanterweise tauchen alle Kanten des RNG auch in der Delaunay Triangulation
der gleichen Knotenmenge auf. Dies kann man nutzen, um RNGs in \(\mathcal{O}(N \log N)\)
zu konstruieren.
Meiner persönlichen Meinung nach, bildet der RNG mit dem Verhältnis von Knoten
zu Kanten ein ästhetisches Optimum.
Ein Algorithmus, von dem jeder schoneinmal gehört haben sollte, ist die
Tiefensuche (Depth First Search). Wenn man Zusammenhangskomponenten in einem
Graphen finden will oder nach einem bestimmten Knoten in einem Graphen sucht,
ist die Tiefensuche meist der einfachste und oft ein geeigneter Algorithmus
mit einer Zeitkomplexität \(\mathcal{O}(N+M)\), die linear in der Anzahl der
Knoten und der Kanten ist. Da man gefühlt alle Graphalgorithmen am besten
rekursiv beschreiben kann, folgt hier eine (nichtrigorose) Beschreibung.
Man startet die Tiefensuche an einem beliebigen Knoten.
Bei jedem noch nicht besuchten Nachbarn startet man wieder eine Tiefensuche.
Aber was macht man im Alltag mit einer Tiefensuche?
Meine Antwort darauf ist: Labyrinthe bauen.
Bei dieser Gelegenheit muss NetworkX erwähnt werden. Ein Python
Modul, das sehr schöne Klassen für Graphen bereitstellt und perfekt geeignet
ist, um schnell Prototypen von Graphalgorithmen zu testen.