Verschachtelte for schleife mit dynamischer Anzahl an Schleifen

[Jagito]

Hallo,

programmiere gerade einen Algorithmus, welcher generisch sein soll (also bei Änderung der Eingabedaten, muss kein Programmcode verändert werden).

Nun stehe ich vor folgendem Problem. Vielleicht habt ihr eine kreative Lösung dazu:

Am Anfang gebe ich eine Problemgröße an, z.B. 400. Eine Hashmap hm mit 400 Einträgen wird nun erzeugt, wobei jeder Eintrag aus einer arraylist besteht, welche im Laufe des Durchlaufs mit Zahlen gefüllt wird.

Nun möchte ich jedes einzelne Element der arraylist von der hm an den Stellen 100,200,300,400 abfragen und eine mathematische Umformung damit machen. (siehe java-code unten, wobei die hier angegebenen Umformungen "o[...]=..." vereinfacht sind)

Das Problem ist bei Änderung der Hashmap-Größe z.B. auf 300 oder 700, da ich dann zuerst for-schleifen löschen bzw. einbauen muss.

int max = 0;
int o_gesamt = 0;
for (int i=0; i<hm.get(100).size();i++){
	o[1]=hm.get(100).get(i)+1;
	for (int i=0; i<hm.get(200).size();j++){
		o[2]=hm.get(200).get(i)+1;
		for (int k=0; k<hm.get(300).size();k++){
			o[3]=hm.get(300).get(i)+1;
			for (int l=0; l<hm.get(400).size();l++){
				o[4]=hm.get(400).get(i)+1;
				o_gesamt=o[1]+o[1]+o[2]+o[3];
				if (o_gesamt >max){
				   max = o_gesamt;
			        }
			}
		}
	}	
}

Wie könnte ich dieses Problem angehen?

 

[Marco13]

Groß in Richtung von

for (Integer i : hashMap.keySet())
{
    ArrayList list = hashMap.get(i);
    ...
}

(ggf. effizienter mit EntrySet, nur zur Verdeutlichung)

EDIT: Sieht aber insgesamt seltsam aus - beschreib' am besten mal formaler/genauer, WAS für eine Datenstruktur das ist.... also, was damit wie modelliert wird und so...

 

[Jagito]

Hi,

ich versuche mal das Problem näher darzustellen. Es handelt sich um einen "Dynamischen Programm" -Algorithmus. Nehmen wir an, wir haben z.B. 400 Knoten, welche Städte in Deutschland darstellen und wir wollen den "besten" Weg zwischen Stadt 1 und Stadt 400 finden, wobei die Städte nach der Reihe, also 1,2,3,...,400 durchlaufen werden sollen. Man kann nun entscheiden, ob man z.B. per Bahn, Bus, Auto, Rad von einer zur anderen Stadt gelangt, was eine unterschiedliche Anzahl an Ressourcen (Zeit, Geld, CO2) verbraucht.
Ziel ist eine möglichst günstige Kombination an Ressourcenverbrauch, wobei ein gewisser maximaler Wert an Zeit, Geld, CO2 nicht überschritten werden darf.

In jeder Stadt wird nun gespeichert, wieviel an Ressource bis zu dieser Stadt verbraucht worden ist. z.B. wird in Stadt 45 alle Möglichkeiten gespeichert, wie man zu dieser Stadt kommen kann und der jeweilige Ressourcenverbrauch (bei 4 Fortbewegungsmöglichkeiten-Bahn, Bus, Auto, Rad- und 45 Städten, sind das also 4^45 Möglichkeiten, wobei einige davon gelöscht werden können)

Da das Problem zu groß ist, zerlege ich es in 100er Schritten. Also ich bilde Wege von Stadt 1-100, 101-200, 201-300, etc. und speicher im Knoten 100, 200,300,... den Bedarf an Zeit, Geld, CO2 von allen "guten" Wegen (d.h. alle Wege, die nicht in allen drei Kategorien schlechter als ein anderer Weg sind und daher gelöscht werden können).

In Java habe ich das so modelliert, dass der key einer Hashmap eine Stadt bildet. Jeder Stadt wird eine Arraylist zugeordnet, welche die Möglichkeiten enthält, wie man zu dieser Stadt kommen kann.

Am Ende suche ich dann aus allen guten Wegen der 100er, 200er, 300er,... Knoten die Kombination derer aus, bei denen der Maximalverbrauch an Zeit,Geld,CO2 eingehalten wurde und die dabei die beste Kombination von Ressourcenverbrauch haben. Beispielsweise könnte ein Ergebnis sein: Von Stadt 1 bis Stadt 100 nehme ich Weg Nummer 7. Von 101-200 den Weg Nr. 27 und von 201-300 Weg Nr 3 etc.

Der letzte Absatz beschreibt das Kombinationsproblem, das ich durch die for-schleifen abbilden möchte. Hierbei ändern sich natürlich die Anzahl an for-Schleifen, falls ich eine unterschiedliche Anzahl an Städten habe und vor diesem Problem stehe ich gerade.

Falls ich noch etwas genauer erklären soll, gebt mir einen Hinweis.

 

