Java - Distanzmatrix Algorithmus, Wie ansetzen?

Hallo, ich bin gerade dabei ein Graphenprogramm zu schreiben und stecke bisschen bei der Distanzmatrix.

Ich weiß nicht ob sich jemand bei Graphentheorie auskennt oder nicht aber der Algorithmus für die Distanzmatrix ist relativ einfach. Nur das umsetzen in Code fällt mir sehr schwer und deswegen hoffe ich, dass ihr mir vielleicht dabei helfen könnt..

Der Algorithmus für eine Distanzmatrix lautet so:

Man hat eine Eingangsmatrix (Adjazentmatrix).
Die könnte so aussehen:

Man markiert sich alle Nuller die in der Adjazentmatrix vorkommen (AUßER DIE HAUPTDIAGONALE, DIE BLEIBT UNBERÜHRT).

Dann erstellt man sich eine eigene Matrix die man "DistanzMatrix" nennen kann und setzt alle Nuller die eben in der Adjazentmatrix vorkommen auf "Unendlich" oder auch auf INTEGER.MAX_VALUE in der Programmiersprache .

Das schaut dann so aus:

Also haben wir jetzt 2 Matrizen. Bis dahin habe ich es auch geschafft in meinem Programm. Die Ausgabe schaut bei mir so aus:

Die "-9" sind alle Nuller, die auf UNENDLICH gesetzt sind (siehe zweites Bild).

Der nächste Schritt ist es die Potenzen der Eingangsmatrix (Adjazentmatrix) zu berechnen. Das habe ich ebenfalls schon geschafft im Code.

Das heißt, die Adjazentmatrix (siehe Bild 1) wurde potenziert und so könnte das Ergebnis der Potenzberechnug aussehen.

Man schaut sich jetzt alle Nuller (außer die Hauptdiagonale von der Eingangsmatrix an (siehe Bild 1)) und markiert sich nur die Zahlen (rot), die sich von der Potenzierung der Eingangsmatrix verändert haben. (Außer die Nuller (=Neue Nuller die durch die Potenzierung entstanden sind bleiben auch weiterhin eine Null))

Und der letzte Schritt ist es jetzt, die von mir erstellte DistanzMatrix upzudaten, indem ich im ersten Schritt alle rote Zahlen von A²(G) in 2 umwandle. Alle Nuller die übrig bleiben, werden wieder in UNENDLICH umgewandelt.

Und das wird jetzt so oft wiederholt, bis es keine UNENDLICH Zeichen mehr in der Distanzmatrix gibt. Und aus UNENDLICH wird 3. Und immer so weiter.. Falls es zb nach der fünften Potenzierung immer noch Nuller bzw UNENDLICH Werte gibt dann wird aus UNENDLICH 5.

Somit ist D³(G) das Ergebnis.

Ich hoffe ich konnte es ausführlich genug erklären

Danke

Bild zum Beitrag
Computer, Schule, Technik, programmieren, Java, Informatik, Technologie, Algorithmus, Graphentheorie
Maze Solving Algorithmus?

Hi,

ich will mehrere Algorithmen implementieren, womit ich ein Maze lösen kann. Dabei gehts mir um Geschwindigkeit. Das gesamte Maze ist schon bekannt, also die "Maus" kann von jedem Punkt erfahren ob es eine Wand, oder ein Weg ist.

Derzeit habe ich den Wavepropagation, den Wallfollower und einen Kombi algorithmus implementiert. Der Kombi algorithmus entstand, nachdem ich Rekursion versucht hatte, bis ich gemerkt habe, dass das ja garnicht in C# geht xD

Dann hab ich per While loop einfach immer geguckt welche Richtungen sind möglich und dann halt random eine Richtung gewählt. Wenns deadend ist, halt wieder zurück, bis eine unbesichtigte Zelle kommt. Vllt habt ihr ja eine Idee wie der heißt.

Für mich neuling kling der Wavepropagation algorithmus derzeit am optimalsten, denn er hört auf, sobald das ziel gefunden ist.

Man könnte evtl. den noch Optimieren, indem man an an jeder Kreuzung ein Node setzt.

