efinf:blcks2017:labyrinth [https://fginfo.ksbg.ch Fachgruppe Informatik der KSBG]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Graphentheorie ======
  * Knoten (meist Zahlen)
  * Kanten: Paare von Knoten (orientiert oder nicht)
  * Weg: Folge von Knoten, die durch Kanten verbunden sind.
  * Zusammenhängender Graph: Zwischen jedem Paar von Knoten existiert ein Weg
  * Zyklus: Weg mit identischem Start- und Endknoten

===== Bäume =====
  * Zusammenhängender Graph ohne Zyklus.

Für Bäume beweisen Sie: 
  * Es gibt exakt einen Weg zwischen zwei beliebigen Knoten
  * Ein Baum mit $n$ Knoten hat $n-1$ Kanten.

===== Labyrinth =====
  * Im einfachsten Fall ein Baum (keine Zyklen, garantierter Weg).
  * Grundstuktur: Raster, Knoten sind ganzzahlige Koordinatenpunkte, Kanten achsenparallel, Länge 1.

===== Graphen-Such-Algorithmen =====
**Input** Graph mit Knotenmenge $V$ und Kantenmengen $E$, Startknoten $s$, Zielknoten $z$.

**Output** Weg von $s$ nach $z$

  - Markiere alle Knoten mit ''None''.
  - Setze Todo-Liste $t=(s)$
  - Solange $z$ mit ''None'' markiert ist, wiederhole:
    - entferne einen Knoten $v$ aus $t$
    - für alle Nachbarn $u$ von $v$, die noch mit ''None'' markiert sind:
      - markiere $u$ mit $v$ (als Vorgäger)
      - füge $u$ der Liste $t$ hinzu.
    - Wenn $t$ leer ist, **return** "Kein Weg von $s$ zu $z$
  - Weg $w$ = $(z)$
  - Setze $v=z$
  - Solange $v \neq s$, wiederhole:
    - Setze $v$ = Markierung von $v$
    - Füge $v$ vorne zum Weg $w$ hinzu
  - **return** Weg $w$


Je nachdem, wie die Todo-Liste gehandhabt wird, erhält an verschiedene Algorithmen:
  * Wird immer der zuletzt eingefügte Knoten entfernt, erhält man die Tiefensuche (Depthfirst search). D.h. man geht erst soweit in die Tiefe wie möglich.
  * Werden die Knoten in der Reihenfolge entfernt, in der sie eingefügt wurden, erhält man die Breitensuche (Breadhfirst search). D.h. man besucht die Knoten in der Reihenfolge ihrer Entfernung vom Startknoten aus (gemessen in Anzahl Kanten).
  * Die Knoten nach einem Kriterium ausgewählt. Wählt man z.B. den nächsten Knoten bezüglich seiner Distanz zum Startknoten aus, erhält man Dijkstras Algorithmus zur Bestimmung des kürzesten Weges (Voraussetzung sind positive Kantenlängen). Addiert man dazu zusätzlich eine unterschätzende Distanz zum Zielknoten, erhält man den $A^\star$-Algorithmus.

Diese Algorithmen werden z.B. auch von Webcrawlern verwendet und finden (in massiv effizienteren Formen) in Navigationsgeräten anwendung.

==== Anwendung zu Generierung eines Labyrinths ====
Wird kein Zielknoten festegelegt, erzeugt obiger Algorithmus exakt einen Weg vom Startknoten zu jedem anderen Knoten, d.h. ein Baum. Wird der nächste Knoten "zufällig" aus der Todo-Liste ausgewählt, entsteht ein "zufälliger" Baum und damit ein zufälliges Labyrinth.

Damit ansprechende Labyrinthe entstehen, darf nicht jeder Knoten sofort vollständig abgearbeitet werden, sondern nur ein Weg. Danach wird der Knoten wieder in die Todo-Liste eingefügt.

Der Zufall kann so gesteuert werden, dass "ansprechende" Labyrinthe entstehen.

===== Alternative Baum-Generierung =====
  - Start mit $n$ Knoten, keine Kanten.
  - Wiederhole $n-1$ mal:
    - Man wählt zwei Knoten $u$, $v$ aus, die nicht in der gleichen zusammenhängenden Komponente sind.
    - Man verbindet $u$, $v$ mit einer Kante


===== Python Code =====
<code python laby.py>
import random

class Laby:
    # directions, trigonometric
    VECS=[[1,0], [0,1], [-1,0], [0,-1]];
    def __init__(self, width, height):
        self.width = width
        self.height = height
        # Gibt für jede Koordinate an, ob nach links und nach unten gegangen werden kann.
        # Z.B. self.canGo[3,4,0] ist True, wenn von 3,4 auf 4,4 gegangen werden kann
        # self.canGo[3,4,1] ist False, wenn nicht von 3,4 auf 3,5 gegangen werden kann.
        self.canGo = [[[False, False] for y in range(self.height)] for x in range(self.width)]
        
        # Mark enthaelt ein String der Laenge 1, der bei der Ausgabe mit ausgegeben wird.
        self.mark = [[" " for y in range(self.height)] for x in range(self.width)]
        

    
    def clearMarks(self):
        for y in range(self.height):
            for x in range(self.width):
                self.mark[x][y]=" "
      
    # c ist ein Koordinatenpaar        
    def onBoard(self,c):
        return c[0]>=0 and c[0]<self.width and c[1]>=0 and c[1]<self.height
    
  
    def move(self, c,d):
        return (c[0]+Laby.VECS[d][0], c[1]+Laby.VECS[d][1])
    
    # c ist ein Koordinatenpaar, 
    # gibt True zurueck, wenn von c in Richtung d gegangen werden kann.
    def edge(self, c, d):
        if self.onBoard(c) and self.onBoard(self.move(c,d)):
            if d>1:
                c = self.move(c,d)
                d-=2
            return self.canGo[c[0]][c[1]][d]
        return False
        
        
    def setEdge(self, c,d, value=True):
         if self.onBoard(c) and self.onBoard(self.move(c,d)):
            if d>1:
                c = self.move(c,d)
                d-=2
            self.canGo[c[0]][c[1]][d] = value
            
    def __str__(self):
        res = "+" + ("---+"*self.width)+"\n"
        for y in range(self.height):
            line1 = "|"
            line2 = "+"
            for x in range(self.width):
                line1 += " "+self.mark[x][y]+" "
                line1 += " " if self.edge((x,y),0) else "|"
                line2 += "   +" if self.edge((x,y),1) else "---+"
            res+=line1+"\n"+line2+"\n"
        return res
    
   
                                                
            
# Nur wenn Datei dekt ausgefuehrt wird:    
if __name__== "__main__":
    l = Laby(12,12);
    print(l)
  
</code>