Autor Beitrag
Xart
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 18

XP
D6 Pers
BeitragVerfasst: So 28.03.04 18:28 
Hallo Leute,
bin neu hier und hoffe das mir ein paar erfahrene Programmierer mir meine vielleicht dummen Fragen beantworten können. Ich muss bis Dienstag folgendes Problem im Informatikunterricht vorstellen (ist leider auch Klausurthema) und ich habe leider nicht wirklich viel Ahnung davon :(
Unser Informatiklehrer hat dieses Thema unter dem Namen "GRAPHEN" vorgestellt. Inwiefern das zutreffend ist vermag ich nicht zu beurteilen. Wir besprechen zur Zeit n-p Probleme (weiß nicht wirklich was das sein soll), Greedy Algo. und haben das folgende unter dem Problem des "Handlungsreisenden" "besprochen".
Das Problem ist jedoch das wir nicht wirklich was erklärt bekommen, sondern das wir alles selbst erarbeiten müssen :(

Eine Aufgabe sieht wie folgt aus:

Die Function kurzweg soll den kürzesten Weg von 1 nach 4 finden: Erkläre!
ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
Function kurzweg :integer ;  
Begin
  kn:=1; sum:=0; {Initialisierung}
  repeat   
     for i:=1 to 4 do nachbarentfernungen[i]:=a[kn,i];
     suche_min_entfernung(nachbarentfernungen, num, entf );
     sum:=sum+entf; 
     kn:=num
   Until kn=4; 
{Ziel erreicht.(Problem:Wenn kn=4 nicht erreicht wird, hängen wir in einer Endlosschleife!}
 kurzweg:=sum;
End;

Ich muss zu meiner Schande gestehen das ich den source nicht wirklich verstehe/durchschaue.
Das fängt bei
Zitat:
nachbarentfernungen[i]:=a[kn,i];
an.
Ich muss gestehen das ich ein wenig hilflos bin.

Doch leider ist das noch nicht alles:

Zitat:
Es fehlt natürlich noch die Funktion suche_min_entfernung( ).
Diese sucht im Array nachbarentfernungen den kleinsten Wert
und liefert die Werte num (=nächster Nachbar) und entf (=kürzesteEntfernung) zurück;
Entwirf eine solche Funktion;


Hier habe ich noch weniger Ahnung was ich machen soll.

Ich bin für jede Antwort/Hilfe sehr sehr dankbar :wink:
Ich hoffe das mir jemand helfen kann.

Vielen Dank,
Xart

Moderiert von user profile iconPeter Lustig: Code- durch Delphi-Tags ersetzt
Christian S.
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 20451
Erhaltene Danke: 2264

Win 10
C# (VS 2019)
BeitragVerfasst: So 28.03.04 18:43 
Hallo und :welcome:!


Bis Dienstag? Haben wir ein wenig später angefangen? ;-)

Vorweg: Wir werden Dir nicht die Hausaufgaben machen. Wir werden Dir dabei helfen, dass Du sie machst.

Was noch nötig wäre, wären ein paar Informationen über die verwendeten Arrays, also was für Werte sie speichern.

MfG
Peter

_________________
Zwei Worte werden Dir im Leben viele Türen öffnen - "ziehen" und "drücken".
Xart Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 18

XP
D6 Pers
BeitragVerfasst: So 28.03.04 18:47 
Peter Lustig hat folgendes geschrieben:
Hallo und :welcome:!
Bis Dienstag? Haben wir ein wenig später angefangen? ;-)
Vorweg: Wir werden Dir nicht die Hausaufgaben machen. Wir werden Dir dabei helfen, dass Du sie machst.
Was noch nötig wäre, wären ein paar Informationen über die verwendeten Arrays, also was für Werte sie speichern.


Ja. In der Tat ein wenig spät. Bin aber gewillt zu arbeiten.. Erwarte also nicht (unbedingt ;)) fertige Lösungen.
Weitere Infos zu der Aufgabe die ich habe sind folgende:

"Gegeben ist eine Entfernungsmatrix mit n=4 Orten 1,2,3,4"
ausblenden Quelltext
1:
2:
3:
4:
0  10  60  -
10  0  -  20
60  -  0  25
-  20  25  0


