5

に関していくつかの不等式が{x,y}あり、次の方程式を満たします。

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

xandyは整数でなければならないことに注意してください。

グラフでは次のように表すことができます。青い領域は、上記の不等式を満たす領域です。

代替テキスト

問題は、Matlab に許容可能なすべてのペアを見つける関数がある{x,y}かどうかです。この種のことを行うアルゴリズムがあれば、私もそれについて聞いてうれしいです.

もちろん、いつでも使用できるアプローチの 1 つは{x,y}、不等式が満たされるかどうかを確認するために、可能なすべての組み合わせをテストするブルート フォース アプローチです。しかし、これは時間がかかるため、最後の手段です。これを行う賢いアルゴリズムを探しています。または、最良の場合、すぐに使用できる既存のライブラリを探しています。

これらx^2+y^2>=100 and x^2+y^2<=200は単なる例です。実際fにgは、任意の次数の任意の多項式関数にすることができます。

編集: C# コードも歓迎されます。

4

1 に答える 1

4

これは、有限数の解がある場合でも、列挙型検索以外の方法では、多項式不等式の一般的なセットに対して一般的に行うことは確かに不可能です。(可能であれば、些細なことではないと言うべきでしょう。浮動小数点の問題を条件として、列挙型検索が機能します。) 関心のあるドメインは、高次の不等式に対して単純に接続される必要はないことに注意してください。

編集：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

これを 8 ギガの RAM を搭載した 64 ビット マシンで実行しました。とはいえ、テスト自体は CPU を大量に消費するものでした。

Elapsed time is 50.182385 seconds.

浮動小数点を考慮すると、計算方法によっては異なる数のポイントが検出される場合があることに注意してください。

最後に、制約方程式がより複雑な場合は、y の境界の式で根を使用して、制約が満たされている場所を特定する必要がある場合があります。ここでの良い点は、より複雑な多項式の範囲でも機能することです。

于 2010-09-25T13:51:40.580 に答える