問題文:変数とペア
を与えます。各変数に 1 ～ の値を割り当てることで、変数を区別できます。各ペアには 2 つの変数が含まれており、2 つの変数の差の絶対値はです。差の上限を と定義します。nknppabs(p)U=max(Abs(p)|every p)
を最小化する割り当てを見つけますU。
Limit:
n<=100
k<=1000
各変数は、ペアのリストに少なくとも 2 回表示されます。
A problem instance:
Input
n=9, k=12
1 2 (meaning pair x1 x2)
1 3
1 4
1 5
2 3
2 6
3 5
3 7
3 8
3 9
6 9
8 9
Output:
1 2 5 4 3 6 7 8 9
(meaning x1=1,x2=2,x3=5,...)
説明:x1=1,x2=2,x3=3,... will を割り当てると、 U=6(3 9 が最大の絶対値を持つ) になります。出力割り当てはU=4、最小値 (変更されたペア:3 7 => 5 7, 3 8 => 5 8などで、3 5 は変更されません。この場合、abs(p)<=4すべてのペアに対して) を取得します。
重要なポイントがあります。最適な割り当てを達成するには、最大の絶対値を持つペアの変数を変更する必要があります。
これに基づいて、貪欲なアルゴリズムを考えました。
1)Assign every x to default assignment (x(i)=i)
2)Locate pairs that have largest abs and x(i)'s contained in them.
3)For every i,j: Calculate U. Swap value of x(i),x(j). Calculate U'. If U'<U, stop and repeat step 3. If U'>=U for every i,j, end and output the assignment.
ただし、次のような割り当てが必要な場合、この方法には大きな落とし穴があります。
x(a)<<x(b), x(b)<<x(c), x(c)<<x(a)
、次のように 2 つのステップでスワップする必要があります。x(a)<=>x(b)次に、最初のステップで abs が U よりも大きくなり、スワップが失敗x(b)<=>x(c)する可能性があります。
この問題を解決するための効率的なアルゴリズムはありますか?x(b)<<x(a)