Mehr Infos auch in Bezug auf die Arrays habe ich nicht bekommen.

Vielen Dank schon mal im vorraus für kleine Denkhilfen ;)

Moderiert von user profile iconPeter Lustig: Code-Tags hinzugefügt
raziel
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 2453

Arch Linux
JS (WebStorm), C#, C++/CLI, C++ (VS2013)
BeitragVerfasst: So 28.03.04 18:52 
also wenn ichs recht verstanden hab, dann gibs vier punkte/orte/"kn":
1, 2, 3 und 4
Diese vier sind untereinander verbunden.
im array "a" werden die entfernungen gespeichert.
also a[2,3] = entfernung zwischen 2 und 3,
a[4,1] = a[1, 4] = entfernung zwischen 1 und 4.

und nun soll von 1 -> 4 der kürzeste weg berechnet werden.


raziel

_________________
JSXGraph
raziel
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 2453

Arch Linux
JS (WebStorm), C#, C++/CLI, C++ (VS2013)
BeitragVerfasst: So 28.03.04 18:57 
*grml* wieder ma zu langsam...

aber ich hatte recht... :lol:

nur: was sollen die "-" in der matrix? so richtig bringen tun die ja nix, sin ja keine integer werte -> führt eigentlich zu fehler beim ausführen..., oder?
*grübel*
also eigentlich bedeuten die, dass die orte 1 und 4 und die orte 2 und 3 nicht miteinander verbunden sind...
aber dann sollten sie 0 sein!


raziel

_________________
JSXGraph
Xart Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 18

XP
D6 Pers
BeitragVerfasst: So 28.03.04 19:01 
danke raziel und auch peter für die antworten bisher
zu den dashes in der Matrix
das hat er uns einfach gesagt: dash =keine Verbindung
Christian S.
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 20451
Erhaltene Danke: 2264

Win 10
C# (VS 2019)
BeitragVerfasst: So 28.03.04 19:04 
Okay, raziel hat es ja schon gesagt:

Die Entfernungsmatrix gibt die Entfernungen zwischen den Orten an. Es ist logisch, dass die Entfernung zwischen Ort 4 und Ort 4 Null ist. Wenn die "-" wirklich "nicht verbunden" heißen, würde ich im Array die Werte dort auf einen negativen Wert setzen, damit das markiert wird.

Die erste Schleife ("nachbarentfernungen ...") liest nun also die vier Entfernungen vom aktuellen Ort zu den Nachbarorten (inkl. sich selbst). Die Funktion suche_min_entfernung muss von diesen vier Werten nun den kleinsten Suchen und dann dessen Index und den Wert ausgeben.

So, der Rest sollte dann eigentlich zu schaffen sein. :-)

MfG
Peter

//edit: man muss natürlich drauf achten, dass als kleinster Weg nicht der Nullweg und der gesperrte Weg genommen werden!

_________________
Zwei Worte werden Dir im Leben viele Türen öffnen - "ziehen" und "drücken".
Xart Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 18

XP
D6 Pers
BeitragVerfasst: So 28.03.04 21:43 
vielen Dank soweit.
Ich werde mich damit morgen nochmal genau beschäftigen und hoffe mit Hilfe der Antworten einen Einblick in die Thematik zu bekommen.

Im moment fehlt mir noch der nötige zusammenhang in der prozedur kurzweg, um eine procedure suche_min_entf schreiben zu können.
Gausi
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8554
Erhaltene Danke: 481

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: Mo 29.03.04 12:21 
Wenn ich diese Aufgabe sehe, wird mir schlecht, muss ich sagen. Pisa lässt grüßen. Ihr macht NP(vollständige)-Probleme?
(1) Kürzeste Wege sind nicht NP-vollständig, sondern recht einfach zu finden.
(2) Das HandlungsreisendenProblem (Traveling Salesman Problem, TSP) ist etwas anderes, (nämlich die kürzeste Rundreise über alle Orte zu finden, und dabei jeden Ort nur einmal zu besuchen).
(3) Kürzste Wege sind nicht ein typisches NP-Problem, und meines Wissens nach auch nicht Greedy, und was NP mit Greedy zu tun haben soll, is mir auch schleierhaft.
(4) Außerdem: Der Algorithmus, den ihr da verwenden sollt, ist kein kürzester-Wege Algorithmus (aber er funktioniert in diesem Beispiel)

