問題タブ [approximation]

プロジェクトに取り組んでいると、この問題に遭遇しました。ここでは、問題の実際の領域外の用語で言い換えます (花火と形状の口径について話すことはできると思いますが、理解がさらに複雑になります)。それを解決するための（おそらくおおよその）アルゴリズムを探しています。

さまざまなサイズのn 個のコンテナーと、さまざまなサイズの職業とさまざまな色の m個のオブジェクトがあります (オブジェクトは多色になる可能性があるため、オブジェクトの色は本当にセットです)。

私の目的は、コンテナーごとにさまざまな色が最小限に抑えられるように、すべてのオブジェクトをコンテナーに収めることです (それが可能であることは既にわかっています)。「色の種類が最小限に抑えられている」とは、コンテナごとの異なる色の数の合計が最小限であることを意味します。

例。サイズ 2 の 2 つのコンテナと、{red}、{red, green}、{blue}、{blue, green} の色を持つ 4 つのオブジェクトがあり、それぞれのサイズは 1 です。最適なソリューションは [{red} 、{赤、緑}]、[{青}、{青、緑}]、合計の種類は 2+2=4 です。悪い解決策は [{red}, {blue}], [{red, green}, {blue, green}] で、合計の種類は 2+3=5 です。

私の推測では、ナップザックの問題よりも難しいように聞こえるので、この問題は NP 困難であると思います。オブジェクトの値は負の値に変換され、さらに同じコンテナー内の他のオブジェクトに依存します。しかし、おおよその解決策を得るために問題に取り組む方法については、私には良い考えがありません。とにかくそれは大歓迎です。

私は「確率に関する 50 の挑戦的な問題」という本を読んでいました。この本には、確率に関する多くの頭の体操が詰まっています。私はそこにある問題の 1 つを解決できず、解決策も理解できませんでした。それで、私はより良い感じを得るためにコードを書いていました. 元の問題はこちら。

The Theater Row: 8 人の有能な独身男性と 7 人の美しいモデルが、たまたま劇場の同じ 15 席の列のシングル シートを購入しました。平均して、結婚適性があるカップルの隣り合った席のペアは何組ですか?

そして、これが私のコードで、100回のランダムサンプリングから隣接するペアの平均数を取得しています:

このコードは、ランダムな一連の 0 (女性を表す) と 1 (男性) を生成します。次に、0 または 1 が繰り返されないように、ランダム シーケンスを "縮小" します。たとえば、コードが 011100110010011 のランダム シーケンスを生成する場合 (これには 7 つの隣接するペアがあります)、シーケンスは 01010101 に縮小されます。縮小された形式では、隣接するペアの数を計算するには、「size- 1」。

これが私の質問です。

1. 質問への答え (本によると) は 7.47 ですが、コードからは平均で約 7 が得られます。不一致がどこで発生したかを誰かが見ていますか?

2. 私のコードは時々非常に非効率的です。ランダムなシーケンスを生成する方法が原因ですか? (ご覧のとおり、8 人の男性と 7 人の女性のランダムなシーケンスを生成するために、たまたま 8 人の男性 (または「1」) と 7 人の女性 (または「0」) になるまで、サイズ 15 のランダムなシーケンスを要求し続けます)このような制約がある場合、ランダムなシーケンスを生成するより良い方法はありますか?

プログラミングに関しては、私はそれほど熟練していません。コメントをいただければ幸いです。助けてくれてありがとう!!

大きくて負の実数を扱うときに、次のMatlabコードで指数関数をより正確に近似する方法を知っている人はいますか?

たとえば、x = 1 の場合、コードはうまく機能し、x = -100 の場合、3.7201e-44 に近づくはずのときに 8.7364e+31 という答えを返します。

コードは次のとおりです。

どんな支援も大歓迎です、乾杯。

編集：

わかりましたので、質問は次のとおりです。

このコードが近似する数学関数はどれですか? (指数関数と言います。) x = 1 のときはうまくいきますか? (はい。)残念ながら、x = -100 のときにこれを使用すると、答えは s = 8.7364e+31 になります。あなたの同僚は、プログラムにばかげたバグがあると信じており、あなたの助けを求めています。動作を注意深く説明し、より良い結果が得られる簡単な修正を行います。[上記のコードの変更を提案するか、それを使用する必要があります。簡単な修正が機能することも確認する必要があります。]

したがって、用語間に16桁（またはそれ以上）の桁数がある場合、問題が大きな数を取り囲み、精度が失われることをある程度理解していますが、解決策はわかりません。

ありがとう

編集：

だから最後に私はこれで行きました：

完全に正しいかどうかはわかりませんが、適切な近似が返されます。

exp(-100) = 3.720075976020836e-
044s = 3.722053303838800e-044

さらに分析した後 (そして残念ながら課題を提出した後)、反復回数を増やして項を増やすと、効率がさらに向上することに気付きました。実際、次の方法はさらに効率的でした。

これにより、次のことが得られます。

exp(-100) = 3.720075976020836e-044
秒 = 3.720075976020701e-044

注：旅行が開始した場所と同じ場所で終了しないという事実と、すべてのポイントを訪問している限り、すべてのポイントを複数回訪問できるという事実のため、これは実際にはTSPバリアントではありませんが、問題のより良い定義が不足しているため、私はそれを置きました。

それで..

n個の興味のあるポイントでハイキング旅行に行くとします。これらのポイントはすべてハイキングコースでつながっています。すべてのトレイルとその距離を示す地図があり、有向グラフが表示されます。

私の問題は、A地点から始まり、nの関心のあるすべての地点を訪れるツアーを概算し、開始地点以外の場所でツアーを終了する方法です。ツアーをできるだけ短くしたいと思います。

