13

正の整数の 2 つの範囲とx: [1 ... n]、y: [1 ... m]0 から 1 までのランダムな実数 R が与えられた場合、x_i / y_j が R に最も近くなるように、x と y から要素のペア (i,j) を見つける必要があります。

このペアを見つける最も効率的な方法は何ですか?

4

7 に答える 7

15

ファリ列の使用

これは、これを解決するためのシンプルで数学的に美しいアルゴリズムです。二分探索を実行すると、各反復で次の数が中央値の式 (以下) によって与えられます。ファレイ数列の特性により、その数はその間隔内で最小の分母を持つ数です。したがって、このシーケンスは常に収束し、有効な解を「見逃す」ことはありません。

擬似コード:

input: m, n, R

a_num = 0, a_denom = 1
b_num = 1, b_denom = 1

repeat:
    -- interestingly c_num/c_denom is already in reduced form
    c_num = a_num + b_num
    c_denom = a_denom + b_denom

    -- if the numbers are too big, return the closest of a and b
    if c_num > n or c_denom > m then
        if R - a_num/a_denom < b_num/b_denom - R then
            return a_num, a_denom
        else
            return b_num, b_denom

    -- adjust the interval:
    if c_num/c_denom < R then
        a_num = c_num, a_denom = c_denom
    else
        b_num = c_num, b_denom = c_denom

goto repeat

平均的には高速ですが (私の推測ではO(log max(m,n)))、R が小さな分母を持つ分数に近い場合でも低速になる可能性があります。たとえば、1/1000000withの近似値を見つけるm = n = 1000000には、100 万回の反復が必要です。

于 2010-12-08T08:59:58.553 に答える
6

実数を有理数で近似する標準的な方法は、連分数級数を計算することです([1] を参照)。級数の一部を計算する際に分子と分母に制限を加えると、制限を破る前の最後の値は実数に非常に近い分数になります。

これは非常に良い近似を非常に高速に見つけますが、これが常に最も近い近似を見つけるかどうかはわかりません。と知られている

収束する [連分数展開の部分値] は、分母が収束の分母よりも小さい他の分数よりも連分数に近い

ただし、分母が大きい (まだ制限を下回っている) 近似が存在する可能性があり、これはより適切な近似ですが、収束しません。

[1] http://en.wikipedia.org/wiki/Continued_fraction

于 2010-12-08T09:00:04.683 に答える
1

R が0 <= R <= 1、整数x: [1 ... n]、整数 などの実数であるとしますy: [1 ... m]。はよりも大きくなり、 に最も近い近似値になることはできないため、とn <= m仮定されます。n > mx[n]/y[m]1R

したがって、分母 d を使用した R の最適な近似は、 または のいずれfloor(R*d) / dかになりますceil(R*d) / d。

O(m)問題は時間と空間で解決できますO(1)(Python の場合):

from __future__ import division
from random import random
from math import floor

def fractionize(R, n, d):
    error = abs(n/d - R)
    return (n, d, error)  # (numerator, denominator, absolute difference to R)

def better(a, b):
    return a if a[2] < b[2] else b

def approximate(R, n, m):
    best = (0, 1, R)
    for d in xrange(1, m+1):
        n1 = min(n, int(floor(R * d)))
        n2 = min(n, n1 + 1) # ceil(R*d)
        best = better(best, fractionize(R, n1, d))
        best = better(best, fractionize(R, n2, d))
    return best

if __name__ == '__main__': 
    def main():
        R = random()
        n = 30
        m = 100
        print R, approximate(R, n, m)
    main()
于 2010-12-08T10:42:58.630 に答える
0

プロリーは炎上しますが、可能な値のそれぞれについて小数の値をすべて計算するルックアップが最適かもしれません..したがって、小数部を介してインデックス付けされた2次元配列に、実際の等価物を含む配列要素でインデックス付けするだけです. X 部分と Y 部分が離散していると思いますので、これは有限であり、その逆ではありません....ああ、そうです、実際の検索部分....ええと....

于 2010-12-08T08:54:07.167 に答える
0

解決策: このO(1)スペースとO(m log(n))時間を実行できます。

検索するリストを作成する必要はありません。

疑似コードにはバグがあるかもしれませんが、アイデアは次のとおりです。

r: input number to search.
n,m: the ranges.

for (int i=1;i<=m;i++)
{
    minVal = min(Search(i,1,n,r), minVal);
}

//x and y are start and end of array:
decimal Search(i,x,y,r)
{
   if (i/x > r)
      return i/x - r;

   decimal middle1 = i/Cill((x+y)/2); 
   decimal middle2 = i/Roof((x+y)/2);

   decimal dist = min(middle1,middle2)

   decimal searchResult = 100000;

   if( middle > r)
     searchResult = Search (i, x, cill((x+y)/2),r)
  else
     searchResult = Search(i, roof((x+y)/2), y,r)

  if  (searchResult < dist)
     dist = searchResult;

  return dist;
}

読者への宿題としてインデックスを見つける。

説明: コードでアイデアが理解できると思いますが、for ループの 1 つをトレースしてみましょう: i=1 の場合:

次の数字で検索する必要があります: 1,1/2,1/3,1/4,....,1/n (1,1/cill(n/2)) と (1/ floor(n/2), 1/n) を検索し、同様のバイナリ検索を実行して最小のものを見つけます。

すべてのアイテムに対してこれを for ループで実行する必要があるため、m回実行されます。そして、O（log（n））かかるたびに。この関数は、いくつかの数学的規則によって改善できますが、複雑になるのでスキップします。

于 2010-12-08T08:58:52.473 に答える
0

完全に力ずくで検索するのではなく、ラウンドを使用して各要素に最適な一致を見つけ、最短のリストに対して線形検索を実行します。多分このようなもの：

best_x,best_y=(1,1)
for x in 1...n:
    y=max(1,min(m,round(x/R)))
    #optional optimization (if you have a fast gcd)
    if gcd(x,y)>1:
        continue

    if abs(R-x/y)<abs(R-bestx/besty):
        best_x,best_y=(x,y)
return (best_x,best_y)

gcd「最適化」がこれまでより高速になるかどうかはまったくわかりません...

于 2010-12-08T09:00:27.367 に答える
0

の分母Rが よりも大きい場合mは、Farey 法 (Fraction.limit_denominatorメソッドが実装する) を制限付きで使用して、 がelse letよりも小さいm分数を取得しa/bます。を使用して、終了するか、Farey メソッドを再実行します。bma/b = Rb <= ma <= nM = math.ceil(n/R)

def approx2(a, b, n, m):
    from math import ceil
    from fractions import Fraction
    R = Fraction(a, b)
    if R < Fraction(1, m):
        return 1, m
    r = R.limit_denominator(m)
    if r.numerator > n:
        M = ceil(n/R)
        r = R.limit_denominator(M)
    return r.numerator, r.denominator

>>> approx2(113, 205, 50, 200)
(43, 78)

の制限分母を使用して Farey メソッドを 1 回だけ実行することは可能かもしれませんが、それmin(ceil(n/R), m)についてはわかりません。

def approx(a, b, n, m):
    from math import ceil
    from fractions import Fraction
    R = Fraction(a, b)
    if R < Fraction(1, m):
        return 1, m
    r = R.limit_denominator(min(ceil(n/R), m))
    return r.numerator, r.denominator
于 2021-06-28T20:16:46.927 に答える