[Marco13]

OK, das ist dann schon nicht so trivial... Da müßte man sich eigentlich über das Problem an sich und dessen Modellierung einige Gedanken machen, und DANN nochmal über die konkrete Lösung mit DP, daher sieh' meine Antworten immer unter dem Vorbehalt, dass ich das ja noch nicht gemacht habe...

Du hast also eine Menge von Knoten. Jedem Knoten ist eine Liste von Möglichen Wegen zugeordnet (vom vorherigen Knoten zu diesem), und jeder Weg hat bestimmte Kosten...

*grübel*

Eigentlich müßte man auf dieses Problem jetzt auch wieder einen "Dynamic-Programming-Ansatz" anwenden ....

Aber das hast du im ursprünglichen Post (mit den Schleifen) ja auch nicht, von daher ...

Hm... so als zwischenfrage: Warum liegen die Daten in einer Map? Also, warum statt der Map, die {100->DatenA, 200->DatenB, 300->DatenC...} enthält nicht einfach eine List, die nur {DatenA, DatenB, DatenC} enthält? (Ich glaube, an sich könnte man die Lösung relativ einfach rekursiv bauen - auch wenn das eben NICHT DP wäre...)

 

[Jagito]

Hi,

die Daten liegen ursprünglich in einer Map, um auf sie während des Durchlaufs des DP gezielt zugreifen zu können.

Am Ende könnte man diese dann auch in eine List, die nur {DatenA, DatenB, DatenC} enthält, überspielen. Kein Problem.

Wie kann ich jedoch dann mein Problem lösen, dass ich die optimalste Kombination aus je einem einzigen Element aus A,B und C haben möchte, wenn dies generisch sein soll, also ich z.B. beim nächsten Durchlauf die Einstellung vornehme, dass ich nun bis 500 Knoten habe, also am Ende eine Liste mit {DatenA, DatenB, DatenC, DatenD, DatenE}?

EDIT: Eigentlich läuft es auf ein Kombinatorik-Problem hinaus. Man hat z.B. fünf Töpfe A,B,C,D,E mit einer unterschiedlichen Anzahl an Elementen darin. Wie kann ich jetzt jedes Element mit jedem anderen kombinieren, wobei ich aus jedem Topf genau ein Element entnehme? (die Reihenfolge, wann ich aus welchem Topf nehme, spielt keine Rolle). Das generische ist, dass ich am Anfang die Anzahl der Töpfe angebe und während des Durchlaufs die Elemente in den Töpfen erzeugt werden.

 

[Marco13]

Hab' gerade nicht viel Zeit, aber es klang jetzt als könnte man da grob sowas machen wie

private Path bestPath = null;

void findPath(List input, int index, Path currentPath)
{
    if (index >= input.size())
    {
        if (currentPath.betterThan(bestPath)) bestPath = currentPath.copy();
        return;
    }
    for (all possible path segments at input.get(index))
    {
        currentPath.append(segment);
        findPath(input, index+1, currentPath);
        currentPath.remove(segment);
    }
}

Wenn's zu knapp ist (oder nicht passt - das klingt für dieses komplexe Problem eigentlich ZU einfach) sag' nochmal bescheid.

 

[Jagito]

Hi,
schaut spannend aus. Eine rekursive Lösung, wenn ich es richtig verstanden habe. Das einfache könnte die Lösung sein. Dank deiner Hilfe ist mir klar geworden, dass sich mein aktuelles Problem als reine Permutation (Kombinationsproblem) lösen läst.

Beim Code ist mir noch unklar, wie sichergestellt ist, dass (um beim Beispiel mit den Töpfen zu bleiben) aus jedem Topf jeweils nur ein Element genommen wird und dies mit allen möglichen Kombinationen der andern Töpfe kombiniert wird.

Also bspw. haben wir |A|=7, |B|=5 und |C|=11, dann müsste der Code 7*5*11=385 Kombinationen berechnen. Macht er das?

Wie kann der Code also folgende Aufgabe berechnen:
Seien die Mengen A,B,C wie oben, wobei jede Menge z.B. Tupel aus (Zeitbedarf/Geldverbrauch) enthält.
Jetzt wird das Minimum einer Dreier-Kombination von je einem Element aus A,B,C gesucht, wobei das Minimum aus der Funktion a.zeit+2*a.geld+b.zeit+2*b.geld+c.zeit+2*c.geld berechnet wird.
Ich suche also die konkreten a,b,c (bzw. die Indizes in den Mengen A,B,C, um a,b,c zu identifizieren), welche obige Funktion minimieren.

 

[Marco13]

Ja, ein paar Utility-Klassen für sowas gibt's unter http://www.java-forum.org/codeschnipsel-u-projekte/81973-combinatorics.html aber das braucht's hier eigentlich nicht.


Hier nochmal ein ausführlicheres Beispiel

// For http://www.java-forum.org/java-basics-anfaenger-themen/90564-verschachtelte-schleife-dynamischer-anzahl-schleifen.html#post573696
import java.util.*;

class Segment
{
    int zeit;
    int geld;

