問題タブ [mathematical-optimization]

数式をプログラムに変換する作業をしています。この公式は、生鮮食品の最適価格設定ポリシーと呼ばれます。私はこれを記事で見ました、そしてそれはKarush-Kuhn-Tucker状態と呼ばれています。どういうわけか私はすべての数学のスキルを失い、その中で説明されている式を理解することができませんでした。最適な価格を実現するための解決策を考え出す方法は理解できますが、この記事に記載されている条件に対処できない可能性があるのではないかと心配しています。参考までに、ここにリンクを示します。誰かが私にこのKarush-Kuhn-Tuckerの状態を平易な英語で説明してくれれば、プログラミング言語で考えることができます。私はその言語に興味がありません。どの言語でも実装する準備ができています。

また、数学スタック交換で投稿した質問のリンクを提供します。

誰かがこのような状況に遭遇しましたか？この種の数式のプログラムによる解決策を考え出すにはどうすればよいですか？

同じためのWiki記事はここにあります

この種の式のためにすでに開発されたライブラリがある場合は、私に知らせてください。

特定の金額を構成するコインの最適な組み合わせを見つける必要があります。だから本質的に、私はそこに到達するために最小限のコインを使用したいと思います。

例えば：

通貨システムにコインがある場合：{13、8、1}、貪欲なソリューションは24に対して{13、8、1、1、1}として変更されますが、真の最適なソリューションは{8、8、8}です。 。

私はこれをJavascriptで書きたいと思っていますが、より多くの人に役立つと確信しているので、擬似コードは問題ありません。

私は NP 困難であると思われる組み合わせ最適化問題に取り組んでおり、遺伝的アルゴリズムは私たちのデータセットでうまく機能しています。私たちは研究グループであり、私たちの分野 (数学や CS ではなく) で結果を公開する予定です。原稿をレビューに送る前に、NP 困難な問題を調査したいと思います。

主な質問は 2 つあります。

1) この特定の最適化問題が研究されているかどうか知りたいです。私はライトを徹底的に検索しましたが、まったく同じものは見たことがありません.

2）問題が研究されていない場合は、還元可能性の証明を行うことに挑戦する可能性があり、還元のための優れたNP完全候補へのいくつかのポインターが必要です。

この問題は、サブシーケンス バリアントと 2 部グラフ問題の 2 つの方法で説明できます。

サブシーケンス フレーバーでは、順列を許可する「リラックスした」サブシーケンスを見つけ、最適化して順列数を最小限に抑えたいと考えています。例: (. = その他の文字)

クエリ: abc、ターゲット: ..babc、結果: abc (通常のサブシーケンス)

クエリ: abc、ターゲット: ..baca、結果: bac (1 つの順列を持つサブシーケンス)

二部定式化は、マッチング問題または線形代入問題であり、グラフはクエリ文字ノードとターゲット文字ノードに分割されます。エッジは、各クエリ文字からターゲット文字へのエッジが 1 つだけ存在するように、クエリ文字をターゲット文字に接続します。目的関数は、エッジ交差の数 (「交差数」とも呼ばれます) を最小化することです。これは、エッジの交差を最小限に抑えるためにノードの配置を並べ替える 2 部グラフ レイアウト アルゴリズムに似ていますが、私の問題では、両方のノードの順序が固定されている必要があります。

質問 1 または 2 に関する専門家からの意見はありますか?

前もって感謝します！

3D Max Studios には、3D モデルを 2 つにカットする機能 (関数の名前を思い出せませんでした、申し訳ありません) があることを思い出しました。たとえば、球体を作成し、それを真ん中で切り取り、2 つの半球体を残します。では、人体はどうでしょうか。武士が敵の腹を切り裂くと想像してください。敵のモデルは 2 つのモデルになります。1 つは頭から腹までの上部、もう 1 つは腹から足までの下部です。また、プレイヤーがカット モデルの内部を見るのを防ぐために、追加のポリゴンも両方のモデルに配置する必要があります。(できれば、このポリゴンに血液テクスチャを追加して、これが体内の血液であるという印象を与えてください) 説明が下手で申し訳ありませんが、私が言おうとしていることがわかりますか?

3D Max Studios では、上記のことができます。さて、3D プログラミングに関しては、このようなことを達成したい場合はどうすればよいでしょうか? 確かに、安価な方法の 1 つはカット モデルを事前に作成することですが、これは現実的ではありません。

