Salesman Problem - Bruteforce Algorithmus

Bitte aktiviere JavaScript!
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:
Java:
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
 
A

Anzeige




Schau mal hier —> (hier klicken)
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.
 
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.
 
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.
 
Hallo,
also Salesman Brut Force Ansatz wäre zum Bleistift das:
ts1.gif
das:
ts2.gif oder das:
ts3.gif
....und dabei habe ich bei nur 12 Städten die Rückwärts-Duplikate noch nich mit drinne.
 
Code:
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.
 
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...
 
Ok ein einfacher Brute force Ansatz ohne Optimierung mit 5 alphabetisch sortierten Städten macht genau das:

ts4.gif

habe mal den Backgrund grau und jeweils 1 Sekunde, wie man sieht dauert es ewig
 
@mihe7 ;)
Sage mir mal wie ich das aufbauen soll ich schreibe gerad eine Art winziges Framework dafür:
Java:
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.?
 
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.

.... 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.
 
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
 
Dies zB:
Java:
        City[] übrStädte = this.cities.clone();
        weg[0] = cities[0];
        übrStädte[0] = null;
oder dies:
Java:
private City[] rekursion(int tiefe, /*... ,*/ int limit) { 
        /*
        ...
        */
        tiefe--;
        limit  = tiefe;
Das ist so das auffälligste an völlig unsinnigem Code...


Oder diese Schleife:
Java:
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++;
                }
            }
        }
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...
 
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
 
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 ;)

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).

das 3te hast du ja bereits gesagt
und warum schreibst du das dann so obfuskiert dahin? ;)
 
A

Anzeige




Vielleicht hilft dir das hier weiter: (klicke hier)
Passende Stellenanzeigen aus deiner Region:

Neue Themen

Oben