我有一个优化问题，我想知道是否有一个聪明的方法来解决它。(这可能已经被广泛研究过了，我只是不知道该用什么名字来查找。)
我有一个(编辑:自由)有限生成阿贝尔群，G，在n生成器。我也有G的一组P元素，每一个都被标记为严格的正成本。G的所有生成器都出现在P中，因此G的任何元素都可以表示为P元素或其逆元素的乘积。任何此类产品的成本是P中出现的元素的成本之和，考虑到它们出现的频率。表示G的单位元的虚积的代价为0。
给定组中的一个元素，我想找到一种方法来找到用P的元素表示它的最小成本产品。
很容易将其转化为没有负双环的最短路径问题(在无限图上，但对于任何给定元素，你只需要在单位元素附近的有限部分)。也可以直接将其转化为整数线性规划问题。
也许其中一种翻译是正确的?还是这个问题的附加结构导致了一个更简单的解决方法?在我的实际问题中，5 <= n <= 10和我感兴趣的元素的任何生成器的倍数都不会大于大约+/- 20。
我在Haskell中工作，所以函数式方法比有状态方法更可取，但有状态方法也可以。
警告:未经测试的伪代码
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减少到一个生成器，直到它达到一个基本情况或成本累积到阈值以上。(这可以通过忽略迄今为止在任何并行分支上计算的最低成本来改进。)它不能重复计算，因为我们已经排除了路径中所有先前步骤的倒数。
追悔
说e即使不在 p 中也会生成自身，这是不正确的要求，也是不必要的正确性:算法从不将元素添加到其自身的逆中，因此只有当我们明确地询问如何生成恒等时才会发生这种情况。这是一个有效的问题:单位的复根?
经过进一步思考，感谢您将恒等式表示为副乘积的建议。否则，我们将失败，因为我们从来没有根据它们的逆检查生成器!它也有正确的类型!
有一种情况，使返回类型[[generator]]而不是Maybe [generator]，并返回所有最优产品，将Nothing表示为[]。maybeCons的定义将变成map ((:)g)。然而，如果有很多同样便宜的路径，这种风险就会呈指数级增长。
在元组中返回代价和分解，都可以让我们更快地修剪任何代价更高的并行分支。或者我们可以使用pathCost。
你的组的特殊晶格结构可能会建议更多的方法来修剪，虽然我不认为任何其他一般。例如，对于加法下的复整数，我们可以很容易地从实系数和虚系数中检测出两个(最多)生成器必须是什么。在许多组中，我们可以很容易地检测到某些东西不是G所在子集的特定生成器的产物。这些可能是附加的保护，可以对gs的适当子集进行尾递归。
由于成本函数，generator类型必须与element或其实例相同。排序关系可能仅为生成器定义，或者它们的结构可能更简单。如果该组的自然排序恰好对算法效率较低，则该组可能会有不同的名称。
我将在注释中留下代码不应该编译，因为我很确定我至少写了一个错误。