切断角度に関してリアルタイムでモデルを 2 つに切断する方法を探しています。これは可能ですか？

Rで単純な移動平均交差戦略をチェックしています。2次元のパラメーター空間（短期移動平均の長さ、長期移動平均の長さ）で大規模なシミュレーションを実行する代わりに、粒子群を実装したいと思います。最適なパラメータ値を見つけるための最適化アルゴリズム。私はWebを閲覧していて、このアルゴリズムが非常に効果的であると読んでいました。さらに、アルゴリズムが機能する方法は私を魅了します...

このアルゴリズムをRに実装した経験のある人はいますか？使える便利なパッケージはありますか？

コメントありがとうございます。

マーティン

NumPyに連続微分可能関数の評価を含む配列があり、極小値を見つけたいとします。ノイズがないため、すべての隣接する値よりも値が低いすべての点が、極小値の基準を満たしています。

境界上の潜在的な最小値を無視して、2次元配列で機能する次のリスト内包表記があります。

ただし、これは非常に遅いです。また、これを任意の数の次元で機能させたいと思います。たとえば、任意の次元の配列内の点のすべての近傍を取得する簡単な方法はありますか？それとも、私はこの問題にまったく間違った方法で取り組んでいますか？numpy.gradient()代わりに使用する必要がありますか？

有向グラフで最大フローと最小カットを見つけるアルゴリズムの高速実装を備えた、信頼性が高く十分に文書化された Python ライブラリはありますか?

python-graph のpygraph.algorithms.minmax.maximum_flowは問題を解決しますが、非常に遅いです: 4000 ノードと 11000 エッジのような有向グラフで最大フローと最小カットを見つけるには 1 分以上かかります。少なくとも一桁速いものを探しています。

報奨金 : この質問に対して報奨金を提供して、この質問が行われた時点から状況が変わったかどうかを確認します。お勧めの図書館で個人的な経験がある場合は、ボーナス ポイントを獲得できます。

次の問題を解決する必要があります。おそらく、問題の解決方法に関するアイデアを教えてください。

がある：

• 8教室
• 16名の教師
• 201 人の学生
• 149名の親
• 241 の予約 (複数の子供がいる、または 1 人の子供が 2 人以上の教師によって教えられているため、ほとんどの保護者は複数の教師に会う必要があります)

• 2日。

• 毎日：

  • 7教室は1日20時間利用可能です。
  • 1教室1日10時間利用可能です。

• 各教師が 1 つの教室を占有します

• 各予定は 1 時間です

その他の制約: - 各保護者に対して、すべての予約は連続して行う必要があります (最大 1 時間の休止があります) - 各保護者は 1 日だけ学校を訪問する必要があります。- 各教師について、その日のすべての予定は連続していなければなりません (最大 2 時間の休止があります)。

すべての要件が満たされるまで、可能なすべてのバリエーションを計算する必要がないことは明らかです。何か案は？

私は最近、次の問題に遭遇しました。ベクトルのリスト（ここではタプルを意味します）がすべて整数のエントリを持つ場合、別の整数ベクトルがいつ入っているかを非常に迅速に判断するためのパッケージがありますか（言語はそれほど問題ではなく、速いほど良いので、Cを推測します）元のリストのスパン？整数に対してこの算術演算を行う必要があります (除算なし)。あると確信していますが、長い文献レビューを回避したかったのです。

オルタント型の領域が繰り返し切り出された整数格子上の大きな箱の重心を効率的に追跡することに興味があります。私は計算幾何学の文献を探し回っていましたが、関連する可能性のあるさまざまなデータ構造がありますが、ほとんどの議論は可視性の計算 (コンピューター グラフィックスの場合) または最近傍探索 (データ マイニングなどの場合) に関するものです。

論文 http://www.graphicsinterface.org/pre1996/92-NaylorSolidGeometry.pdf、つまり:

「バイナリ空間分割ツリー」によって幾何学的オブジェクトを表し、集合操作をサポートし、集合操作の後にオブジェクトの重心が再計算されるという興味深い言及 (詳細なし) があるシステムについて説明しています。おそらく私には盲点がありますが、ツリー マージ アルゴリズム中に質量の中心を効率的に更新する方法がすぐにはわかりません。また、Naylor のものを引用している論文で質量の中心の計算に関する議論を見つけられませんでした。ポインタはありますか？