1

我的问题是某种中国邮递员问题。

我得到了一个迷宫，程序在其中放置了 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;
}
4

1 回答 1

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()));
}

活生生的例子

于 2014-11-21T09:51:15.930 回答