Entwickler-Ecke

Algorithmen, Optimierung und Assembler - kürzeste Verbindung von A nach B , Graphentheorie


Debo - Sa 23.12.06 21:06
Titel: kürzeste Verbindung von A nach B , Graphentheorie
NabenT,

Darf ein Referat über das Thema "kürzeste Verbindung von A nach B" halten. Das Oberthema lautet zur Zeit Graphentheorie.

Der Graph besteht aus ungewichteten Kanten, also kann ich mit Algorithmen, wie den A*-Algorithmus oder dem Dijkstra- Algorithmus nicht viel Anfangen.

Ich dachte mir, dass ich das Problem mit der Breiten- und Tiefensuche lösen kann, doch bekomm ich zwar eine Lösung (von A nach B), jedoch nicht immer den kürzesten Weg.

Eine andere Möglichkeit wäre alle Wege auszuprobieren und sich einfach alle Kanten zu merken, sprich wie lang der Weg nun war. Dies erscheint mir aber zu umständlich und zu Rechenaufwändig.

In der Suche finde ich auch den schnellsten oder kürzesten Weg bei gewichteten Kanten, jedoch nicht für ungewichtete Kanten.

Ich wäre über Hilfe sehr erfreut, gerne auch mathemathische Ansätze, die vielleicht zeigen, wie man den Rechenaufwand minimiert.

Ciao


Gausi - Sa 23.12.06 21:37
Das sollte eigentlich mit Breitensuche gehen. Starte bei A eine Breitensuche, merke dir dabei jeweils den Vorgängerknoten und breche ab, wenn du bei B ankommst.
Tiefensuche ist natürlich nicht das richtige.

Ansonsten: Nimm den Algorithmus für gewichtete Graphen und setze als Kantengewicht immer 1 ;-).


alzaimar - Sa 23.12.06 22:19
Titel: Re: kürzeste Verbindung von A nach B , Graphentheorie
user profile iconDebo hat folgendes geschrieben:
Der Graph besteht aus ungewichteten Kanten, also kann ich mit Algorithmen, wie den A*-Algorithmus oder dem Dijkstra- Algorithmus nicht viel Anfangen.

Wenn die Kanten wirklich *keine* Gewichtung hätten, gäbe es keinen kürzesten Weg, denn wie will man den denn messen (ode jegliche Wichtung)? Wenn die Kanten das Gewicht '0' hätten, wäre ja ein Weg, der alle Kanten besucht genauso kurz, wie einer, der direkt von A nach B läuft...
'Ungewichtet' bedeutet hier nur, das alle Kanten gleich viel wert sind, oder lang, oder eben gleich gewichtet sind. Dann kannst du selbstverständlich ebenso mit A* oder Dijkstra ran: Setze für jede Kante einfach den Wert '1' ein (oder 1000, vollkommen egal).

[edit] Hatte Gausis letzten Satz übersehen... :oops: [/edit]


Debo - So 24.12.06 23:26
okeh ihr habt recht. ich habe mich falsch ausgedrückt.

ich wollte nicht algorithmen nehmen, die dafür eigentlich nicht vorgesehen sind. ich wollte vielmehr wissen ob es dafür spezielle lösungen gibt.


Debo - Do 11.01.07 20:24
Also,

ich habe nun die Breitensuche programmiert nur bekomm ich den Weg nicht heraus, den ich gegangen bin bzw. die Länge des Weges.

Mit meiner jetzigen Ausgabe bekomme ich nur ein Protokoll meiner Schlange....

Danke schonmal für eure Hilfe!


Delphi-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:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
 
CONST maxn = 6;
      weg = 1;
      frei = 1;
      wartend = 2;
      fertig = 3;

TYPE tinfo  = RECORD
                nr : Integer;
              END;
     matrix_type = ARRAY[1..maxn, 1..maxn] OF INTEGER;
     knottype    = Array[1..maxn] of Integer;

{$I QUEUE.ADT}
{$R *.dfm}

VAR A, B            : INTEGER;
    qu1             : tqueue;
    matrix          : matrix_type;
    aktuell,nachbar : tinfo;
    knoten          : knottype;


PROCEDURE init(VAR matrix: matrix_type);
VAR von, nach, i : INTEGER;
BEGIN
 FOR von := 1 TO maxn DO
   FOR nach := 1 TO maxn DO matrix[von, nach] := 0;
 matrix[1, 2] := weg;
 matrix[2, 3] := weg;
 matrix[3, 6] := weg;
 matrix[3, 4] := weg;
 matrix[6, 1] := weg;
 matrix[6, 5] := weg;
 matrix[5, 2] := weg;
 matrix[5, 4] := weg;
 matrix[4, 5] := weg;
 matrix[4, 1] := weg;

END;



PROCEDURE BREITENSUCHE(A : Integer; B : Integer; VAR knoten : knottype);
Var i,j : INTEGER;
BEGIN
FOR j:=1 to maxn DO knoten[j] := frei;
create_qu(qu1);
aktuell.nr:=A;
en_qu(qu1,aktuell);
knoten[A]:=wartend;
while not empty_qu(qu1) do
begin
  front_qu(qu1,aktuell);
  if aktuell.nr = B then
  begin
    showmessage('weg gefunden');
  end;
  knoten[aktuell.nr] := fertig;
  Form1.ListBox1.Items.Add(IntToStr(aktuell.nr));
  de_qu(qu1);
  For i:=1 to maxn do
  begin
    if matrix[aktuell.nr,i] = weg then
      if knoten[i] = frei then
      begin
        nachbar.nr := i;
        en_qu(qu1,nachbar);
        knoten[i] := wartend;
      end;
  end;
end;
END;



procedure TForm1.Button1Click(Sender: TObject);
begin
A := StrToInt(Edit1.Text);
B := StrToInt(Edit2.Text);
init(matrix);
Breitensuche(A,B,knoten);
end;

end.


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!