問題タブ [approximation]

正の整数 [a0、a1、a2、...、an] の配列 A と正の数 K があります。次のような配列 A のサブセット U と V のすべての (またはほぼすべての) ペアを見つける必要があります。

1. U のすべての要素の合計が K 以下
2. V のすべての要素の合計が K 以下
3. U + V には、元の配列 A のすべての要素が含まれていない可能性があります
4. U のすべての要素は、最初の配列 A の V のすべての要素の前に配置する必要があります。たとえば、U = [a1, a3, a5] を選択すると、a6 からのみ配列 V の構築を開始できるとします。この場合、要素 a0、a2、a4 は使用できません。

O（N ^ 2 * K ^ 2）（NはAの要素の総数）であるDPソリューションを見つけることができました。N と K は小さい (< 100) ですが、それでも遅すぎます。

近似アルゴリズムまたは疑似多項式動的計画法アルゴリズムを探しています。ビン パッキングの問題は私のものと似ていますが、制約にどのように適用できるかわかりません...

お知らせ下さい。

編集: 各数値の上限は 50 です

したがって、アルファのベクトルが 1 つ、ベータのベクトルが 1 つあり、すべての推定値 (アルファの i から n およびベータの i から n) の合計が 60 になるときのシータを見つけようとしています。

math.exp(alpha[i] * (theta - beta[i])) / (1 + math.exp(alpha[i] * (theta - beta[i])

基本的に私がしたことは、theta = 0.0001 から開始し、これらすべての合計を計算して反復し、60 未満の場合は毎回 0.0001 を追加して続行し、60 を超えることを意味します。

この方法でシータの値を見つけました。問題は、Python を使用して 0.456 のシータを見つけるのに約 60 秒かかったということです。

このシータを見つけるためのより迅速なアプローチは何ですか (これを他のデータに適用したいため)?

最初にお読みください: 問題は、絶対値の括弧が実際のスコアを囲む必要があるということでした。現在の問題は、実際には十分に正確ではなく、0.000001 を無視し、許容範囲として 0.0001 を好むことです (55 に近づけるように要求すると、54.994397921372205 で停止します)。私は許容範囲を 0 の後に 1 が続くクレイジーな量に増やしましたが、たとえば 50 に近づくと、49.14 と推定されます!! ひどい！なぜこれが起こるのですか？

更新：それはある必要がありますfloat()

いくつかのベクトルに基づく関数に属するシータを見つけようとしています。このコードを R で実行して、これを文字通り R から Python に変換しようとしました。

grensscore が 50 に等しいときの Theta の値を概算したいと考えています。最初の値は theta = 0.5 で、R で繰り返します。R で約 11 回の繰り返しだけで目的に到達します。

悲しいことに、これは Python では機能せず、私はこれだけ分離しました。何らかの理由で、値は 0.5 を下回ることしかできず、0.5 を超えることはできません。これらの場所でプリントを使用すると#a、コード内のパーツが実行されていないにもかかわらず、パーツが実行されていることが#bわかります。これは、値が決して上がらないことを示しているため、0.4 のような値を見つけることはできません (0.5、0.25、0.37.5、0.4375 などになる必要がありますが、0.5、0.25、0.125 しか下がらないため)。そして遅かれ早かれ停止します）

#b が実行されていることがわかります。下げなければならないときに何度も別れますが、上がることはありません。私もそれらを切り替えて、順序効果があるかどうかを確認しましたが、そうではありません:それは単にそれが真であると評価されないだけです(私がそれを知っている場合でも) Rで働いていますか？

私はバイナリ形式での浮動小数点表現を十分に認識しているため、プログラミング言語で浮動小数点数を完全に表現しようとすると、数学的な「不可能」があることを知っています。ただし、プログラミング言語は、近似を処理する際に、よく知られた確立された規則に従うことを期待しています。

そうは言っても、私は（ここでもstackoverflowで）PHPのprintfがおそらく数値を「正しく切り捨て/概算」するための最良の方法であることを読みました。私に「完璧な」近似を与えるために。これは、「XXX を使用しないのはなぜですか、または YYY を使用しないのですか?」のような回答を避けるためです。

これを試して：

これは出力です：

1.500000 1.50
1.501000 1.50
1.502000 1.50
1.503000 1.50
1.504000 1.50
1.505000 1.50
1.506000 1.51
1.507000 1.51
10.508000
1.5.0915

簡単にわかるように、1.504 は (正しく) 1.50 として出力され、1.506 は (正しく) 1.51 として出力されます。しかし、なぜ 1.505 が 1.50 と印刷されるのでしょうか?! 1.50 ではなく、1.51 でなければなりません。

ありがとうございました...

私たちのシミュレーションでは、閉じた曲線 (赤い線) が移動できる基礎となる 2D グリッドがあります。グリッド セルは、中心の位置に基づいて、曲線の内側 (緑) または曲線の外側 (青) として色付けされ、圧力などの状態変数に対してそれぞれ異なる値を持つことができます。ドメイン内の任意のポイントについて、それが内側か外側かを正確に知ることができ、補間によりポイントの特定の状態を得ることができます (つまり、この情報はセル中心のデカルト グリッドを使用するよりも具体的です)。

曲線内の「ピーク」圧力の堅牢な測定値を取得しようとしています (ここで、ピークは、たとえば値の上位 1% の平均である可能性があります)。

現在、セル中心の値の最大値のみを取得していますが、画像でわかるように、曲線が移動するたびに非常に大きな分散が発生する可能性があります。さまざまなオプションを評価しようとしていますが、それらの有効性、特に使用できる統計手法があるかどうかについてはわかりません.

検討したオプション:

1. N*N*num_of_2D_cellsグリッド全体でポイントのランダム サンプルを取得する
2. 各 2D セルについて、N*Nポイントのランダム サンプルを取得します
3. 各 2d セルをN*Nより小さなセルに分割し、それらのセル中心の値を計算します

これらNのメソッドが大きくなると収束するはずですが、2D グリッドは 1e7 セルを超える可能性があります。そのため、計算時間により、サイズの上限が設定されNます。

この種の問題を扱った経験のある人、または扱っている一連の文献を知っている人はいますか?

http://en.wikipedia.org/wiki/Nearest_neighbour_algorithm

巡回セールスマンの問題を解決するために最近傍アルゴリズムを使用しています。非常に高速ですが、正確ではありません。私ができる2つの改善についてどこかで読みました。1 つ目は、1 つのランダム ポイントから開始する代わりに、各ノードから開始する最近傍アルゴリズムを実行します。(したがって、N 個のノードがある場合、最近傍が N 回実行されます) 次に、合計距離が最小のルートを比較して選択します。これははるかに正確であるように見えます。しかし、遅すぎます。

もう 1 つの方法は、開始ノードをランダムに選択する代わりに、特別なノードを選択することです。その後、最近傍を 1 回だけ実行して結果を取得します。これは上記の方法ほど正確ではありませんが、以前のようにアルゴリズムが 1 回だけ実行されるため、はるかに高速です。しかし残念ながら、その記事をどこで読んだのか、この開始ノードを選択する基準を思い出せませんでした。

各ノードから他のノードまでの合計距離を取得する必要があると思います。次に、最大値を持つノードを開始ノードとして選択する必要があります。（私の言葉では、これはグラフから「最も離れた」ノードを選択すると同時に、グラフの中心に近いノードを選択することを避けています）この方法で得られるルートは、最適な最短ルートにかなり近いはずです。

私は正しいと思いますか？

編集:ユークリッド距離を持つメトリック TSP を扱っています。

いくつかの重要な値によって特徴付けられるいくつかの要素があります。

キー値の降順で要素を検討します。したがって、キー値が 4、5、7、10、2、8、9、10、8.5、9 の 10 個の要素がある場合、要素をキー値で並べ替え、キー値が等しい要素をまとめて検討します。

そのため、キー値が等しい要素 (10 など) はまとめて考慮され、その後にキー値 9 を持つ要素が続きます。要素が考慮され、特定のフィットネス関数を通過すると、リストから削除され、考慮されなくなります。

ここで、キー値が等しいという制限を少し緩和し、キー値がほぼ等しい要素をまとめて考えます。したがって、ソートされた順序で 2 番目の要素が最初の要素の 10% 以内にあると言うとき、それらは一緒に考慮されます。

そのため、キー値が 10、10、9、9 の要素が一緒に考慮されるようになりました。そして、キー値 9 を持つ 1 つの要素がここで削除されない場合、8.5 で再度検討する必要があります。

上記のシナリオを実装する唯一の方法は、次のようなものです。

1. キー値の降順で要素を並べ替えます。
2. 順序の最初の要素について、許容偏差として 10% を見つけます。この偏差ウィンドウ内に収まる要素を見つけます。したがって、ここでは、このウィンドウで 10、10、9、9 を検討します。
3. いずれかの要素がフィットネス関数を通過する場合は、リストから削除します。
4. 次のウィンドウを形成し、サイクルを繰り返します。

ここが私の考えが行き詰まるところです。次のウィンドウの開始から開始を形成するにはどうすればよいですか? ソートされた値が 10、10、9、9、8.5、8 ... であり、10、10、9、9 が最初のウィンドウで考慮された場合、次のウィンドウは 9 で始まり、9、8 で構成される必要があります。 、5。

前のウィンドウの最後の値で次のウィンドウを開始するだけで常に十分ですか? いくつかの反例を試しましたが、どれも私の推測を無効にしませんでした。しかし、両方の 9 がフィットネス関数を通過し、リストから削除された場合、次のウィンドウを開始する値はどれでしょうか? 並べ替えられたリストで次に利用できるものは?

それで、私の質問は、

1. 前のウィンドウの最後の値 (および削除された場合は次の値) で次のウィンドウを開始することに関する推測は正しいですか?
2. プロセス全体のためのより良いアルゴリズムはありますか?

Heron の方法は、 √nのより適切な近似を表す一連の数値を生成します。シーケンスの最初の数字は任意の推測です。シーケンス内の他のすべての数値は、次の式を使用して前の数値prevから取得されます。

nとerrorheron()の 2 つの数値を入力として受け取る関数を作成することになっています。関数は、 √nの初期推定値 1.0で開始し、連続する近似間の差 (より正確には、差の絶対値) が最大でerrorになるまで、より良い近似を繰り返し生成する必要があります。

これは少し難しいですが、次の 4 つの変数を追跡する必要があります。

条件付きのwhile ループも必要です。

whileループの一般的なルールは次のとおりです。

だから、これは私がこれまでに得たものです。最初はwhileループの下に「if」ステートメントを組み込む方法がわからないため、それほど多くはありません。

誰かが正しい方向へのいくつかの指針を教えてもらえますか?

ありがとうございました