Bestand wählen
Merken

# Traversing Mazes the pythonic way and other Algorithmic Adventures

Embed Code
DVD bestellen

#### Automatisierte Medienanalyse

Beta
Erkannte Entitäten
Sprachtranskript
the
the guy thanks a lot for coming and very excited to be here today In this talk I would like to talk about something I like it a lot in computer science which is algorithms and in particular graph algorithms that are graphs are great data structures and almost useful for every problem you solve every in your everyday code OK so the
said comes in different flavors we may have directed or undirected graphs in the the figure you may see that the edges house and and and the notion of directions is the are unweighted or weighted graphs work sorry were the there is not a weights on the on the edges that there may be simple or non simple graphs the non-simple right here means that there's some edges make that may require some special handling in your in our algorithm for instance and this case self loops or groups in general uh we'll see another example of this in a few minutes and are sometimes thermal will be group ages that may be it may be incident multiple times in the signal in that case there will be a that will be graph not graph action OK so we may have cycling versus psychic graphs and understands for and cited references a tree uh trees are connected STT and undirected graphs we may have sold the well known in the so called Don which stands for directed acyclic graphs and we'd actually be made the applied topological sorting and stuff like that this is that these are called concepts for it a from very basic in introductory algorithmic blasts can and finally we may have a label advertis labeled graphs where there is a label on nodes so versus on the graph a graphs may be its forests or maybe bands in which refers to the number of edges in the graph uh and last but not least on graphs may be explicit or implicit this is what I was referring before when I told you that graphs are a great big structure and a powerful man mental model because sometimes when you have to deal with with the problem you have to solve such kind of problem you may think to the prom being uh as a graph problem so you may represent your data your problem as a graph and you may apply graph algorithms to your to problem so here we can here we go to the graph representation so finally we we start to see some code and actions of 1 of the most common way to represent
graphs use the education Salazar and something like that that what is additionally so 1 of the most intuitive ways to implement graphs and for each node we can access a list what as we will see in few minutes all its neighbors so this is the idea and this is the graph we're going to have to use the right sample in the next slides again so we have nodes labeled from 8 to age and for simplicity we assume that we number all the notes from a to age assigning a number that goes from 0 to 7 so and minus 1 in Python we want to implement
objections set which shows up In this case we is the shape of the notes from a to and H and then we use create the structure and which is an a list of additionally the uh over all sets are kind of come before just just the mention before Python 274 or Python 3 of you would use the set constructed here but and now we Europe you may
dictionary where that's for and efficiencies X and uh with the structure we are allowed to just 4 membership for neighborhood membership which is still a constant time and we may calculate the degree of a new the other well known structure to represent graphs use the adhesion to metrics and so on In addition Semantics will list all the neighbors for each node of character so uh we want to store of value indicating the presence or the absence of the edge in the graph connecting 2 nodes which is true or false instance 0 1 1 atmosphere respectively OK and we may try to implement in addition metrics with nested lists the we may argue that this is not a and actually matrix this is a list of lists of guide this just implementation details of Python this just to adjust just to do that sort of proof of concept of and so a with this
structure we are able to implement we're able to test for membership as usual were able to to to calculate the degree of the nodes and of course you may substitute this homemade implementation of the metrics using for instance new pi race cancer which is of course even more efficient and if we will have time I will uh I would like to to talk about the the sci-fi graph implementation and already in the library of uh all sci-fi token of the
the same ways of more than once a cat cover the basic idea is backtracking so the idea is some looking in any direction once and then backtracked whenever you came to dead end or an intersection that you are ready to walk through to avoid cycles this is the basic idea and we will see and details of this 1 OK so I'm sorry for the the formatting this this may be due to the the font size the
server that we may have this kind of functions in Python which is the arbitrary walk can we assume as said before we assume our graph represented as a dictionary agency set and we have an input and an S node which is the starting point OK so we select a random starting point or the point the point where we are and how we have to structures that P and acute uh structures these the predecessors to use the set of the nodes to
be we selected randomly uh we simply we add to the to the to the set to the starting point and we traits while Q while the the the the set Q has elements inside we pick 1 element in the queue completely arbitrary OK I by using that you don't popped method and for every node switches in the which is incident to the you know to what has not been visited yet we and there's no to the you and then we sort the predecessor so in this case we walked through the to do graph 1 step the step by step I actually this algorithm will travesti a single connected component OK so we'll try we will weird you we will find the connected components of a graph starting from the uh from at a given node p is that processes 3 if
you would like to be uh if you would like to get all the connected components in graph we might I rate only ever every node in the graph and we call the walk functions and we use this is simply um updates the structure of a scene which is a set of this is nodes again OK well thank you could have the time complexity of this algorithm is status of the plus of these so this the which is the complexity of almost every traversal of a but just a little another detail about this is the important point here is that when we select the notes we want to do this if we use real on
the the the pop method here on the set which takes randomly an element in the sector of character so this is why this is called an arbitrary uh and that's if
we want to go deep so we want to apply the on the so called adapt 1st trouble so we might use another trick so instead of picking randomly the the the elements in the In this structure we might use a structure that task of the size of a predefined particle to get the elements in this case in the case of the death 1st proposal is the last in 1st out particles cat but this is a recursive implementation but in Python where we may we generally we made every always translated custom implementation to a unintelligible 1 In this case we rely on the list structure mechanics so every time we at the end up to a node which is which is new a week extend the the the frames to the the set of incidence nodes to do today to be you want of God and you know a mock implementation we use a set of characters so we would risk having the same nodes scheduled from more than 1 this OK so this is why the depth-first traversal yes more efficient in general case in the DFS we use the Allies uh therefore use so every node is scheduled for only once if you want to generalize this role so we might write this function which is the progress and um did the did the type of turbo so we're going to my depends on the
structure we're going to use for the french OK in general this is a set which is very similar to the arbitrary walk already showed a few slides go if we use the the list of so the Python lists these will end up to be depth-first 1st reversal and using the yield that allows for it lazy iterations so on uh it will may create an generated Python which is very very useful and this is more efficient for dance and the graphs can and that's it for yes thank you and that's it for it and the mazes OK but what about the infinite mazes and unweighted shortest path a so far the over EGA behaviors 4th deft 1st for fossils have hasn't the a problem actually the problem of the dead dead 1st reversal of the 1st search is that you may run for ages and never get back a character so in case of very very deep graph the graph the depth 1st reversal is not a good is not a good choice that in fact in case of visiting of trolling the graph of the web the adapt 1st proposal is not that the solution can in general the debris uh the the distillate Bayesian here's another kind of 2 rules so which is the breadth 1st search at that I'm going to talk about now and what if we would like to follow the shortest path from s and amazing so in this case the shoppers sparse means the minimum number of the intersection of time the 1st attempt is the iterative deepening their 1st search and I'm not going into the details of this ordering the basic idea is that this algorithm applies a depth-first search for causal many times with different our death limits OK kind but this algorithm led to another well known algorithm which is the breath 1st search breath 1st search is versatility the ITER DFS so the idea of a version of the depth-first-search but if it uses a different our structure OK in disguise the daft breath 1st search for users are um a structure which is a Q and follow that follows the FIFO set first-come-first-served uh which is the 1st the 1st of words and then we may be implemented in Python using the DTD structure which is in the standard library in this for a very simple and very retrieval to to implement the did you actually corresponds to a double links to in Python as you may know that ends up in this case we rely on the top-left function to be get the element we want to start visiting start traversing and the proper leftists constant time because of the implementation of the uh the you structure the complexity of overall breath 1st search is always again that's out of the each of the dimension of edges plus the dimension of purchases and it can be demonstrated that the birth the BFS calculus always apparent
and in case of weighted graphs and other well known problem in computer science and and algorithms in general is the shortest path but this time the short to spot means the path with the minimum within the minimum cost start as these comics as I would like to have a pillow talk sort uh we will talk about the dice for algorithm not the moment for as in this it's a comic OK they and the dice threshold back on directed acyclic graphs relies on the relaxed function which the basic idea of the relaxed function is to propagate the knowledge about the shortest path 1 uh step at a time we looked for an improvement to the publicly known distance to be by trying to take a shortcut through are you which is the they vertex we want to test OK if the structure if the it is a short so if we pass through the you know to cost less than the already computed shortest path we will follow that direction and we tested this 1 step at a time a kind of OK and so on yep did I saw
algorithm applied and exploits the EQ structure which is a priority queue that allows us to get the notes every time we add a note to this structure we Our guaranteed to respect the EP fight uh relations so that and we add the a the notes you in order this is a priority queue so this is a Q order to and we get the elements a with the pop which which returns the the element with the least priority OK of the difference in the relationship between the dice frog remember breath 1st search algorithm is that by allows assigning distances of the then 1 for each step meanwhile the breadth-first-search search basically just expands the search by 1 step of that which happens to have the effect of finding the moles the number of steps it takes to get to and even a to any given node from any source
it can the last example here is the shortest path from all of for all pairs because I story is the sure this past also known as shortest paths Single source so you have and nodes a target that you want to optimized and you start looking for the shortest paths considering that single node the another very interesting problem is the shortest path for all pairs OK so we're interested in getting the shot response for every possible proposal on our graph this is usually solved by a well known algorithm which is the Floyd-Warshall algorithm that relies on a technique an optimization technique which is called dynamic programming also known as don't repeat yourself In mathematics Adamic programming is a method for solving complex problems by breaking them down into simpler subproblems it is applicable to problems 6 beating the properties of overlapping subproblems and optimal substructure so the basic idea is memoization memoization means cash value already solved problems is so instead of recomputing every time the same subproblems we might create
function for memorization implies that in a very elegant way I like this a lot we may create a mammal decorated which relies on which exploits the prox function from fund tools which it wraps is a sort of show that for a partial and another function is a function of Fund tools to sort function which is partial and in this case we create
them this decorator to uh in this broker recreated cash which is the dictionary that stores the values of all the problems OK this is it in action the Floyd-Warshall algorithm is a problem that may relying on the dynamic programming technique because the the basic idea is that uh let us consider the DUP k be the length of the shortest path that exists from node u to node b a if you're only allowed to use that you're only allowed to use the 1st k nodes in your graph right you can decompose the problem as it follows that the distance from node u to node v using the k a notice in your path corresponds to the minimum to the distance from you to the without taking that node or the cost uh from that good of the path that goes from a you to can and k to the maybe this is uh this is uh more clear in this in this slide we might considering whether or not to include not k in the in the the shortest path of character so we calculate the cost of the paths that pass through the k nodes that starting from you and ending to to be if this as I'm not a convenient costs so so if the cost of not taking that node is less than taking that node we simply consider we simply disregarded node but otherwise we include that node the node k initial paths we may I create the so we may implement the Floyd-Warshall algorithm in Python considering 1st since the additional semantics and the distance all the solution in this case we a deep copy the graphs and updates that implies that the the the weights of the of the distances but we may also exploit the memoization a wraps for afford formatting is very often awful
and we made a recursively apply the but this the D function which is the function that calculates the distance from notes using the memorization so if we end up to our distance from a node u v and K already calculated the memorization functions of Y to calculated again and
returns the value thanks to the decorator presented before so that sets some references to buy the logarithms this a very introductory route for this kind of stuff uh of the algorithm this manually as not actually related to fight and but it's very a good reference manual and that's it thank you very much for a definitive thank you very much for their
only any questions there
is the lifetimes lunch break Saul please feel free to ask questions OK so I think it was a very compact introduction thank you very much like what the
Algorithmus
Algorithmus
Ungerichteter Graph
Datenstruktur
Informatik
Code
Computeranimation
PROM
Bit
Dichte <Physik>
Selbstrepräsentation
Program Slicing
Formale Sprache
Gruppenkeim
Computerunterstütztes Verfahren
Ungerichteter Graph
Extrempunkt
Komplex <Algebra>
Analysis
Computeranimation
Richtung
Netzwerktopologie
Arithmetischer Ausdruck
Zahlensystem
Algorithmus
Gruppe <Mathematik>
Ungerichteter Graph
Emulator
Elektronischer Programmführer
Figurierte Zahl
Bildauflösung
Metropolitan area network
Parametersystem
Nichtlinearer Operator
Lineares Funktional
Datennetz
Asymptotik
Systemaufruf
Quellcode
Bitrate
Ein-Ausgabe
Teilmenge
Datenfeld
Funktion <Mathematik>
Menge
Rechter Winkel
Festspeicher
Information
Tabelle <Informatik>
Instantiierung
Folge <Mathematik>
Subtraktion
Gewicht <Mathematik>
Stab
Dezimalbruch
Gruppenoperation
Klasse <Mathematik>
Mathematisierung
Zahlenbereich
Implementierung
Kombinatorische Gruppentheorie
Transportproblem
Asymptote
Abenteuerspiel
Code
Komplexitätstheorie
Schwach besetzte Matrix
Loop
Virtuelle Maschine
Multiplikation
Knotenmenge
Informationsmodellierung
Spieltheorie
Endlicher Graph
Zeitkomplexität
Gewichtung
Abstand
Datenstruktur
Informatik
Leistung <Physik>
Analysis
Algorithmus
Transinformation
Wald <Graphentheorie>
Matching <Graphentheorie>
Stochastische Abhängigkeit
Relativitätstheorie
Datenmodell
Physikalisches System
Binder <Informatik>
Teilgraph
Unendlichkeit
Mereologie
Dreiecksfreier Graph
Mehrrechnersystem
Wort <Informatik>
Binäre Relation
Shape <Informatik>
Zahlenbereich
Mailing-Liste
Ungerichteter Graph
Menge
Computeranimation
Rechenschieber
Objekt <Kategorie>
Knotenmenge
Menge
Stichprobenumfang
Ungerichteter Graph
Selbstrepräsentation
Datenstruktur
Nachbarschaft <Mathematik>
Matrizenrechnung
Bit
Punkt
Web log
Selbstrepräsentation
Ungerichteter Graph
Element <Mathematik>
Extrempunkt
Binärcode
Komplex <Algebra>
Computeranimation
Formale Semantik
Poisson-Klammer
Arithmetischer Ausdruck
Algorithmus
Code
Mustersprache
Elektronischer Programmführer
Softwaretest
Datennetz
Schwach besetzte Matrix
Ereignishorizont
Entscheidungstheorie
Dichte <Physik>
Sinusfunktion
Arithmetisches Mittel
Rechenschieber
Menge
Physikalische Theorie
Beweistheorie
Information
Graphentheorie
Computerunterstützte Übersetzung
Schlüsselverwaltung
Instantiierung
Subtraktion
Luftreibung
Gewicht <Mathematik>
Implementierung
Zahlenbereich
Code
Mailing-Liste
Knotenmenge
Endlicher Graph
Programmbibliothek
Zeitkomplexität
Speicher <Informatik>
Datenstruktur
Soundverarbeitung
Assoziativgesetz
Linienelement
Zwei
Mathematisierung
Mailing-Liste
Vektorraum
Menge
Quick-Sort
Data Dictionary
Selbstrepräsentation
Normalvektor
Punkt
Klassische Physik
Selbstrepräsentation
Versionsverwaltung
Ungerichteter Graph
Element <Mathematik>
Extrempunkt
Binärcode
Raum-Zeit
Marketinginformationssystem
Computeranimation
Formale Semantik
Netzwerktopologie
Algorithmus
Polygonzug
Reverse Engineering
Typentheorie
Ungerichteter Graph
Softwaretest
Parametersystem
Kategorie <Mathematik>
Ausnahmebehandlung
Bitrate
Dreiecksmatrix
Arithmetisches Mittel
Rechenschieber
Menge
Einheit <Mathematik>
Konditionszahl
Information
Diagonale <Geometrie>
Instantiierung
Subtraktion
Gewicht <Mathematik>
Thumbnail
Klasse <Mathematik>
Matrizenrechnung
Zahlenbereich
Implementierung
Kombinatorische Gruppentheorie
Unendlichkeit
Loop
Mailing-Liste
Datensatz
Knotenmenge
Gewicht <Mathematik>
Netzbetriebssystem
Datentyp
Programmbibliothek
Datenstruktur
Grundraum
Informatik
Einfach zusammenhängender Raum
Algorithmus
Videospiel
Linienelement
Mailing-Liste
Schlussregel
Schlussregel
Unendlichkeit
Diagonalform
System F
Lineares Funktional
Punkt
Ungerichteter Graph
Ein-Ausgabe
Computeranimation
Richtung
Knotenmenge
Menge
Font
Dreiecksfreier Graph
Server
Dateiformat
Computerunterstützte Übersetzung
Datenstruktur
Einfach zusammenhängender Raum
Lineares Funktional
Punkt
Einfach zusammenhängender Raum
Ungerichteter Graph
Element <Mathematik>
Komplex <Algebra>
Computeranimation
Demoszene <Programmierung>
Komponente <Software>
Knotenmenge
Algorithmus
Menge
Polygonzug
Warteschlange
Datenstruktur
Lineares Funktional
Rahmenproblem
Strukturmechanik
Implementierung
Tiefensuche
Mailing-Liste
Turbo-Code
Element <Mathematik>
Ungerichteter Graph
Computeranimation
Komponente <Software>
Knotenmenge
Menge
Arithmetische Folge
Datentyp
Grundsätze ordnungsmäßiger Datenverarbeitung
Rekursive Funktion
Partikelsystem
Computerunterstützte Übersetzung
Datenstruktur
Term
Information Retrieval
Kalkül
Momentenproblem
Extrempunkt
Versionsverwaltung
Iteration
Ungerichteter Graph
Element <Mathematik>
Information
Dicke
Komplex <Algebra>
Ähnlichkeitsgeometrie
Marketinginformationssystem
Computeranimation
Richtung
Dijkstra-Algorithmus
Vier
Algorithmus
Reverse Engineering
Auswahlaxiom
Bayes-Netz
Lineares Funktional
Schnelltaste
Dicke
Schwellwertverfahren
Physikalischer Effekt
Güte der Anpassung
Konstante
Rechenschieber
Funktion <Mathematik>
Menge
Gewicht <Mathematik>
Hausdorff-Dimension
Tiefensuche
DTD
Zahlenbereich
Implementierung
Benutzerbeteiligung
Endlicher Graph
Konstante
Programmbibliothek
Inverser Limes
Gewichtung
Abstand
Datenstruktur
Operations Research
Informatik
Schlussregel
Binder <Informatik>
EINKAUF <Programm>
Quick-Sort
Unendlichkeit
Wort <Informatik>
Eigentliche Abbildung
Soundverarbeitung
Algorithmus
Subtraktion
Mathematik
Kategorie <Mathematik>
Minimierung
Relativitätstheorie
Einfache Genauigkeit
Zahlenbereich
Gasströmung
Quellcode
Ungerichteter Graph
Element <Mathematik>
Optimierung
Computeranimation
Suchverfahren
Abstand
Dijkstra-Algorithmus
Knotenmenge
Algorithmus
Prioritätswarteschlange
Endogene Variable
Gotcha <Informatik>
Abstand
Optimierung
Datenstruktur
Gewicht <Mathematik>
Extrempunkt
Gruppenoperation
Ungerichteter Graph
Extrempunkt
Computeranimation
Formale Semantik
Knotenmenge
Algorithmus
Primzahlzwillinge
Abstand
Optimierung
Speicher <Informatik>
Serviceorientierte Architektur
Inklusion <Mathematik>
Algorithmus
Lineares Funktional
Dicke
Multifunktion
Diskretes System
Konvexe Hülle
Quick-Sort
Rechenschieber
Einheit <Mathematik>
Rechter Winkel
Dateiformat
Hill-Differentialgleichung
Algorithmus
Lineares Funktional
Knotenmenge
Logarithmus
Algorithmus
Güte der Anpassung
Mixed Reality
Routing
Abstand
Computeranimation
Fehlermeldung
Bus <Informatik>
Kontrollstruktur
Computeranimation