# Salesman Problem - Bruteforce Algorithmus



## MrXeth (15. Okt 2018)

Hallo, ich sitze gerade an dem Salesman Problem ( Problem des Handlungsreisenden) an einem Bruteforce Algotithmus.
Mein Problem ist, dass ich auf dem Schlauch stehe, wie ich Wege wie A-B-C-D-A und A-D-C-B-A im Vorfeld ausgrenze (ungerichteter Graph).
Mein Code:

```
private City[] cities;
   
    @Override
    public City[] getOrder(City[] cities) {
        this.cities = cities;
        City[] weg = new City[cities.length + 1];
        City[] übrStädte = this.cities.clone();
        weg[0] = cities[0];
        übrStädte[0] = null;
       
        City[] comp1, comp2;
        comp1 = rekursion(cities.length - 1, 1, übrStädte.clone(),1 , weg.clone());
       
        for(int i = 1; i < cities.length - 1; i++) {
            comp2 = rekursion(cities.length - 1, i+1, übrStädte.clone(), 1, weg.clone());
            if(compare(comp1, comp2) > 0) {
                comp1 = comp2;
            }
        }
       
        return comp1;
    }
   
   
    private City[] rekursion(int tiefe, int nimmNr, City[] übrStädte,int index, City[] weg) {   
        if(tiefe == 0) {
            weg[weg.length-1] = cities[0];
            for (int i = 0; i < weg.length; i++) {
                System.out.println(weg[i].getName());
               
            }
            System.out.println();
            return weg;
        }
        tiefe--;
        City[] comp1, comp2;
       
        for(int i = 0, j = 0; i < übrStädte.length && j < nimmNr; i++) {
            if(übrStädte[i] != null) {
                j++;
                if(j == nimmNr ) {
                    weg[index] = übrStädte[i];
                    übrStädte[i] = null;
                    index++;
                }
            }
        }
        comp1 = rekursion(tiefe, 1, übrStädte.clone(), index, weg.clone());
        for(int i = 1; i < tiefe; i++) {
            comp2 = rekursion(tiefe, i + 1, übrStädte.clone(), index, weg.clone());
            if(compare(comp1, comp2) > 0) {
                comp1 = comp2;
            }
        }
       
        return comp1;
    }
```

Die Funktion compare gibt einfach nur einen positiven Wert aus, wenn Stadt 1 > Stadt2 und einen negativen wenn andersherum.

Vielen Dank schonmal für eure Antworten.

Lg MrXeth


----------



## diggaa1984 (23. Okt 2018)

Warum willst du denn etwas ausgrenzen?


----------



## MoxxiManagarm (23. Okt 2018)

diggaa1984 hat gesagt.:


> Warum willst du denn etwas ausgrenzen?


Sein Beispiel ist der Gleiche Weg, nur in anderer Richtung. Er will sicherlich nur ein Ergebnis von beiden. aber an sich würde dieser Gedanke dem Brute-Force Ansatz widersprechen. Brute-Force soll ja alle Varianten berechnen. Muss es denn auch wirklich Brute-Force sein?


----------



## MrXeth (26. Okt 2018)

Jap, ist für eine Facharbeit. ich möchte da einen Brute Force Algo, ne primitive Heuristik und ne Heuristik, wie man sie in der praxis nutzt haben.


----------



## MrXeth (26. Okt 2018)

Oder ich schreibe rein, dass man den Brute Force Algorithmus auf diese Weise noch optimieren kann, aber er trotzdem bei großen Mengen keinen Sinn macht.


----------



## MoxxiManagarm (26. Okt 2018)

Naja du kannst ja erstmal alle Lösungen generieren mit Brut Force und anschließend Rückwärts-Duplikate entfernen. Während des Brut-Force Algorithm würde ich es nicht beachten.


----------



## Xyz1 (26. Okt 2018)

Hallo,
also Salesman Brut Force Ansatz wäre zum Bleistift das:
 
das:
 oder das:
 
....und dabei habe ich bei nur 12 Städten die Rückwärts-Duplikate noch nich mit drinne.


----------



## MrXeth (26. Okt 2018)

habe jetzt nach ner längeren pause am projekt auch ne idee, muss die nurnoch ausprogrammieren


----------



## MrXeth (26. Okt 2018)

