algorithm - 找到满足给定 f 的属性的最大 f 在其参数中是非递减的

Question

这个问题困扰了我一段时间。

假设您有一个函数 f x y，其中 x 和 y 是整数，并且您知道 f 在其参数中是严格非递减的，

即f (x+1) y >= f x y 且 f x (y+1) >= f x y。

在给定 x 和 y 有界的情况下，找到满足属性的最大 f x y 的最快方法是什么。

我在想这可能是鞍背搜索的变体，我想知道是否有此类问题的名称。

另外，更具体地说，我想知道如果您知道 f 是乘法运算符，是否有更快的方法来解决这个问题。

谢谢!

编辑:看下面的评论，属性可以是任何东西

给定一个属性 g(其中 g 接受一个值并返回一个 bool 值)我只是在寻找最大的 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 on hackage 来解决这个问题，但它很一般。您可以调整以上内容以在域等上添加额外的约束。