問題タブ [hungarian-algorithm]
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.
python - PySpark UDF のエッジ ケースで代入問題 (ハンガリー/linear_sum_assignment など) を解決する方法
割り当ての問題があり、SO コミュニティに、spark データフレーム (spark 3.1+ を使用) にこれを実装するための最良の方法を尋ねたいと思いました。最初に問題を説明してから、実装に移ります。
問題は次のとおりです。最大 N 個のタスクと最大 N 個の個人があります (この問題の場合、N=10)。各個人には、各タスクを実行するためのコストがかかります。最小コストは 0 ドル、最大コストは 10 ドルです。これは、いくつかの注意点があるハンガリーのアルゴリズムの問題のようなものです。
- 10 個未満のタスクおよび/または 10 個未満の個人が存在し、誰かにタスクが割り当てられなくても (またはタスクが個人に割り当てられなくても) よい場合があります。
- [より複雑なエッジケース/私が問題を抱えているもの] - リストには、フラグを持つタスクが 1 つある可能性があります
multiTask=True(複数存在することはできず、存在しないmultiTask可能性もあります)。ワーカーのコストが multiTask よりも低い場合、ワーカーxは自動的に multiTask に割り当てられ、multiTask は最適化中に取得されたと見なされます。- いくつかの例を紹介します。この例では、マルチ タスクに割り当てられる x 値は 1 です。
- 10 人中 1 人のワーカーの multiTask コストが 0.25 の場合、そのワーカーは multiTask に割り当てられ、残りの 9 人のワーカーは他の 9 つのタスクに割り当てられます。
- 10 人のうち 2 人のワーカーのコストが multiTask で 1 未満の場合、その両方が multiTask に割り当てられ、残りの 9 つのタスクのうち 8 つに他の 8 人のワーカーが割り当てられます。1 つのタスクは誰にも割り当てられません。
- 10 個のワーカーすべてのコストが multiTask で 1 未満の場合、それらすべてが multiTask に割り当てられます。これは非常にまれですが、可能です。
- multiTask のコストが 1 未満のワーカーがいない場合、コストを最小限に抑えるために、最適化中に multiTask は 1 人の担当者にのみ割り当てられます。
- いくつかの例を紹介します。この例では、マルチ タスクに割り当てられる x 値は 1 です。
Spark データフレームは次のようになります。注: 簡単にするために、N=3 (3 タスク、3 人) の例を示しています。
日付/場所のグループ化ごとにこの割り当ての問題を解決する必要があるため、日付/場所があることがわかります。これを解決するために、各ワーカーとタスクに ID に基づいて「インデックス」を割り当てdense_rank()、パンダ UDF を使用し、インデックスに基づいて N x N numpy 配列を設定し、linear_sum_assignment関数を呼び出すことで解決することを計画していました。ただし、マルチタスクでレイアウトした2番目のエッジケースのために、この計画がうまくいくとは思いません。
ご覧のとおり、このケースは multiTask をまったくカバーしていません。これを可能な限り最も効率的な方法で解決したいので、pandas udf や scipy に縛られません。
python - PyTorch でのトレーニング中に損失が減少しない
ニューラルネットトレーニングのためにPyTorchを使用しています。ハンガリーのアルゴリズムの代わりになるようにネットをトレーニングしようとしています。サイズが500x500のコストマトリックスの各行にニューラルネットがあります-それぞれ500個の要素を含む500個のリストを含むリスト。トレーニングのために、各マトリックスから 1 つの特定の行 (500 要素のリスト) を入力として渡し、割り当てのインデックスを出力として渡します。バッチサイズは 10 です。したがって、各バッチには 10 個のリストを持つリストが含まれ、それぞれに 500 個の要素が含まれ、各行に割り当てられたインデックスとして 10 個の整数を持つリストが含まれます。
このペアの最初の要素をネットの入力として渡し、2 番目の要素を損失計算に渡します
私が想像しているように、行のバッチを入力として渡し、この行インデックスに割り当てられたバッチを出力として渡す必要があります
しかし、最終的に損失は 6.2 あたりで止まり、それ以上減少することはありません。基本的な概念のいくつかを失っている可能性があります。事前に助けてくれてありがとう
python - Python を使用したハンガリー語アルゴリズムの制約
仕事と従業員のデータフレームがあり、各従業員が各仕事を終えることができる期間があります。ハンガリーのアルゴリズムを使用して、各ジョブを 1 人の従業員に割り当てたいのですが、各従業員は 1 つのジョブによってのみ割り当てることができます。
データは次のとおりです。
期待される結果は次のとおりです。
そして、これを印刷します：
誰でもこの問題について私を助けることができますか? 前もって感謝します！