Грубая сила из пространства памяти - PullRequest
Новая
       6

Грубая сила из пространства памяти

0 голосов
/ 25 мая 2018

Я занят созданием алгоритма грубой силы TSP, программа в настоящее время работает и вычисляет кратчайший возможный маршрут, который я ввожу.К сожалению, максимальное количество узлов, которое я могу использовать, равно 10, потому что всякий раз, когда я поднимаюсь выше, я получаю: «Java.lang.OutofMemoryError: пространство кучи Java».Я уже пытался оптимизировать код, но результат был незначительным.Как я могу дополнительно оптимизировать мой код, чтобы я мог использовать больше узлов при выполнении моего алгоритма?

Это мой код: 

import com.sybrand.TSP.*;
import java.util.*;

public class BruteForce extends TSP_Algorithm {

    private ArrayList<Coordinate> sortedCoords = new ArrayList<>();
    ArrayList<Coordinate> coords = new ArrayList<>();
    ArrayList<Coordinate> shortestRoute;

    public BruteForce(ArrayList<Coordinate> coords) {
        sortedCoords.addAll(coords);
        permutation(sortedCoords);
    }

    public void permutation(ArrayList<Coordinate> nums) {
        List<List<Coordinate>> accum = new ArrayList<>();
        permutation(accum, Collections.emptyList(), nums);
        float shortestDistance = 0.0f;
        for (List<Coordinate> routeOption: accum) {
            Path calcDistance = new Path((ArrayList<Coordinate>) routeOption);
            if (shortestDistance == 0.0f || calcDistance.getDistance() < shortestDistance) {
                shortestDistance = calcDistance.getDistance();
                this.shortestRoute = (ArrayList<Coordinate>) routeOption;
            }
        }
    }

    private static void permutation(List<List<Coordinate>> accum, List<Coordinate> prefix, List<Coordinate> nums) {
        int n = nums.size();
        if (n == 0) {
            accum.add(prefix);
        } else {
            for (int i = 0; i < n; ++i) {
                List<Coordinate> newPrefix = new ArrayList<>(prefix);
                newPrefix.add(nums.get(i));
                List<Coordinate> numsLeft = new ArrayList<>(nums);
                numsLeft.remove(i);
                permutation(accum, newPrefix, numsLeft);
            }
        }
    }

    public ArrayList<Coordinate> getSortedCoordinates() {
        return shortestRoute;
    }
}
...