Нахождение наибольшего f, удовлетворяющего свойству заданного f, является неубывающим в своих аргументах

Question

это меня давно беспокоило.

Допустим, у вас есть функция f x y, где x и y - целые числа, и вы знаете, что f строго неубывающая в своих аргументах,

т.е. f (x + 1) y> = f x y и f x (y + 1)> = f x y.

Какой самый быстрый способ найти наибольшее f x y, удовлетворяющее свойству, учитывая, что x и y ограничены.

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

Кроме того, более конкретно, мне было интересно, есть ли более быстрый способ решения этой проблемы, если бы вы знали, что f является оператором умножения.

Спасибо!

Редактировать: видя комментарии ниже, свойство может быть любым

Учитывая свойство g (где g принимает значение и возвращает логическое значение), я просто ищу наибольшее f, такое что g (f) == True

Например, наивная реализация (в haskell) будет:

maximise :: (Int -> Int -> Int) -> (Int -> Bool) -> Int -> Int -> Int
maximise f g xLim yLim = head . filter g . reverse . sort $ results
    where results = [f x y | x <- [1..xLim], y <- [1..yLim]]

Answer 1

Давайте нарисуем пример сетки для вашей проблемы, чтобы помочь подумать об этом.Вот примерный график f для каждого x и y.Он монотонен в каждом аргументе, что является интересным ограничением, с которым мы могли бы сделать что-то умное.

+------- x --------->
| 0  0  1  1  1  2 
| 0  1  1  2  2  4
y 1  1  3  4  6  6
| 1  2  3  6  6  7
| 7  7  7  7  7  7
v

Поскольку мы ничего не знаем о свойстве, мы не можем сделать лучше, чемперечислить значения в диапазоне f в порядке убывания.Вопрос в том, как сделать это эффективно.

Первое, что приходит на ум, - это пройтись по нему, как график, начинающийся с правого нижнего угла.Вот моя попытка:

import Data.Maybe (listToMaybe)

maximise :: (Ord b, Num b) => (Int -> Int -> b) -> (b -> Bool) -> Int -> Int -> Maybe b
maximise f p xLim yLim = 
    listToMaybe . filter p . map (negate . snd) $ 
       enumIncreasing measure successors (xLim,yLim)
  where
    measure (x,y) = negate $ f x y
    successors (x,y) = [ (x-1,y) | x > 0 ] ++ [ (x,y-1) | y > 0 ] ]

Сигнатура не такая общая, как могла бы быть (Num не нужно, но мне нужно было отменить функцию меры, потому что enumIncreasing возвращает скорее растущий, чем убывающий список - я мог бы также сделать это с помощью обертки нового типа).

Используя эту функцию, мы можем найти наибольшее нечетное число, которое можно записать как произведение двух чисел <= 100:

ghci> maximise (*) odd 100 100
Just 9801

Я написал enumIncreasing , используя meldable-heap для взлома, чтобы решить эту проблему, но она довольно общая.Вы можете настроить вышеупомянутое, чтобы добавить дополнительные ограничения на домен и т. Д.

Answer 2

Ответ зависит от того, что дорого. Случай, который может быть интересен, это когда f стоит дорого.

Что вы, возможно, захотите сделать, это посмотреть на pareto-optimity . Предположим, у вас есть две точки

(1, 2)    and    (3, 4)

Тогда вы знаете, что последняя точка будет лучшим решением, если f является неубывающей функцией. Однако, конечно, если у вас есть очки,

(1, 2)    and    (2, 1)

тогда ты не можешь знать. Таким образом, одним из решений было бы установить оптимальную по Парето границу точек, которую допускает предикат g , и затем оценить их, хотя f .