Traveling Salesman - MST Heuristik Problem

MrXeth

Aktives 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:
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);
            }
        }
    }

}

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;
    }

}
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!
 

mihe7

Top Contributor
Soweit ich das überblicke, müsstest Du in MinTree#searchShortestPath die Suche auf nicht markierte Knoten beschränken.
 

MrXeth

Aktives 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:

MrXeth

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

Ähnliche Java Themen

Neue Themen


Oben