慶應義塾大学学術情報リポジトリ(KOARA)KeiO Associated Repository of Academic resources

慶應義塾大学学術情報リポジトリ(KOARA)

ホーム  »»  アイテム一覧  »»  アイテム詳細

アイテム詳細

アイテムタイプ Article
ID
KAKEN_24540140seika  
プレビュー
画像
thumbnail  
キャプション  
本文
KAKEN_24540140seika.pdf
Type :application/pdf Download
Size :172.6 KB
Last updated :Jan 6, 2017
Downloads : 77

Total downloads since Jan 6, 2017 : 77
 
タイトル
タイトル 経路の形を緩和した車両配送問題の多項式時間で解けるクラス  
カナ ケイロ ノ カタチ オ カンワシタ シャリョウ ハイソウ モンダイ ノ タコウシキ ジカン デ トケル クラス  
ローマ字 Keiro no katachi o kanwashita sharyo haiso mondai no takoshiki jikan de tokeru kurasu  
別タイトル
名前 Special cases of several routing problems and various relaxations of routes  
カナ  
ローマ字  
著者
名前 小田, 芳彰  
カナ オダ, ヨシアキ  
ローマ字 Oda, Yoshiaki  
所属 慶應義塾大学・理工学部・准教授  
所属(翻訳)  
役割 Research team head  
外部リンク 科研費研究者番号 : 90325043  

名前 渡辺, 守  
カナ ワタナベ, マモル  
ローマ字 Watanabe, Mamoru  
所属  
所属(翻訳)  
役割 Research team member  
外部リンク  
Publisher  
出版地
 
出版者
名前  
カナ  
ローマ字  
日付
出版年(from:yyyy) 2016  
出版年(to:yyyy)  
作成日(yyyy-mm-dd)  
更新日(yyyy-mm-dd)  
記録日(yyyy-mm-dd)  
形態
1 pdf  
上位タイトル
名前 科学研究費補助金研究成果報告書  
翻訳  
 
 
2015  
 
開始ページ  
終了ページ  
ISSN
 
ISBN
 
DOI
URI
 
JaLCDOI
NII論文ID
 
医中誌ID
 
その他ID
 
博士論文情報
学位授与番号  
学位授与年月日  
学位名  
学位授与機関  
抄録
巡回セールスマン問題とは与えられた複数の都市をすべて1回ずつ通り, 出発点に戻ってくるような最短経路を求める問題である。この問題はNP困難のクラスに属し, 都市数が増えたとき実用的な時間(多項式時間)で最短経路(最適解)を求めるのは不可能と予想される代表例になっている。この問題やその一般化した問題に対し, どのような条件をみたしていれば多項式時間で解けるのかについて数学の側面から研究を行った。この研究では, 最適解が持つ経路の形の特徴付けとその証明, および具体的に最適解を求めるアルゴリズムの両方が必要である。また, これに関連する円順列, 順列, 集合の均等分割に関する問題にもいくつかの成果を得た。
The Traveling Salesman Problem is the problem to find a shortest route which starts from some city, visits each city exactly once and comes back to the initial city. This problem is one of the most famous NP-hard problems. This shows that when the number of cities increases it becomes to be hard to find a shortest route (optimal solution) in a reasonable time (polynomial time). In this work, we studied those problems from mathematical points of view and found polynomial time solvable cases for the problem and its extended routing problems. In this research area, we need not only characterizations of optimal solutions for those cases together with proofs but also algorithms to compute a shortest routes among all solutions. Also, we worked several problems on balanced partitions for cyclic permutations, permutations and sets of finite integers which relate to the Traveling Salesman Problem.
 
目次

 
キーワード
組合せ論  

離散数学  

経路問題  

整数の分割  
NDC
 
注記
研究種目 : 基盤研究(C)(一般)
研究期間 : 2012~2015
課題番号 : 24540140
研究分野 : 数物系科学
 
言語
日本語  

英語  
資源タイプ
text  
ジャンル
Research Paper  
著者版フラグ
 
本文URI
 
アクセス条件

 
最終更新日
Dec 27, 2016 11:18:22  
作成日
Dec 27, 2016 11:18:22  
所有者
mediacenter
 
更新履歴
 
インデックス
/ Public / 科学研究費補助金研究成果報告書 / 2015年度 / 日本学術振興会
 
関連アイテム
 

ランキング

最も多く閲覧されたアイテム
1位 新自由主義に抗す... (371) 1st
2位 日本におけるスペ... (365)
3位 ロマン主義として... (339)
4位 歌舞伎における後... (309)
5位 『慈照院自歌合』... (293)

最も多くダウンロードされたアイテム
1位 Benchmark 2011 i... (1576) 1st
2位 日本におけるスペ... (1295)
3位 日本における赤痢... (384)
4位 『詩人玉屑』版本... (353)
5位 モスクワオリンピ... (287)

LINK

慶應義塾ホームページへ
慶應義塾大学メディアセンターデジタルコレクション
慶應義塾大学メディアセンター本部
慶應義塾研究者情報データベース