algorithm - SPOJ 问题集(经典): 9386. 重新排列 II #[MAIN112]

Question

问题描述(为方便起见在此处引用):

For a sequence of N integers, A1, A2, ..... AN

We can calculate the stability factor P, as

P = sum of all (abs(Ai-Ai-1)*C[i]) where 2 <= i <= N

C[i] is the cost of putting a number at position i

Your task is find the minimum P for the given N numbers considering all the different permutations of them.

---

关于解决此问题的一般方法，我只需要朝着正确的方向轻推。 (欢迎使用少量伪代码，但我有信心在整个算法大体清晰后编写出一个解决方案)

我已经考虑了很长一段时间，但我仍然无法找到满足该问题约束的任何解决方案 (N <= 15) 蛮力方法似乎只在 N= 时表现良好10 真的。

---

首先，对于最大可能的测试用例 N=15，我不相信您能够枚举并考虑所有 15 个!排列以便在足够好的时间找到你的答案，因为复杂性类不允许这样做。

所以我们需要做几个简化的假设来减少这个搜索空间。这就是我被困的地方。或者它可能只是归结为一种更智能的方式来开始遍历这个排列空间？

我尝试使用动态编程来解决这个问题，因为排列共享许多公共(public)位，这些位可以预先计算(内存)并在必要时存储和重用，例如。 A[] = 123456 & A[] = 123465 两者都会给出 1234- 的相同部分和，但这没有成功，因为你仍然必须经过 15!排列，并且会在那之前 TLE 方式，所以这不好。

另一个想法是处理连续 A 与 C[] 的所有元素之间的差异的所有可能排列，并首先找到将产生最小 abs(A[i]-A[j])* 的对所有这些中的 C[k] 值，分配那些并将它们标记为已使用，然后继续 i 或 j 中的一个以形成下一对，再次迭代并重复。这应该在多项式时间内完成(我猜大约是 n^3)，但对于某些示例，该假设不成立。

我不认为这个问题应该很难将其转化为某种图问题 - 其中 A[i]、A[j] 形成节点，C[k] 是边链接的成本这些节点，或者可能是一些 bool SAT 问题……所有这些似乎都走错了路。

如果您用谷歌搜索这个问题，除了托管此问题的 SPOJ 网站外，您可能几乎找不到任何与此问题相关的内容。

非常感谢。

Answer 1

可以用一个O(n*2^n)空间，O(n^2*n^2)时间的子集动态规划算法来求解。

关键的见解是，当您从左到右构建最佳解决方案时，只有先前放置的数字和使用的子集很重要，而不是事物在使用的子集中放置的顺序。

计算与 Travelling Salesman Problem. 的解决方案具有基本相同的结构

您的 DP 想法走在了正确的轨道上。洞察只是所有这些部分路径之后的最优路径是相同的

1235

1325

2135

2315

3125

3215

因此您实际上不需要探索所有可能的排列，只需探索那些具有最佳部分路径的排列即可。

这里是一些实现所描述算法的 TLE Python 代码，但由于 Python 中的常数因子减速而失败。我转换为 C++ 并获得了 AC。

global A
global C

A = []
C = []

def Solve(used, last, cache):
  if (used, last) in cache:
      return cache[(used, last)]
  cur_pos = len(used)
  if cur_pos == len(A):
    return 0

  mn = 1e10
  for idx in range(len(A)):
      if not idx in used:
          next_used = used.union([idx])
          subcost = Solve(next_used, A[idx], cache)
          additional = C[cur_pos] * abs(last - A[idx])
          mn = min(mn, subcost + additional)
  cache[(used, last)] = mn
  return mn

T = int(raw_input())
for i in range(T):
  N = int(raw_input())
  A = map(int, raw_input().split())
  C = map(int, raw_input().split())
  cache = {}
  print min(Solve(frozenset([idx]), A[idx], cache) for idx in range(len(A)))