Grafové a geometrické algoritmy a efektivní datové struktury

Graph and Geometric Algorithms and Efficient Data Structures

book chapter

en

Many NP-complete optimization problems may be approximately solved by stochastic or deterministic heuristic methods and it is necessary to find their efficient data representation to minimize iteration computational time. In this chapter, we will touch the Minimum Steiner Tree Problems in Graphs (or Network Steiner Tree Problem), which can be solved by heuristics based on the Minimum Spanning Tree Problem and/or the Shortest Path Problem using a binary heap that enables to implement a priority queue that substantially increases the algorithm efficiency. We will also show a Delaunay triangulation-based way of finding minimal networks connecting a set of given points in the Euclidean plane using straight lines (minimum spanning tree) and its more general case (Steiner minimum tree) where additional points can be considered. Finally, we will deal with visibility graphs, Voronoi diagrams and rapidly exploring trees and focus on their applications in robot motion planning, where the robot should pass around obstacles from a given starting position to a given target position, touching none of them.

Řadu NP-úplných optimalizačních problémů lze přibližně řešit stochastickými nebo deterministickými heuristickými metodami a je proto třeba nalézt jejich efektivní reprezentaci, aby byl minimalizován počet iterací a výpočetní čas. V této kapitole se dotkneme problému hledání minimálního Steinerova stromy v grafech, který lze pomocí heuristik založených na minimální kostře grafu a nebo nejkratší cestě s využitím binární haldy, která umožňuje implementovat prioritní frontu, podstatně zvyšující efektivitu algoritmu. Rovněž ukážeme způsob hledání minimálních sítí spojujících množinu daných bodů v euklidovské rovině pomocí úseček mezi danými body (tj. hledání minimální kostry v euklidovské rovině), založený na využití Delaunayho triangulace, a také obecnější případ (hledání Steinerova minimálního stromu), kde lze uvažovat I jiné než zadané body. Nakonec se budeme zabývat grafy viditelnosti, Voroného diagramy a rychle rostoucími stromy a zaměříme se na jejich aplikace v plánování pohybu robotu, kde robot by měl projít kolem překážek z dané startovní pozice do dané cílové pozici bez kolize s překážkami.

Many NP-complete optimization problems may be approximately solved by stochastic or deterministic heuristic methods and it is necessary to find their efficient data representation to minimize iteration computational time. In this chapter, we will touch the Minimum Steiner Tree Problems in Graphs (or Network Steiner Tree Problem), which can be solved by heuristics based on the Minimum Spanning Tree Problem and/or the Shortest Path Problem using a binary heap that enables to implement a priority queue that substantially increases the algorithm efficiency. We will also show a Delaunay triangulation-based way of finding minimal networks connecting a set of given points in the Euclidean plane using straight lines (minimum spanning tree) and its more general case (Steiner minimum tree) where additional points can be considered. Finally, we will deal with visibility graphs, Voronoi diagrams and rapidly exploring trees and focus on their applications in robot motion planning, where the robot should pass around obstacles from a given starting position to a given target position, touching none of them.

Steinerův strom, Voroného diagram, Delaunayho triangulace, graf viditelnosti, rychle rostoucí strom, binární halda

Steiner tree, Voronoi diagram, Delaunay triangulation, visibility graph, rapidly exploring tree, binary heap

2012

31.12.2012

Springer-Verlag

Berlin (Germany)

978-3-642-30503-0

Zelinka, I., Snášel, V., Abraham, A. (eds.): Handbook of Optimization. From Classical to Modern Approach.

1

73–95

23