c# - 查找满足不等式约束的离散对{x，y}

我有一些关于{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#代码。

最佳答案

对于一般的多项式不等式，即使有有限数量的解决方案，也无法通过枚举搜索以外的任何其他方法来实现，这对于一般的多项式不等式而言，通常肯定是不可能的。 (可能的话，也许我不应该说琐碎的事。枚举搜索将有效，但要考虑浮点问题。)请注意，对于高阶不等式，不必简单地关联关注域。

编辑:OP询问了如何进行搜索。

考虑问题

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

x >= 0, y >= 0

解决该系统的所有整数解。请注意，此处以ANY形式进行整数编程是不够的，因为需要所有整数解决方案。

在这里使用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

我在带有8 gig内存的64位计算机上运行了该程序。但是即使如此，测试本身还是CPU的负担。

Elapsed time is 50.182385 seconds.

注意，浮点数的考虑有时会导致找到不同数量的点，具体取决于计算的方式。

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

关于c# - 查找满足不等式约束的离散对{x，y}，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/3793510/