Verschoben! Berechnung von Kruskal Algorithmus

Neue Frage »

Jator08 Auf diesen Beitrag antworten »
Berechnung von Kruskal Algorithmus
Hallo, ich hätte eine Frage zu der Berechnung von Kruskal Algorithmus.

Und zwar habe ich da eine Excel Tabelle mit 5 verschiedenen Spalten: "Kante", "von", nach", "Distanz", und "SCHALTER".

Also die ersten 4 Spalten kann ich ja lösen, aber wie berechnet man die Spalte "Schalter" ?

Danke
Jator08 Auf diesen Beitrag antworten »

UP
Jator08 Auf diesen Beitrag antworten »

Kann mir niemand helfen? unglücklich
RavenOnJ Auf diesen Beitrag antworten »
RE: Berechnung von Kruskal Algorithmus
Zitat:
Original von Jator08
Und zwar habe ich da eine Excel Tabelle mit 5 verschiedenen Spalten: "Kante", "von", nach", "Distanz", und "SCHALTER".

Also die ersten 4 Spalten kann ich ja lösen, aber wie berechnet man die Spalte "Schalter" ?


Wovon redest du eigentlich? Und jetzt antworte bloß nicht "vom Kruskal Algorithmus".
Jator08 Auf diesen Beitrag antworten »

Also wir möchten in der Schule einen Routenplaner erstellen.
Dazu haben wir z.B. 10 Städte. Angenommen von Madrid nach Lissabon sind es 500 km. Von Madrid nach Paris 700 km usw.

Diese Daten tragen wir in eine Excel Tabelle ein.
In diesem Beispiel wäre Madrid "1", Lissabon "2", Paris "3" usw.

"Kante" ist einfach die Nummerierung (1, 2, 3, 4, 5, usw.)
"von" ist die Stadtnummer vom Ausgangsort (Madrid hat 1)
"nach" ist die Stadtnummer vom Zielort (Lissabon hat 2)
"Distanz" ist dann die Kilometeranzahl (also von 1 nach 2: 500)

Und bei Schalter weiß ich leider nicht wie man diese Spalte berechnet. Man muss entweder "0" oder "1" eintragen. Aber wovon ist das abhängig?


Man muss halt einfach die kürzeste Strecke berechnen, wenn man z.B. von Madrid nach London will.
RavenOnJ Auf diesen Beitrag antworten »

Und welche Bedeutung hat "Schalter"?
 
 
Huggy Auf diesen Beitrag antworten »

Offenbar weiß das der Fragesteller nicht. Aber wie sollen es dann potentielle Helfer wissen? Eine vage Vermutung: Der Schalter könnte aussagen, ob es eine direkte Straßenverbindung zwischen den beiden Städten gibt. Falls man Schalter = 1 als ja interpretiert, wären dann für den Algorithmus nur solche Kanten relevant bei denen Schalter = 1 ist.

@Jator08
Frage doch mal den Lehrer, welche Bedeutung der Schalter hat.
RavenOnJ Auf diesen Beitrag antworten »

@Huggy
Aber dies soll doch angeblich berechnet werden. Aber wahrscheinlich hast du recht, dass der FS das selber nicht weiß.

Ansonsten sehe ich gerade nicht, was ein minimaler Spannbaum für eine Routenberechnung bringen soll. Da wäre doch eher der Dijkstra-Algorithums geeignet.
Huggy Auf diesen Beitrag antworten »

Zitat:
Original von RavenOnJ
Ansonsten sehe ich gerade nicht, was ein minimaler Spannbaum für eine Routenberechnung bringen soll. Da wäre doch eher der Dijkstra-Algorithums geeignet.

Sehe ich auch so.
Jator08 Auf diesen Beitrag antworten »

Achso ja, es kann auch dieses Dijkstra Algorithmus sein.
RavenOnJ Auf diesen Beitrag antworten »

Zitat:
Original von Jator08
Achso ja, es kann auch dieses Dijkstra Algorithmus sein.


Übrigens: Es heißt der Algorithmus, nicht das.
Jator08 Auf diesen Beitrag antworten »

Okay, also ich habe jetzt hier die Angabe für dieses Beispiel. Vielleicht ist es dann verständlicher.


a) "Ermitteln der Entfernungen zwischen den Orten
Hilfsmittel: Straßenkarte, Routenplaner"


b) Eine Firma besitzt zwei Lager in Innsbruck und Linz. Für beide Städte soll ein Tabelle mit den minimalen Distanzen zwischen dem jeweiligen Lager und jedem übrigen Ort ermittelt werden. Die zu fahrenden Routen sind außerdem graphisch darzustellen.



"Verfahren: Algorithmus von Dijkstra oder Ford bzw. Tripel-Algorithmus
Hilfsmittel: Mathe-Light, Unterprogramm ""Kurzweg"""


c) Ein Außendiestmitarbeiter fährt einmal pro Woche alle Ortschaften ab. Die optimale Route ist zu ermitteln.


"Verfahren: verschiedene Verfahren des TSP
Hilfsmittel: Mathe-Light, Unterprogramm ""Rundreise"""


d) Alle Ortschaften sollen durch ein Versorgungsnetz mit minimaler Länge verbunden werden.

"Verfahren: Algorithmus von Kruskal oder Prim
Hilfsmittel: Excel"
RavenOnJ Auf diesen Beitrag antworten »

Schön, dann mach mal. Du erwartest wohl nicht, dass wir dir eine Lösung präsentieren, oder? Du musst einfach mehr selber liefern, dann wird dir auch geholfen.
Jator08 Auf diesen Beitrag antworten »

Dein Ernst?
Die Aufgabe ist doch nur nebensächlich, ich möchte doch nur wissen wie man "Schalter" berechnet.
Dass ich jetzt die ganze Aufgabe geschrieben habe, war nur deshalb, damit man weiß kann um was es genau geht...

Edit: Die Lösung bis zu "Schalter" hab ich etwas weiter oben geschrieben, nur halt mit Beispielsstädten und Beispielszahlen
RavenOnJ Auf diesen Beitrag antworten »

Du hast noch nicht mal geschrieben, was "Schalter" eigentlich bedeutet. Wie soll dann jemand wissen, wie das berechnet wird?
Jator08 Auf diesen Beitrag antworten »

Weil ich mich in einem Forum mit Matheexperten befinde.
Ich hab die ganze Aufgabe geschrieben, damit jeder weiß um was es genau geht. Ich gehe eigentlich schon davon aus, dass irgendjemand hier im Algebra Unterforum diese Aufgabe lösen kann.

Meinen Ansatz habe ich bereits geschrieben.
"Kante", "von", "nach", "Distanz", "Schalter"
Die ersten 4 Spalten kann ich selbstständig rechnen. Nur weiß ich nicht wie man Schalter berechnet. Diese Spalte soll den minimalen Spannbaum darstellen.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »