最小コストソートの考え方を理解できるようにまとめます。
最小コストソートを利用する問題
AIZU OINLINE JUDGEの最小コストソートに関する問題を例題として利用します。
問題
重さ wi(i=0,1,...,n−1) の n 個の荷物が１列に並んでいます。
これらの荷物をロボットアームを用いて並べ替えます。
１度の操作でロボットアームは荷物 i と荷物 j を持ち上げ、それらの位置を交換することができますが、
wi+wj のコストがかかります。
ロボットアームは何度でも操作することができます。
与えられた荷物の列を重さの昇順に整列するコストの総和の最小値を求めてください。
入力
１行目に整数 n が与えられます。２行目に n 個の整数 wi(i=0,1,2,...n−1) が空白区切りで与えられます。
出力
最小値を１行に出力してください。
入力例 1
5 1 5 3 4 2
出力例 1
7
最小コストソートの考え方
例として、{4,3,2,7,1,6,5}という数列の最小コストを考えます。
この数列において、各々の数値が最終的にどの位置に置かれればいいかということに絞って、 次のような入れ替えを行う。
まず先頭の4からを3番目のindexの7と交換して、
7,3,2,4,1,6,5
続いて、7を最大index6の5と交換して
5,3,2,4,1,6,7
続いて、5をindex4の1と交換して、
1,3,2,4,5,6,7
続いて、対象となる1はすでにソートの位置に置かれているので、ここで一連の流れが一旦終了することになります。
先頭から順にソートする作業を再開する、次のindex1の3に着目してindex2の2と交換する
1,2,3,4,5,6,7
2は適切な位置に置かれているので、ここで一連の流れが終了します。
つづいて、まだソート完了フラグが立っていない、index5の6に着目しますが、
6は正しい位置に置かれているので、これでソート終了ということになります。
ここで、行った処理の流れをまとめると、
①4 → 7 → 5 → 1 → 4 ②3 → 2 → 3 ③6 → 6
この①②③というサイクルにおいての最小コストについて考えます。
サイクルの長さが1のケース
③のようなケースでは入れ替える必要がないので、コストは0になります。
サイクルの長さが2のケース
②のようなサイクルの長さが2のケースでは、1回の交換でそれぞれの要素が最終位置に到達するので、
対象となる2つの要素の和がコストになります。
②のケースだと3 + 2 = 5がコストになる。
サイクルの長さが3以上のケース
①のケース{4 7 5 1}を考えます。
①のケースでは、以下のようにこのサイクルにおける最小コスト1を使って、それ以外の要素を移動することで、最小コストの19になります。
cost = 1 + 5 = 6 4 7 1 5
cost = 1 + 7 = 8 4 7 5 1
cost = 1 + 4 = 5 4 1 5 7
総コストはcost = 6 + 8 + 5 = 19となる
つまり、このケースでは、サイクルの中で最小値を使って、それ以外の要素を移動することが、
最適な方法となる。
最小コスト移動の総コストを考える
サイクルの中の要素を$w_i$サイクル内の要素の個数をnとすると、
コストの総和 + (最小値 * (個数 - 2))と一致するので、
$\displaystyle \sum w_i + (n - 2) * min(w_i)$
となります。
最小コスト移動を行なった場合の各サイクルの総移動コスト
サイクル①のコストは0サイクル②のコストは5、
サイクル③のコストは19なので、この数列の最小総移動コストは24ということになる。
が、この考え方には反例があります。
反例を考える
数列{2,1,8,10,7,9}を例に先ほどのアルゴリズムを適応してみます。
まず、index0の先頭2とindex1の1を交換します。
1 2 8 10 7 9
交換した1は交換する必要がないので、コスト3となりここでこのサイクルは終了
続いて、8 10 7 9についてソートします。
ここではサイクルの長さが4になるので、最小コストソートを利用します。
まず、7と9を交換(コスト16)
8 10 9 7
続いて、7と10を交換(コスト17)
8 7 9 10
最後に、7と8を交換(コスト15)
7 8 9 10
総コストは、3 + (16 + 17 + 15) = 51となります。
最小コストを他のサイクルから借りてくる方法
8 → 10 → 9 → 7 → 8のサイクルについて、7と1を交換して、
8 → 10 → 9 → 1 → 8のサイクルとして、コストの総和を考えると
28 + 2 * 1に1と7の2回分の交換を加えて、このサイクルのコストは46となり、
合計しても49となるので、先ほどのアルゴリズムよりもコストが低くなります。
つまり、サイクルの外から借りてきた要素を使って、移動した方がコストが小さくなる場合があります。
最小コストをサイクルの外から借りてきた場合の計算量を考える
サイクルの外の要素を最小値をxとすると、
$2 * (min(w_i) + x$だけコストが増加するが、
$(n - 1) * (min(w_i) - x)$だけコストが減ります。
この時のコストは
$\displaystyle \sum w_i + (n - 2) * min(w_i) + 2 * (min(w_i) + x - (n - 1) * (min(w_i) - x)$ $ = \displaystyle \sum w_i + min(w_i) + (n + 1) * x$
となる。
以上を考えると、各サイクルのコストは、要素全体の最小値を借りた場合と借りない場合を計算して、
コストが小さい方を採用する必要があります。
最小コスト問題の実装のポイント
上記の仕組みを利用して、プログラムを組む上でのポイントをまとめます。
ソートされた数値がどの位置に置かれるか保存する配列を持つ
ソートされた数列の各々の数値がどの位置に入るかを記録することで、
数値を交換する動作を計算なしで行うことができます。
例えば、以下のようなコードを考えます。
#define MAX 1000
// 最大入力値
#define VMAX 10001
int n;
//数列入力用
int A[MAX];
// 入力数列の中の最小値
int s;
// 入力したAをソートした配列
int B[MAX];
// 数値をINDEXとしてソートした数列がどの位置に置かれるのかを記録する
int T[VMAX];
以下のように、ソートされた数列の各々の数値が何番目に置かれるのかを記録します。
計数ソートの考え方と同じです。
for(int i = 0;i < n;++i){
B[i] = A[i];
}
// Bをソートする
sort(B,B + n);
for(int i = 0;i < n;++i){
// ソートされた並び順ごとに順番を入れておく
// ソートされた数列が1 3 5 7 9とするとT[1] = 0,T[3] = 1のように順番が入る
T[B[i]] = i;
}
配列T[]は交換するサイクルにおいて、以下のように使えます。
for(int i = 0;i < n;++i){
if(V[i]) continue;
// 初回は0が対象になる
int cursor = i;
// 1サイクルでかかるコスト
int S = 0;
// 1サイクルにおける最小コスト、取りうる最大数値にしておく
int m = VMAX;
// サイクルの長さ
int an = 0;
// 1サイクル処理
while(1){
// ソート済みフラグ
V[cursor] = true;
an++;
// 対象のコスト
int v = A[cursor];
// 最小コスト
m = min(m,v);
// 最小の値においての交換を加味しないサイクルの合計コスト
S += v;
// 対象が置かれるべき位置を割り出すT[v]に置かれるべき位置を入れる
cursor = T[v];
// サイクルが終了していたら、次に移る
if(V[cursor]) break;
}
// サイクル内の最小値を利用したコスト計算(Σwi + (n - 2) * min(wi)
int cost1 = S + (an - 2) * m;
// 数列の最小コストを借りた場合のコスト(Σwi + min(wi) + (n + 1) * min(全数列)
int cost2 = S + m + (an + 1) * s;
// 最小値のコストを外から借りた場合とコストを比較する
ans += min(cost1,cost2);
}
全体のソースコード
c++の全体のコードを載せます。
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 1000
// 最大入力値
#define VMAX 10001
int n;
//数列入力用
int A[MAX];
// 入力数列の中の最小値
int s;
// 入力したAをソートした配列
int B[MAX];
// 数値をINDEXとしてソートした数列がどの位置に置かれるのかを記録する
int T[VMAX];
int solve(){
// コスト
int ans = 0;
// 交換終了フラグ
bool V[MAX] = {};
for(int i = 0;i < n;++i){
B[i] = A[i];
}
// Bをソートする
sort(B,B + n);
for(int i = 0;i < n;++i){
// ソートされた並び順ごとに順番を入れておく
// ソートされた数列が1 3 5 7 9とするとT[1] = 0,T[3] = 1のように順番が入る
T[B[i]] = i;
}
for(int i = 0;i < n;++i){
if(V[i]) continue;
// 初回は0が対象になる
int cursor = i;
// 1サイクルでかかるコスト
int S = 0;
// 1サイクルにおける最小コスト、取りうる最大数値にしておく
int m = VMAX;
// サイクルの長さ
int an = 0;
// 1サイクル処理
while(1){
// ソート済みフラグ
V[cursor] = true;
an++;
// 対象のコスト
int v = A[cursor];
// 最小コスト
m = min(m,v);
// 最小の値においての交換を加味しないサイクルの合計コスト
S += v;
// 対象が置かれるべき位置を割り出すT[v]に置かれるべき位置を入れる
cursor = T[v];
// サイクルが終了していたら、次に移る
if(V[cursor]) break;
}
// サイクル内の最小値を利用したコスト計算(Σwi + (n - 2) * min(wi)
int cost1 = S + (an - 2) * m;
// 数列の最小コストを借りた場合のコスト(Σwi + min(wi) + (n + 1) * min(全数列)
int cost2 = S + m + (an + 1) * s;
// 最小値のコストを外から借りた場合とコストを比較する
ans += min(cost1,cost2);
}
return ans;
}
int main(){
cin >> n;
// 最小値
s = VMAX;
for(int i = 0;i < n;++i){
cin >> A[i];
s = min(s,A[i]);
}
int ans = solve();
cout << ans << endl;
}
0 件のコメント:
コメントを投稿