Traveling Salesman - MST Heuristik Problem

Diskutiere Traveling Salesman - MST Heuristik Problem im Allgemeine Java-Themen Forum; Hallo, vielleicht kennt sich jemand ja mit dem Problem hier aus ^^ Problem ist, dass bei meiner MST- Heuristik immer das gleiche Ergebnis...

  1. MrXeth
    MrXeth Mitglied
    Hallo, vielleicht kennt sich jemand ja mit dem Problem hier aus ^^

    Problem ist, dass bei meiner MST- Heuristik immer das gleiche Ergebnis herauskommt, wie bei meiner Nearest-Neighbour Heuristik, also ich habe erstere implementiert. Gegebenenfalls könnte der "Fehler" sein, dass ich am Ende wieder den ersten Knoten hinzufüge, wie beim Nearest-Neighbour verfahren.
    Mein Code:
    Code (Java):
    package travelingSalesmanProblem;

    import java.util.ArrayList;
    import java.util.List;

    import map.City;

    /**
    * class representing the MST Heuristic
    *
    * @author MrXeth
    * @version 1.0
    */

    public class MSTHeuristic extends Method {

        /*
         * (non-Javadoc)
         *
         * @see travelingSalesmanProblem.Method#getOrder(java.util.List)
         */

        @Override
        public List<City> getOrder(List<City> cities) {
            cities = new MinTree(cities).getCities();
            List<City> way = new ArrayList<City>();
            // unmarks all cities, because now they are in the right order
            for (City c : cities) {
                c.marked = false;
            }
            // recursion for creating an euler circle
            recursion(cities.get(0), way);
            way.add(cities.get(0));
            // setting to the begin: neighbours are just for the MinTree necessary
            /*for (City c : cities) {
                c.remNeighbours();
            }*/

            return way;
        }

        /**
         * recursion for creating a way of the cities
         *
         * @param par city to add
         * @param way list to add city
         */

        private void recursion(City par, List<City> way) {
            // marks city
            par.marked = true;
            // adds city to way
            way.add(par);
            List<City> parNeighbours = par.getNeighbours();
            // go through neighbours and add them at the next call -> the neighbours are
            // already sorted by the mintree after their importance
            for (City c : parNeighbours) {
                // if the city is not in the way
                if (!c.marked) {
                    recursion(c, way);
                }
            }
        }

    }
     
    Code (Java):
    package travelingSalesmanProblem;

    import java.util.List;

    import map.City;

    // Prim Algorithmus, da es viel E^E Kanten gibt

    /**
    * class for creating a minimal tree by the prim algorithm
    *
    * @author MrXeth
    * @version 1.0
    *
    */

    public class MinTree {

        private List<City> cities;
        // with which city the city at the n-pos has the shortest way - example:
        // parent[0] = 1
        // -> city at position 0 's best connection partner is 1
        private int[] parent;
        // connection values
        private double[] queue;

        /**
         * constructor
         *
         * @param cities cities to build a min tree
         */

        public MinTree(List<City> cities) {
            this.cities = cities;
            queue = new double[cities.size()];
            parent = new int[cities.size()];
            buildTree();
        }

        /**
         * adds city to the mintree
         *
         * @param par parent of city / node before
         */

        private void addCity(int par) {

            int unmarked = calcMinDist(par);

            int minS = searchShortestPath();
            // add and mark
            City conPar = cities.get(parent[minS]);
            City conChild = cities.get(minS);

            queue[minS] = Double.MAX_VALUE;

            // connect both nodes and mark child
            conPar.connect(conChild);
            conChild.marked = true;
            // because marked, unmarked can be reduced
            unmarked--;

            // until all nodes are in the graph
            if (unmarked > 0) {
                addCity(minS);
            }

        }

        private void buildTree() {
            // prepare and set everything on the worst - case
            for (int i = 0; i < cities.size(); i++) {
                queue[i] = Double.MAX_VALUE;
                parent[i] = -1;
                cities.get(i).marked = false;
            }
            addCity(0);
        }

        /**
         * updates the queue- and the parent array for the parent city in the parameters
         *
         * @param par current city
         * @return number of unmarked cities
         */

        private int calcMinDist(int par) {

            // city for making a connection
            City c = cities.get(par);
            // city is a part of the minimal tree now
            c.marked = true;
            // how many nodes have to be added ( in the next step counted)
            int unmarked = 0;

            // minimal distance
            double min;
            City temp;
            for (int i = 0; i < cities.size(); i++) {
                // for preventing distance 0
                if (i != par) {
                    temp = cities.get(i);
                    // if temp is not in the graph
                    if (!temp.marked) {
                        // count unmarked cities
                        unmarked++;
                        // calc distance
                        min = c.dist(temp);
                        // tests, if the distance is smaller than the value before ( at the beginning
                        // yes, because unlimited)
                        // saves for every city the optimal distance, if it is not already in the graph
                        // -> if city is not in the graph, it looks, if the distance to the current node
                        // is smaller than the distance before
                        if (min < queue[i]) {
                            // saving the current node ( par ) as the parent node
                            parent[i] = par;
                            // write in the queue the minimal distance
                            queue[i] = min;
                        }
                    }
                }
            }
            return unmarked;
        }

        /**
         * returns the ready mintree
         *
         * @return ready mintree
         */

        public List<City> getCities() {
            return cities;
        }

        /**
         * searches the city with the shortest way
         *
         * @return index of the city
         */

        private int searchShortestPath() {
            double minP = Double.MAX_VALUE;
            // index of the city
            int minS = -1;
            for (int i = 0; i < cities.size(); i++) {
                if (queue[i] < minP) {
                    minS = i;
                    minP = queue[i];
                }
            }
            return minS;
        }

    }
     
    Code (Java):
    package travelingSalesmanProblem;

    import java.util.LinkedList;
    import java.util.List;

    import map.City;

    /**
    * Class for finding a way to visit the cities via the Nearest Neighbour
    * Heuristic
    *
    * @author MrXeth
    * @version 1.0
    *
    */

    public class NearestNeighbourHeuristic extends Method {

        /*
         * (non-Javadoc)
         *
         * @see salesmanProblem.Method#getOrder(java.util.List)
         */

        @Override
        public List<City> getOrder(List<City> cities) {
            if (cities.size() > 0) {
                List<City> way = new LinkedList<City>();
                double temp, dist;
                way.add(cities.get(0));
                for (int i = 1; i < cities.size(); i++) {
                    dist = Double.POSITIVE_INFINITY; // worst case
                    for (int j = 1; j < cities.size(); j++) {
                        if (!way.contains(cities.get(j))) { // tests if the city has already been visited
                            temp = way.get(i - 1).dist(cities.get(j)); // ggf compare funktion
                            if (temp < dist) { // swap if other city is closer
                                try {
                                    way.set(i, cities.get(j));
                                } catch (IndexOutOfBoundsException e) {
                                    way.add(cities.get(j));
                                }
                                dist = temp;
                            }
                        }
                    }
                }
                way.add(cities.get(0));
                return way;
            }
            return null;
        }
    }
     
    Danke für eure Hilfe!
     
  2. Vielleicht hilft dir dieses Training hier weiter.
  3. mihe7
    mihe7 Bekanntes Mitglied
    Soweit ich das überblicke, müsstest Du in MinTree#searchShortestPath die Suche auf nicht markierte Knoten beschränken.
     
  4. MrXeth
    MrXeth Mitglied
    Das passt soweit, im MinTree#addNode wird, wenn ein Knoten hinzugefügt wird, in der queue der wert auf unendlich gesetzt :( ich denke, dass ich am Ende einen schlechten Algorithmus zum verwerten des Spannbaumes genutzt habe.
     
    Zuletzt bearbeitet: 7. Dez. 2018
  5. mihe7
    mihe7 Bekanntes Mitglied
    Stimmt. Was gibt denn City#getNeighbours() zurück? Dürfte im MST nur die verbundene City sein, oder?
     
  6. MrXeth
    MrXeth Mitglied
    Es werden alle verbundenen Städte zurückgegeben ( Also vom MinTree). Im MST repräsentiert die Reihenfolge in der Way-Liste die Reihenfolge für das Besuchen.
     
  7. Wenn du Java lernen möchtest, empfehlen wir dir dieses Online-Training hier
Passende Stellenanzeigen aus deiner Region:





Die Seite wird geladen...

Traveling Salesman - MST Heuristik Problem - Ähnliche Themen

Traveling Salesman Problem
Traveling Salesman Problem im Forum Allgemeine Java-Themen
Traveling Salesman Tour
Traveling Salesman Tour im Forum Allgemeine Java-Themen
Traveling Salesman Problem (TSP)
Traveling Salesman Problem (TSP) im Forum Java Basics - Anfänger-Themen
Traveling Salesman Problem
Traveling Salesman Problem im Forum Hausaufgaben
Problem mit TravelingSalesman
Problem mit TravelingSalesman im Forum Java Basics - Anfänger-Themen
Thema: Traveling Salesman - MST Heuristik Problem