DGL • Thema anzeigen

Wegsuche

Moderator: DGL-Team

Seite 1 von 1

[ 3 Beiträge ]

Vorheriges Thema | Nächstes Thema

Autor

Nachricht

Sentinel

Betreff des Beitrags: Wegsuche

Verfasst: Do Dez 11, 2003 09:20

DGL Member

Registriert: Mo Nov 17, 2003 09:07
Beiträge: 24
Wohnort: Regensburg

Hi Leutz !

Ich bräuchte für ein Projekt einen NICHT rekursiven (Also eine Funktion die sich selbst aufruft) Wegsuch-Algorithmus, und zwar für folgendes Problem: Ich habe z.B. ein Netzwerk mit ca. 1000 Knotenpunkten,wobei jeder Knotenpunkt bis zu 20 Verbindungen mit anderen Knoten haben kann. Falls jemand dafür eine Idee hat, bitte melden.

Nach oben

Flash

Betreff des Beitrags:

Verfasst: Do Dez 11, 2003 13:00

Guitar Hero

Registriert: Do Sep 25, 2003 15:56
Beiträge: 7810
Wohnort: Sachsen - ERZ / C
Programmiersprache: Java (, Pascal)

Denk dir nen Rekursiven Algor. aus und entferne die Rekursion. Eins kann ich dir jetzt schon sagen: Das wird wohl ein recht langer Algorithmus werden.

_________________
Blog: kevin-fleischer.de und fbaingermany.com

Nach oben

tyr

Betreff des Beitrags:

Verfasst: Do Dez 11, 2003 13:58

DGL Member

Registriert: Mi Aug 20, 2003 09:15
Beiträge: 70
Wohnort: Italien

Wenn du alle Knoten in einem Array (oder irgendeiner Liste) speicherst, kannst du einfach alle Knotenpunkte durchgehen und du merkst dir die Position deines Elements.
Danach musst du nur mehr die Position/ Pfad zu deinem Knoten heraussuchen: Du must noch mal alle Elemente durchgehen, und das Element finden, das der Vorgänger des gemerkten Knotens ist.

Ist zwar langsam, aber funktioniert:

Pseudocode:

Code:

 
var i,j : integer;
      ergebnis : array of integer;
 
for i:=1 to SizeOf(<array>) do
  if <array>[i] = gesuchtes_Element then
    merker := i;
 
j:=1;
repeat
  for i:=1 to SizeOf(<array>) do
    if <array>[i].nextes_element = merker then
    begin
      j := j+1;
      SetLength(ergebnis, j);
      ergebnis[j-1] := i;
    end;
until i = Wurzel_knoten_index;
 

_________________
"Phantasie ist wichtiger als Wissen, denn Wissen ist begrenzt" Albert Einstein

Nach oben

Seite 1 von 1

[ 3 Beiträge ]

Foren-Übersicht » Programmierung » Allgemein

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 3 Gäste

Du darfst keine neuen Themen in diesem Forum erstellen.
Du darfst keine Antworten zu Themen in diesem Forum erstellen.
Du darfst deine Beiträge in diesem Forum nicht ändern.
Du darfst deine Beiträge in diesem Forum nicht löschen.
Du darfst keine Dateianhänge in diesem Forum erstellen.