```
package travelingSalesmanProblem;

import map.City;

public class BruteForce extends Method {
   
    private City[] cities;
   
    @Override
    public City[] getOrder(City[] cities) {
        this.cities = cities;
        City[] weg = new City[cities.length + 1];
        City[] übrStädte = this.cities.clone();
        weg[0] = cities[0];
        übrStädte[0] = null;
        int limit = cities.length - 1;
       
        City[] comp1, comp2;
        comp1 = rekursion(cities.length - 1, 1, übrStädte.clone(),1 , weg.clone(), cities.length-1);
       
        for(int i = 1; i < cities.length - 2; i++) {
            limit --;
            comp2 = rekursion(cities.length - 1, i+1, übrStädte.clone(), 1, weg.clone(), limit);
            if(compare(comp1, comp2) > 0) {
                comp1 = comp2;
            }
        }
       
        return comp1;
    }
   
   
    private City[] rekursion(int tiefe, int nimmNr, City[] übrStädte,int index, City[] weg, int limit) {   
        if(tiefe == 0) {
            weg[weg.length-1] = cities[0];S
            return weg;
        }
        tiefe--;
        limit  = tiefe;
        City[] comp1, comp2;
       
        for(int i = 0, j = 0; i < übrStädte.length && j < nimmNr; i++) {
            if(übrStädte[i] != null) {
                j++;
                if(j == nimmNr ) {
                    weg[index] = übrStädte[i];
                    übrStädte[i] = null;
                    index++;
                }
            }
        }
        comp1 = rekursion(tiefe, 1, übrStädte.clone(), index, weg.clone(), tiefe);
        for(int i = 1; i < limit; i++) {
            comp2 = rekursion(tiefe, i + 1, übrStädte.clone(), index, weg.clone(), tiefe);
            if(compare(comp1, comp2) > 0) {
                comp1 = comp2;
            }
        }
       
        return comp1;
    }
   
    private int compare(City[] c1, City[] c2) {
        double ci1 = 0, ci2 = 0;
        for(int i = 1; i < c1.length; i++) {
            ci1 += dist(c1[i-1], c1[i]);
        }
        for(int i = 1; i < c2.length; i++) {
            ci2 += dist(c2[i-1], c2[i]);
        }
        return (int) (ci1 - ci2);
    }
   
}
```

das ist jetzt mein code, falls noch jemand anderes hilfe braucht ^^

am anfang lasse ich den letzten kinderbaum einfach direkt weg.

dann setze ich limits, also wie oft beim ersten kinderbaum das nächste aufgerufen wird.
da habe ich den zusammenhang gefunden, dass ich einfach immer beim nächsten aufrufen, die nächste Stadt bzw. die nächsten 2 städte bei einer anzahl von 5 Städten löschen kann.

Selbstverständlich muss der code noch laufzeittechnisch aufgepimpt werden, funktioniert so aber schon einmal.


----------



## mrBrown (26. Okt 2018)

Puh, sicher, dass der Code so korrekt arbeitet?

Bevor du da irgendwas an der Laufzeit machst, würde ich da erstmal an der Lesbarkeit arbeiten, da liegt doch so einiges im Argen...


----------



## Xyz1 (27. Okt 2018)

Ok ein einfacher Brute force Ansatz ohne Optimierung mit 5 alphabetisch sortierten Städten macht genau das:

 

habe mal den Backgrund grau und jeweils 1 Sekunde, wie man sieht dauert es ewig


----------



## mihe7 (27. Okt 2018)

@DerWissende macht das nicht zu viel: TSP für jede Stadt?


----------



## Xyz1 (27. Okt 2018)

mihe7 hat gesagt.:


> TSP für jede Stadt


ja


mihe7 hat gesagt.:


> macht das nicht zu viel


ja


----------



## Xyz1 (27. Okt 2018)

@mihe7 
Sage mir mal wie ich das aufbauen soll ich schreibe gerad eine Art winziges Framework dafür:

```
nods.add(new Nod(1, 'a', new Point(700 / 2, 550 / 4)));
drawItInternal(new boolean[nods.size()], new ArrayList<>(), gsw);
nods.add(new Nod(2, 'b', new Point(50, 50)));
drawItInternal(new boolean[nods.size()], new ArrayList<>(), gsw);
nods.add(new Nod(3, 'c', new Point(50, 500)));
drawItInternal(new boolean[nods.size()], new ArrayList<>(), gsw);
nods.add(new Nod(4, 'd', new Point(650, 50)));
drawItInternal(new boolean[nods.size()], new ArrayList<>(), gsw);
nods.add(new Nod(5, 'e', new Point(650, 500)));
drawItInternal(new boolean[nods.size()], new ArrayList<>(), gsw);

tsp(0, new boolean[nods.size()], new ArrayList<>(), gsw);
```

