© ＡＴＳＵＴＯ ＮＩＳＨＩＯ パイプライン（ｐｉｐ ｅ ｌｉｎｅ） １つのセンターと幾つかのポイントがあり、 そのポイント間を結ぶ経路があるとき、 総距離を最小にするような経路を探す問題。 たとえば、 水道管・ガス管の配管、電線の設置 道路の舗装化、高速道路の計画、 新幹線の経路 など.

Presentation on theme: "© ＡＴＳＵＴＯ ＮＩＳＨＩＯ パイプライン（ｐｉｐ ｅ ｌｉｎｅ） １つのセンターと幾つかのポイントがあり、 そのポイント間を結ぶ経路があるとき、 総距離を最小にするような経路を探す問題。 たとえば、 水道管・ガス管の配管、電線の設置 道路の舗装化、高速道路の計画、 新幹線の経路 など."— Presentation transcript:

1 © ＡＴＳＵＴＯ ＮＩＳＨＩＯ パイプライン（ｐｉｐ ｅ ｌｉｎｅ） １つのセンターと幾つかのポイントがあり、 そのポイント間を結ぶ経路があるとき、 総距離を最小にするような経路を探す問題。 たとえば、 水道管・ガス管の配管、電線の設置 道路の舗装化、高速道路の計画、 新幹線の経路 など

2 © ＡＴＳＵＴＯ ＮＩＳＨＩＯ 配管総距離最小ネット問題 ９か所のゴミ投入口と、１つの収集センター の 予定位置が図のように決定したとき、 配管総距離が最小となるような配管を定める。 １ １０１０ ８ ７ ６ ５ ４ ３ ２ ９ ｾﾝﾀｰ １８１８ ２０２０ ２１２１ ５２５２ １ ２３２３ １２１２ １５１５ ３ ２７２７ ２５２５ ３４３４ ２６２６ ４３４３ ５７５７ ２９２９ １３１３

3 © ＡＴＳＵＴＯ ＮＩＳＨＩＯ 考え方 ゴミ投入口のすべてを結び、 しかもループを描く経路がないようにして 収集センターへ収集させるネットを 作り、 かつ、 配管総距離の最小となるようなものを探す。

4 © ＡＴＳＵＴＯ ＮＩＳＨＩＯ 接続順序を求める① ２点間を結ぶすべての距離のうち、最小のものを 探し、この間に配管することにする。 １ １０１０ ８ ７ ６ ５ ４ ３ ２ ９ ｾﾝﾀｰ １８１８ ２０２０ ２１２１ ５２５２ １ ２３２３ １２１２ １５１５ ３ ２７２７ ２５２５ ３４３４ ２６２６ ４３４３ ５７５７ ２９２９ １３１３ 最小値

5 © ＡＴＳＵＴＯ ＮＩＳＨＩＯ 接続順序を求める② 最短距離で結ばれている投入口と結ばれ ているものの中から最小の距離にある 投入口を探し、そこに配管をする。 １ １０１０ ８ ７ ６ ５ ４ ３ ２ ９ ｾﾝﾀｰ １８１８ ２０２０ ２１２１ ５２５２ １ ２３２３ １２１２ １５１５ ３ ２７２７ ２５２５ ３４３４ ２６２６ ４３４３ ５７５７ ２９２９ １３１３

6 © ＡＴＳＵＴＯ ＮＩＳＨＩＯ 接続順序を求める③ すでに接続されている投入口と結ばれて いる投入口以外は、配管しない（すべ ての実線を消す）。 １ １０１０ ８ ７ ６ ５ ４ ３ ２ ９ ｾﾝﾀｰ １８１８ ２０２０ ２１２１ １ １２１２ １５１５ ３ ２７２７ ３４３４ ２６２６ ４３４３ ５７５７ ２９２９ １３１３

7 © ＡＴＳＵＴＯ ＮＩＳＨＩＯ 接続順序を求める④ 残った経路について、手順①～③を繰り返 す。 １ １０１０ ８ ７ ６ ５ ４ ３ ２ ９ ｾﾝﾀｰ １８１８ ２０２０ ２１２１ １ １２１２ １５１５ ３ ２７２７ ３４３４ ２６２６ ４３４３ ５７５７ ２９２９ １３１３