ハイキングの性質上、高地から低地への移動は他の方法よりも明らかに簡単なので、これは残念ながら対称的な問題ではないと考えました（または、非対称のグラフを対称のグラフに変換できますか？）。

また、aからbに移動する方が、aからcに移動する非常に長くて奇妙な道路を使用するよりも高速である可能性があるため、三角不等式が満たされない非メトリックグラフで機能するアルゴリズムである必要があると思います。直接。三角不等式がまだ成立するかどうかを検討しました。すべてのポイントを訪問する限り、各ポイントを訪問する回数に制限はないためです。つまり、aからcまでの2つの異なるパスの最短を常に選択するため、決して長くて奇妙な道をたたく。

私の問題はTSPよりも簡単だと思うので、これらのアルゴリズムはこの問題に適合しません。最小全域木を使用することを考えましたが、非メートル法の非対称有向グラフに適用できることを確信するのに苦労しています。

私が本当に望んでいるのは、n個のポイントすべてを通るほぼ最適なツアーを見つける近似アルゴリズムをどのように考え出すことができるかについてのいくつかの指針です。

グラフとして表示する必要のあるN個の測定値の配列がありますが、グラフの幅はMピクセルのみで、スクロールされるのはMピクセルのみです。

Mは一定ですが、Nは数十から数千の範囲になります。グラフを表示する必要があるたびに、Nが何であるかがわかりますが、N / Mは整数ではないため、何らかの方法で補正したい累積エラーがあります。

私はプレーンCで作業しており、数学ライブラリは使用できません。

編集2：データは比較的均一で、時々ピークがあります。補間中にこれらのピークを見逃したくありません。

編集3：私は、Mより大きくMより小さい任意のNに対して十分に機能するソリューションを探しています。

ありがとう。

目的関数は、その 1 次導関数と 2 次導関数と共に内挿範囲内で有限かつ連続的であることが保証され[a, b]、この範囲内に最小値が 1 つしかありません (最小値がない場合は単調です)。この関数は、補間範囲に狭いピークがなく、一般に放物線に近いy = a*x + b*x^2(ただし、正確には放物線ではない)。範囲内の任意の点で所定の相対精度で目的関数を近似する補間関数を構築するために、「最良の」新しいサンプリング点 (点aおよびから開始) を選択する反復アルゴリズム (および補間方法) を提案してください。b[a, b]（少なくとも合理的な確率で）。関数の計算は非常にコストがかかるため、関数の評価 (サンプリング ポイント) の数は最小限にする必要があります。同時に、アルゴリズムの複雑さは重要ではありません。

問題は次のとおりです。データの 1D 配列があり、最適な方法で特定の量の水平線 (たとえば、3 本の線) で近似する必要があります (そのため、要約エラーは最小限になります)。近似の方法は、可能な限り高速にする必要があります (したがって、すべての水平線を取り、データ セットを近似し、データ セットからその値を抽出し、残りの線のセットで残りを近似することはできません)。さて、この問題の解決策が最大サブアレイ問題の解決策にリンクされていることをわずかに感じることを除いて、私はそれを行う方法がわかりません。よろしければ、解決方法を教えていただけないでしょうか。

ARMA モデルのパラメーターを推定するために、MATLAB ドキュメントから取得した次のコードを使用しています。

y = sin([1:300]') + 0.5 * randn(300, 1);
y = iddata(y);
mb = ar(y, 4, 'burg');

この時点で、入力すると次のmbようになります。

離散時間 IDPOLY モデル:
A(q)y(t) = e(t)
A(q) = 1 - 0.2764 q^-1 + 0.2069 q^-2 + 0.4804 q^-3 + 0.1424 q^-4
推定データセット y の AR ('burg'/'now') を使用
損失関数 0.314965 および FPE 0.323364
サンプリング間隔: 1

mb取得した変数を使用して、これらの係数を持つサンプルを生成するにはどうすればよいですか?
mbベクトルに見えません。
特に、欠落しているデータをどのように処理できますか?

ランダムに分散された実験データの2つの異なるセットがあります。それぞれの値に何らかの関数を適用して、分布の1つを別の分布にできるだけ類似させる必要があります。関数の例：F（x）= x *（1+（x + p1）* p2、ここでp1とp2は任意のパラメーターです。可能かどうか、可能であれば、p1のどの値を使用するかを確認します。そしてp2、私は簡単なpythonスクリプトを書きました：

私は、考えられるすべての方法の中で、これが最も醜くて最も遅い方法であることを理解しています。残念ながら、私にはプログラミングのバックグラウンドがまったくなく、これが私の最初の謙虚な努力です。結果の分布の平均値が既知の定数であることを考えると、適切なp1-p2ペアの数は非常に限られていますが、ここでは単純なブルートフォースを使用します。p2をp1の関数として表現する方法があるはずだと思いますが、どうすればいいのか全くわかりません。多分あなたは私にいくつかの考えを投げることができますか？
私の悪い英語でごめんなさい...

容量の異なるビンと、指定されたサイズのオブジェクトがあります。目標は、これらのオブジェクトをビンに詰めることです。これまでは、ビンパッキング問題に似ています。しかし、ねじれは、各オブジェクトが別のオブジェクトと部分的にオーバーラップしていることです。したがって、オブジェクト1と2のサイズはs1とs2ですが、同じビンに入れると、埋められたスペースはs1+s2未満になります。オブジェクトの各ペアについてこの重複する値を知っていると仮定すると、この問題の元のビンパッキングのような近似アルゴリズムもありますか？