WEKO3
-
RootNode
アイテム
最短路問題と最長路問題
https://doi.org/10.14988/pa.2017.0000013294
https://doi.org/10.14988/pa.2017.000001329411756d90-0e12-4d9f-a24c-d4ae8b1f937b
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
023054020009.pdf (641.0 kB)
|
|
| Item type | 紀要論文 / Departmental Bulletin Paper(1) | |||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2013-10-24 | |||||||||||||||||
| タイトル | ||||||||||||||||||
| タイトル | 最短路問題と最長路問題 | |||||||||||||||||
| 言語 | ja | |||||||||||||||||
| タイトル | ||||||||||||||||||
| タイトル | サイタンロ モンダイ ト サイチョウロ モンダイ | |||||||||||||||||
| 言語 | ja-Kana | |||||||||||||||||
| タイトル | ||||||||||||||||||
| タイトル | The shortest path problem and the longest path problem | |||||||||||||||||
| 言語 | en | |||||||||||||||||
| 言語 | ||||||||||||||||||
| 言語 | jpn | |||||||||||||||||
| キーワード | ||||||||||||||||||
| 主題 | 最短路問題, 最長路問題, 線形計画問題 Shortest path problem, Longest path problem, Linear programming problem |
|||||||||||||||||
| 資源タイプ | ||||||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||||||||
| 資源タイプ | departmental bulletin paper | |||||||||||||||||
| ID登録 | ||||||||||||||||||
| ID登録 | 10.14988/pa.2017.0000013294 | |||||||||||||||||
| ID登録タイプ | JaLC | |||||||||||||||||
| アクセス権 | ||||||||||||||||||
| アクセス権 | open access | |||||||||||||||||
| アクセス権URI | http://purl.org/coar/access_right/c_abf2 | |||||||||||||||||
| 著者 |
渡辺, 扇之介
× 渡辺, 扇之介
WEKO
2484
× 渡邊, 芳英
WEKO
15621
|
|||||||||||||||||
| 著者所属 | ||||||||||||||||||
| 言語 | ja | |||||||||||||||||
| 値 | 渡辺, 扇之介 / Graduate School of Science and Engineering, Doshisha University | |||||||||||||||||
| 著者所属 | ||||||||||||||||||
| 言語 | ja | |||||||||||||||||
| 値 | 渡邊, 芳英 / 同志社大学理工学部数理システム学科 | |||||||||||||||||
| 著者所属（英） | ||||||||||||||||||
| 言語 | en | |||||||||||||||||
| 値 | Doshisha University | |||||||||||||||||
| 所属機関識別子種別 | ||||||||||||||||||
| 値 | kakenhi | |||||||||||||||||
| 所属機関識別子 | ||||||||||||||||||
| 値 | 34310 | |||||||||||||||||
| 抄録 | ||||||||||||||||||
| 内容記述タイプ | Abstract | |||||||||||||||||
| 内容記述 | 組合せ最適化問題の多くは,線形計画問題として定式化することができるため,それぞれの問題に合った組合せ論的アルゴリズムだけでなく,線形計画問題におけるアルゴリズムを使っても解くことが出来る.本論文で取り上げる最適化問題は,フローネットワークにおける最適化問題の代表例である最短路問題と最長路問題である.最短路問題とは重みが最小となる道を求める問題で,最長路問題とはその逆に,重みが最大となる道を求める問題である.本研究の目的は,最短路問題と最長路問題の線形計画問題としての定式化と,最長路問題を解く組合せ論的アルゴリズムを見つけることである.本論文では,最短路問題の線形計画問題としての定式化は与えるが,最長路問題については,線形計画問題としてではない定式化を与えるにとどまる.最長路問題については,組合せ論的アルゴリズムを与える. | |||||||||||||||||
| 言語 | ja | |||||||||||||||||
| 抄録 | ||||||||||||||||||
| 内容記述タイプ | Abstract | |||||||||||||||||
| 内容記述 | Many of combinatorial optimization problems can be formulated as the linear programming (LP) problem. So they can be solved not only by their proper combinatorial algorithms but also by the algorithm in the LP problem. In the present paper, we focus on the shortest path problem and the longest path problem which are typical examples of the combinatorial optimization problem on the flow-networks. The shortest path problem is the problem for finding the path whose weight is minimal. Conversely, the longest path problem is the problem for finding the path whose weight is maximal. The purpose of our study is to formulate the shortest path problem and the longest path problem as the LP problem, and to find an algorithm for solving the longest path problem. In the present paper, we give the formulation of the shortest path problem as the LP problem. However, the longest path problem is not easy to formulate as the LP problem. So we give one formulation of the longest path problem by using rank condition, and give a combinatorial algorithm for the longest path problem. | |||||||||||||||||
| 言語 | en | |||||||||||||||||
| 書誌情報 |
ja : 同志社大学理工学研究報告 en : The Science and Engineering Review of Doshisha University 巻 54, 号 2, p. 166-170, 発行日 2013-07-31 |
|||||||||||||||||
| 出版者 | ||||||||||||||||||
| 出版者 | 同志社大学理工学研究所 | |||||||||||||||||
| 言語 | ja | |||||||||||||||||
| 出版者（英） | ||||||||||||||||||
| 出版者 | Science and Engineering Research Institute of Doshisha University | |||||||||||||||||
| 言語 | en | |||||||||||||||||
| ISSN | ||||||||||||||||||
| 収録物識別子タイプ | PISSN | |||||||||||||||||
| 収録物識別子 | 00368172 | |||||||||||||||||
| 書誌レコードID | ||||||||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||||||||
| 収録物識別子 | AN00165868 | |||||||||||||||||
| 権利者情報 | ||||||||||||||||||
| 権利者識別子Scheme | AID | |||||||||||||||||
| 権利者識別子 | DA03974933 | |||||||||||||||||
| 権利者名 | 同志社大学理工学研究所 | |||||||||||||||||
| 言語 | ja | |||||||||||||||||
| 権利者名 | Science and Engineering Research Institute of Doshisha University | |||||||||||||||||
| 言語 | en | |||||||||||||||||
| 関連サイト | ||||||||||||||||||
| 関連タイプ | isFormatOf | |||||||||||||||||
| 識別子タイプ | URI | |||||||||||||||||
| 関連識別子 | https://doors.doshisha.ac.jp/opac/opac_link/bibid/SB00960326/?lang=0 | |||||||||||||||||
| 言語 | ja | |||||||||||||||||
| 関連名称 | 掲載刊行物所蔵情報へのリンク ／ Link to Contents | |||||||||||||||||
| フォーマット | ||||||||||||||||||
| 内容記述タイプ | Other | |||||||||||||||||
| 内容記述 | application/pdf | |||||||||||||||||
| 出版タイプ | ||||||||||||||||||
| 出版タイプ | VoR | |||||||||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||||||||||||||
| 日本十進分類法 | ||||||||||||||||||
| 主題Scheme | NDC | |||||||||||||||||
| 主題 | 417 | |||||||||||||||||