Wenn schon die Aufgabenstellung so vermurkst ist...Da frag ich mich doch, was an den Schulen heute so gelehrt wird...

Aber ein paar "Hilfen" geb ich trotzdem:
Zu den NP-Problemen: Es wundert mich, dass ihr das macht, denn das is ganz schön hart für den Anfang. Es gibt in der theoretischen Informatik eine sogenannte Turingmaschine. Das ist ein Modell für einen "Rechner". Sie besteht aus einem Turing-Band (unendlich lang), und einem Schreib/Lesekopf, und einer endlichen Menge von Zuständen. In jedem Schritt liest die Maschine ein Zeichen auf dem Band und reagiert darauf, wie es ihr Programm vorgibt. Z.B. Sie ist im Zustand "Grade eine 1 gelesen", und an der Kopfposition wird eine "0" gelesen. Das Programm gibt dann die Anweisung: Wechsle in Zustand "Grade eine 0 gelesen" und verschiebe den Kopf um eine Position nach rechts, usw. Dies ist eine sogenannte "Deterministiche Turingmaschine (DTM)". Es ist durch das Programm genau festgelegt, was zu tun ist. Im wesentlichen kann man alle Computer als eine DTM auffassen, und amn kann damit alles berechnen, was berechenbar ist.

Es gibt aber auch Nicht-Deterministische TM, wo das Programm auch beinhalten kann: "Zustand: X, Gelesen Y, dann mache das, oder jenes oder ganz was anderes.. Die Maschine hat also Wahlmöglichkeiten, die nicht vorherbestimmt sind. Und dieses Prinzip is etwas kompliziert zu begreifen. Wenn ich in eine solche Maschine was eingebe, dann gibt es mehrere Möglichkeiten, was die Mashine daraufhin "ausspuckt", bzw. ob sie überhaupt irgendwann anhält oder nicht.
Eine NDTM löst ein Problem, wenn es eine Abfolge von Entscheidungen gibt, so dass die Maschine anhält und ein Ergebnis ausspuckt. Wenn dies "schnell geht", d.h. in "Polynomial-Zeit", d.h. z.b. wenn ich 100 eingebe, braucht die Maschine 100^2 Rechenschritte (aber nicht 2^100, das wäre exponentiell...), dann is das Problem in Polynomialzeit mit einer Nichtdeterministischen TM lösbar. Alle Probleme, für die es eine solche NDTM gibt, fasst man in einer Klasse von Problemen zusammen. Diese Klasse nennt man NP (Nichtdeterministisch Polynomiell).

Probleme in dieser Klasse sind in der Regel "ziemlich schwierig" zu lösen, weil unsere Computer nicht nichtdeterministisch arbeiten können, und im Prinzip alle Wahlmöglichkeits-Kombinationen hintereinander abarbeiten müssen.
Ein Beispiel: das TSP ist NP vollständig. 1970 konnte man das in einigermaßen vernünftiger Zeit mit 100 Städten mit den Computern lösen. 2000 konnte man das mit 120 Städten machen.

Soweit ein kleiner Einblick in die Theoritische Informatik und das Thema "NP".

Im nächsten Beitrag erklär ich ein bissel den Algorithmus, was da gemacht wird, und warum der falsch ist.

_________________
We are, we were and will not be.
Gausi
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8554
Erhaltene Danke: 481

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: Mo 29.03.04 12:45 
Zum Algorithmus
ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
repeat    
(1)  for i:=1 to 4 do nachbarentfernungen[i]:=a[kn,i]; 
(2)  suche_min_entfernung(nachbarentfernungen, num, entf ); 
(3)  sum:=sum+entf;  
(4)  kn:=num 
Until kn=4;


Stell dir vor, du stehst in Stadt 1 (sagen wir mal Düsseldorf ;-) ) und willst auf dem kürzesten Weg nach Köln.

