阿贝尔群体的最低成本因素

Question

我有一个优化问题,我想知道是否有一个聪明的方法来解决它.(这可能已经被广泛研究过,我只是不知道要查找它的名称.)

我有一个(编辑:免费)有限生成的阿贝尔群G,在n发电机上.我还有一组P元素G,每个元素都标有严格正数的成本.所有的生成器都G出现在P,因此总是可以表达G作为元素P或其反转的产物的任何元素.任何此类产品的成本是P其中出现的元素的成本之和,并考虑它们出现的频率.表示身份元素的nullary产品的成本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。为了便于阅读，我的伪代码没有完全正确的语法来执行此操作。

从允许的生成器中排除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减少到生成器，直到它达到基本情况之一或成本累积到阈值以上。（这可以通过传递迄今为止在任何并行分支上计算的最低成本来改进。）它不能重复计算，因为我们已经排除了路径中所有先前步骤的逆。

事后的想法

即使不在P中，说e也会生成自身，这根据要求是不正确的，并且对于正确性来说也是不必要的：该算法永远不会将元素添加到其自身的逆元素中，因此只有当我们明确询问如何生成恒等式时，才会发生这种情况。这是一个有效的问题：复数根？

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

有一种情况是使用返回类型[[generator]]代替Maybe [generator]并返回所有最佳产生式，表示Nothing为[]。的定义maybeCons将变成公正的map ((:)g)。然而，如果存在许多同样便宜的路径，则存在指数级爆炸的风险。

在元组中返回成本和因式分解，都可以让我们更快地修剪任何具有更高成本的后续并行分支。或者我们可以用pathCost这个。

尽管我一般不会考虑任何其他方法，但您的组的特定晶格结构可能会建议更多的修剪方法。例如，对于加法下的复整数，我们可以轻松地从实数和虚数系数中检测出两个（最多）生成器必须是什么。在许多组中，我们可以很容易地检测到某些东西不是G的哪个子集的特定生成器的产物。这些可能是使用 的适当子集进行尾递归的附加保护gs。

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

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