.... oder die Bundesländer München, Frankfurt, Hesswn usw. usf.?


----------



## mrBrown (27. Okt 2018)

DerWissende hat gesagt.:


> Sage mir mal wie ich das aufbauen soll ich schreibe gerad eine Art winziges Framework dafür:


Im Idealfall so aufgebaut, dass man es auf den ersten Blick verstehen kann.



DerWissende hat gesagt.:


> .... oder die Bundesländer München, Frankfurt, Hesswn usw. usf.?


Abgesehen davon, dass München & Frankfurt keine Bundesländer sind, sind Bundesländer eher ungeeignet:
Bayern - Hessen -> gemeinsame Grenze, keine Entfernung.
Hessen - Niedersachen -> gemeinsame Grenze, keine Entfernung.
Niedersachen - Schleswig-Holstein -> gemeinsame Grenze, keine Entfernung.
Bayern - Schleswig-Holstein -> ziemlich weit entfernt.


----------



## Xyz1 (27. Okt 2018)

Etwas Feintuning gemacht, tsp nur für a und


----------



## MrXeth (8. Nov 2018)

mrBrown hat gesagt.:


> Puh, sicher, dass der Code so korrekt arbeitet?
> 
> Bevor du da irgendwas an der Laufzeit machst, würde ich da erstmal an der Lesbarkeit arbeiten, da liegt doch so einiges im Argen...



Habe etwas dran gearbeitet, aber was meinst du denn zB genau? Also mit Zeug, wie Point, Lists usw arbeite ich bei schulprojekten ungerne, da es hier nicht zwingend erforderlich ist und unser LK noch nicht so weit ist


----------



## mrBrown (8. Nov 2018)

Dies zB:


MrXeth hat gesagt.:


> ```
> City[] übrStädte = this.cities.clone();
> weg[0] = cities[0];
> übrStädte[0] = null;
> ```



oder dies:


MrXeth hat gesagt.:


> ```
> private City[] rekursion(int tiefe, /*... ,*/ int limit) {
> /*
> ...
> ...



Das ist so das auffälligste an völlig unsinnigem Code...


Oder diese Schleife:


MrXeth hat gesagt.:


> ```
> for(int i = 0, j = 0; i < übrStädte.length && j < nimmNr; i++) {
> if(übrStädte[i] != null) {
> j++;
> ...


Ich bin ehrlich gesagt immer noch nicht sicher, ob ich verstanden hab, was du da wirklich machen möchtest...
Es sieht aus nach nimmNr'ste Stadt aus übrStädte entfernen und an weg anhängen, aber das lässt sich kaum besser da drin verstecken...


----------



## MrXeth (9. Nov 2018)

Das erste hat den sinn, dass es nur flache kopien sind. Das Zweite hat was mit dem rausschneiden zu tun und das 3te hast du ja bereits gesagt


----------



## mrBrown (9. Nov 2018)

MrXeth hat gesagt.:


> Das erste hat den sinn, dass es nur flache kopien sind


Stimmt, sieht man mal, wie unübersichtlich das ist, wenn sowas nicht mal auffällt 



MrXeth hat gesagt.:


> Das Zweite hat was mit dem rausschneiden zu tun


Du übergibst 2 Variable, um die eine dann direkt mit der anderen zu überschreiben -das hat einfach keinen Sinn (außer Verwirrung zu schaffen).



MrXeth hat gesagt.:


> das 3te hast du ja bereits gesagt


und warum schreibst du das dann so obfuskiert dahin?


----------



## MrXeth (9. Nov 2018)

Woow danke dass du mich nochmal drauf hingewiesen hast, das limit = tiefe muss weg und dann in der 2ten forschleife muss anstatt limit limit - 1 stehen

Also ich hab mir mal wieder was schlaues ausgedacht und es durch dummheit unnütz gemacht


----------



## mihe7 (9. Nov 2018)

MrXeth hat gesagt.:


> Also ich hab mir mal wieder was schlaues ausgedacht und es durch dummheit unnütz gemacht


Die schlausten Ansätze sind meist die schlechtesten. Der Code soll nicht schlau sondern lesbar sein und das verhält sich meist diametral zueinander.


----------



## MrXeth (9. Nov 2018)

Kann man ja z.B. durch Kommentare o.Ä. erreichen.


----------



## mrBrown (9. Nov 2018)

Kommentare machen Code auch nicht lesbarer, oft eher im Gegenteil...


----------

