Matroids Matheplanet Forum Index
Moderiert von matroid
Kombinatorik & Graphentheorie » Graphentheorie » Algorithmus: Punkte mit geraden Linien verbinden
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Algorithmus: Punkte mit geraden Linien verbinden
mathletic
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 11.11.2013
Mitteilungen: 1435
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-12-01


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?



Wahlurne Für mathletic bei den Matheplanet-Awards stimmen
Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
viertel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.03.2003
Mitteilungen: 27691
Herkunft: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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 ¼


-----------------
Bild
\(\endgroup\)


Wahlurne Für viertel bei den Matheplanet-Awards stimmen
Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
mathletic
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 11.11.2013
Mitteilungen: 1435
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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\)


Wahlurne Für mathletic bei den Matheplanet-Awards stimmen
Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
mathletic
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 11.11.2013
Mitteilungen: 1435
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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?



Wahlurne Für mathletic bei den Matheplanet-Awards stimmen
Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
viertel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.03.2003
Mitteilungen: 27691
Herkunft: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2020-12-01


Was soll daran falsch sein, einen Graphen zu erstellen?

Willst du jetzt nach jedem Codeschnipselchen fragen?



Wahlurne Für viertel bei den Matheplanet-Awards stimmen
Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
mathletic
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 11.11.2013
Mitteilungen: 1435
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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?



Wahlurne Für mathletic bei den Matheplanet-Awards stimmen
Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
viertel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.03.2003
Mitteilungen: 27691
Herkunft: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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?



Wahlurne Für viertel bei den Matheplanet-Awards stimmen
Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
mathletic
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 11.11.2013
Mitteilungen: 1435
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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?



Wahlurne Für mathletic bei den Matheplanet-Awards stimmen
Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
mathletic hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
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]