Autor |
Beitrag |
dubstep
      
Beiträge: 72
Win XP, Win 7
C# (VS 2010)
|
Verfasst: Fr 03.12.10 23:24
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
      

Beiträge: 4798
Erhaltene Danke: 1059
Win10
C#, C++ (VS 2017/19/22)
|
Verfasst: 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 
      
Beiträge: 72
Win XP, Win 7
C# (VS 2010)
|
Verfasst: 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
      
Beiträge: 3803
Erhaltene Danke: 176
Arch Linux
Python, C, C++ (vim)
|
Verfasst: Sa 04.12.10 14:11
LINQ to Objects fehlen leider ein paar wichtige Methoden. Was du eigentlich suchst, ist MinBy.
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
      

Beiträge: 4798
Erhaltene Danke: 1059
Win10
C#, C++ (VS 2017/19/22)
|
Verfasst: 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 
      
Beiträge: 72
Win XP, Win 7
C# (VS 2010)
|
Verfasst: 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 ... 
|
|
Kha
      
Beiträge: 3803
Erhaltene Danke: 176
Arch Linux
Python, C, C++ (vim)
|
Verfasst: Mi 08.12.10 20:32
|
|
dubstep 
      
Beiträge: 72
Win XP, Win 7
C# (VS 2010)
|
Verfasst: 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  . 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
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
      
Beiträge: 3803
Erhaltene Danke: 176
Arch Linux
Python, C, C++ (vim)
|
Verfasst: 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|²) 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 
      
Beiträge: 72
Win XP, Win 7
C# (VS 2010)
|
Verfasst: 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
      
Beiträge: 3803
Erhaltene Danke: 176
Arch Linux
Python, C, C++ (vim)
|
Verfasst: 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  ? 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  ?
_________________ >λ=
|
|
|