Rectilinear Steiner arborescence問題の厳密解法における枝刈り規則について

摘要

平面上に原点を含むn個の点集合Sが与えられたとき，原点を根とし，原点から各点への経路が(L_1距離で）最短となるように水平線分，垂直線分で構成された根付木をRectilinear Steiner arborescence (RSA)と呼ぶ.また，総線分長が最小となるRSAを最小RSA(MRSA)と呼ぶ.Sが第一象限の点のみからなる場合に，MRSAを求める効率的な厳密解法RSA/DPがLeung and Congによって提案された.本論文では，最初にRSA/DPに二つの枝刈り規則を導入し高速化したアルゴリズムRSA/DP++を示す,計算機実験により，n=100程度の場合，RSA/DP++の生成する部分問題数がRSA/DPの約1/200以下になることを確認した.次に，RSA/DP++に更に二つの新しい枝刈り規則を加えたアルゴリズムRSA/DP+++を提案する.同様の計算機実験により，RSA/DP+++の生成部分問題数はRSA/DP++の約10分の1以下となること，及び2時間以内にn=400程度のMRSAを求めることが可能であることを確認した.