9

私は高頻度取引会社の面接を受けていました。彼らは私に次のアルゴリズムを求めましたO(n):

  • 空間内の与えられnた点
  • の平面の点を返すハッシュ関数が与えられるとO(1)、
  • 空間内で最も多くの点をカバーする最適な円を見つけます。

要件：

  • 円の中心には整数の座標が必要で、半径は になります3。
  • 円内の点は必ずしも整数座標を持つとは限りません

私はグーグルで検索し、いくつかの調査を行いました。O(n) アルゴリズム (プリンストン大学の Chazelle によるベスト サークル配置)がありますが、それを理解してまとめて 10 分で説明するには、私のレベルを超えています。私はすでにアルゴリズムを知っO(n^2)ています。O(n^3)

O(n)アルゴリズムを見つけるのを手伝ってください。

4

2 に答える 2

8

整数座標の制約により、問題が大幅に簡素化されると思います。これは私には O(n) のように見えます:

-空間内のすべての整数点の辞書を作成し、エントリを 0 に設定します。

- 各データポイントについて、半径 3 以内にある整数ポイントを見つけ、辞書の対応するエントリに 1 を追加します。これを行う理由は、その特定のデータポイントが内側にある円の中心になることができるポイントのセットが、そのデータポイントの周りの同じ半径を持つ円の整数制限であるためです。検索は、長さ 6 の正方形上にあるすべてのポイントに対して実行できます (内接ハイパーキューブ内のこれらのポイントは確実に内部にあるため、すべてのポイントを明示的に評価する必要はありません)。

- ディクショナリの最大値に対応する整数点、つまりほとんどのデータポイントが円の内側にある中心を返します。

編集：一部のコードは説明よりも優れていると思います。これは numpy と matplotlib で動作する python です。読むのが難しすぎてはいけません:

# -*- coding: utf-8 -*-
"""
Created on Mon Mar 11 19:22:12 2013

@author: Zah
"""

from __future__ import division
import numpy as np
import numpy.random
import matplotlib.pyplot as plt
from collections import defaultdict
import timeit
def make_points(n):
    """Generates n random points"""
    return np.random.uniform(0,30,(n,2))

def find_centers(point, r):
    """Given 1 point, find all possible integer centers searching in a square 
    around that point. Note that this method can be imporved."""
    posx, posy = point
    centers = ((x,y) 
        for x in xrange(int(np.ceil(posx - r)), int(np.floor(posx + r)) + 1)
        for y in xrange(int(np.ceil(posy - r)), int(np.floor(posy + r)) + 1)        
        if (x-posx)**2 + (y-posy)**2 < r*r)
    return centers


def find_circle(n, r=3.):
    """Find the best center"""
    points = make_points(n)
    d = defaultdict(int)
    for point in points:
        for center in find_centers(point, r):
            d[center] += 1
    return max(d , key = lambda x: d[x]), points

def make_results():
    """Green circle is the best center. Red crosses are posible centers for some
    random point as an example"""
    r = 3
    center, points = find_circle(100)
    xv,yv = points.transpose()
    fig = plt.figure()
    ax = fig.add_subplot(111)
    ax.set_aspect(1)
    ax.scatter(xv,yv)
    ax.add_artist(plt.Circle(center, r, facecolor = 'g', alpha = .5, zorder = 0))
    centersx, centersy  = np.array(list(find_centers(points[0], r))).transpose()
    plt.scatter(centersx, centersy,c = 'r', marker = '+')
    ax.add_artist(plt.Circle(points[0], r, facecolor = 'r', alpha = .25, zorder = 0))
    plt.show()

if __name__ == "__main__":
    make_results()

結果: 結果図 緑色の円が最適です。赤い円は、ランダムな点の中心がどのように選択されるかを示しています。

In [70]: %timeit find_circle(1000)
1 loops, best of 3: 1.76 s per loop

In [71]: %timeit find_circle(2000)
1 loops, best of 3: 3.51 s per loop

In [72]: %timeit find_circle(3000)
1 loops, best of 3: 5.3 s per loop

In [73]: %timeit find_circle(4000)
1 loops, best of 3: 7.03 s per loop

私の本当に遅いマシンで。行動は明らかに直線的です。

于 2013-03-09T01:32:02.180 に答える
4

(1)で述べたのとは別の考え方で、調べる円の数をO(n)

重要な発見: - 1 つのデータ ポイント p に対して、データ ポイント p を含むことができる半径 3 の限られた数の円のみが存在する必要があります。言い換えると、(1 つ目) 半径 3 の整数 (2 つ目) を中心点の座標として持ち、(3 つ目) 1 つの特定のデータ ポイントを含む円の数は O(1) です!

重要なアイデア: 半径 3 のすべての潜在的な円を反復処理し、円ごとに含まれるデータ ポイントの数を数えます。

アルゴリズム: - 円の中心点 (つまり、i と j の両方が整数である (i,j) の組み合わせ) を整数にマッピングする空のハッシュテーブル h を初期化します。

- For data point p_i in p_1 ... p_n // this loop takes O(n)
    - determine all the centerpoints c_1, c_2 ... c_k of circles which 
      can include p_i (in O(1))
    - for each centerpoint c_j in c_1... c_k // this loop takes O(1)
       - lookup if there is an entry hashtable i.e. test h[c_j]==nil
       - if h[c_j]==nil then h[c_j]:=1 end
       - else h[c_j] := h[c_j] +1 end
    - end for 
 end for

// この最後の最大値の決定には O(n) がかかります - h のすべての c_k を反復処理します - h_[c_max] が h の最大値であるキー c_max を決定します

どう思いますか？どんなコメントでも大歓迎です。

于 2013-03-10T03:35:55.760 に答える