Der Djiktra klingt für mich als Neuling wie ähnlich des Wavepropagation Algorithmus, zumindest wenn man nicht die Map in nodes (bei jeder Kreuzung) plaziert.

Gibts einen viel schnelleren?

Die Map ist so um die 10k x 10k bis 15k x15k

Evtl auch mehr, wenn ich diese nicht painten würde, sondern nur als byte array lasse. Dauert aber so schon lang genug xD

Generiert wird dieses per Binary Tree derzeit. Dieser ist wenigstens Ultra schnell. Prims algorithmus ist mir zu langsam für diese Größenordnung.

Computer, Mathematik, programmieren, Datenverarbeitung, Informatik, Algorithmus
Bei Djkstra mit negativen Kantengewichten positive Konstante addieren?

Einen wunderschönen guten boungiorno an alle,

Gegeben sei ein Graph G mit negativen Kantengewichten w ∈ ℤ \ℕ. Sei k das kleinste Gewicht einer Kante. Wir verfolgen die folgende Strategie, um die negativen Gewichte in positive zu transformieren: Addiere |k| auf jedes Kantengewicht und führe den Dijkstra-Algorithmus aus.Führt unsere Strategie zu einer korrekten Bestimmung der kürzesten Wege in G? Begründe Deine Antwort anhand eines Beispielgraphen.

Ansatz: Ich bin mir nicht sicher ob ich die Aufgabe richtig verstanden habe. Wir haben hier jetzt einen Graphen, der ausschließlich aus negativen Kantengewichten besteht. Und jetzt sollen wir |k| also das größte negative Gewicht auf jede einzelne Kante addieren und prüfen, ob Dijkstra noch korrekt funktioniert. Und genau da liegt der Hund in der Petersilie begraben. Weil Djkstra arbeitet doch ohnehin schon nicht mehr 100 % korrekt mit negativen Kantangewichten. Wie soll ich dann prüfen, ob er unter dieser Modifikation ( |k| drauf addieren ), dann noch korrekt arbeitet, wenn schon mal die Voraussetzung für korrektes Arbeiten nicht mehr erfüllt ist.

In dem Hinweis steht jetzt „Begründe Deine Antwort anhand eines Beispielgraphen“.. das hört sich so an als würden die dann nach einem Gegenbeispiel fragen.

Aber es würde sich doch nichts an den Kürzesten Wegen ändrern. Angenommen wir haben jetzt einen Graphen mit den Kantengewichten k = -10, -9, -8, -7, -6, -5, -4, -3, -2, -1. Dann wäre das kleinste Gewicht k = - 10. Also ist |k| = 10. Also überall 10 addieren

-10 + 10 = 0

-9 + 10 = -1

-8 + 10 = - 2

-1 + 10 = 9

usw.

Dann sind die Kantengewichte halt alle um 10 größer. Ändert sich nichts dran.Die Wege die früher "-10" waren und die kürzesten wahren, sind jetzt halt die Wege die "0" heißen und die kürzesten sind. Diejenigen die früher die zweitkürzesten waren und "-9" hießen, heißen jetzt halt "-1" usw.. Selbes System. Oder hat jemand ein gutes Gegenbeispiel wo es nicht funktioniert? Bei positiven Kantengewichten würde mir jetzt sowart was einfallen, aber hier sollen die Gewichte ja nur negativ sein.

Danke und einen wunderschönen sonnigen Sonntag Nachmittag

Studium, Schule, Mathematik, rechnen, gewichte, Informatik, Theoretische Informatik, Universität, Algorithmus, Graphentheorie, Kante
C Programmcode Ceasar Cipher?

Hallo,

die aufgabe ist folgende:

