問題タブ [operations-research]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
algorithm - 負のサイクルを含まない強く接続されたサブグラフを見つける
次の決定問題を解決するアルゴリズムはありますか?
G遷移行列で定義された強連結加重有向グラフ が与えられた場合、G負のサイクルを持たない強連結スパンサブグラフは存在するか?
の強連結スパニング サブグラフは、 と同じ頂点を共有するGの強連結サブグラフです。強く連結されたスパニングサブグラフの定義については、このペーパーを参照してください。この論文では、最小の強連結サブグラフ問題の近似を示しています。GG
この問題に対する素朴なアプローチは、フォード-ベルマンまたはフロイド-ウォーシャル アルゴリズムを使用してグラフの負のサイクルを見つけ、このサイクルからエッジを削除し、グラフがまだ強く接続されている間に繰り返すことです。しかし、この素朴なアプローチは時間の複雑性に欠けます。これは、Ford-bellman アルゴリズムを実行して強い接続性を何度も確認する可能性があるためです。さらに、このアルゴリズムがすべてのインスタンスで正しいかどうかを証明することはできません。
この決定問題が多項式時間で解決できるかどうか、またどのようなアルゴリズムで解決できるかを教えてくれる専門家をここで見つけたいと思っています。よろしくお願いします。
java - CPLEX Java API での目的関数のモデル化
Java を使用して Cplexで目的関数sum(i in Sites,j in Sites, k in Routings)(c[i][j] * x[i][j][k]*TruckKmCost)をモデル化しようとしています。
これは私の試みでしたが、addTerm メソッドは (double, IloNumVar) しか受け入れず、c[i][j] を IloNumVar に変換できません。これは、int 値を追加できるように int として必要なためです。
かなり簡単な解決策があるはずです。誰かが私を助けてくれるかもしれません。私は今少し困惑しています。
どうもありがとう！
algorithm - 有向グラフの最長サイクルの概算
有向グラフで最長のサイクル (サイクルとは、ノードの繰り返しがないサイクルを意味します) を見つけることは NP 困難な問題です。私の質問は次のとおりです。この問題に対するアルファ近似多項式アルゴリズムはありますか?