Рекурсивно найти путь

Question

У меня есть ряд чисел от 0 до 9. Каждое число представляет собой позицию с координатой x и y. Таким образом, позиция 0 может представлять (5, 5) или что-то подобное, всегда (x, y). Теперь мне нужно сделать рекурсивно bash каждый возможный маршрут, используя 5 позиций, чтобы получить позицию, заданную пользователем. Так, например:

Input = (1, 2) //This is the co-ordinate the user gives. 

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

start 0 1 2 3 4 input 
start 0 1 2 3 5 input 
start 0 1 2 3 6 input 
start 0 1 2 3 7 input 
start 0 1 2 4 3 input 
start 1 0 2 3 5 input 
and so on.... 

Это может быть любая комбинация из 5 цифр из 0-9. Он должен заканчиваться на входе и начинаться с начала назначения. Номера нельзя использовать повторно. Поэтому мне нужно рекурсивно добавить все расстояния для данного курса (например, начать 0 1 2 3 4 ввода) и найти кратчайший курс, пройдя через эти 5 баллов.

Вопрос: Каким будет базовый и рекурсивный случай?

Answer 1

В принципе, вы хотите сгенерировать все комбинации размера k (длина пути) из набора {1, .., n}, а затем вычислить значение пути для него.

Вот C# пример кода:

void OPTPathForKSteps(List<int> currentPath, List<int> remainingPositions, int remainingSteps) 
    { 
     if (remainingSteps == 0) 
     { 
      // currentPath now contains a combination of k positions 
      // do something with currentPath... 
     } 
     else 
     { 
      for (int i = 0; i < remainingPositions.Count; i++) 
      { 
       int TempPositionIndex = remainingPositions[i]; 
       currentPath.Add(TempPositionIndex); 
       remainingPositions.RemoveAt(i); 

       OPTPathForKSteps(currentPath, remainingPositions, remainingSteps - 1); 

       remainingPositions.Insert(i, TempPositionIndex); 
       currentPath.RemoveAt(currentPath.Count - 1); 
      } 
     } 
    } 

Это первоначальный вызов для функции (предположим, что позиции представляет собой целое число список 0 ... N позиций, и к длина пути):

OPTPathForKSteps(new List<int>(), Positions, K); 

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