OR事典

筆順最適化 (地図描画の)

読み方：ひつじゅんさいてきか
【英】：optimal drawing (of map)

地図(例えば道路地図)は多数の線分からなる図形と見なせるが, 一筆書きできればプロッター等で無駄なく描ける. 一筆書きできないとき, ペンを上げて次に描くべき点まで移動して再びペンをおろして描くことになる. このペンを上げて空送りする操作は無駄な部分で, 高速に図を描く際は, できるだけ小さくしたい. これが筆順最適化問題であるが, この問題は, 平面最小重み完全マッチングになり, バケット法を基づいて高速に解かれている.