トップ整数計画問題 > リング配列

リング配列

1.リング配列

配列末尾の次を先頭とするのはプログラムではよくある話である。代表的なのがリングバッファ[1]である。 リングバッファでは、一般に、サイズを N とすると、要素 n (n = 0, 1, 2, ... , N-1)の次の要素を (n + 1) % N とするものである。

このホームページでも、ハッシュ法ライフゲームなど多くのプログラムで、 配列の末尾の次は先頭であり、次の要素の配列添え字を (n+1)%N としている。 こうすると、0 の次は 1、1 の次は 2、... 、N-1 の次は 0 となる。 (N-1 + 1) % N = N % N = 0 である。

巡回セールスマン問題でも、経路末尾の次は先頭と考える。 経路 Tour[0], Tour[1], ... , Tour[N-1] があり、Tour[N-1] の次が Tour[0] とする。 ノード間の距離関数を Dist とすると、巡回路の総距離は次の TourDistance関数で表される。

TSPLIBでは、一般にノード座標は実数で表すが、ノード間距離は四捨五入で整数化することが多い。 ここでもその慣例に従った。

int Dist(int id1, int id2) {
    double xdif = Nd[id2].X - Nd[id1].X;
    double ydif = Nd[id2].Y - Nd[id1].Y;
    return (int)(sqrt(xdif*xdif + ydif*ydif) + 0.5);	// 四捨五入
}

int TourDistance(int N) {
    int sumdist = 0;
    for (int i = 0; i < N; i++) {
        sumdist += Dist(Tour[i], Tour[(i+1)%N]);
    }
    return sumdist;
}

参考文献

[1] リングバッファ