問題タブ [approximation]

いくつかの単純な分析関数f（s、Г）で逆不完全ガンマ関数Г（s、x）をどのように近似できますか？つまり、x = f（s、Г）= 12 * log（123.45 *Г）+Г+ 123.4^sのように記述します。

（少なくともアイデアや参考資料が必要です。）

バウンティ

この質問は、いくつかの問題を引き起こします。報奨金は、全体的に対処する回答に送られます。

これが私が遊んできた問題です。

注私は、ユークリッド空間に基づかないソリューションに特に興味があります。

サイズ K の群集を形成するアクタのセットがあります。距離d(ActorA,ActorB)は任意の 2 つのアクタについて簡単に計算できます (「距離」のさまざまな定義に対してソリューションが機能するはずです)。数多くの確立されたアルゴリズムのいずれか。

この隣接セットは最初は正しいですが、アクタは常に移動しているため、各アクタの N 個の最近傍の展開リストを維持したいと考えています。私が興味を持っているのは、完全解よりも効率的な近似解です。

1. エラーが導入された後、ソリューションは正確に収束する必要があります。
2. エラーが大きくなりすぎた場合は、完全な再計算を実行しても問題ありませんが、これらのエラーの検出は安価です。

これまでのところ、友人の友人アルゴリズムを使用してきました。

これは、群集の動きが遅く、N が適切に大きい場合に、適切に機能します。小さな誤差の後に収束し、最初の基準を満たしますが、

• 大きなエラーを検出する良い方法がありません。
• エラーのサイズと頻度の定量的な説明はありませんが、
• 実際には収束しますが、常に収束することを証明することはできません。

これらの点について何かお手伝いできますか？

また、うまく機能する代替アプローチを知っていますか

• 群衆の動きが速いとき、
• 一部のアクターの動きが速い場合、
• N が小さい場合、
• ある場所では群衆がまばらで、別の場所では密集している場合、
• または特定の空間索引付けアルゴリズムを使用しますか?

私が現在取り組んでいる拡張機能は、友人の友人を一般化して、隣人の動きが速い場合に友人の友人の友人を取ることです。これはうまくスケーリングできず、エラーを定量化せずに適切なパラメーターを導き出すのは難しいと思います。

私はすべての提案を歓迎します！それは楽しい小さな問題です:-)

これまでの注目すべき提案

Fexvez: エージェントの速度に応じて、ランダムな余分な隣人をサンプリングします。サンプル サイズ。移動しようとしているエリアからサンプリングすることもおそらく役立つでしょう。

エージェントspeed*delta_timeが既知の最も遠い隣人までの距離を超えると、隣人を再サンプリングします。

最近傍グラフのスーパーセットであるDelaunay 三角形分割を維持します。1 つの最近傍のみを考慮します。

David Mount のANN ライブラリは、 移動体を処理していないようです。

float データ型が近似と見なされ、decimal データ型が正確と見なされる理由がわかりません。良い説明を探しています、ありがとう。

私は、いくつかの人気のあるpythonパッケージをベースとして使用して、グラフとネットワーク用のオープンソース近似アルゴリズムライブラリに取り組んでいます。主な目標は、グラフとネットワーク上のNP完全問題の最新の近似アルゴリズムを網羅することです。この理由は、1）これをカバーする優れた（最新の）統合パッケージを見たことがないこと、および2）NP困難最適化問題の近似アルゴリズムについて学習するための優れた教育ツールになることです。

このライブラリを構築する際に、私はユニットテストを使用して健全性チェックを行っています（適切な開発者が行うように）。ユニットテストは、その性質上、近似アルゴリズムが正しい解を返さない可能性があるため、多少注意が必要です。現在、私はいくつかの小さなインスタンスを手作業で解決し、返された結果がそれに一致することを確認していますが、これは望ましくなく、実装の意味でスケーラブルでもありません。

近似アルゴリズムをユニットテストするための最良の方法は何でしょうか？ランダムなインスタンスを生成し、返される結果がアルゴリズムによって保証された範囲よりも小さいことを確認しますか？これには誤検知があるように思われます（テストはその時点で幸運であり、すべてのインスタンスが制限を下回ることが保証されているわけではありません）。

