Оптимизировать двухмерную поиск

Question

Предположит, мы имеем два положительных целочисленные переменные:

x = [1, W] 
y = [1, H] 

и функция:

F(x, y) 

Задача состоит в том, чтобы найти х и у, что дает максимум выходное значение функции (в пределах диапазона).

Часть функции F это, как известно, в область:

F(x, y) = (x * y) * T(x, y) 

Теперь другая функция Т (х, у) имеет некоторые интересные свойства:

T(x + c, y) <= T(x, y) 
T(x, y + c) <= T(x, y) 

Где c - любое положительное целое число больше нуля (косвенное это составляет T (x + c, y + d) true, где d имеет те же ограничения, что и c).

Нахождение рабочего раствора легко путем тестирования всех возможных х/Y комбинации, но сложность O (W * H).

Есть ли способ использовать описанные выше свойства для уменьшения сложности?

Что-то вроде бинарной эквивалентности поиска для 2D или такого?

Прогулка по границе в некотором роде?

У любого из вас яркие умы есть интересные идеи или указатели?

Пример вывода Т (х, у):

9 7 7 4 2 
8 7 6 4 2 
8 7 5 4 1 
6 5 3 3 0 
3 3 2 1 0 

В этом примере х = 4 и у = 3 дает наибольшее значение: 4 * 3 * T (4, 3) = 4 * 3 * 4 = .

Answer 1

Пусть R(x,y) функция, которая удовлетворяет

R(x,y) >= 1

и следующее условие Липшица: для всех (x,y) в [1,W]x[1,H],

• |R(x,y)-R(x+1,y)| <= 0.5 * 1/(W*H)^2

• |R(x,y+1)-R(x,y)| <= 0.5 * 1/(W*H)^2

Тогда это простое упражнение в исчислении, чтобы показать, что R(x,y)/(x*y) является убывающей функцией x и y.

Таким образом, мы можем задать проблемы с T(x,y) = R(x,y)/(x*y). Мы получаем задачу максимизации F(x,y) = R(x,y). Поскольку нет быстрого способа получить максимум непрерывной функции Липшица, ваша проблема не допускает решения лучше, чем исчерпывающий поиск.