Ваша проблема кажется очень близкой к проблеме коммивояжера , классика среди классиков.
Как вы и сделали, интуитивно, граф, который будет представлять все возможные решения, действительно является деревом (пути от корня до любого его листа должны представлять решение).
Оттуда вы можете задать себе несколько вопросов:
Является ли первый город, в котором я побываю, важной информацией или важен только порядок? Например, Лондон-Варшава-Берлин-Лидз эквивалентен Варшаве-Берлин-Лидз-Лондон?
Обычно мы считаем, что эти решения эквивалентны решению TSP, но это может быть не так.
Вы видели связь между потенциальным решением для TSP и перестановкой? На самом деле, то, что вы ищете, - это способ (и соответствующая ему структура данных) для генерации всех перестановок данного набора (вашего набора городов).
С учетом этих двух моментов мы можем подумать о том, как создать такое дерево. Хорошая стратегия работы с деревьями - думать рекурсивно.
У нас есть частичное решение, означающее k
первые города. Затем следующим возможным городом может быть любой из оставшихся n-k
городов. Это дает следующий псевдокод.
get_all_permutations(TreeNode node, Set<int>not_visited){
for (city in not_visited){
new_set = copy(not_visited);
new_set.remove(city);
new_node = new TreeNode();
new_node.city = city;
node.add_child(new_node);
get_all_permutations(new_node, new_set);
}
}
Это будет строить дерево рекурсивно.
В зависимости от вашего ответа на первый пункт, который я упомянул (о важности первого города), вы можете назначить город корневому узлу или нет.
Некоторые хорошие моменты, на которые стоит обратить внимание, если вы хотите пойти дальше с этим типом проблемы / мышления, - это алгоритмы перечисления и рекурсивные алгоритмы. Как правило, они являются хорошим вариантом, когда ваша цель состоит в перечислении всех элементов набора. Но они также, как правило, неэффективный способ решения проблем (например, в случае TSP, решение с использованием этого алгоритма приводит к очень неэффективному подходу. Есть некоторые гораздо более лучшие).