Forum:  Graphentheorie
Thema: Algorithmus: Punkte mit geraden Linien verbinden
Themen-Übersicht
mathletic
Aktiv
Dabei seit: 11.11.2013
Mitteilungen: 1435
Themenstart: 2020-12-01 15:21

Hallo,

ich gucke folgendes:


Sei eine Menge von $N$ Punkten $(x_i, y_i)$, $1 \leq i \leq N$ in der Ebene. Entwerfen und analysieren Sie einen Algorithmus, der die Punkte mit geraden Linien verbindet, sodass die Gesamtlänge der Linien minimal ist und wenn wir den Linien folgen, können wir von jeden Punkt überall gelangen können.


Ich habe mir folgendes überlegt:


Wir definieren einen gewichteten, ungerichteten Graphen $G=(V,E)$ wie folgt:
Die Menge der Ecken ist $V=\{p_i:=(x_i,y_i)\mid (x_i,y_i)\in N\}$ und die Menge der Kanten ist $E=\{(p_i,p_j)\mid \forall p_i,p_j\in N, \ i\neq j\}$.

Somit entsteht ein vollständiger Graph.

Das Gewicht von jeder Kante $(p_i,p_j)\in E$ ist der Abstand $d(p_i,p_j)$ zwischen den Punkten $p_i$ und $p_j$.

Wir können als Abstand den euklidischen Abstand betrachten, oder?

Also seien $p_i=(x_i,y_i)$ und $p_j=(x_j,y_j)$ dann $d(p_i,p_j)=\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}$.

Jetzt wenden wir ein Algorithmus für Minimum spanning tree an, also Prim oder Kruskal, und so erhalten wir dann das gewünsche Ergebnis.


Ist meine Idee richtig?


viertel
Senior
Dabei seit: 04.03.2003
Mitteilungen: 27746
Herkunft: Hessen
Beitrag No.1, eingetragen 2020-12-01 16:00
\(\begingroup\)\(\newcommand\d{\mathop{}\!\mathrm{d}}\)
Hi mathletic

Deine Idee sieht soweit vernünftig aus, siehe auch Minimum_spanning_tree
Viel Spaß/Erfolg bei der Umsetzung. Den Graphen mußt du natürlich als vollständigen G mit allen $\frac{N(N-1)}{2}$ Verbindungen ansetzen.

Gruß vom ¼
\(\endgroup\)

mathletic
Aktiv
Dabei seit: 11.11.2013
Mitteilungen: 1435
Beitrag No.2, vom Themenstarter, eingetragen 2020-12-01 16:09
\(\begingroup\)\(\newcommand\d{\mathop{}\!\mathrm{d}} \newcommand\d{\mathop{}\!\mathrm{d}}\)
2020-12-01 16:00 - viertel in Beitrag No. 1 schreibt:
Deine Idee sieht soweit vernünftig aus, siehe auch Minimum_spanning_tree
Viel Spaß/Erfolg bei der Umsetzung. Den Graphen mußt du natürlich als vollständigen G mit allen $\frac{N(N-1)}{2}$ Verbindungen ansetzen.

Ok! Ich versuche die Idee jetzt als Pseudocode dazustellen.

Eine Frage... Welcher Algorithmus ist hier besser zu benutzen Prim oder Kruskal? Oder gibt in diesem Fall kein Unterschied?
\(\endgroup\)

mathletic
Aktiv
Dabei seit: 11.11.2013
Mitteilungen: 1435
Beitrag No.3, vom Themenstarter, eingetragen 2020-12-01 16:32

Um den Graphen zu erstellen habe ich folgendes gemacht:

    Algorithm d
       Input: point ((u1,u2),(v1,v2))
       Output: Distance between the two points  
        return sqrt( (u1-v1)^2 + (u2-v2)^2)
   
   
    Algorithm Create_Graph
       Input: Number of points N, Set of points S
       Output: Graph  
        G <- new empty graph
        for i <- 1 to N do
              G.AddVertex( S[i] )
        for i <- 1 to N do
              for j <- i to N do
              G.AddEdge( S[i], S[j], d(S[i],S[j]) )


