Блог

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

Вот моя структура данных:-

 public class Airport {
    String name;
    Set<Neighbour> neighbours;
    ...
}

public class Neighbour {
    Airport airport;
    double costToReach;
    ...
}
 

Я пытаюсь получить доступные пути(список списков) от одного Airport к другому Airport .

 List<List<Airport>> getPaths(Airport source, Airport destination) {
    // Logic goes here
}
 

Ожидаемый входной образец:-

 Source airport - Mumbai
Destination airport - Delhi
 

Пример ожидаемого результата:-

 Mumbai -> Pune -> Delhi
Mumbai -> Ahmedabad -> Noida -> Delhi
 

Любая помощь была бы очень признательна. Спасибо!

Что вы можете сделать, так это создать метод, который использует начальную точку, целевую точку и набор уже посещенных аэропортов. В этом методе вы можете:

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

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

Вот решение на Python, так как я не разбираюсь в Java; но поскольку вы отметили вопрос «алгоритмом», я думаю, что его легко понять и преобразовать.

 def getPaths(source, destination):
  # We’ve reached the destination
  if source["name"] == destination["name"]:
    # Return a list of lists
    return [[destination["name"]]]

  result = []

  # If there are no neighbours or
  # none of them yield a destination,
  # ‘result’ will be an empty list
  for neighbour in source["neighbours"]:
    paths = getPaths(neighbour, destination)
    result.extend([[source["name"]]   path for path in paths])

  return result
 

Пример:

 mumbai = {"name": "Mumbai"}
pune = {"name": "Pune"}
delhi = {"name": "Delhi"}
ahmedabad = {"name": "Ahmedabad"}
noida = {"name": "Noida"}

# Assign neighbours
mumbai["neighbours"] = [pune, ahmedabad]
pune["neighbours"] = [delhi]
delhi["neighbours"] = []
ahmedabad["neighbours"] = [noida]
noida["neighbours"] = [delhi]

print(getPaths(mumbai, delhi))