長方形のグリッド、つまり N ノードと 2N エッジの形式のグラフがあり、隣接するすべてのノードが接続されています。これは、2 色対応であることを意味するため、2 部構成のマッチングを行うことができます。
各 (無向) エッジには、-2、-1、0、1、または 2 のいずれかの重みが割り当てられています。他の値は使用できません。
このグラフで、マッチングの重みの合計を最大化するマッチングを見つけるにはどうすればよいでしょうか? 特定の言語を気にしないでください。
理想的には、二次時間で実行されるアルゴリズムを探しています - 最悪でも O(n^2 log n) かもしれません。
解決策を提案する前に、重み 2 のエッジ、次に重み 1 のエッジを使用して最大一致を試みました (重み 2 のエッジを超えることはありません)。私はこの実装で 98% のスコアを獲得しました (問題は情報オリンピックからのものです)。