問題タブ [mathematical-optimization]

私の大学のディベート クラブでは、ディベート セッションを割り当てるためのアプリケーションを作成するように依頼されましたが、適切なデザインを考え出すのに苦労しています。Javaでやります。必要なものは次のとおりです。

BP ディベートについて知っておくべきこと: それぞれ 2 人のディベーターと 1 人のジャッジからなる 4 つのチームがあります。4 つのグループには、特定の役職 (gov1、gov2、op1、op2) が割り当てられています。チーム内の順番に意味はありません。

アプリケーションの目的は、出席している討論者を入力として取得し (たとえば、20 人がいる場合は 2 つの討論を行います)、各討論者の履歴に関してチームと役割に割り当てることです。

• 各討論者は、できるだけ多くの人と討論する (同じチームにいる) 必要があります。
• 各討論者は、異なる立場で均一に討論する必要があります。
• ディベートは公平であるべきです - 討論者は異なるレベルの経験を持っており、これは可能な限り均等であるべきです - つまり、2 人の非常に経験豊富なディベーターのチームと若いディベーターのチームであってはなりません。
• ユーザーが次のようなさまざまな方法で割り当てを制限するオプションが必要です。
  • 特定の立場であるかどうかにかかわらず、2 人が一緒に討論する必要があることを指定します。
  • パートナーに関係なく、1 人の討論者が特定の位置にいる必要があることを指定します。

誰かがこのアプリケーションのデザインのヒントを教えてくれたら、とても感謝しています! また、私は以前に GUI を実装したことがないので、それについてもいくつかの指針をいただければ幸いですが、現時点では大きな問題ではありません。

また、Debater 情報をファイルに保持するという問題もありますが、これも Java で実装したことはありません。それについてもいくつかのヒントが必要です。

都市建設ゲームを設計していて、問題が発生しました。

Sierra のCaesar IIIのゲーム メカニクスを想像してみてください。それぞれに 1 つの市場がある多くの都市地区があるとします。有向加重グラフで接続された距離にあるいくつかの穀倉地帯があります。違い: 人 (ここでは車) は交通渋滞を形成する単位です (ここではグラフの重みが続きます)。

注: Ceasar ゲーム シリーズでは、人々は食料を収穫していくつかの大きな穀倉に備蓄しましたが、多くの市場 (小さな店) は穀倉から食料を取り出して市民に届けました。

タスク: 各地区に食料をどこから調達すべきかを伝えると同時に、時間を最小限に抑え、都市の道路の混雑を最小限に抑えます。

マップの例

黄色の地区にはそれぞれ 7 個、7 個、4 個のリンゴが必要であるとします。青みがかった穀倉には、それに応じて 7 個と 11 個のリンゴがあります。

エッジの重みがそれらの長さに比例するとします。次に、解決策は、端に示されている灰色の数字のようなものになるはずです。たとえば、第 1 地区は第 1 穀倉から 4 個のリンゴを、第 2 穀倉からは 3 個のリンゴを取得しますが、最後の地区は第 2 穀倉からのみ 4 個のリンゴを取得します。

ここでは、最初に垂直道路が最大まで占有され、次に残りの労働者が斜めの経路に送られます。

質問

どの実用的で非常に高速なアルゴリズムを使用する必要がありますか? 輻輳ゲームについて説明している論文 ( Congestion Games: Optimization in Competitionなど) を見ていましたが、全体像をつかむことができませんでした。

Android で線形代数を計算するための優れたライブラリ (SVD、QR、LU、最小二乗法、逆数など) を知っている人はいますか?

Mean-Variance-Optimization (Markowitz) を実行したいのですが、これを行う php で書かれたものは見つかりませんでした。MVP には微分計算が必要です。

1. それはphpで行うことができますか?なぜ大学からのクラス/作品がないのですか?

2. Webアプリケーションの場合（パフォーマンスに関して）、重い計算を処理するには別の言語の方が適していますか?

これに関するヘルプ/回答をありがとう

