Entwickler-Ecke
Algorithmen, Optimierung und Assembler - Hilfe bei Prim-Algorithmus
dubstep - Fr 03.12.10 23:24
Titel: Hilfe bei Prim-Algorithmus
Ich würde gerne selbst einen Prim-Algorithmus implementieren. Die Effizienz ist dabei mal nicht so wichtig.
C#-Quelltext
1: 2: 3: 4: 5: 6: 7: 8:
| Node Startknoten = new Node("Berlin"); string knotenname = Startknoten.name;
Dictionary<double, Edge> Kantendatenbank = new Dictionary<double, Edge>(); Kantendatenbank.Add(1, new Edge(Startknoten.name, "Hamburg", 85)); Kantendatenbank.Add(2, new Edge(Startknoten.name, "Köln", 140));
var minvalue = Kantendatenbank.Min(x => x.Value.distanz); |
Ich kann zwar die kürzeste Distanz aus dem Dictionary auslesen, aber irgendwie schaffe ich es nicht, auch noch den zur kürzesten Distanz zugehörigen Namen des Knotens (also Berlin) aus Edge rauszubekommen.
Die vorläufige Ausgabe(mir ist schon klar, dass das noch lange keinen Prim-Algorithmus ergibt) sollte dann die Information der kürzesten Distanz und die des zugehörigen Knotens enthalten. Diese Information möchte ich dann in einer weiteren dynamischen Datenstruktur speichern.
Kann mir vielleicht jemand einen Ansatz geben - ich finde weder etwas passendes im C# noch im Internet? :?
Th69 - Sa 04.12.10 00:23
Du brauchst doch nur mittels 'minvalue' wieder auf das Dictionary zuzugreifen:
C#-Quelltext
1: 2: 3:
| Edge edge = Kantendatenbank[minvalue]; Node node = edge.StartNode; string name = node.name; |
P.S. 'name' und 'distanz' solltest du besser als Eigenschaften 'Name' und 'Distanz' anlegen (auf keine Fall als öffentliche Membervariablen: Kapselungsprinzip der OOP).
dubstep - Sa 04.12.10 13:51
Danke erstmal!
C#-Quelltext
1:
| Edge edge = Kantendatenbank[minvalue]; |
Das Problem bei diesem Befehl ist, dass hier ausschließlich nach dem Key im Dicitionary gesucht wird: Dictionary[Key]. Klar könnte ich jetzt den Keys die selbe Zahl, wie den Kantengewichten geben (und damit wäre das Problem vorerst gelöst), aber langfristig können Kantengewichte ja auch doppelt vorkommen und spätestens dann hat man mit den Keys ein Problem.
Mit Dictionary.TryGetValue(key, out) habe ich es auch schon versucht, dies führt aber ebenfalls nicht zum gewünschten Ergebnis.
Ich suche einen Befehl, der mir aufgrund eines bekannten value-Wertes (nämlich minvalue), die restlichen value-Werte (vorknoten und nachknoten) zurückgibt - dies unter der Vorraussetzung, dass der zugehörige Key nicht bekannt ist.
Hmm, wäre vielleich ein Priority-Queue die bessere Lösung?
Kha - Sa 04.12.10 14:11
LINQ to Objects fehlen leider ein paar wichtige Methoden. Was du eigentlich suchst, ist
MinBy [
http://code.google.com/p/morelinq/wiki/OperatorsOverview].
dubstep hat folgendes geschrieben : |
Hmm, wäre vielleich ein Priority-Queue die bessere Lösung? |
Wenn "besser" "performanter" heißen soll, dann dürfte Wikipedia deine Frage beantworten ;) . Was der Key deines Dictionaries eigentlich darstellen soll, habe ich sowieso nicht verstanden.
Th69 - Sa 04.12.10 14:56
Sorry dubstep,
da war ich wohl gestern abend nicht mehr ganz fit. Du ermittelst ja die minimale Distanz und diese steht dann in 'minvalue', nicht der Index. Somit macht mein direkter Zugriff keinen Sinn...
Dir fehlt wohl wirklich ein MinBy -)
dubstep - Di 07.12.10 03:17
Das ist eine Art Erweiterung zu den schon vorhandenen Methoden - oder? Das Problem ist nur, dass dadurch meine C#-Datei sehr individuell wird und ich sie zur (z.B. Kontrolle durch Dritte) nicht weitergeben kann, da diese die von mir verwendeten Methoden nicht haben.
Ich denke, dass ich um das "Priority Queue" nun doch nicht herumkommen werde. Die Implementierung eines Queue ist nicht schwer - es wird das FIFO-Verfahren genutzt. Bei der Implementierung eines Priority Queue habe ich jedoch Probleme.
Im Internet findet man sehr viel über Priority Queues - brauchbare Information kann ich jedoch nicht wirklich daraus gewinnen.
Ein Codebeispiel habe ich gefunden: Dabei hat der Benutzer jedem Wort eine Priorität zugeordnet. Bei der Ausgabe sind dann die Wörter ihrer Priorität nach ausgegeben worden. Umgesetzt auf den Prim-Algorithmus, müsste ich dann jedem Kantengewicht (also die Distanz zwischen Knoten "x" und Knoten "y") eine Priorität zuweisen? Logischerweise würde das geringste Kantengewicht auch die höchste Priorität erhalten.
Ein weiteres Problem: Die dynamische Datenstruktur "Queue" wird in C# automatisch erkannt, "Priority Queue" jedoch nicht. Liege ich also richtig, dass das erst selbst erzeugt werden muss?
Th69 hat folgendes geschrieben : |
Sorry dubstep,... |
Absolut kein Problem - wie gesagt, ich bin eigentlich über jeden Vorschlag dankbar ... :wink:
Kha - Mi 08.12.10 20:32
dubstep hat folgendes geschrieben : |
Das ist eine Art Erweiterung zu den schon vorhandenen Methoden - oder? |
Naja, was heißt Erweiterung... eher eine alleinstehende Methode, die du natürlich auch direkt in deine Klasse kopieren kannst, wenn dir das so wichtig ist, oder sicher auch mit ein wenig Überlegen selbst schnell heruntertippen könntest. Im Vergleich zum Heap für die Priority Queue dürfte das ein Klacks sein ;) .
Kha hat folgendes geschrieben : |
Umgesetzt auf den Prim-Algorithmus, müsste ich dann jedem Kantengewicht (also die Distanz zwischen Knoten "x" und Knoten "y") eine Priorität zuweisen? |
Ja.
Kha hat folgendes geschrieben : |
Liege ich also richtig, dass das erst selbst erzeugt werden muss? |
Ja. [
http://stackoverflow.com/questions/102398/priority-queue-in-net]
dubstep - Fr 10.12.10 03:56
Also, ich hab jetzt mal ein (hoffentlich richtiges) Priority Queue gebastelt. Jedenfalls arbeitet es wie es soll - es sortiert die Einträge ihrer Priorität nach. Im Prinzip ist ein Priority Queue nicht einmal ein Queue :shock:. Es ist vielmehr eine Umsetzung eines primitiven (eigentlich nur eine for-Schleife) Sortieralgorithmus mit zwei List<T>-Datenstrukturen. Irgendwie schon verwunderlich, dass die Performance eines Priority Queues besser, als die eines Dictionaries sein soll.
Um nun weiterarbeiten zu können, sollte ich die List<T> im Priority Queue durch ein Dictionary (mit Vorknoten, Nachknoten und Kantengewicht) ersetzen ...?
Hier noch das Priority Queue:
PriorityQueue.cs
C#-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35:
| using System; using System.Collections.Generic; using System.Linq; using System.Text;
namespace Prim_Algorithmus { public class PriorityQueue<T> { public List<string> Knotenliste = new List<string>(); public List<int> Prioritätenliste = new List<int>(); public void Enqueue(string name, int priorität) { Knotenliste.Add(name); Prioritätenliste.Add(priorität); } public void Dequeue(out string TopKnoten, out int TopPriority) { int BestIndex = 0; int BestPriority = Prioritätenliste[0]; for (int i = 0; i < Prioritätenliste.Count; i++) { if (BestPriority < Prioritätenliste[i]) { BestPriority = Prioritätenliste[i]; BestIndex = i; } } TopKnoten = Knotenliste[BestIndex]; TopPriority = Prioritätenliste[BestIndex]; Knotenliste.RemoveAt(BestIndex); Prioritätenliste.RemoveAt(BestIndex); } } } |
Program.cs
C#-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26:
| using System; using System.Collections.Generic; using System.Linq; using System.Text;
namespace Prim_Algorithmus { public class Program { public static void functionname(string TopKnoten, int TopPriority, PriorityQueue<string> Queue) { Queue.Enqueue("Frankfurt", 11); Queue.Enqueue("Berlin", 13); Queue.Enqueue("Hamburg", 12); Queue.Dequeue(out TopKnoten, out TopPriority); Console.WriteLine(TopKnoten); }
static void Main(string[] args) { PriorityQueue<string> Queue = new PriorityQueue<string>(); functionname("",0,Queue); Console.ReadLine(); } } } |
Kha - Fr 10.12.10 16:01
dubstep hat folgendes geschrieben : |
Irgendwie schon verwunderlich, dass die Performance eines Priority Queues besser, als die eines Dictionaries sein soll. |
Rechne die asymptotische Laufzeit doch mal selbst nach - du hast die denkbar einfachste Implementierung einer Priority Queue umgesetzt, damit wirst du nur
O(|V|²) [
http://en.wikipedia.org/wiki/Prim%27s_algorithm] erreichen.
dubstep hat folgendes geschrieben : |
Um nun weiterarbeiten zu können, sollte ich die List<T> im Priority Queue durch ein Dictionary (mit Vorknoten, Nachknoten und Kantengewicht) ersetzen ...? |
Ich weiß wie bei deinem ersten Dictionary nicht, was du dort als Key verwenden willst und warum. Eigentlich sollte die Priority-Queue einfach Objekte einer Kanten-Klasse enthalten.
dubstep - Fr 10.12.10 20:35
Kha hat folgendes geschrieben : |
Ich weiß wie bei deinem ersten Dictionary nicht, was du dort als Key verwenden willst und warum. Eigentlich sollte die Priority-Queue einfach Objekte einer Kanten-Klasse enthalten. |
Die Frage ist berechtigt. Ich verwende gerne ein Dictionary, weil es - so wurde mir immer wieder gesagt - die effizienteste dynamische Datenstruktur ist. Beim Dictionary werden beim Suchprozess nicht alle Einträge durchlaufen (bei anderen Datenstrukturen, wie z.B. einer LinkedList, ist das anders ...). Ein weiterer Grund: Ich sehe den Key als zusätzlichen Parameter und daher nicht wirklich als Nachteil.
Kha - Sa 11.12.10 15:49
Ich fürchte, du hast den Sinn und die Funktionsweise von Dictionaries noch nicht ganz verstanden. Ja, sie geben dir eine O(1)-Suche nach Keys - aber wo sollte das bei Prim hilfreich/relevant sein :nixweiss: ? Was hier
wirklich die effizienteste Datenstruktur ist, sollte dir Wikipedia doch langsam gesagt haben: Eine Fibonacci Queue.
dubstep hat folgendes geschrieben : |
Ein weiterer Grund: Ich sehe den Key als zusätzlichen Parameter und daher nicht wirklich als Nachteil. |
Und eine komplexe Zahl speicherst du als
List<double>, oder wie ;) ?
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!