Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Maximale Verbindungstiefe in einem Diagramm mit Zyklen berechnen

Werbeanzeige

Garzec

Alter Hase

  • »Garzec« ist der Autor dieses Themas

Beiträge: 693

Wohnort: Gießen

  • Private Nachricht senden

1

26.06.2018, 09:43

Maximale Verbindungstiefe in einem Diagramm mit Zyklen berechnen

Hallo,
ich habe ein Array von "Elementen". Diese Elemente haben eine ID. Zusätzlich gibt es noch ein Array von "Verbindungen", diese Verbindungen halten die IDs zwei Elementen, die miteinander verbunden sind.

Jedes Element kann mit jedem Element verbunden sein, ein Kreislauf ist also möglich!

Ausgehend vom ersten Element mit der ID 1 möchte ich die maximale Verbindungstiefe, also die Anzahl der Schritte über die Verbindungen von Element zu Element, für jedes Element berechnen.


(Link)


Die Elemente auf dem Bild sind zufällig angeordnet und miteinander verbunden.

Weg blau bildet einen längeren Weg ab, dieser wäre also vorzuziehen. Dadurch, dass ein Zyklus möglich ist, könnte der Algorithmus aber in eine Endlosschleife laufen!

Ich kenne also meinen Ausgangspunkt ( ID 1 ) und kenne mein aktuelles Ziel Element und möchte den maximalen Weg berechnen.

Testdaten habe ich zufällig zusammengewürfelt

Quellcode

 
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

function Element(id) {
  this.id = id;
}

function Connection(startElementId, targetElementId) {
  this.startElementId = startElementId;
  this.targetElementId = targetElementId;
}

const elements = [
  new Element(1),
  new Element(2),
  new Element(3),
  new Element(4),
  new Element(5),
  new Element(6),
  new Element(7),
  new Element(8),
  new Element(9),
  new Element(10)
];

const connections = [
  new Connection(7, 5),
  new Connection(9, 2),
  new Connection(4, 6),
  new Connection(3, 6),
  new Connection(8, 2),
  new Connection(1, 8),
  new Connection(7, 9),
  new Connection(2, 5),
  new Connection(4, 7),
  new Connection(9, 6),
  new Connection(3, 4),
  new Connection(1, 7),
  new Connection(5, 3),
  new Connection(9, 4)
];


Hat jemand eine Idee, wie man diese Verbindungen untersuchen kann, um die maximale Verbindungslänge herauszufinden und nicht in einen Zyklus zu laufen?

DNKpp

Alter Hase

Beiträge: 635

  • Private Nachricht senden

2

26.06.2018, 09:50

Stichwort breitensuche. Hatten wir das nicht schonmal?

Edit: Noch mal nachgelesen. Ich glaub ich verstehe nicht ganz worauf du hinaus willst.

Edit2: Du möchtest also den längst möglichen Pfad von einem bestimmten Element zu einem bestimmten anderen Element finden? Versuch's doch mal mit einem A* mit umgekehrter prio (sprich immer das unpassendste Node nehmen, statt des besten). Und statt bereits gefundene Knoten mit den günstigeren zu überschreiben eben immer den ungünstigsten behalten.

Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von »DNKpp« (26.06.2018, 09:56)

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

3

26.06.2018, 09:57

Das Problem des längsten Pfades für zyklische Graphen ist NP-schwer (laut Wikipedia). Das bedeutet, dass es höchstwahrscheinlich (d. h. wenn P != NP) keine effizientere Möglichkeit gibt als alle möglichen Pfade durchzuprobieren und am Ende den längsten gefundenen Pfad zurückzugeben.

Google hilft übrigens auch ... https://stackoverflow.com/questions/2679…tween-two-nodes

Ich frage mich ja oft: Wenn ich innerhalb von einer Minute die Antwort mit Google finde, wieso findet sie der Fragensteller nicht? ?(
David Scherfgens Website | Konzentrationstest Polizei

equinox

Frischling

Beiträge: 56

Beruf: Student

  • Private Nachricht senden

4

26.06.2018, 19:24

In so einem Fall vermute ich das der Threadersteller vielleicht das Wort Graph in diesem Kontext nicht kennt (wegen Bezeichnung als "Diagramm") und somit einfach nicht die passenden Suchbegriffe eingeben kann?

Garzec

Alter Hase

  • »Garzec« ist der Autor dieses Themas

Beiträge: 693

Wohnort: Gießen

  • Private Nachricht senden

5

26.06.2018, 20:59

Das ist richtig. Aber ich habe mir jetzt etwas eigenes ausgedacht.

Über Rekursion laufe ich vom Startpunkt aus sämtliche Verbindungen ab und prüfe dabei, ob

- die Verbindung bereits untersucht wurde, falls ja, kann sie geschlossen werden, um eine Endlosschleife zu verhindern
- mein Ziel schon erreicht ist, der Pfad muss nicht weiter untersucht werden
- die Verbindung noch weitere Verbindungen hat, die weiteren Verbindungen müssen untersucht werden
- die Verbindung verworfen werden kann, weil sie nicht zum Ziel führt

Dabei erzeuge ich mir bei gültigen Untersuchungen ein Objekt, dass sich die Vorgänger und Nachfolger merkt, damit auch aus dem Array dieser Objekte einen vollständigen Pfad bauen kann und hinterher der längste Pfad meine maximale Tiefe ergibt.

DNKpp

Alter Hase

Beiträge: 635

  • Private Nachricht senden

6

26.06.2018, 21:14

Zitat von »Garzec«

Über Rekursion laufe ich vom Startpunkt aus sämtliche Verbindungen ab und prüfe dabei, ob

- die Verbindung bereits untersucht wurde, falls ja, kann sie geschlossen werden, um eine Endlosschleife zu verhindern
- mein Ziel schon erreicht ist, der Pfad muss nicht weiter untersucht werden
- die Verbindung noch weitere Verbindungen hat, die weiteren Verbindungen müssen untersucht werden
- die Verbindung verworfen werden kann, weil sie nicht zum Ziel führt

Naja, das ist so ziemlich das Basis-Vorgehen einer jeden Pfadsuche :D

Garzec

Alter Hase

  • »Garzec« ist der Autor dieses Themas

Beiträge: 693

Wohnort: Gießen

  • Private Nachricht senden

7

02.08.2018, 10:39

So, einige Wochen später...

Ziel war es, aus einer Prozessmatrix einen Graphen abzubilden. Dabei konnten die einzelnen Schritte mit sich selbst verbunden sein und weitere Besonderheiten aufweisen. Die gezeichnete Lösung sieht bei Prozessmonstern (zB Support Fälle) nicht schick aus, aber sie erfüllt ihren Zweck.

Hier mal eine Beispielmatrix

https://cdn.discordapp.com/attachments/3…905/unknown.png

und der dazugehörige Graph

https://cdn.discordapp.com/attachments/3…336/unknown.png

Gelöst wurde die Berechnung dank der großen Hilfe von DNKpp mit einem umgedrehten A*, d.h. er sucht sich immer den "teuersten" Weg.

Bitte beachtet auf gar keinen Fall die Lesbarkeit des Codes!!!

https://jsfiddle.net/96nvcedp/5/

Die ganzen Zeichenroutinen, wie sich die Linien ausrichten etc. sind für den Thread ja uninteressant :)

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »Garzec« (02.08.2018, 10:55)

Werbeanzeige

Ähnliche Themen