パイプライン（ｐｉｐｅ ｌｉｎｅ） １つのセンターと幾つかのポイントがあり、 そのポイント間を結ぶ経路があるとき、 総距離を最小にするような経路を探す問題。 たとえば、 水道管・ガス管の配管、電線の設置 道路の舗装化、高速道路の計画、 新幹線の経路 など ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ 配管総距離最小ネット問題 ９か所のゴミ投入口と、１つの収集センターの 予定位置が図のように決定したとき、 配管総距離が最小となるような配管を定める。 １１ １ ５２ ２ ２５ ２３ ３ ２０ ５ ２９ １５ １０ ｾﾝﾀｰ ６ ２６ ２７ ３４ ４３ １３ １２ ２１ ５７ ８ ４ １８ ３３ ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ ７ ９ 考え方 ゴミ投入口のすべてを結び、 しかもループを描く経路がないようにして 収集センターへ収集させるネットを作り、 かつ、 配管総距離の最小となるようなものを探す。 ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ 接続順序を求める① ２点間を結ぶすべての距離のうち、最小のものを探し、 この間に配管することにする。 最小値 １１ １ ５２ ２ ２５ ２３ ３ ２０ ５ ２９ １５ １０ ｾﾝﾀｰ ６ ２６ ２７ ３４ ４３ １３ １２ ２１ ５７ ８ ４ １８ ３３ ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ ７ ９ 接続順序を求める② 最短距離で結ばれている投入口と結ばれて いるものの中から最小の距離にある投入 口を探し、そこに配管をする。 １１ １ ５２ ２ ２５ ２３ ３ ２０ ５ ２９ １５ １０ ｾﾝﾀｰ ６ ２６ ２７ ３４ ４３ １３ １２ ２１ ５７ ８ ４ １８ ３３ ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ ７ ９ 接続順序を求める③ すでに接続されている投入口と結ばれてい る投入口以外は、配管しない（すべての実 線を消す）。 １１ １ ２ ５ ２９ １５ ５７ ８ ３ ２０ ４ ２１ １０ ｾﾝﾀｰ ６ ２６ ２７ ３４ ４３ １３ １２ １８ ３３ ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ ７ ９ 接続順序を求める④ 残った経路について、手順①～③を繰り返す。 １１ １ ２ ５ ２９ １５ ５７ ８ ３ ２０ ４ ２１ １０ ｾﾝﾀｰ ６ ２６ ２７ ３４ ４３ １３ １２ １８ ３３ ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ ７ ９ 接続順序を求める⑤ 残った経路について、手順①～③を繰り返す。 １１ １ ２ ５ ２９ １５ ５７ ８ ３ ２０ ４ ２１ １０ ｾﾝﾀｰ ６ ２６ ２７ ３４ ４３ １３ １２ １８ ３３ ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ ７ ９ 接続順序を求める⑥ 残った経路について、手順①～③を繰り返す。 １１ １ ２ ５ ２９ １５ ５７ ８ ３ ２０ ４ ２１ １０ ｾﾝﾀｰ ６ ２６ ２７ ３４ ４３ １３ １２ １８ ３３ ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ ７ ９ 接続順序を求める⑦ 残った経路について、手順①～③を繰り返す。 １１ １ ２ ５ ２９ １５ ５７ ８ ３ ２０ ４ １０ ｾﾝﾀｰ ６ ２６ ２７ ３４ ４３ １３ １２ １８ ３３ ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ ７ ９ 接続順序を求める⑦ 残った経路について、手順①～③を繰り返す。 １１ １ ２ ５ ２９ １５ ５７ ８ ３ ２０ ４ １２ ６ ２６ ２７ ３４ ４３ １３ １０ ｾﾝﾀｰ １８ ７ ９ ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ 接続順序を求める⑧ 残った経路について、手順①～③を繰り返す。 １１ １ ２ ５ ２９ １５ ５７ ８ ３ ２０ ４ １２ ６ ２６ ２７ ３４ ４３ １３ １０ ｾﾝﾀｰ １８ ７ ９ ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ 接続順序を求める⑨ 残った経路について、手順①～③を繰り返す。 １１ １ ２ ５ １８ １５ ６ ８ ３ ２０ ４ １２ ３４ ４３ １３ １０ ｾﾝﾀｰ ２６ ２７ ７ ９ ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ 接続順序を求める 配管総距離は 11＋15＋20＋12＋27＋13＋26＋18＋34＝176 １１ １ ２ ５ １８ １５ ６ ８ ３ ２０ ４ １２ ３４ １３ １０ ｾﾝﾀｰ ２６ ２７ ７ ９ ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ 各投入口からセンターまでの距離 ①：11＋15＋12＝38 ②：15+12＝27 ④：12 ⑤：18＋26＋27＝71 ⑦：34＋26＋27＝87 ⑧：27 １１ １ ２ ③：20＋12＝32 ⑥：26＋27＝53 ⑨：13＋27＝40 ５ １８ １５ ６ ８ ３ ２０ ４ １２ ３４ １３ １０ ｾﾝﾀｰ ２６ ２７ ７ ９ ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ
© Copyright 2024 ExpyDoc
