Discovery Sagaサイレントキーワード俯瞰

離散数学 / 組合せ論 / 巡回セールスマン問題 / アルゴリズム / 計算量理論

巡回セールスマン問題はNP困難に属することで知られる有名な問題の1つである.本研究では,この問題とその一般化である車両配送問題および複数の倉庫を持つ車両配送問題について,特に「交差」の条件に着目して取り組み,これらの問題に対する多項式時間で解けるクラスに関していくつかの結果を得た.また,平面上のn点凸状配置に対するハミルトン閉路のフリップによる「交差」の解消に関する問題およびそれに類似する問題についても結果を得た.

組合せ論 / 離散数学 / アルゴリズム論 / 巡回セールスマン問題 / 計算量理論 / アルゴリズム / 国際研究者交流 / アメリカ : イギリス / 車両配送問題 / 多項式時間アルゴリズム / 国際情報交換 / ニュージーランド

巡回セールスマン問題は与えられた複数の都市をすべて1回ずつ通り、出発点に戻ってくるような最短経路を見つける問題である。この問題は板の穴あけなど実社会の問題にも直結する有名な最適化問題の1つである。しかし、都市数が増えるにつれ、コンピュータを利用しても計算にかる時間が指数的に増大する。そこで、問題がどのような条件をみたしていれば、実用的な時間で解が得られるかという研究がなされてきた。研究では、この効率よく解ける状況を考察するとともに、巡回セールスマン問題におけるこれらの条件を車両配送問題に適用した場合に、最適がもつ構造を明らかにした。

応用数学 / 組合せ論 / アルゴリズム / 巡回セールスマン問題 / 計算量理論 / 組合せ最適化 / 計算幾何学 / 離散数学

巡回セールスマン問題(以下、TSP)とは与えられた複数の都市をすべて1回ずつ通り、出発点に戻ってくるような最短経路を見つける問題である。この問題はNP困難のクラスに属し、都市数が増えたとき実用的な時間(多項式時間)で最短経路(最適解)を求めるのは不可能と予想される代表例になっている。そこで、実社会での応用の観点から、実用的は時間で最適解に近い解を求める近似解法の研究がさかんに行われてきた。
TSPの近似解法を考える際、木は重要な概念の1つである。この木は、グラフ理論においてもさまざまな研究がなされている。例えば、与えられたグラフG_1,…,G_k,Hに対し、HがG_1,…,G_kを辺素に含むことができるかどうかを判定する問題はNP完全に属しており、一般にその判定は難しい。そこで、さまざまなグラフのクラスに関する十分条件について研究されてきた。この問題に対し、特にHを平面グラフにした場合どのようなグラフを辺素に含むことができるかに興味を持っている。今年度は2つの木の平面グラフへの埋め込みに関する研究を行った。
Garciaら(2002)は、2つのスターでない木はある平面グラフに辺素に埋め込むことができると予想した。同じ論文で、Garciaらは、スターでない木とパスはある平面グラフに辺素に埋め込めることを示している。予想の解決を目標に、より広い木のクラスについて考えた。まず、スターのいくつかの辺を1回細分して得られるグラフとスターでない木に、2つのキャタピラ、について榎本,太田,神田,枡井とともに示した。また、直径5以下のキャタピラとスターでない木に関して構成的に証明し、最終的にスターでないキャタピラとスターでない木について太田とともに示した。この証明方法が予想の解決の糸口にならないかを考察することが今後の課題である。