123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345 |
- package pathgame.algorithm;
- import pathgame.gameplay.Player;
- import pathgame.logging.Logger;
- import pathgame.tilemap.TileMap;
- import java.util.ArrayList;
- import java.util.Collections;
- /** Class for calculating an approximation of the travelling salesman problem, using the Christofides algorithm
- *
- */
- public class TravellingSalesAlg {
- /** Calculates an approximation of the travelling salesman problem, using the Christofides algorithm
- *
- * @param map the TileMap that the algorithm should be used on
- * @param player that is traversing the map
- * @return
- */
- public static int calcSalesPathLen(TileMap map, Player player) {
- DijkstraMagic dijkstra = new DijkstraMagic(map, player);
- ArrayList<ArrayList<SaleRoute>> salesPitch = dijkstra.getSalesPitch();
- //make minimum spanning tree
- ArrayList<TreeEdge> MSTree = makeMSTree(salesPitch);
- //find pairs-shortest path for verteces with odd degree and add those edges to MSTree
- ArrayList<TreeEdge> oddDegEdges = makeOddDegEdges(MSTree, salesPitch);
- MSTree.addAll(oddDegEdges);
- //finde euler tour
- ArrayList<Integer> eulerTour = getEulerTour(MSTree);
- //cut short
- cutShort(eulerTour);
- Logger.onAlgoDone(salesPitch, eulerTour);
- //calculate the total weight of the tour using the edge table (salesPitch)
- int tourWeight = calcTourWeight(eulerTour, salesPitch);
- System.out.println("min cost: " + tourWeight);
- return tourWeight;
- //brute force
- //return bruteForce(salesPitch);
- }
- private static int calcTourWeight(ArrayList<Integer> tour, ArrayList<ArrayList<SaleRoute>> salesPitch) {
- int totalWeight = 0;
- for(int i = 0; i < tour.size()-1; i++) {
- int startNode, endNode;
- if(tour.get(i) < tour.get(i+1)) {
- startNode = tour.get(i);
- endNode = tour.get(i+1) - startNode - 1;
- }
- else {
- startNode = tour.get(i+1);
- endNode = tour.get(i) - startNode - 1;
- }
- totalWeight += salesPitch.get(startNode).get(endNode).getTotalCost();
- }
- return totalWeight;
- }
- private static void cutShort(ArrayList<Integer> eulerTour) {
- int counter = 2;
- while(counter < eulerTour.size()-1) {
- int current = eulerTour.get(counter);
- boolean found = false;
- for(int i = 0; i < counter; i++) {
- if(eulerTour.get(i) == current) {
- found = true;
- break;
- }
- }
- if(found) {
- eulerTour.remove(counter);
- }
- else {
- counter++;
- }
- }
- }
- private static ArrayList<Integer> getEulerTour(ArrayList<TreeEdge> graph) {
- ArrayList<Integer> tour = new ArrayList<>();
- while (graph.size() > 0) {
- if(tour.size() == 0) {
- tour = getSubtour(graph, graph.get(0).getSrc());
- }
- else {
- int start = -1;
- for(int e = 0; e < graph.size(); e++) {
- TreeEdge edge = graph.get(e);
- for(int tp = 0; tp < tour.size(); tp++) {
- if(edge.getSrc() == tour.get(tp)) {
- start = edge.getSrc();
- break;
- }
- else if(edge.getDest() == tour.get(tp)) {
- start = edge.getDest();
- break;
- }
- }
- if(start!= -1) {
- break;
- }
- }
- ArrayList<Integer> subTour = getSubtour(graph, start);
- mergeTours(tour, subTour);
- }
- }
- return tour;
- }
- private static ArrayList<Integer> getSubtour(ArrayList<TreeEdge> graph, int start) {
- ArrayList<Integer> tour = new ArrayList<>();
- tour.add(start);
- int pos = nextTourEdgePos(graph, start);
- int next = graph.get(pos).getOtherVertex(start);
- graph.remove(pos);
- tour.add(next);
- while (next != start) {
- pos = nextTourEdgePos(graph, next);
- next = graph.get(pos).getOtherVertex(next);
- graph.remove(pos);
- tour.add(next);
- }
- return tour;
- }
- private static int nextTourEdgePos(ArrayList<TreeEdge> graph, int vertex) {
- for(int i = 0; i < graph.size(); i++) {
- if(graph.get(i).getSrc() == vertex || graph.get(i).getDest() == vertex) {
- return i;
- }
- }
- return -1;
- }
- private static void mergeTours(ArrayList<Integer> tour, ArrayList<Integer> subTour) {
- int mergeTo = subTour.get(0);
- int mergePos = -1;
- for(int i = 0; i < tour.size(); i++) {
- if (tour.get(i) == mergeTo) {
- mergePos = i;
- }
- }
- for(int i = subTour.size()-1; i > 0; i--) {
- tour.add(mergePos+1, subTour.get(i));
- }
- }
- private static ArrayList<TreeEdge> makeOddDegEdges(ArrayList<TreeEdge> msTree, ArrayList<ArrayList<SaleRoute>> salesPitch) {
- int numOfEdges[] = new int[salesPitch.size()];
- for (int i = 0; i < msTree.size(); i++) {
- numOfEdges[msTree.get(i).getSrc()]++;
- numOfEdges[msTree.get(i).getDest()]++;
- }
- OddDegreeList oddDegs = new OddDegreeList();
- for (int i = 0; i < numOfEdges.length; i++) {
- //System.out.println(numOfEdges[i]);
- if (numOfEdges[i] % 2 == 1) {
- oddDegs.add(i);
- }
- }
- Permutation permut = new Permutation(oddDegs.size(), 2);
- calcPairShortest(oddDegs, salesPitch, permut, 0, 0);
- permut.makePermutMinimal();
- //System.out.println(permut.tempCounter1);
- //System.out.println(permut.tempCounter2);
- //System.out.println("min cost: " + permut.getMinCost());
- //permut.printPermut();
- ArrayList<TreeEdge> oddEdges = new ArrayList<>();
- oddDegs.resetUsed();
- for(int i = 0; i < permut.size(); i++) {
- int offSet = permut.getValAtPos(i);
- addOddEdge(oddEdges, oddDegs, salesPitch, offSet);
- }
- addOddEdge(oddEdges, oddDegs, salesPitch, 0);
- return oddEdges;
- }
- private static void addOddEdge(ArrayList<TreeEdge> oddEdges, OddDegreeList oddDegs, ArrayList<ArrayList<SaleRoute>> salesPitch, int offSet) {
- int orig = oddDegs.getUnused(0);
- oddDegs.makeOffsetUsed(0);
- int dest = oddDegs.getUnused(offSet);
- oddDegs.makeOffsetUsed(offSet);
- oddEdges.add(new TreeEdge(orig, dest, salesPitch.get(orig).get(dest - orig - 1).getTotalCost()));
- }
- private static void calcPairShortest(OddDegreeList oddDegs, ArrayList<ArrayList<SaleRoute>> salesPitch, Permutation permut, int permutPos, int costSoFar) {
- while(true) {
- int offSet;
- if(permutPos == permut.size()) {
- offSet = 0;
- }
- else {
- offSet = permut.getValAtPos(permutPos);
- }
- int orig = oddDegs.getUnused(0);
- int dest = oddDegs.getUnused(1 + offSet);
- int edgeWeight = salesPitch.get(orig).get(dest - orig - 1).getTotalCost();
- int newCost = costSoFar + edgeWeight;
- //permut.tempCounter1++;
- /*System.out.println();
- System.out.println("permut pos: " + permutPos);
- System.out.println(orig + " : " + dest);
- System.out.println("newCost: " + newCost);
- permut.printPermut();*/
- if(newCost < permut.getMinCost()) {
- if(permutPos == permut.size()) {
- permut.setMinCost(newCost);
- /*System.out.println();
- System.out.println("!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!");
- System.out.println("New Min: " + newCost);
- System.out.println("!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!");*/
- }
- else {
- int used1 = oddDegs.makeOffsetUsed(0);
- int used2 = oddDegs.makeOffsetUsed(offSet);
- calcPairShortest(oddDegs, salesPitch, permut, permutPos+1, costSoFar+edgeWeight);
- oddDegs.makeUnused(used1);
- oddDegs.makeUnused(used2);
- }
- }
- if(permutPos == permut.size()) {
- //permut.tempCounter2++;
- break;
- }
- if(permut.isPosAtMax(permutPos)) {
- break;
- }
- permut.increaseAtPos(permutPos);
- }
- }
- private static ArrayList<TreeEdge> makeMSTree(ArrayList<ArrayList<SaleRoute>> salesPitch) {
- ArrayList<TreeEdge> allEdges = new ArrayList<>();
- ArrayList<TreeEdge> msTree = new ArrayList<>();
- int vertNum = salesPitch.size();
- for (int orig = 0; orig < salesPitch.size(); orig++) {
- for (int dest = 0; dest < salesPitch.get(orig).size(); dest++) {
- allEdges.add(new TreeEdge(orig, dest + 1 + orig, salesPitch.get(orig).get(dest).getTotalCost()));
- //System.out.println(edge.getSrc() + " " + edge.getDest() + " " + edge.getWeight());
- //System.out.println(salesPitch.get(orig).get(dest).getTotalCost());
- }
- }
- //System.out.println(vertNum);
- Collections.sort(allEdges);
- while (msTree.size() < vertNum - 1) {
- if (notCycle(msTree, allEdges.get(0))) {
- msTree.add(allEdges.get(0));
- //System.out.println(allEdges.get(0).getSrc() + " " + allEdges.get(0).getDest() + " " + allEdges.get(0).getWeight());
- }
- allEdges.remove(0);
- }
- return msTree;
- }
- private static void qEdges(ArrayList<TreeEdge> tree, ArrayList<TreeEdge> edgeQ, int vertex) {
- for(int i = 0; i < tree.size(); i++) {
- TreeEdge edge = tree.get(i);
- if(edge.getSrc() == vertex || edge.getDest() == vertex) {
- if(!edge.isChecked()) {
- edgeQ.add(edge);
- //System.out.println("src: " + edge.getSrc() + "; dest: " + edge.getDest());
- edge.setChecked(true);
- }
- }
- }
- }
- private static boolean notCycle(ArrayList<TreeEdge> tree, TreeEdge additon) {
- ArrayList<TreeEdge> edgeQ = new ArrayList<>();
- int dest = additon.getDest();
- resetEdges(tree);
- qEdges(tree, edgeQ, additon.getSrc());
- while(edgeQ.size() > 0) {
- TreeEdge edge = edgeQ.get(0);
- edgeQ.remove(0);
- if(edge.getSrc() == dest || edge.getDest() == dest) {
- return false;
- }
- else {
- qEdges(tree, edgeQ, edge.getSrc());
- qEdges(tree, edgeQ, edge.getDest());
- }
- }
- return true;
- }
- private static void resetEdges(ArrayList<TreeEdge> tree) {
- for(int i = 0; i < tree.size(); i++) {
- tree.get(i).setChecked(false);
- }
- }
- }
|