Рассчитайте все возможные и значимые перестановки
Моя проблема — какая-то проблема китайского почтальона.
Я получил лабиринт, в котором программа помещает n агентов и n целей. Теперь каждый агент должен посетить каждую цель хотя бы один раз. Поэтому я должен рассчитать кратчайший путь между всеми целями, используя алгоритм A *, возможно, позже D *.
Теперь моя задача — рассчитать перестановки целей. Я имею в виду, у меня есть программа, которая рассчитывает все возможные перестановки. Но это не значит, что умно знать их всех. Я имею в виду, если у меня есть 4 цели, я получил n! перестановки (в этом примере 24). Но перестановка 1234 получила ту же длину пути, что и 4321. Поэтому мне нужно обновить мою функцию, чтобы найти симметрии во всех перестановках, и просто использовать A * для минимального числа перестановок.
Так что это код, который я сейчас использую для генерации всех перестановок. В настоящее время я просто распечатываю их, но позже я хочу обработать перестановки в виде массива или вектора, но это довольно просто по сравнению с моей основной проблемой.
#include <iostream>
#include <algorithm>
#include <iterator>
int main( int argc, char *argv[] )
{
unsigned int n = atoi( argv[1] );
unsigned int f[n], *const fn = f + sizeof(f) / sizeof(*f);
for(int j=0; j<n; j++)
{
f[j]=(j+1);
}
unsigned int i = 0;
do
{
std::cout << ++i << ". Permutation: ";
copy(f, fn, std::ostream_iterator<int>(std::cout, " "));;
std::cout << std::endl;
}
while(std::next_permutation(f, fn));
return 0;
}
Решение
Чтобы пропустить симметричные перестановки, вы можете пропустить тот, где последний узел уступает первому узлу:
void show_permutation(std::vector<unsigned int> v)
{
int i = 0;
do {
if (v.back() < v.front()) {
continue;
}
std::cout << ++i << ". Permutation: ";
copy(v.begin(), v.end(), std::ostream_iterator<unsigned int>(std::cout, " "));
std::cout << std::endl;
} while(std::next_permutation(v.begin(), v.end()));
}
Другие решения