Как найти все возможные решения в обратном пути

Question

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

Проблема заключается в том, что я не могу понять, как сделать мою функцию «обратным трафиком» ... когда она находит решение, она полностью возвращается к корню. Как мне вернуться к точке, где я могу попробовать другой путь, и заставить его идти по этому пути, а не делать то же самое снова?

Вот мой код, хотя я знаю, что моя идея, вероятно, неправильна ... просто я старался думать об этом по-разному, и я совершенно потерялся здесь. Спасибо за любую помощь!

void allPairs (int x, int pref[], bool teamed[], int* max, int score, int numWorkers) { 
    for (int i=1; i < numWorkers; i++) { 
     int count = 0; 
     pairTwo(x, i, pref, teamed, max, score, numWorkers, &count); 
    } 
} 

int pairTwo (int x, int y, int pref[], bool teamed[], int* max, int score, int numWorkers, int* howMany) { 
     if (x >= numWorkers) { 
      arrToZero(teamed, numWorkers); 
      return score; 
     } 
     else if (x==y) { 
      if(y < numWorkers-1) { 
       y = findUnteamed(teamed, y+1, numWorkers); 
      } 
      else { 
       arrToZero(teamed, numWorkers); 
       return score; 
      } 
     } 

     int pairScore = sumPair(pref, x, y, teamed, numWorkers); 
     x = findUnteamed(teamed, x, numWorkers); 
     y = findUnteamed(teamed, 0, numWorkers); 
     int temp = pairTwo(x, y, pref, teamed, max, score + pairScore, numWorkers, howMany); 
     teamed[x] = 0; // here I tried to "erase" the last move but it's useless 
     teamed[y] = 0; 
     if (temp >= *max) { 
      max = &temp; 
      *howMany++; 
      printf("There are %d optimal pairings:, with a total score of: %d\n", *howMany, *max); 
      return *max; 
     } 
     else { 
     return -1; 
     } 
} 

Answer 1

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

Стандартный алгоритм рекурсивного обратного отслеживания состоит из solve(), getSuccessors(), isGoal() и isValid(). Используя пример массива целых чисел, которые в настоящее время manuipulated быть решена, решить() функция выглядеть следующим образом:

int[] solve(int[] list) { 
    if (isGoal(list)) { 
     return list; 
    } 
    int[][] successors = getSuccessors(list) 
    for (int[] successor : successors) { 
     if (isValid(successor)) { 
      if (sizeof(solve(successor)) != 0) { 
       return successor; 
      } 
     } 
    } 
    return []; 
} 

Где getSuccessors() возвращает список глубоких копий текущего массива, которые были изменены для изучения новых решений, isGoal() проверяет, найдено ли решение, и isValid() проверяет, можно ли найти цель, продолжающую этот путь. Эти три функции специфичны для проблемы, которую вы пытаетесь решить.

Альтернативно, существует итеративная версия solve(), в которой исходное состояние помещается в пустой стек, хотя вам нужен стек, созданный в первую очередь. Проверьте страницу Википедии на итеративном обратном следе, чтобы увидеть, как работает этот метод решения.