找到满足不平等约束的{x，y}的离散对

Question

我有一些关于 {x,y}, ，满足以下方程式：

x>=0
y>=0
f(x,y)=x^2+y^2>=100
g(x,y)=x^2+y^2<=200

注意 x 和 y 必须是整数。

从图形上可以说明如下，蓝色区域是满足上述不平等的区域：

现在的问题是，MATLAB中是否有任何功能可以找到每对可允许的一对 {x,y}？如果有算法要做这种事情，我也很高兴听到它。

当然，我们始终可以使用一种方法是蛮力方法，我们在其中测试了所有可能的组合 {x,y} 查看是否满足不平等现象。但这是最后的手段，因为它很耗时。我正在寻找一种可以执行此操作的巧妙算法，或者在最好的情况下，我可以直接使用的现有库。

这 x^2+y^2>=100 and x^2+y^2<=200 只是例子；事实上 f 和 g 可以是任何程度的任何多项式函数。

编辑：C＃代码也受到欢迎。

Answer 1

通常，除枚举搜索以外的任何方法，即使有有限数量的解决方案，这肯定是不可能的。 （也许我应该说不是很重要。

编辑：OP询问了如何继续进行搜索。

考虑问题

x^3 + y^3 >= 1e12
x^4 + y^4 <= 1e16

x >= 0, y >= 0

解决该系统的所有整数解决方案。请注意，以任何形式的整数编程都不足够，因为请求所有整数解决方案。

Meshgrid的使用将迫使我们查看域中的点（0：10000）x（0：10000）。因此，这将迫使我们采样一组1E8点，测试每个点以查看它们是否满足约束。

一个简单的循环可能比这更有效，尽管它仍然需要一些努力。

% Note that I will store these in a cell array,
% since I cannot preallocate the results.
tic
xmax = 10000;
xy = cell(1,xmax);
for x = 0:xmax
  % solve for y, given x. This requires us to
  % solve for those values of y such that
  %   y^3 >= 1e12 - x.^3
  %   y^4 <= 1e16 - x.^4
  % These are simple expressions to solve for.
  y = ceil((1e12 - x.^3).^(1/3)):floor((1e16 - x.^4).^0.25);
  n = numel(y);
  if n > 0
    xy{x+1} = [repmat(x,1,n);y];
  end
end
% flatten the cell array
xy = cell2mat(xy);
toc

所需的时间是...

Elapsed time is 0.600419 seconds.

在我们可能已经测试的100020001组合中，我们找到了多少个解决方案？

size(xy)
ans =
           2     4371264

诚然，详尽的搜索更简单地编写。

tic
[x,y] = meshgrid(0:10000);
k = (x.^3 + y.^3 >= 1e12) & (x.^4 + y.^4 <= 1e16);
xy = [x(k),y(k)];
toc

我在64位机器上运行了这件，并带有8次RAM。但是即便如此，测试本身就是CPU猪。

Elapsed time is 50.182385 seconds.

请注意，浮点注意事项有时会导致不同数量的点，具体取决于如何完成计算。

最后，如果您的约束方程式更为复杂，则可能需要在y上的界限中使用词根，以帮助确定满足约束的位置。这里的好处是，它仍然适用于更复杂的多项式界限。