10

我有一个优化问题，我想知道是否有解决它的聪明方法。（这很可能已经被广泛研究过，我只是不知道在什么名称下查找它。）

G我在生成器上有一个（编辑：免费）有限生成的阿贝尔群n。我还有一组P的元素G，每个都标有严格的正成本。的所有生成元都G出现在 中P，因此总是可以将 的任何元素表示为 的元素或其逆G元素的乘积。P任何此类产品的成本是P其中出现的元素成本的总和，考虑到它们出现的频率。表示 的单位元的零产品的成本G为零。

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

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

可能是这些翻译之一是要走的路？或者这个问题的附加结构会导致更简单的方法吗？在我的实际问题5 <= n <= 10和我感兴趣的元素中，任何生成器的复数都不会大于大约 +/- 20。

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

4

1 回答 1

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将变为 just map ((:)g)。但是，如果有很多同样便宜的路径，这将面临指数级爆炸的风险。

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

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

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

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

于 2015-09-21T04:42:43.250 回答