Schreiben Sie eine Funktion, welche eine Variante des [Caesar Cipher](https://en.wikipedia.org/wiki/Caesar_cipher) auf einen String anwendet. Hierbei wird anstatt eines vorgegebenen Betrages und einer vorgegebenen Richtung für die Chiffrierung der Schlüssel für jeden Buchstaben des Klartextes neu berechnet.

Funktionsweise:

Jede Verschiebung erfolgt abhängig vom Schlüssel. Ist der Schlüssel für das aktuelle Zeichen eine gerade Zahl, so wird das aktuelle Zeichen um diesen Betrag im Alphabet nach rechts verschoben (z.B. beim Schlüssel 2 wird aus einem A ein C). Ist der Schlüssel ungerade, so erfolgt eine Verschiebung nach links (z.B. beim Schlüssel 3 wird aus einem D ein A).

Würde eine Verschiebung über das Ende des Alphabets hinaus erfolgen, so wird die Zählung bei Beginn des Alphabets fortgesetzt. Beim Schlüssel 2 wird aus einem Z also ein B bzw. beim Schlüssel 3 aus einem A ein X.

Es werden nur Buchstaben des englsichen Alphabets (A-Z und a-z) chiffriert. Alle anderen Zeichen bleiben unverändert.

Der Startschlüssel wird nur auf das erste Zeichen angewendet. Danach wird der Schlüssel nach jeder Anwendung neu berechnet, indem der Zahlenwert des zuletzt veränderten Klartext-Zeichens (also 1 für A und a, 2 für B und b, bis 26 für Z und z) durch den zuletzt verwendeten Schlüssel dividiert wird. Der neue Schlüssel für das nächste Zeichen ist der ganzzahlige Rest dieser Division. Falls es hierbei zu einer Division durch Null kommen würde (weil der zuletzt verwendete Schlüssel 0 war) wird der neue Schlüssel wieder auf den Wert des Startschlüssels gesetzt.

Folgenden Code habe ich bis jetzt geschrieben, allerdings bekomm ich bei großen Schlüsseln (zb: start_key = 100) falsche Ergebnisse raus. Weiß glaube ich auch warum: Mein Algorithmus funktioniert ja über Werteverschiebung, d.h. ab einem bestimmt großen Wert des Schlüssels verschiebt sich mein Zahlenwert des chars zu weit und dann stimmt meine "Formel" nicht mehr. Hätte es jetzt damit gelöst, dass ich zuerst mit einer if Schleife auf einen zu großen Key prüfe (zB.: if Key > 25), anschließend dividiere ich diesen Key und gehe mit dem Ergebniss in eine neue Schleife rein wobei jetzt anstatt des Keys der neue Wert addiert bzw subtrahiert wird. Anschließend durchlaufe ich diese Schleife Key%25 mal.

Aber wie setze ich das um? Zusätzlich dazu wird der Code dann mega unübersichtlich und viel zu lang für eine simple Funktion. Gibt es auch andere Möglichkeiten als meinen Code?

Ps: Ich sende den Code extra weil sonst das Zeichenlimit überschritten wird

Computer, Mathematik, IT, programmieren, EDV, Informatik, Kryptographie, Universität, Algorithmus
Pivotwahl bei Quicksort und Quickselect?

Guten Abend,

ich bräuchte mal kurz Hilfe bei folgenden Aufgaben, bitte. Es geht mir darum, dass ich einfach nicht versteh', was zu tun ist. Wir hatten in der Vorlesung den Quicksort-Algorithmus. Ich weiß, dass bei Quicksort das zu sortierende Array in immer kleiner Teilarrays eingeteilt wird, wobei das größere Array zuerst auf den Stack gelegt wird. Das Pivotelement ist entweder das linke oder das rechte und man setzt dann links und rechts einen Pointer am entsprechenden Teilarray. Ist das erste Element des zu sortierenden Teilarrays, welches größer als das Pivotelement ist, gefunden, und es findet sich vom rechten Pointer aus das erste Element, welches kleiner als das Pivotelement ist, so werden diese vertauscht. Bei Überkreuzungen tausche jenes Element auf dass der linke Pointer zeigt mit dem Pivotelement. So hatten wir's zumindest in der Vorlesung (Partitionswahl). Zu den Aufgaben

Aufgabe 1

Ein wichtiger Faktor für die Laufzeit von Quicksort und Quickselect (das Auswahlverfahren des k-kleinsten Elements analog zu Quicksort) ist die Wahl des Pivotelements. Das Pivotelement sollte die zu sortierende Folge in zwei möglichst gleich große Teilfolgen aufspalten.Gegeben sei eine unsortierte Folge mit n paarweise verschiedenen Elementen. Weiterhin sei r(x) die Position des Elements x in der sortierten Folge. Eine mögliche Strategie für die Pivotwahl ist:Wähle uniform zufällig 7 Elemente aus der Eingabefolge und gib das viertkleinste als Pivotelement aus. Dabei können Elemente in der Auswahl mehrmals vorkommen (Ziehen mit Zurücklegen)

.a) Berechne die Wahrscheinlichkeit für das Ereignis: n/4 < r(Pivot) ≤ 3n/4.

