algorithm - 阿贝尔群中的最小成本因式分解

Question

我有一个特定的优化问题，我想知道是否有解决它的聪明方法。 (这很可能已经被广泛研究过，我只是不知道用什么名字来查找它。)

我有一个(编辑:免费)有限生成的阿贝尔群，G , 关于 n发电机。我也有一套P G 的元素，每个都标有严格的正成本。 G 的所有发电机出现在 P , 所以总是可以表达 G 的任何元素作为 P 元素的产物或他们的倒数。任何此类产品的成本都是 P 元素成本的总和出现在其中，考虑到它们出现的频率。零产品的成本，表示 G 的标识元素, 为零。

给定组中的一个元素，我想要一种方法来找到用 P 的元素表示它的最低成本产品.

将其转化为没有负双循环的最短路径问题很简单(在无限图上，但对于任何给定的元素，您只需要它的有限部分靠近标识元素)。将其转化为整数线性规划问题也很简单。

可能这些翻译之一是要走的路？或者这个问题的额外结构是否导致更简单的方法？在我的实际问题中5 <= n <= 10并且我感兴趣的元素的任何生成器的重数都不会超过大约 +/- 20。

我在 Haskell 工作，所以函数式方法比状态式方法更受欢迎，但状态式方法也可以。

Answer 1

警告:未经测试的伪代码

This is pseudocode.  It isn't finished and probably won't even compile.

minCost :: element -> [generator] -> number -> Maybe [generator]
minCost _ [] _ = Nothing
minCost x _ c | (elemCost x) + c > cutoff = Nothing
minCost e _ _ = Just [] -- The factorization of the identity is the nullary product.
minCost x gs _ | elem x gs = Just [x]
minCost x gs _ | elem x ps = Nothing -- in P but not in gs.
minCost x gs c  =
  argmin
    pathCost
    [maybeCons g (minCost (x-g) [h| h <- gs, h <= g, h /= -g] (c+(elemCost g))) | g<-gs]

maybeCons :: a -> Maybe [a] -> Maybe [a]
maybeCons _ Nothing = Nothing
maybeCons x (Just xs) = Just (x:xs)

elemCost :: element -> number
pathCost :: [element] -> number
pathCost = sum . map elemCost

argmin :: (a -> n) -> [Maybe a] -> Maybe a
-- Return the item with the lowest cost, or Nothing if there isn't one.

这里有一点牵强附会，但我希望逻辑应该是清楚的。我们必须对 P 施加任意总排序，并且 argmin 必须处理 Nothing 的结果，表示无法从 P< 的子集生成 x/em>。为了可读性，我的伪代码没有完全正确的语法来执行此操作。

从允许的生成器中排除 h> g 是安全的，因为任何包含 h 的解都会被 minCost (x-h) 分支找到，直到置换(G 是阿贝尔矩阵，因此任何置换解都是等价的)。排除 -g 是安全的，因为 g + (-g + a) = a，但成本更高，因此没有这样的解决方案是最佳的。

该算法需要一种修剪分支的方法，例如，当 P = {1,-1,i,-i} 时，测试 (2+i) {1,-1,-i }, (2+2i) {1,-1,-i}，无穷大。这可能需要在成本超过截止值时修剪搜索。通过该修复，它会终止，因为每次递归都会减少 gs 的大小或步数，直到 x 减少为生成器，直到达到基本情况之一或成本累积到阈值以上。 (这可以通过传递迄今为止在任何并行分支上计算的最低成本来改进。)它不能重复计算，因为我们已经排除了路径中所有先前步骤的逆运算。

事后思考

说 e 生成自身，即使不在 P 中也是不正确的，并且不需要正确性:该算法从不将元素添加到它自己的逆，所以这可以仅当我们明确询问如何生成身份时才会发生。这是一个有效的查询:复数单位根？

经过进一步思考，感谢您将身份表示为无效产品的建议。否则，我们会失败，因为我们从不检查生成器的逆!它也有正确的类型!

有一种情况可以使返回类型为 [[generator]] 而不是 Maybe [generator] 并返回所有最优产品，将 Nothing 表示为 [] 。 maybeCons 的定义将变成 map ((:)g) 。但是，如果有很多同样便宜的路径，这就有可能出现指数爆炸。

将成本与因式分解一起返回到一个元组中，都可以让我们更快地修剪成本更高的任何后续并行分支。或者我们可以为此使用 pathCost。

虽然我一般没有想到任何其他方法，但您小组的特定格结构可能会建议更多修剪方法。例如，对于加法下的复整数，我们可以很容易地从实系数和虚系数中检测出两个(最多)生成器必须是什么。在许多组中，我们可以很容易地检测到某些东西不是特定生成器的产物，这是通过它位于 G 的哪个子集。这些可能是额外的守卫，它们使用 gs 的适当子集进行尾递归。

由于成本函数，generator 类型必须与 element 或其实例相同。排序关系可能仅为生成器定义，或者它们的结构可能更简单。如果该组具有恰好对算法效率较低的自然排序，它可能有不同的名称。

我会在注释中注明该代码不应编译，因为我很确定我至少写了一个错误。