Преобразование рекурсивного алгоритма поиска комбинаций в итеративный, чтобы избежать ограничения верхнего предела ОВ. Превышена ошибка

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 

с заданной начальной точкой А будет возвращать следующие последовательности:

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 

Я новичок в концепции рекурсии, так что я не ожидал эту проблему, но я теперь понимаю, почему это происходит. Я пытаюсь решить, что я должен делать вместо этого.

• Какова была бы итеративная версия этого алгоритма? Будет ли итерация использовать достаточно небольшой объем памяти?
• Это хорошая идея просто увеличить размер кучи, чтобы избежать этой ошибки?

Я попытался полностью переписать алгоритм для решения основной проблемы (т. Е. Генерации последовательностей с указанными начальными и конечными точками), но я очень застрял.

Я был бы признателен за любую помощь!

EDIT Вот классы, используемые в алгоритме.

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

EDIT Следующий генератор создает список, который размер тот, который вызывает мою ошибку.

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

ли один и тот же алгоритм, используя математическую комбинацию с помощью Lib (Combinatoricslib)

Вот код, это использовать много меньше памяти, но кадры занимает много времени потому что используйте грубую силу, пробуя все возможное сочетание и фильтруя те, которые соответствуют правилам.

Вам понадобится java 8, чтобы скомпилировать это, проверьте, подходит ли вам ваши потребности.

The Lib

Algorithm refactored

Answer 2

Звучит как классическая проблема с памятью.

1. Проверьте код: Вы называете getTripSequences функцию рекурсивного в for цикле. Это совсем не оптимально.
2. увеличить размер памяти до -Xmx512m или даже -Xmx1024m

Answer 3

java.lang.OutOfMemoryError: GC overhead limit превышены не является "реальным" из памяти ошибки. Это означает, что GC пытается работать, но слишком много времени для выяснения того, что он может очистить, чтобы он освобождался. Я столкнулся с этим вопросом в самых сложных ситуациях, когда GC испытывает трудности с выяснением того, что он может освободить, и является пограничной ошибкой. Решение состоит в использовании параметра JVM -XX:-UseGCOverheadLimit. Вы все еще можете получить ошибку памяти, так как вы выполняете очень дорогостоящие операции, но может найти некоторое свободное пространство и продолжить.

Также вытащите эти два определения переменных intermSq и smallerList из середины цикла for как небольшую оптимизацию. Вы также можете рассмотреть возможность инициализации их до нужного размера, если он потенциально большой, в противном случае у вас много перетасовки памяти.