b) Nach wie vielen unabhängigen Wiederholungen der Pivotwahl ist zu erwarten, dass der Rang des Pivotelements das erste Mal außerhalb des Intervalls aus Aufgabenteil a) liegt? Hinweis: Du darfst annehmen, dass n= 4·kfür ein k∈N.

Aufgabe 2

Konstruiere eine Folge der Länge7, so dass Quickselect bei Verwendung der Pivotfunktionpivot(links, rechts) =⌈(links+rechts)/2⌉ auf der Suche nach dem viertgrößten Schlüssel die Problemgröße stets nur um 1verringert. Der Algorithmus soll insgesamt also sieben Schritte benötigen, bis er terminiert. Wende Quickselect auf Ihre Folge an, um die Korrektheit zu zeigen

Ansatz Ich verstehe hier nicht, wie n/4 gemeint ist. Wir hatten in der Vorlesung immer das Pivotelement ganz links oder ganz rechts. Jetzt steht hier "Pivot(links,rechts) = [(links+rechts)/2]. Greift man sich also da Element in der Mitte? Das ist bei einer Folge der Länge 7 doch nicht möglich, oder? WIe gehe ich allgemein vor um eine solche Folge zu finden.

LG

Jensek81

Computer, Schule, Mathematik, programmieren, rechnen, Array, Informatik, Theoretische Informatik, Algorithmus, stack, Binomialverteilung, Quicksort, Sortieralgorithmus, Algorithmen und Datenstrukturen
Gibt es einen effizienten Algorithmus um alle Wortkombination bestimmter Buchstaben zu erstellen?

Ich versuch die Frage mal ein bisschen präziser zu stellen: Man gibt einem Programm n Buchstaben, das Programm gibt jetzt alle möglichen Wortkombinationen aus diesen Buchstaben zurück, sodass für zb 6 Buchstaben 6! = 720 Wörter ausgegeben werden.

Ich habe mir bereits etwas dazu überlegt, aber der Algorithmus ist extrem ineffizient: Ich lasse alle Wörter der Länge von a bis z durch, also bei n=6 zb. aaaaaa, aaaaab, aaaaac, ... usw. und überprüfe dabei den Wert und die Anzahl eines Charakters, wenn Wert und Anzahl mit meinen eingegeben Buchstaben übereinstimmt wird das Wort zurückgegeben, ansonsten wird das nächste Wort betrachtet und dasselbe noch mal überprüft. Da nur n! Wörter gefunden werden können bricht das Programm dann ab wenn n! Wörter gefunden wurden (möglicherweise auch früher, wenn sich unter den eingegeben Buchstaben Dopplungen befinden). Das Problem ist, dass dieser Algorithmus extrem ineffizient ist, da er bis zu 26^n - n! falsche Wörter durchgehen kann bis er fertig wird, die 26 Potenz ist natürlich derbe, deshalb wollte ich fragen, ob es vielleicht einen clevereren Algorithmus gibt der das besser machen kann.

Vielleicht sowas in der Form, dass bestimmte Elemente an bestimmten Indizes auf eine bestimmte Art und Weise mit einem anderen Element vertauscht werden, sodass in jedem Schritt ein neues gesuchtes Wort entsteht und somit nur n! Rechenschritte benötigt werden, gibts sowas?

Mathematik, rechnen, Informatik, Algorithmus

Meistgelesene Fragen zum Thema Algorithmus