| |
| Autor |
 Algorithmus: Punkte mit geraden Linien verbinden |
|
mathletic
Aktiv 
Dabei seit: 11.11.2013
Mitteilungen: 1435
 |
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?
|
 Notiz  Profil
 Quote
 Link |
viertel
Senior 
Dabei seit: 04.03.2003
Mitteilungen: 27755
Herkunft: Hessen
 |      Beitrag No.1, eingetragen 2020-12-01
|
\(\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\)
|
Notiz Profil
Quote
Link |
mathletic
Aktiv
Dabei seit: 11.11.2013
Mitteilungen: 1435
| Beitrag No.2, vom Themenstarter, eingetragen 2020-12-01
|
\(\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\)
|
Notiz Profil
Quote
Link |
mathletic
Aktiv 
Dabei seit: 11.11.2013
Mitteilungen: 1435
| Beitrag No.3, vom Themenstarter, eingetragen 2020-12-01
|
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?
|
Notiz Profil
Quote
Link |
viertel
Senior 
Dabei seit: 04.03.2003
Mitteilungen: 27755
Herkunft: Hessen
| Beitrag No.4, eingetragen 2020-12-01
|
Was soll daran falsch sein, einen Graphen zu erstellen?
Willst du jetzt nach jedem Codeschnipselchen fragen?
|
Notiz Profil
Quote
Link |
mathletic
Aktiv
Dabei seit: 11.11.2013
Mitteilungen: 1435
| Beitrag No.5, vom Themenstarter, eingetragen 2020-12-01
|
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?
|
Notiz Profil
Quote
Link |
viertel
Senior
Dabei seit: 04.03.2003
Mitteilungen: 27755
Herkunft: Hessen
| Beitrag No.6, eingetragen 2020-12-01
|
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?
|
Notiz Profil
Quote
Link |
mathletic
Aktiv
Dabei seit: 11.11.2013
Mitteilungen: 1435
| Beitrag No.7, vom Themenstarter, eingetragen 2020-12-01
|
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?
|
Notiz Profil
Quote
Link |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
