<質疑応答> 浦田:最後の部分巡回をばらすところの計算量は?(スライド29)    どのように部分巡回のところを考えているの? 伊藤:今回の例でいうとすべての状況で3,4を通る。三つの条件に場合分けできる。緩和したとこを考える。 羽藤:分枝限定法ってどのような分野に適用できるの。       その組み合わせは無限にあるから、作ることは出来そう。子問題に分割することで何かを出来そう。 伊藤:僕の分野ではあまりなさそう。 若林:TSPのような問題の場合、僕の研究の場合車で運転する人が一筆書きで動きながら、車を玉突きで動かせないときどのような風になるかを考えられる。 羽藤:確率的な配送なども 今泉:分枝限定法は、施設配置問題に関しては出来そう 羽藤:なんでもできそうだけど。 柳沼:ハイパーパスなどの考え方でもできそう。 羽藤:一番のポイントはどこですか。 伊藤:部分巡回、先に緩和させてそこが答えじゃないとわかったら、そうじゃない条件を与えると計算できる 笠原:分枝限定法って一筆書きと一筆書きできないときって。    最終的にやりたいことは、一筆書き出来るかってことですか。 伊藤:最小のコストを探しながら、それが一筆書きならラッキー。    例題なら子供で終わりだが、終わらなければ孫問題が出来る。 柳沼:TSPは一筆書きで書いたものを求める。 笠原:絶対一筆書きにできないってことってあるのか 柳沼:絶対一筆書きにする。どんなコストになっても。 浦田:逆にTSPの課題は? 伊藤:前処理で計算される限界って書いてある。この場合。。。 柳沼:輸送問題のコストが高いってことでは。 笠原:擬多項式問題でカットするところ。。。最大フロー問題は、最小カット問題の考え方を用いているってことですか。 伊藤:そうですね。そもそも出流量を最大化させたい、その時はどこかでカットしたときどこかの経路は容量いっぱいという状況になっている。    何処かで適当に切れば、必ずそこの流量っているのは、その最初と同じになるってこと。カットした面はs,tに分かれていることが必要。 笠原:s,tっていうのをどうやって分けるのか 伊藤:余っているリンクを埋めていく。 羽藤:埋めているっていうのと、切るっていうのが。。切るっていう説明がないからわからないのかもね。 日下部:最小カットとは。 伊藤:そこに流せるキャパが最小ってこと 柳沼:ネックになるところを探すってこと。最小の場所を探すってことは底のを基準にして流量が決まる。