同じ入力で同じまたは類似の出力を生成する関数（b）を受け取るために、遺伝的アルゴリズムで特定の関数（a）を近似するPythonのモジュールはありますか？なぜ概算ですか？関数（a）の動作は不明です。したがって、基本的にアルゴリズムが行うべきことは、function（a）およびmutating function（b）によって生成されたサンプル値からの偏差を最小化することです。何か案は？

例：

プロジェクトで、アドホック関数を使用し続けるよりも、ベクトルやその他の三角法のサポート クラスの構築を開始する方が理にかなっている点に到達しました。これには多くの C++ ライブラリがあると思いますが、使い慣れた速度と機能を犠牲にしたくありません。

具体的には、整数の角度を使用できるようにしたいと考えており、次のような近似によって得られる超高速を維持したいと考えています。

したがって、不必要に自分自身をロールバックする前に、使用する整数の幅を指定でき、上記のような高速な近似値を持つベクトルなどのテンプレート クラスを備えた C++ 用の非常に高速な固定小数点ライブラリはありますか? ?

直線シュタイナー最小木 (RSMT) の近似を求めるアルゴリズムは多数あります。その中には次のものがあります。

• 最小全域木を見つける一連のアルゴリズム
• RST-T（直線単幹シュタイナー木）
• BGA (一括貪欲アルゴリズム)
• BI1S (バッチ反復 1-Steiner ツリー)
• FLUTE (RSMT 構築およびワイヤ長推定のための高速ルックアップ テーブル ベースの手法)

RSMT の長さは、rectlinear spanning 最小ツリーの 3/2 倍にもなり得ることが示されました。他のアルゴリズムの限界を文献で見つけられませんでした。それらは存在しますか？

FLUTE は最も効率的なアルゴリズムのようですが、それが最悪のケースで上限があるかどうかはわかりません。見つかりましたか？

3/2 未満に制限されたアルゴリズムはありますか?

here is what I want to do (preferably with Matlab):

Basically I have several traces of cars driving on an intersection. Each one is noisy, so I want to take the mean over all measurements to get a better approximation of the real route. In other words, I am looking for a way to approximate the Curve, which has the smallest distence to all of the meassured traces (in a least-square sense).

At the first glance, this is quite similar what can be achieved with spap2 of the CurveFitting Toolbox (good example in section Least-Squares Approximation here). But this algorithm has some major drawback: It assumes a function (with exactly one y(x) for every x), but what I want is a curve in 2d (which may have several y(x) for one x). This leads to problems when cars turn right or left with more then 90 degrees. Futhermore it takes the vertical offsets and not the perpendicular offsets (according to the definition on wolfram).

Has anybody an idea how to solve this problem? I thought of using a B-Spline and change the number of knots and the degree until I reached a certain fitting quality, but I can't find a way to solve this problem analytically or with the functions provided by the CurveFitting Toolbox. Is there a way to solve this without numerical optimization?

そこで、超幾何分布計算機（確率と統計）を作成することにしました。問題は、出力が常に0から1の間にあることです。したがって、Pythonは、出力値に応じて0または1に切り捨てます。

これが私のコードです

10進モジュールをインポートしようとしましたが、正しく使用しているかどうか、またはそれが目的であるかどうかさえわかりません。どんな助けでも素晴らしいでしょう！

編集：例として、N = 15、n = 6、r = 5、およびk = 3に設定すると、答えは0に丸められます。代わりに、適切な答えを出力したいと思います：.2397802398。ありがとう！

動的計画法を使用して関数 F(x,y) を計算しようとしています。機能的に:

F(X,Y) = a1 F(X-1,Y)+ a2 F(X-2,Y) ... + ak F(Xk,Y) + b1 F(X,Y-1)+ b2 F (X,Y-2) ... + bk F(X,Yk)

ここで、k は小さい数です (k=10)。

問題は、X=1,000,000、Y=1,000,000 です。したがって、x=1..1000000 と y=1..1000000 の間のすべての値に対して F(x,y) を計算することは不可能です。多数の入力に対して F(x,y) の計算を回避し、F(X,Y) の正確な推定値を取得できる DP のおおよそのバージョンはありますか。

同様の例は、2 つの非常に長く類似した文字列 (例: 類似した DNA 配列) に対する文字列マッチング アルゴリズム (レーベンシュタイン距離) です。このような場合、対角スコアのみが重要であり、対角から遠いエントリは最終的な距離には寄与しません。対角外のエントリの計算を回避するにはどうすればよいですか?

PS: 境界ケース (x < k および y < k の場合) は無視してください。