購入したい商品のリストがあります。アイテムは、さまざまなショップとさまざまな価格で提供されています。ショップには個別の配送料がかかります。最小限の合計価格ですべてのアイテムを購入するための最適なショッピング戦略（およびそれをサポートするJavaライブラリ）を探しています。

例：

• Item1はShop1で$100、Shop2で$111で提供されます。
• Item2はShop1で$90、Shop2で$85で提供されます。
• Shop1の配送料1：注文総額が150ドル未満の場合は10ドル。それ以外の場合は$0
• Shop2の配送料：注文合計が$50未満の場合は$5。それ以外の場合は$0

• Shop1でItem1とItem2を購入した場合、合計費用は$ 100 + $ 90 + $ 0 =$190になります。
• Shop2でItem1とItem2を購入した場合、合計費用は$ 111 + $ 85 + $ 0 =$196です。
• Shop1でItem1を購入し、Shop2でItem2を購入した場合、合計コストは$ 100 + $ 10 + $ 85 + $ 0=195になります。

Shop1でItem1とItem2を注文すると、最低価格が表示されます：$ 190

これまでに試したこと

その前に別の質問をしたところ、制約プログラミングの分野にたどり着きました。クリームとチョコを見てみましたが、問題を解決するためのモデルの作り方がわかりませんでした。

私のアイデアは、これらの制約を定義することでした。

• 各価格「pxy」はドメイン（0、c）で定義されます。ここで、cはこのショップの商品の価格です。
• 1行の1つの価格のみがゼロ以外である必要があります
• 1つのショップで1つ以上の商品を購入し、価格の合計が制限を下回っている場合は、合計費用に送料を追加します。
• ショップの総費用は、ショップ内のすべてのアイテムの価格の合計です。
• 総費用は、すべてのショップの合計の合計です

目的は「総コスト」です。これを最小限に抑えたい。

クリームでは、条件付き送料の「ifthen」制約を表現できませんでした。

チョコにはこれらの制約がありますが、5つのアイテムと10のショップでさえ、プログラムは解決策を見つけることなく10分間実行されていました。

質問

この問題を制約プログラミングソルバーで解決できるようにするには、制約をどのように表現すればよいですか？

次のように定義されたシグモイド伝達関数を使用するJavaで記述されたニューラルネットワークがあります。

これは、ネットワークを使用したトレーニングおよび計算中に何度も呼び出されます。これをスピードアップする方法はありますか？遅いということではなく、頻繁に使用されるというだけなので、ここでの小さな最適化は全体的に大きな利益になります。

米国のコインの価値:

.01、.05、.10、.25

可能な限り少ないコインを使用して、.01 から .99 までのすべての値を一致させるために使用できる米国のコインの構成を決定するアルゴリズムは何ですか?

次のコードは、真夜中から数分単位の時間枠を取り、分/時間の配列を作成します。しかし、それは遅いです。そこにもっと良い提案はありますか？（いいえ、言語の変更はオプションではありません:-)）

配列には次のものが含まれているはずです。

（0,0）（1,0）（2,57）（3,53）（4,0）....。

よろしく

コンピューターは、100 * 55 などの 2 つの数値の乗算をどのように実行しますか。

私の推測では、コンピューターは掛け算を達成するために足し算を繰り返していたのです。もちろん、これは整数の場合にも当てはまります。ただし、浮動小数点数の場合は、他のロジックが必要です。

注：これはインタビューで尋ねられました。

純粋な興味から、プロセスの結果の後に数値が生成されるのではなく、プロセス自体が生成されているときに数値が表示されるように、PI を順次作成する方法に興味があります。この場合、数値はそれ自体で生成される可能性があり、以前に見た数値にガベージ コレクションを実装して、無限級数を作成することができます。結果は、一連の Pi に続く毎秒生成される数値です。

インターネットをふるいにかけたときに見つけたものは次のとおりです。

これは、コンピューターに適した人気のあるアルゴリズムである The Machin-like Algorithm です。