Optimization and Greedy Algorithms

Transcrição

Fachhochschule Braunschweig / Wolfenbüttel
- University of Applied Sciences -
Data Structures
and Algorithm Design
- CSCI 340 Friedhelm Seutter
Institut für Angewandte Informatik
© Friedhelm Seutter, 2007
Contents
1.
2.
3.
4.
6.
7.
8.
10.
13.
Analyzing Algorithms and Problems
Data Abstraction
Recursion and Induction
Sorting
Dynamic Sets and Searching
Graphs and Graph Traversals
Optimization and Greedy Algorithms
Dynamic Programming
NP-Complete Problems
2
1
8. Optimization and Greedy Algorithms
• Minimum spanning Trees
• Shortest Paths
3
Minimum Spanning Tree
• Let G = (V,E) be a connected, undirected,
weighted graph with weight function
w : E → IR.
• A tree G’ = (V,T) with edges T ⊆ E which
connect all vertices and whose total weight
w(T) = ∑ (u,v)∈T w(u,v)
is minimized is called a minimum spanning
tree of G.
4
2
Optimization Problem
• A problem with many possible solutions is
called an optimization problem, if an optimal
solution under a given valuation function is to
find.
• An optimal solution may be a minimized or a
maximized value of the given function.
5
Optimization Problem
• First try algorithm (in general):
Compute all solutions and then decide which
is optimal.
• Minimum spanning tree:
Compute all spanning trees and supply the
one with minimum weight.
• Not efficient: exponential number of
alternatives
6
3
Greedy Algorithm
• Type of algorithm which solves optimization
problems efficiently.
• It starts with an empty subsolution and
expands this iteratively with the present best
alternative.
7
Greedy Algorithm
• A local optimal decision should lead to a
global optimal solution.
• But an optimal solution is not found in all
cases, sometimes only “good” solutions are
found.
• The algorithm in each step “takes the biggest
piece”, therefore it is called “greedy”.
8
4
Kruskal‘s Algorithm
• A set T of edges is iteratively expanded to the
set of edges of the minimum spanning tree.
• T contains the edges of a forest and each tree
in this forest corresponds to a connected
component.
• In each step the edge with next smallest
weight is inserted into T to connect two trees.
9
10
MST-Kruskal(G,w)
5
Disjoint Set Operations
11
12
MST-Example
6
MST-Example
13
14
MST-Example
7
Verification
15
Time-Complexity
• Initialization (lines 1-3):
O(|V |)
• Sorting the edges (line 4):
O(|E | log|E |)
• Passes of loop (lines 5-8):
• Disjoint set operations:
|E |
O(|E| lg*|E|))
• Worst-case running time:
O(|E | log|E |)
16
8
Storage Complexity
• Adjacency-List:
O( |V |+ |E | )
• Set T:
O( |E | )
• Disjoint Sets:
O( |V | )
• Worst-case storage needs: O( |V |+ |E | )
17
Shortest Paths
A motorist wishes to find the shortest possible
route from Brunswick to Berlin, Germany. Given
a road map of Germany on which the distance
between each pair of adjacent cities is marked,
how can we determine the shortest route?
18
9
Map of Germany
19
20
Weight of a Path
10
Shortest Path
21
Shortest-Paths Problems
• Single-source shortest-paths
(is solved by Dijkstra’s algorithm)
• Single-destination shortest-paths
• Single-pair shortest-path
• All-pairs shortest-paths
22
11
Predecessor Subgraph
23
Relaxation
• A technique called relaxation is denoting a
process of approximation.
• In Dijkstra’s algorithm the upper bounds for
shortest paths are tightened until they equal
the shortest path.
• The shortest-path estimates d[v] for vertices v
are initialized and then improved repeatedly.
24
12
Initialize-Single-Source (G,s)
25
26
Relax (u,v,w)
13
Dijkstra‘s Algorithm
• A set of vertices S is maintained whose final
shortest paths weights from the source s have
already been determined.
• A vertex u ∈ V – S with the minimum shortestpath estimate is selected repeatedly, inserted
into S and all edges leaving u are relaxed.
The vertices in V – S are maintained in a
priority queue Q.
27
28
Dijkstra(G,w,s)
14
Dijkstra - Example
29
30
Dijkstra - Example
15
Dijkstra - Example
31
Shortest-Paths Tree
32
16
Verification
33
34
Verification
17
Time-Complexity
O(|V |)
• Initialization (lines 1-3):
• Passes of while-loop (lines 4-8):|V |
• Extraction of Q (line 5):
O(log|V |)
• Passes of for-loop (lines 7-8):
|E |
• Worst-case running time: O(|V | log|V | + |E |)
35
Storage Complexity
• Adjacency-List:
O( |V |+ |E | )
• Data structures
S, Q, d, π :
O( |V | )
• Worst-case storage needs: O( |V |+ |E | )
36
18

Optimization and Greedy Algorithms

Transcrição

Documentos relacionados

10th Anniversary 2015/Flyer Seite 1+4

Alphacool Lighttower adapter for Eheim 1260/1262

38100 Braunschweig Konzert-Kasse ECE Schloss

Sorting

Hochschulpakt 2020 - 315 Studienplätze mehr an der FH

DCG Symposium Übernachtungsmöglichkeiten

Schulungen_Jonas Karnagel

Stadtbetriebe Wolfenbüttel GmbH

Hagemann_Gummi und Kunststoffmatten 6

pressekit kurzinfo / pressetext weblinks

Theater Bergen