Du guckst dir zunächst den Wegweiser an, und guckst nach, wie weit es zu den Nachbarstädten ist. Das machst du in (1). Wie Weit ist es zu meinen Nachbarstädten? Das wird in das Array nachbarentfernungen geschrieben. Wenn es keine Verbindung gibt, einfach -1 reinschreiben, wie schon gesagt.
Dann guckst du dir an, welche Stadt am nächsten ist. Z.B. nach Erkrath 8Km, Wuppertal 20KM, Köln -1KM (da keine Verbindung da). Wie das geht, sollte klar sein. Überleg mal, wie man die kleinste Zahl aus mehreren findet, und zusätzlich darf sie nicht 0 oder -1 sein... Dann hats du die Funktion "suche_min_entfernung" so gut wie fertig.
Weil ich faul bin, nehme ich den kürzesten Weg, und gehe nach Erkrath.
In (3) Stelle ich dann fest, dass ich 8Km weitergelaufen bin, und in (4) merk ich mir, dass ich jetzt in Erkrath bin. Da ich nicht in Köln bin, muss ich weitergehen.

Und da komt jetzt das erste Problem: In Erkrath finde ich den Wegweiser Düsseldorf 8KM, Mettman 10KM, sonst nix. Ich bin ja faul, und laufe die kürzeste Strecke, also zurück nach Düsseldorf. Toll gemacht. 16 Km gelaufen, und kein Stück weitergekommen. (Das passier auch in eurem Beispiel, glaube ich...).
Klar kann man sich merken, dass man grad aus Ddorf kommt, und den Weg sperren. Bringt auch nix, wenn der kürzeste Weg aus Mettmann raus nach Ddorf führt => Endlosschleife, weil man immer im Kreis rumläuft.

Dann das zweite: Woher weiss man, dass es von Mettman überhaupt irgendwie nach Köln geht? vielleicht is das ja ne Sackgasse...

Und das dritte: Angenommen, man hätte u.a. folgende Verbindungen:
Ddorf - 30km - Stadt1 - 25km - Stadt2 - 20km - Stadt3 - 15km - Köln (macht 90km) und
Ddorf - 35km - Stadt4 - 5km - Köln (macht 40km)
Rat mal, was der tolle Algorithmus von oben berechnet...

Google mal nach "Dijkstra". Das ist ein echter-Kürzeste Wege Algorithmus, wenn er auch etwas komplizierter ist. Oder frag nach, wenn du da Interesse dran hast...dann erläuter ich den genauer.

_________________
We are, we were and will not be.
Xart Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 18

XP
D6 Pers
BeitragVerfasst: Di 30.03.04 18:05 
Hallo Leute,
vielen Dank nochmal für den Versuch mir das Problem verständlich zu machen ;)
Ich war heut zwar nicht perfekt vorbereitet weil ich nicht in der Lage war die Prozedur zu schreiben... aber naja
wenn es nur ganz kurz ist wär es super cool wenn es verständnishalber (für mich) mir mein Brett vorm Kopf entfernen könnte. Ich hatte auch trotz der vielen Tips hier nicht wirklich ne ahnung.

Aber egal....
ich habe noch ein problem zu Np... Nehmen wir mal an eine Aufgabe würde lauten: "Was sind in der Info. n-p-Probleme?

Meine Antwort würde lauten: " Es sind Probleme welche sich nicht in polynomineller Zeit lösen lassen, d.h. z.B. bei 120 Rechenschritten kann dies exponentiell z.B. 2^120 Schritte => 100te Jahre Rechendauer bedeuten"

Ist das richtig? könnte man das so sagen? Oder was muss man auf jeden Fall ergänzen? Zudem eine andere Verständnisfrage... was genau heißt eigentlich polynominal... ich habe irgendwo etwas von "erfüllbar" gelesen. Ist das korrekt?

Vielen Dank schonmal im vorraus

Xart :)
Christian S.
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 20451
Erhaltene Danke: 2264

Win 10
C# (VS 2019)
BeitragVerfasst: Di 30.03.04 18:09 
Neue Frage -> Neuer Thread

_________________
Zwei Worte werden Dir im Leben viele Türen öffnen - "ziehen" und "drücken".
Dieses Thema ist gesperrt, Du kannst keine Beiträge editieren oder beantworten.

Das Thema wurde von einem Team-Mitglied geschlossen. Wenn du mit der Schließung des Themas nicht einverstanden bist, kontaktiere bitte das Team.