Ist dieser Teil richtig?


viertel
Senior
Dabei seit: 04.03.2003
Mitteilungen: 27746
Herkunft: Hessen
Beitrag No.4, eingetragen 2020-12-01 18:07

Was soll daran falsch sein, einen Graphen zu erstellen?

Willst du jetzt nach jedem Codeschnipselchen fragen?


mathletic
Aktiv
Dabei seit: 11.11.2013
Mitteilungen: 1435
Beitrag No.5, vom Themenstarter, eingetragen 2020-12-01 18:20

2020-12-01 18:07 - viertel in Beitrag No. 4 schreibt:
Was soll daran falsch sein, einen Graphen zu erstellen?

Willst du jetzt nach jedem Codeschnipselchen fragen?

Ich bin mir nicht ganz sicher ob die "for" von j ab i anfängt oder ab 1. Ich dachte ab i weil sonst gibt es manche Kanten doppelt.

Nach diesen Teil ruft man einen Algorithmus auf, Prim oder Kruskal.

Wenn wir z.B anwenden dann machen wir folgendes:


   Algorithm d
       Input: point ((u1,u2),(v1,v2))
       Output: Distance between the two points  
        return sqrt( (u1-v1)^2 + (u2-v2)^2)
   
   
    Algorithm Connect_Points
       Input: Number of points N, Set of points S
       Output: Minimum Spanning Tree of given points  
        G <- new empty graph
        for i <- 1 to N do
              G.AddVertex( S[i] )
        for i <- 1 to N do
              for j <- i to N do
              G.AddEdge( S[i], S[j], d(S[i],S[j]) )    
        prim(G)



Und somit haben wir das gewünschte Ergebnis, richtig?


viertel
Senior
Dabei seit: 04.03.2003
Mitteilungen: 27746
Herkunft: Hessen
Beitrag No.6, eingetragen 2020-12-01 18:28

Wenn schon, dann läuft j ab i+1, denn eine Kante von i nach i macht keinen Sinn.

Aber wenn dir das schon Kopfzerbrechen bereitet, was wird das erst beim Algorithmus?


mathletic
Aktiv
Dabei seit: 11.11.2013
Mitteilungen: 1435
Beitrag No.7, vom Themenstarter, eingetragen 2020-12-01 22:44

Um den Graphen zu erstellen ist die Komplexität die folgende:

Von der ersten "for" haben wir:
$\displaystyle{\sum_{i=1}^Nc_1=c_1\cdot \sum_{i=1}^N1=c_1\cdot N}$, wenn $c_1$ die konstante Komplexität von "G.AddVertex" ist.  

$\displaystyle{\sum_{i=1}^N\sum_{j=i+1}^Nc_2=c_2\cdot \sum_{i=1}^N\sum_{j=i+1}^N1=c_2\cdot \frac{N^2-N}{2}}$
wenn $c_2$ die konstante Komplexität von "G.AddEdge" ist.

Somit ist dieser Teil $c_1\cdot N+c_2\cdot \frac{N^2-N}{2}=O(N^2)$.


Die Komplexität von Prim Algorithmus ist $O\left ((|V|+|E|)\log |V|\right )$ mit $|V|=N$ und $|E|=\frac{N(N-1)}{2}$, also ist die Komplexität $O\left (\left (N+\frac{N(N-1)}{2}\right )\log N\right )=O\left (N^2\log N\right )$.


Der ganze Algorithmus hat somit die Komplexität: $O(N^2)+O\left (N^2\log N\right )=O\left (N^2\log N\right )$.


Oder ist die Komplexität von "G.AddVertex" und "G.AddEdge" nicht konstant?




Dieses Forumbeitrag kommt von Matroids Matheplanet
https://https://matheplanet.de

Die URL für dieses Forum-Thema ist:
https://https://matheplanet.de/default3.html?topic=250787=7080
Druckdatum: 2021-02-25 08:24