Du bist nicht angemeldet.

Werbeanzeige

Garzec

Alter Hase

  • »Garzec« ist der Autor dieses Themas

Beiträge: 692

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?

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.
Besucht mich und meinen Blog unter:
www.simple-world.org

Du magst Tower Defense?
Dann probier doch mal Coregrounds aus ;)

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


David Scherfgen

Administrator

Beiträge: 10 199

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? ?(

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: 692

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.

6

26.06.2018, 21:14

Ü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
Besucht mich und meinen Blog unter:
www.simple-world.org

Du magst Tower Defense?
Dann probier doch mal Coregrounds aus ;)

Garzec

Alter Hase

  • »Garzec« ist der Autor dieses Themas

Beiträge: 692

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