| Autor |
Beitrag |
Debo
 
Beiträge: 26
|
Verfasst: 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
Beiträge: 8549
Erhaltene Danke: 478
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: 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
Beiträge: 2889
Erhaltene Danke: 13
W2000, XP
D6E, BDS2006A, DevExpress
|
Verfasst: Sa 23.12.06 22:19
 Debo 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...  [/edit] _________________ Na denn, dann. Bis dann, denn.
|
|
Debo 
Beiträge: 26
|
Verfasst: 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
Beiträge: 26
|
Verfasst: 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!
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. |
|
|
|