8 © ＡＴＳＵＴＯ ＮＩＳＨＩＯ 接続順序を求める⑤ 残った経路について、手順①～③を繰り返 す。 １ １０１０ ８ ７ ６ ５ ４ ３ ２ ９ ｾﾝﾀｰ １８１８ ２０２０ ２１２１ １ １２１２ １５１５ ３ ２７２７ ３４３４ ２６２６ ４３４３ ５７５７ ２９２９ １３１３

9 © ＡＴＳＵＴＯ ＮＩＳＨＩＯ 接続順序を求める⑥ 残った経路について、手順①～③を繰り返 す。 １ １０１０ ８ ７ ６ ５ ４ ３ ２ ９ ｾﾝﾀｰ １８１８ ２０２０ ２１２１ １ １２１２ １５１５ ３ ２７２７ ３４３４ ２６２６ ４３４３ ５７５７ ２９２９ １３１３

10 © ＡＴＳＵＴＯ ＮＩＳＨＩＯ 接続順序を求める⑦ 残った経路について、手順①～③を繰り返 す。 １ １０１０ ８ ７ ６ ５ ４ ３ ２ ９ ｾﾝﾀｰ １８１８ ２０２０ １ １２１２ １５１５ ３ ２７２７ ３４３４ ２６２６ ４３４３ ５７５７ ２９２９ １３１３

11 © ＡＴＳＵＴＯ ＮＩＳＨＩＯ 接続順序を求める⑦ 残った経路について、手順①～③を繰り返 す。 １ １０１０ ８ ７ ６ ５ ４ ３ ２ ９ ｾﾝﾀｰ １８１８ ２０２０ １ １２１２ １５１５ ２７２７ ３４３４ ２６２６ ４３４３ ５７５７ ２９２９ １３１３

12 © ＡＴＳＵＴＯ ＮＩＳＨＩＯ 接続順序を求める⑧ 残った経路について、手順①～③を繰り返 す。 １ １０１０ ８ ７ ６ ５ ４ ３ ２ ９ ｾﾝﾀｰ １８１８ ２０２０ １ １２１２ １５１５ ２７２７ ３４３４ ２６２６ ４３４３ ５７５７ ２９２９ １３１３

13 © ＡＴＳＵＴＯ ＮＩＳＨＩＯ 接続順序を求める⑨ 残った経路について、手順①～③を繰り返 す。 １ １０１０ ８ ７ ６ ５ ４ ３ ２ ９ ｾﾝﾀｰ １８１８ ２０２０ １ １２１２ １５１５ ２７２７ ３４３４ ２６２６ ４３４３ １３１３

14 © ＡＴＳＵＴＯ ＮＩＳＨＩＯ 接続順序を求める 配管総距離は 11 ＋ 15 ＋ 20 ＋ 12 ＋ 27 ＋ 13 ＋ 26 ＋ 18 ＋ 34 ＝ 176 １ １０１０ ８ ７ ６ ５ ４ ３ ２ ９ ｾﾝﾀｰ １８１８ ２０２０ １ １２１２ １５１５ ２７２７ ３４３４ ２６２６ １３１３

15 © ＡＴＳＵＴＯ ＮＩＳＨＩＯ 各投入口からセンターまでの距離 ①： 11 ＋ 15 ＋ 12 ＝ 38 ②： 15+12 ＝ 27 ③： 20 ＋ 12 ＝ 32 ④： 12 ⑤： 18 ＋ 26 ＋ 27 ＝ 71 ⑥： 26 ＋ 27 ＝ 53 ⑦： 34 ＋ 26 ＋ 27 ＝ 87 ⑧： 27 ⑨： 13 ＋ 27 ＝ 40 １ １０１０ ８ ７ ６ ５ ４ ３ ２ ９ ｾﾝﾀｰ １８１８ ２０２０ １ １２１２ １５１５ ２７２７ ３４３４ ２６２６ １３１３