阿贝尔群中的最小成本因式分解
Minimum cost factoring in abelian groups
我有一个优化问题，我想知道是否有解决它的巧妙方法。 （这很可能已经被广泛研究过，我只是不知道用什么名字来查找它。）
我在 n 生成器上有一个（编辑：免费）有限生成阿贝尔群 G。我还有一组 P 个 G 的元素，每个元素都标有严格的正成本。 G 的所有生成元都出现在 P 中，因此总是可以将 G 的任何元素表示为 P 的元素或其逆元素的乘积。任何此类产品的成本都是其中出现的 P 元素成本的总和，同时考虑到它们出现的频率。表示 G 的单位元素的无效产品的成本为零。
给定组中的一个元素，我想要一种方法来找到用 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 的结果，表示无法生成 x 来自 P 的那个子集。为了可读性，我的伪代码没有完全正确的语法来执行此操作。
从允许的生成器中排除 h > g 是安全的，因为任何包含 h[=67= 的解决方案] 将由 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 中也会自行生成，这在要求上是不正确的，而且对于正确性来说是不必要的：该算法从不添加元素到它自己的逆，所以这只有在我们明确询问如何生成身份时才会发生。这是一个有效的查询：复数单位根？
经过进一步思考，感谢您将身份表示为无效产品的建议。否则，我们会失败，因为我们从不检查生成器的逆！它也有正确的类型！
有一种情况可以使 return 类型 [[generator]] 而不是 Maybe [generator] 和 return 所有最优产品，将 Nothing 表示为 []. maybeCons 的定义将变为 map ((:)g)。但是，如果有很多同样便宜的路径，这可能会导致指数爆炸。
将成本与因式分解一起返回到一个元组中，都可以让我们更快地修剪成本更高的任何后续并行分支。或者我们可以为此使用 pathCost。
你的小组的特定格子结构可能会建议更多的修剪方法，尽管我没有考虑任何其他一般。例如，对于加法下的复整数，我们可以很容易地从实系数和虚系数中检测出两个（最多）生成器必须是什么。在许多组中，我们可以很容易地检测到某些东西不是特定生成器的产物，它位于 G 的哪个子集。这些可能是额外的守卫，使用适当的子集进行尾递归共 gs.
generator 类型必须与 element 相同或它的实例，因为成本函数。排序关系可能仅为生成器定义，或者它们的结构可能更简单。如果该组的自然排序恰好对算法来说效率较低，它可能有不同的名称。
我会在注释中注明该代码无法编译，因为我很确定我至少写了一个错误。
我有一个优化问题，我想知道是否有解决它的巧妙方法。 （这很可能已经被广泛研究过，我只是不知道用什么名字来查找它。）
我在 n 生成器上有一个（编辑：免费）有限生成阿贝尔群 G。我还有一组 P 个 G 的元素，每个元素都标有严格的正成本。 G 的所有生成元都出现在 P 中，因此总是可以将 G 的任何元素表示为 P 的元素或其逆元素的乘积。任何此类产品的成本都是其中出现的 P 元素成本的总和，同时考虑到它们出现的频率。表示 G 的单位元素的无效产品的成本为零。
给定组中的一个元素，我想要一种方法来找到用 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 的结果，表示无法生成 x 来自 P 的那个子集。为了可读性，我的伪代码没有完全正确的语法来执行此操作。
从允许的生成器中排除 h > g 是安全的，因为任何包含 h[=67= 的解决方案] 将由 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 中也会自行生成，这在要求上是不正确的，而且对于正确性来说是不必要的：该算法从不添加元素到它自己的逆，所以这只有在我们明确询问如何生成身份时才会发生。这是一个有效的查询：复数单位根？
经过进一步思考，感谢您将身份表示为无效产品的建议。否则，我们会失败，因为我们从不检查生成器的逆！它也有正确的类型！
有一种情况可以使 return 类型 [[generator]] 而不是 Maybe [generator] 和 return 所有最优产品，将 Nothing 表示为 []. maybeCons 的定义将变为 map ((:)g)。但是，如果有很多同样便宜的路径，这可能会导致指数爆炸。
将成本与因式分解一起返回到一个元组中，都可以让我们更快地修剪成本更高的任何后续并行分支。或者我们可以为此使用 pathCost。
你的小组的特定格子结构可能会建议更多的修剪方法，尽管我没有考虑任何其他一般。例如，对于加法下的复整数，我们可以很容易地从实系数和虚系数中检测出两个（最多）生成器必须是什么。在许多组中，我们可以很容易地检测到某些东西不是特定生成器的产物，它位于 G 的哪个子集。这些可能是额外的守卫，使用适当的子集进行尾递归共 gs.
generator 类型必须与 element 相同或它的实例，因为成本函数。排序关系可能仅为生成器定义，或者它们的结构可能更简单。如果该组的自然排序恰好对算法来说效率较低，它可能有不同的名称。
我会在注释中注明该代码无法编译，因为我很确定我至少写了一个错误。