問題タブ [set-cover]
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.
java - サブセット内の未知の要素を含むセット カバー問題
問題は：
Tommy はサイズ N の正方形の家をセルに分割しており、セキュリティのために家の周りにセンサー検出デバイスを配置したいと考えています。各センサーは、置かれた位置から最大 K 歩数を検出できます。家の中には柱であるM個の位置があり、センサーはそれを介して検出できません。彼は最大 5 台のデバイスを配置する予定で、最小数のデバイスを使用して家全体をカバーする方法を考えています。
以下のようにサンプルを視覚化してみましょう (= は空セル、o は極セル)。
=====
うーん==
=====
=おお=
=====
デバイス (D) を位置 (3, 4) に配置すると、デバイス カバレッジは以下のように視覚化されます (各セル内の数字はデバイスからのインスタンスを示します)。
==323
ooo12
321D1
=ooo2
====3
私の質問は：
この問題を解決するための最適なソリューションはありますか?
Set Cover、Exact Coverの問題に関する記事を検索して読みましたが、上記の問題を解決するためにそれを実装する方法を見つけることができませんでした。
algorithm - 旅のルートをグループ化する方法（セットカバー問題）
この問題を解決する必要があります:
入力:
- 都市間のルートのリスト、すべてのルートは同じ出発地から始まります
- すべての都市のセット
出力:
- すべての都市を訪問できるパスのグループ。見つからない場合は、最小限のルートで都市の大部分をカバーするグループを返します。
例：
テストケース 1:
入力
ルートリスト:
1.
Newyork -> Washington -> Los Angeles -> Chicago
2.Newyork -> Houston -> Alaska
3.Newyork -> Dallas
4.Newyork -> Houston -> Washington -> Chicago -> Los Angeles -> Alaska
5.Newyork -> Alaska
6.Newyork -> Chicago
7.Newyork -> Los Angeles街：
Newyork, Washington, Los Angeles, Chicago, Alaska, Dallas, Houston
出力：
1. Newyork -> Houston -> Washington -> Chicago -> Los Angeles -> Alaska
2.Newyork -> Dallas
ルートが 2 つしかないため、指定されたすべての都市を訪れることができるため、これが最適なグループです。
テストケース 2:
入力
ルートリスト:
1.
Newyork -> Washington -> Los Angeles -> Chicago
2.Newyork -> Houston -> Alaska
3.Newyork -> Dallas
4.Newyork -> Alaska
5.Newyork -> Chicago
6.Newyork -> Los Angeles街：
Newyork, Washington, Los Angeles, Chicago, Alaska, Dallas, Houston
出力：
1. Newyork -> Washington -> Los Angeles -> Chicago
2. Newyork -> Houston -> Alaska
3.Newyork -> Dallas
3 つのルートですべての都市を訪問できるため、これは最適なグループです。
テストケース 3:
入力
ルートリスト:
2.
Newyork -> Houston -> Alaska
3.Newyork -> Dallas
4.Newyork -> Alaska
5.Newyork -> Chicago
6.Newyork -> Los Angeles街：
Newyork, Washington, Los Angeles, Chicago, Alaska, Dallas, Houston
出力：
1. Newyork -> Houston -> Alaska
2. Newyork -> Chicago
3. Newyork -> Dallas
4.Newyork -> Los Angeles
4 つのルートで 6/7 の都市を訪問できるため、これは最適なグループです ( を除くWashington)
実装
それで、私が使用できるアルゴリズムのアドバイスはありますか?
python - 粒子群最適化のための集合被覆問題の定式化方法
私はカバー問題を設定するのが初めてで、Pythonで単純なインスタンスを解決するための単純な貪欲なアルゴリズムを書くことができました。
これは問題なく動作しますが、粒子群最適化などの最適化アルゴリズムを問題に適用したいと考えていますが、問題をアルゴリズム (および他の発見的アルゴリズム) の目的関数として定式化することはできません。助けてください。
python - AttributeError: 'LpAffineExpression' オブジェクトに属性 'solve' がありません。Pullp でエラーが発生しました
問題を実装しようとしています基本的な問題osセットをpythonでカバーしていますが、パルプは常にエラーを出します: AttributeError: 'LpAffineExpression' object has no attribute 'solve'
これが私が解決しようとしているものです
そして、これは私のコードです: