ルパン四世
2006.12.05 23:32 パソコン甲子園 2006
パソコン甲子園2006、唯一どのチームにも解かれなかった問題です。参考記事。
この問題は「巡回セールスマン問題」に帰着できるので、ちょっと勉強すれば簡単に解けます。もちろん、問題のサイズである蔵の数が最高でも 15 個なので、力任せのアルゴリズムでは解くことができません。巡回セールスマン問題は、分岐限定法や遺伝的アルゴリズムなど、様々な方法で解くことができますが、問題のサイズが高々 20 くらいまでなら動的計画法で厳密解を求めることが可能です。
以下の解答プログラムでは、F[][] という配列を用いてます。
ここで、F[state][i] には、
状態 state で i 番目の蔵に至るまでにかかった時間を記録します。
ここで、state は「どの蔵がすでに破られたか」を表す数で、以下の表のように 0 ~ 2n - 1 の数をわりあてます。
例:蔵の数 n が4の場合
この F[][] を、state が 0 から 2n - 1 に向かって、動的計画法により計算していきます。
この問題は「巡回セールスマン問題」に帰着できるので、ちょっと勉強すれば簡単に解けます。もちろん、問題のサイズである蔵の数が最高でも 15 個なので、力任せのアルゴリズムでは解くことができません。巡回セールスマン問題は、分岐限定法や遺伝的アルゴリズムなど、様々な方法で解くことができますが、問題のサイズが高々 20 くらいまでなら動的計画法で厳密解を求めることが可能です。
以下の解答プログラムでは、F[][] という配列を用いてます。
ここで、F[state][i] には、
状態 state で i 番目の蔵に至るまでにかかった時間を記録します。
ここで、state は「どの蔵がすでに破られたか」を表す数で、以下の表のように 0 ~ 2n - 1 の数をわりあてます。
state | bit | 意味 |
0 | 0000 | どの蔵も破られていない |
1 | 0001 | 1 番目の蔵を破った状態 |
2 | 0010 | 2 番目の蔵を破った状態 |
3 | 0011 | 1, 2 番目の蔵を破った状態 |
4 | 0100 | 3 番目の蔵を破った状態 |
5 | 0101 | 1, 3 番目の蔵を破った状態 |
6 | 0110 | 2, 3 番目の蔵を破った状態 |
7 | 0111 | 1, 2, 3 番目の蔵を破った状態 |
8 | 1000 | 4 番目の蔵を破った状態 |
. | . | ... |
. | . | ... |
15 | 1111 | 全ての蔵を破った状態 |
この F[][] を、state が 0 から 2n - 1 に向かって、動的計画法により計算していきます。
#include<iostream> #define INFTY 1e+1000 #define MAX 15 #define SMAX 1 << MAX using namespace std; struct StoreHouse{ int id, dist, nbox; }; int nstore; // the number of storehouse StoreHouse stores[MAX]; double F[SMAX][MAX]; // cost table int W[SMAX]; // total wight in states pair<int, int> P[SMAX][MAX]; // for path generation double getCost( int source, int target, int state ){ return abs(stores[source].dist - stores[target].dist )/(2000.0/(70 + W[state])); } void compute(){ int smax = 1 << nstore; for ( int state = 1; state < smax; state++ ){ for ( int j = 0; j < nstore; j++ ){ F[state][j] = INFTY; P[state][j] = make_pair(-1, -1); } } for ( int j = 0; j < nstore; j++ ) F[1 << j][j] = 0; for ( int state = 1; state < smax; state++ ){ for ( int i = 0; i < nstore; i++ ){ if ( ! (( 1 << i ) & state ) ) continue; for ( int j = 0; j < nstore; j++ ){ if ( ( 1 << j ) & state ) continue; double cost = F[state][i] + getCost(i, j, state); if ( cost < F[state|(1 << j)][j] ){ F[state|(1 << j)][j] = cost; P[state|(1 << j)][j] = make_pair(state, i); } } } } int endpoint = 0; for ( int i = 1; i < nstore; i++ ){ if ( F[smax-1][i] < F[smax-1][endpoint] ) endpoint = i; } pair<int, int> pre = make_pair(smax-1, endpoint); int path[MAX]; for ( int i = 0; pre.first != -1; pre = P[pre.first][pre.second], i++ ){ path[i] = stores[pre.second].id; } for ( int i = 0; i < nstore; i++ ){ if ( i ) cout << " "; cout << path[nstore - i - 1]; } cout << endl; } void input(){ cin >> nstore; for ( int i = 0; i < nstore; i++ ){ cin >> stores[i].id >> stores[i].dist >> stores[i].nbox; } } void init(){ int limit = 1 << nstore; for ( int state = 1; state < limit; state++ ){ int sum = 0; for ( int i = 0; i < nstore; i++ ){ if ( state & (1 << i) ) sum += (stores[i].nbox * 20); } W[state] = sum; } } main(){ input(); init(); compute(); }
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |