Минимальная стоимость факторинга в абелевых группах

Question

У меня есть определенная проблема оптимизации, и мне интересно, есть ли разумный подход для ее решения. (Возможно, это было хорошо изучено, и я просто не знаю, под каким именем его искать.)

У меня есть (EDIT: бесплатно) конечно порожденная абелева группа, 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, представляя, что нет способа генерировать x из этого подмножества P. У моего псевдокода не совсем правильный синтаксис для удобства чтения.

Исключение 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 или его экземпляр, из-за функции стоимости. Отношение порядка может быть определено только для генераторов, или их структура может быть проще. Оно может иметь другое имя, если группа имеет естественный порядок, который оказывается менее эффективным для алгоритма.

Я оставлю в примечании, что код не должен компилироваться, потому что я почти уверен, что написал хотя бы одну ошибку.