問題タブ [mathematical-optimization]

数理最適化（線形計画法、凸最適化、またはより一般的なタイプの問題）を実行するそのようなライブラリを知っている人はいますか？私はMATLABのようなものを探していますが、より大きな問題を処理する機能を備えています。独自の実装を作成する必要がありますか、それともそれらの商用製品（CPLEXなど）の1つを購入する必要がありますか？

NP完全問題とは？なぜそれがコンピュータ サイエンスの重要なトピックなのですか?

特定の領域のオブジェクトがハッチングを通過できるように、全体の線の長さが最短の長方形をハッチングするアルゴリズムを探しています。

たとえば、5x3 cm の長方形があり、幅 1 cm の平行線を使用してハッチングすると、ハッチを通過できる最大のオブジェクトは、1 cm の正方形になります。全体で 22 cm (つまり、4x3+2x5) のハッチ ラインを使用しました。そのため、1 平方センチメートルの領域を通過させるために、22cm のハッチ ラインを使用しました。

アルゴリズムは、現在の 22cm からハッチ ライン全体を最小化しながら、1 平方センチメートルを超える領域を通過させないパターンを見つける必要があります (オブジェクトは正方形または長方形である必要はなく、重要なのは全体の領域です)。

編集: nlucaroni のリードに従って、平面を等面積の領域に分割すると、少なくとも正六角形のグリッドの周囲長があると述べているハニカム予想を見つけました。これは私の質問に部分的に答えます。

私は現在、難しいソートの問題に直面しています。相互にソートする必要があるイベントのコレクション (比較ソート) と、リスト内の相対位置に対してソートする必要があります。

簡単に言えば、優先度 (整数)、期間 (秒)、およびイベントがリストに表示される最も早い発生時刻を持つイベントのリストがあります。優先度に基づいてイベントを並べ替える必要がありますが、最も早い発生時間より前にリストに表示されるイベントはありません。（うまくいけば）より明確にするための例を次に示します。

アイテム "b" は、リストの 6.0 秒まで開始できないため、最後に来る必要があります。したがって、アイテムは延期され、"c" は優先度が低くても "b" の前に移動します。（うまくいけば、上記で私の問題が説明されます。そうでない場合は、お知らせください。編集します。）

私の現在の考えは、挿入ソートを使用してソートプロセスを管理することです。他の一般的な並べ替えアルゴリズムの多くとは異なり、挿入並べ替えはリストの順序を一度に 1 つずつ順番に決定します。したがって、インデックスごとに、最も早い発生時間が満たされる次に優先度の低いイベントを見つけることができるはずです。

この「並べ替え」の問題に対する優れたソリューションを設計するのに役立つ、並べ替えアルゴリズムとデータ構造に関するリソースを見つけたいと思っています。私の本当の問題は実際にはこれよりも複雑です: 階層的な並べ替え、イベント間の可変バッファ、複数の一定でない時間の制約など、情報やアイデアが多ければ多いほど良いのです。速度とスペースは実際には問題ではありません。ソートの精度とコードの保守性が懸念されます。

編集：説明（コメントに基づく）

• イベントはその期間全体を消費します (つまり、イベントのオーバーラップは許可されません)。
• イベントは、earlylyTime 以降に発生する必要があり、earlylyTime より前に発生することはできません。
• 優先度の低いイベントが存在する場合、イベントは EarlyTime よりも遅く発生する可能性があります
• イベントは中断できません
• リストに収まるすべてのイベントの合計に最大期間があります。これは上には示されていません。(実際には、すべてのイベントの期間は、タイム リストの最大期間よりもはるかに長くなります。)
• ギャップがあってはなりません。(試して埋め戻す穴はありません。)

編集：答え

David Nehme が私が選択した回答を提供しましたが、彼の回答は本質的に挿入ソートであり、他の何人かが挿入ソート タイプの回答を提供したことを指摘したいと思います。これは、特殊な挿入ソートがおそらく進むべき道であることを私に確認させます。皆様、ご回答ありがとうございます。

要素の配列 ( ) と、 2 つの要素を取り、数値を返すarr関数 ( ) があります。f

配列の順列が必要です。これは、 inf(arr[i], arr[i+1])ごとにできるだけ少なくなります。（そしてループする必要があります。つまり、最小化する必要もあります）iarrf(arr[arr.length - 1], arr[0])

また、f距離のように機能するので、f(a,b) == f(b,a)

非効率すぎる場合は最適なソリューションは必要ありませんが、ほとんどリアルタイムで計算する必要があるため、適切に機能し、高速なソリューションが必要です (どのくらいの長さになるかはわかりませんarrが、そうなる可能性があると思います30前後くらい）

R用の最適化パッケージを知っている人はいますか（S +のNUOPTに似ています）？

AI 最適化ソフトウェア (Genetic Algorithms、Particle Swarm、Ant Colony など) に取り組むのが大好きです。残念ながら、私は解決すべき興味深い問題を使い果たしました。解決したい問題は何ですか？

私は、速度を大幅に向上させる必要があるmatlabアプリケーションに取り組んでいます。私は linprog を使用して、0 と 1 で囲まれた約 10,000 の変数を持つ 2 制約線形計画法を解いています。Linprog は私のアプリケーションでは非常に遅いです。速度を改善するために再定式化できる方法はありますか? または、便利な matlab 互換のシェアウェア (私は予算が限られています) を知っていますか?

私は、1つのひねりを加えた標準的な線形計画問題のように見える問題を解決しようとしています。

入力として、それぞれに重みがある「フレーズ」のセットがあります。総重量を最大化するために、テキスト内の各フレーズを繰り返す回数を選択する必要がありますが、最大文字長の制限があります。

これは、あるフレーズが別のフレーズのサブフレーズである可能性があるという事実を除けば、単純な線形計画問題のように見えます。したがって、たとえば、入力フレーズに「foo bar」と「foo」が含まれている場合、「foo bar」というフレーズを繰り返すと、「foo」というフレーズも繰り返されます。線形計画モデルでこれを処理する方法がわかりません。

私は導関数を計算するのにかなり高価な (一次) ODE のシステムを持っています。

ただし、導関数は、収束級数から計算され、境界がドロップされた項からの最大寄与に配置できるため、または kd ツリーに格納された事前計算された範囲情報を使用することにより、与えられた誤差範囲内でかなり安価に計算できます。 /octree ルックアップ テーブル。

残念ながら、これを利用できる一般的な ODE ソルバーを見つけることができませんでした。それらはすべて座標を提供するだけで、正確な結果が返されることを望んでいるようです。(注意してください、私は ODE の専門家ではありません。ルンゲ クッタ、Numerical Recipies の資料、LSODE、および Gnu Scientific Library のソルバーには精通しています)。

つまり、私が見たすべてのソルバーに対して、と の配列をderivs受け取り、 backの配列を返すコールバック関数を提供します。しかし、理想的には、コールバック、s、および許容可能なエラーの配列を提供し、微分範囲が必要な精度内にあることが保証されたものを探しています。(おそらく、同様に有用なバリエーションが多数あります)。txdx/dttxdx/dt_mindx/dt_max

この種のことを念頭に置いて設計されたソルバーへのポインタ、または問題への代替アプローチ (私がこのようなものを望んでいる最初の人だとは信じられません) は大歓迎です。