java - 将递归组合查找算法转换为迭代算法以避免 GC Overhead Limit Exceeded 错误

Question

该算法的目的是生成行程序列列表。每次旅行都有起点和终点。用户指定这两者，并且算法返回的列表中的每个序列最终必须以具有指定起点的行程开始，并以具有指定终点的行程结束。

我想出了一种算法，它返回以具有指定起点的行程开始的每个可能的序列(例如，对于起点 A，可能的第一个行程包括 AB、AC、AD 等)。获得序列列表后，我的计划是删除所有不以具有指定结束的行程结束的序列(例如，对于末端 C，最终行程为 BA、CD 和 DB 的序列将从列表中删除)。

public List<ArrayList<Trip>> getTripSequences(List<Trip> tripList, Location start, List<Trip> sequence) {

    List<ArrayList<Trip>> resultList = new ArrayList<ArrayList<Trip>>();

    getTripSequences(tripList, start, sequence, resultList);

    return resultList;
}

private void getTripSequences(List<Trip> tripList, Location start, List<Trip> sequence, List<ArrayList<Trip>> resultList) {
    if (tripList.isEmpty())
        return;

    else {
        for (Trip trip : tripList)

            if (trip.getStart().equals(start)) {

                // intermSq - an intermediary sequence
                ArrayList<Trip> intermSq = new ArrayList<Trip>();

                List<Trip> smallerList = new ArrayList<Trip>();

                smallerList.addAll(tripList);

                intermSq.addAll(sequence);

                intermSq.add(trip);

                resultList.add(intermSq);

                smallerList.remove(trip);

                resultList.addAll(getTripSequences(smallerList, trip.getEnd(), intermSq));      
            }   
     }
}

该算法适用于小型行程列表。例如，输入以下可能的行程列表

AB, BA, BC, CA, CB

指定起始点 A 将返回以下序列:

AB
AB BA
AB BC
AB BC CA
AB BC CB
AB BC CB BA

当然，在这一点之后，我必须删除所有未以正确结束位置结束的序列，但这似乎并不太困难。当我尝试将其用于大量行程且位置数量多于我在测试中使用的位置(即 A B C D)时，问题就出现了。我收到此错误:

java.lang.OutOfMemoryError: GC overhead limit exceeded

我对递归的概念很陌生，所以我没有预料到这个问题，但我现在明白为什么会发生。我正在尝试决定我应该做什么而不是这个。

• 该算法的迭代版本会是什么样子？迭代会使用足够少的内存吗？
• 增加堆大小来避免此错误是个好主意吗？

我尝试完全重写算法来解决主要问题(即生成具有指定起点和终点的序列)，但我陷入了困境。

如果有任何帮助，我将不胜感激!

编辑 以下是算法中使用的类。

public class Location {

    private String continent;
    private String country;

    public Location(){
        super();
    }

    public Location(String continent, String country) {
        super();
        this.continent = continent;
        this.country = country;
    }

    public String getContinent() {
        return continent;
    }

    public void setContinent(String continent) {
        this.continent = continent;
    }

    public String getCountry() {
        return country;
    }

    public void setCountry(String country) {
        this.country = country;
    }   
}

public class Trip {

    private Location start;
    private Location end;

    public Location getStart() {
        return start;
    }

    public void setStart(Location start) {
        this.start = start;
    }

    public Location getEnd() {
        return end;
    }

    public void setEnd(Location end) {
        this.end = end;
    }
}

编辑 以下生成器创建一个列表，其大小与导致我的错误的列表相同。

public class Tester {

    public Trip makeTrip(Location start, Location end) {
        Trip trip = new Trip();
        trip.setStart(start);
        trip.setEnd(end);
        return trip;
    }

    public static void main(String[] args) {

    Tester tester = new Tester();

    ArrayList<Location> locations = new ArrayList<Location>();

    locations.add(new Location("A", "A"));
    locations.add(new Location("B", "B"));
    locations.add(new Location("C", "C"));
    locations.add(new Location("D", "D"));
    locations.add(new Location("E", "E"));
    locations.add(new Location("F", "F"));
    locations.add(new Location("G", "G"));
    locations.add(new Location("H", "H"));
    locations.add(new Location("I", "I"));
    locations.add(new Location("J", "J"));
    locations.add(new Location("K", "K"));
    locations.add(new Location("L", "L"));
    locations.add(new Location("M", "M"));
    locations.add(new Location("N", "N"));
    locations.add(new Location("O", "O"));
    locations.add(new Location("P", "P"));
    locations.add(new Location("Q", "Q"));
    locations.add(new Location("R", "R"));
    locations.add(new Location("S", "S"));
    locations.add(new Location("T", "T"));

    int i = 0;

    Random random = new Random();

    ArrayList<Trip> trips = new ArrayList<Trip>();

    while (i++ < 54) {
        trips.add(tester.makeTrip(locations.get(random.nextInt(20)), locations.get(random.nextInt(20))));
    }

    System.out.println(trips.size());

    for (Trip trip : trips)

    System.out.println(trip.getStart().getCountry() + trip.getEnd().getCountry());
    }
}

Answer 1

通过库(Combinatoricslib)使用数学组合是否有相同的算法

这是代码，它使用的内存少得多，但仍然需要很长时间，因为使用暴力，尝试所有可能的组合并过滤符合规则的组合。

您需要 java 8 来编译它，检查是否适合您的需求。

The Lib

Algorithm refactored