    public Segment(int z, int g)
    {
        zeit = z;
        geld = g;
    }

    public int value()
    {
        return zeit + 2 * geld;
    }

    public String toString()
    {
        return "("+zeit+","+geld+")";
    }

}


class Node
{
    List<Segment> segments = new ArrayList<Segment>();

    void add(Segment segment)
    {
        segments.add(segment);
    }
}

class Path
{
    List<Segment> segments = new ArrayList<Segment>();

    void append(Segment segment)
    {
        segments.add(segment);
    }

    void remove(Segment segment)
    {
        segments.remove(segment);
    }

    int value()
    {
        if (segments.size() == 0) return Integer.MAX_VALUE;

        int result = 0;
        for (Segment segment : segments) result += segment.value();
        return result;
    }

    boolean isBetterThan(Path that)
    {
        return this.value() < that.value();
    }

    public Path copy()
    {
        Path p = new Path();
        p.segments.addAll(segments);
        return p;
    }

    public String toString()
    {
        return "Path "+value()+" : "+segments.toString();
    }


}

class PathFinder
{
    public static void main(String args[])
    {
        new PathFinder().find();
    }

    private Random random = new Random(0);
    private Path bestPath = new Path();
    private List<Node> inputList;
    private int counter = 0;

    public PathFinder()
    {
        inputList = new ArrayList<Node>();
        inputList.add(createRandomNode(7));
        inputList.add(createRandomNode(5));
        inputList.add(createRandomNode(11));
    }

    private Segment createRandomSegment()
    {
        return new Segment(random.nextInt(10), random.nextInt(10));
    }

    private Node createRandomNode(int segments)
    {
        Node node = new Node();
        for (int i=0; i<segments; i++)
        {
            node.add(createRandomSegment());
        }
        return node;
    }


    void find()
    {
        findPath(inputList, 0, new Path());

        System.out.println("bestPath "+bestPath);
        System.out.println("counter "+counter);
    }

    String indent(int n)
    {
        String result = "";
        for (int i=0; i<n; i++)
        {
            result += "    ";
        }
        return result;
    }


    void findPath(List<Node> input, int index, Path currentPath)
    {
        if (index >= input.size())
        {
            counter++;
            System.out.println(indent(index)+"Comparing "+currentPath);
            System.out.println(indent(index)+"to        "+bestPath);

            if (currentPath.isBetterThan(bestPath))
            {
                System.out.println(indent(index)+"Found new best path: "+currentPath);
                bestPath = currentPath.copy();
            }
            return;
        }
        Node node = input.get(index);
        for (Segment segment : node.segments)
        {
            System.out.println(indent(index)+"Appending "+segment+" to "+currentPath+" and recurring");

            currentPath.append(segment);
            findPath(input, index+1, currentPath);
            currentPath.remove(segment);
        }
    }

}

Beachte aber, dass das eben NICHT mit Dynamischer Programmierung gelöst ist (und in obiger Form natürlich auch gehackt...)

 

[Jagito]

Wau, werde mich durch dein Beispiel durcharbeiten und bei Fragen nochmal melden.

Danke

 

[Jagito]

Hi,
hatte jetzt Zeit mir das ganze zu durchdenken. Es läuft wunderbar . Leider weiß ich nicht, wie ich es an meine Gegebenheiten anpassen kann. Das Wichtigste fürs Sortieren ist m.E. die findPath-Methode.
Die segments und node und random-Methoden kann man wahrscheinlich bei konkreten gegebenen Daten weglassen, obwohl ich mir da nicht so ganz sicher bin.

Meine Datenstruktur sieht zur Zeit so aus, dass ich eine Hashmap hm mit z.B. 40 Einträgen habe (die Anzahl kann in 10er Schritten verändert werde, was das generische am Problem darstellt). Jeder dieser Einträge ist eine ArrayList al zugeordnet, welche mit Tupeln aus z.B. Zeit und Geld gefüllt ist. Die Tupel definiere ich mir über eine eigene Klasse Tupel (dürfte deiner Segment-Klasse entsprechen). Die Tupel werden nach gewissen Regeln während des Durchlaufens erzeugt.

Die einzelnen Töpfe (um das vorherige Beispiel aufzugreifen) beinhalten also z.B. von der Hashmap mit Key 10,20,30,40 alle Elemente der dazugehörigen arraylist.

Also hätte der erste Topf alle i's aus hm.get(10).al.get(i), der zweite Topf alle i's aus hm.get(20).al.get(i), etc.

Wie könnte ich das auf den bisherigen Code übertragen?

 

[Marco13]

...alle i's aus hm.get(10).al.get(i),...

hm ist die HashMap
hm.get(10) liefert ... irgendwas, was eine ArrayList "al" enthält ???:L
hm.get(10).al.get(i) liefert ein Tupel?

Wenn ich das jetzt richtig verstanden habe, läßt sich das ziemlich direkt abbilden:
Die Tupel sind die "Segments"
Das Ding, das die al enthält ist ein "Node"
Die Einträge der HashMap sind (als Liste) gerade die List<Node> aus dem Beispiel.

Poste ggf. mal ein bißchen Code...