Heuristik - Vogelsche Approx. 6.1

View all featured content
d-baby

d-baby

Dr Franke Ghostwriter
Heuristik - Vogelsche Approx. 6.1

Hallo!
Vielleicht kann mir einer bei der Heuristik helfen. Ich hänge bei der Aufgabe 6.1 fest. In der Lösung verstehe ich überhaupt nicht was gemacht wurde.
Es heißt doch, man soll den zweitkleinsten wert - den kleinsten rechnen. Und das Zeile für Zeile, Spalte für Spalte.
Das wäre in meinen Augen:

Für Zeile 1 :10-3 = 7
Zeile 2: 2-1 = 1
Zeile 3: 5-4 = 1
Ich verstehe jetzt nicht wo all die Zahlen aus der Lösung herkommen:
Zeile 1: 0 0 0 7
Zeile 2: 1 1 1 6
Zeile 3: 1 2 *

Wo sind die alle her????
Danke schon einmal im vorraus
 
Nach Datum sortieren Nach Stimmen sortieren
In Zeile 1 gibt es zweimal die 3, die Differenz zwischen kleinstem und zweitkleinstem Wert ist 0. Die gleichen Differenzen musst du auch für die Spalten berechnen. Im ersten Durchgang ist die größte Differenz in Spalte 2 (mit 5).
Die Zahlen rechts (in der Spalte di) ergeben sich aus den Durchläufen des Algorithmus. Wenn du den mal (mit den richtigen Differenzen) durchspielst, siehst du das.
 
Positive Stimme 0 Negative Stimme
Hmm...ja ok, den kleinsten und zweitkleinsten die Differenz berechenen und das pro Zeile und jede Spalte.
Dann käm für di raus 0 1 1 und für dj 2 5 1 3 , aber da stehen ja noch viel mehr Zahlen in der ersten Zeile bei di. Nach der 0 die ich ja aus 3-3 = 0 berechnet habe, kommt nochmal eine 0, und noch eine und dann eine 7 in Klammern.
Woher kommen die Zahlen????Und warum ist vorne bei A1 usw. die 7,4,9 durchgestrichen in der Lösung?
 
Positive Stimme 0 Negative Stimme
wie Jens schon geschrieben hat, hast Du mehrere Iterationen des Algorithmus, bei dem jeweils, die Differenz für jede noch nicht gestrichene Zeile/Spalte gebildet werden muss.

In der ersten Iteration berechnest Du einmal die Werte für di und dj
Code: 
     b1    b2    b3   di
------------------------
a1|     |      |      | 5
------------------------
a2|     |      |      | 2 
------------------------
a3|     |      |      | 1 
------------------------
dj|   2  |  1  |   1  |

Wenn Du jetzt Zeile 1 mit dem Wert 5 auswählst und dabei die gesamte Transportmenge von a1 nach b3 überträgst, wird Zeile 1 gestrichen (markiert durch ein X in den Zellen), weil keine Güter mehr vorhanden sind. Sollte bei Berechnung der Differenz in den Spalten vormals ein Wert in Zeile a1 (im Beispiel unten z.B. Spalte b1 und b2) berücksichtigt worden sein, fällt dieser nun weg und die Differenz wird nur noch aus den Werten in Zeile a2 und a3 berechnet. Auch wenn ein Wert gleich bleibt, wird dieser für die nächste Iteration erneut aufgeschrieben (daher die doppelten Werte).

Code: 
     b1    b2    b3   di
------------------------
a1|  X | X   |  X   | 5*
------------------------
a2|     |      |      | 2 2
------------------------
a3|     |      |      | 1 1
------------------------
dj|   2  |  1  |   1  |
  |   1  |  4  |   1  |

So gehst Du jede Iteration durch, streichst immer wieder Zeilen und Spalten und bekommst jedes mal neue Zahlen dazu.

Gruß
Achim
 
Positive Stimme 0 Negative Stimme
Antworten
Oben