著者

渡辺 扇之介 渡邊 芳英 Sennosuke Watanabe Yoshihide Watanabe

出版者

同志社大学理工学研究所

雑誌

同志社大学理工学研究報告 = The Science and Engineering Review of Doshisha University (ISSN:00368172)

巻号頁・発行日

vol.54, no.2, pp.166-170, 2013-07-31

---

組合せ最適化問題の多くは,線形計画問題として定式化することができるため,それぞれの問題に合った組合せ論的アルゴリズムだけでなく,線形計画問題におけるアルゴリズムを使っても解くことが出来る.本論文で取り上げる最適化問題は,フローネットワークにおける最適化問題の代表例である最短路問題と最長路問題である.最短路問題とは重みが最小となる道を求める問題で,最長路問題とはその逆に,重みが最大となる道を求める問題である.本研究の目的は,最短路問題と最長路問題の線形計画問題としての定式化と,最長路問題を解く組合せ論的アルゴリズムを見つけることである.本論文では,最短路問題の線形計画問題としての定式化は与えるが,最長路問題については,線形計画問題としてではない定式化を与えるにとどまる.最長路問題については,組合せ論的アルゴリズムを与える.