Autor Beitrag
Debo
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 26



BeitragVerfasst: Sa 23.12.06 21:06 
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
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8549
Erhaltene Danke: 478

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: 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 ;-).

_________________
We are, we were and will not be.
alzaimar
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: Sa 23.12.06 22:19 
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]

_________________
Na denn, dann. Bis dann, denn.
Debo Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 26



BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 26



BeitragVerfasst: 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!

ausblenden volle Höhe 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[12] := weg;
 matrix[23] := weg;
 matrix[36] := weg;
 matrix[34] := weg;
 matrix[61] := weg;
 matrix[65] := weg;
 matrix[52] := weg;
 matrix[54] := weg;
 matrix[45] := weg;
 matrix[41] := 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.