Skip to main content

研究紹介

このページは執筆中です。


はじめに

近年のハードウェア技術の進歩による計算機性能の向上は著しいものがあります。しかしながら、グラフなどの離散構造を持つ問題の多くはNP-完全あるいはNP-困難であり、現在の計算機でも効率的に解くことが本質的に不可能であろうと考えられています。その中には応用上も重要な問題が数多くあり、それらの計算構造を明らかにすることや、近似解法を用いた効率的なアルゴリズムを開発することは、理論計算機科学における重要な研究テーマとなっています。


アルゴリズム (Algorithm)

計算機を用いて問題を解くためには、その計算方法、処理手順を明確にする必要があります。ある値の集合を入力とし、ある値の集合を出力とするような、明確に定義された計算方法をアルゴリズムといいます。

同じ問題に対しても、それを解くためのアルゴリズムはたくさん考えられます。また、アルゴリズムにも良いものとそうでないものがあります。うまく設計されたアルゴリズムは問題を高速に解くことができますが、そうでないアルゴリズムは、同じ問題を解くのにものすごく時間が掛かったりします。従って、計算機を用いて効率的に問題を解くには、適切なアルゴリズムの選択や良いアルゴリズムの設計が重要となります。


計算複雑さ (Computational Complexity)

様々な問題に対して効率的なアルゴリズムが設計されている一方で、効率的に解くことができないであろうと予想されている問題があります。NP-完全問題やNP-困難問題はそのような問題の代表的なクラスで、巡回セールスマン問題などの多くの重要な問題を含んでいます。これらの計算困難問題は、その計算構造に本質的な難しさを含んでいると考えられています。問題が持つ本質的な難しさを、その問題の計算複雑さといいます。様々な問題に対して、その計算複雑さを明らかにすることは、理論計算機科学における重要なテーマの一つです。


グラフ (Graph)

問題を数学的に扱うためには、問題やそれに対する入力を定式化する必要があり、そのための手段の一つとしてグラフがあります。グラフとは、データ間の離散的な構造を表現するための概念であり、それぞれのデータを点(頂点と呼びます)で、データ間の関係を点と点を結ぶ線(辺と呼びます)で表したものです。
下の図は、10個の頂点と15本の辺を持つグラフの例です。

グラフの例
グラフの例

以下では、グラフに関する問題の例として、グラフ同型性判定問題とグラフ自己同型性判定問題について説明します。

グラフ同型性判定問題 (Graph Isomorphism Problem)

グラフ同型性判定問題(GI)は、2つのグラフGとHが与えられたとき、それらの間に同型写像が存在するか否かを問う問題です。すなわち、2つのグラフの構造が等しいか否かを問う問題です。

下の図は、2つの同型なグラフの例です。赤い矢印がGの頂点とHの頂点の対応を表しており、この対応において、Gの任意の2頂点間に辺があることと、それらに対応するHの2頂点間に辺があることが必要十分であることが確かめられます。この対応のことを同型写像といい、同型写像が存在する2つのグラフは同型であるといいます。

同型なグラフ
同型なグラフ

GIはグラフに関する問題の中でも最も基本的な問題なので、応用上も極めて重要です。それゆえ多くの研究がなされてきましたが、その計算複雑さについてはまだよく分かっていません。この問題を効率よく解くアルゴリズムは知られていませんし、逆に計算困難であるという根拠も示されていません。多くの研究者は、GIを効率的に解くアルゴリズムは存在しないだろうと予想していますが、それを積極的に後押しする理論的な結果もほとんどありません。とても「謎」の多い問題です。

グラフ自己同型性判定問題 (Graph Automorphism Problem)

GIとよく似た問題に、グラフ自己同型性判定問題(GA)があります。グラフGに対して、GからGへの同型写像をG上の自己同型写像といいます。どの頂点も動かさない写像を考えるとそれは(自明な)自己同型写像になりますので、任意のグラフは少なくとも1つの自己同型写像を持ちます。GAは、与えられたグラフに非自明な自己同型写像が存在するか否かを問う問題です。

GIとGAはとてもよく似た問題ですので、それらの計算複雑さも同じようなものだろうという気がします。実際、GIと同様、GAを効率的に解くアルゴリズムは知られていませんし、計算困難であるという証拠も示されていません。しかしながら、これらの問題が等価かどうかは良く知られた未解決問題です。GIとGAの計算複雑さについては、GIはGAより簡単ではない、ということはわかっていますが、それ以上のことについてはほとんどわかっていません。GIとGAが等価な問題なのかそうでないのか?もしそうでないならば、その本質的な違いは何なのか?とても興味深い問題です。


組み合せ最適化問題

問題にもいろいろな種類の問題があります。YesかNoだけを答えればよい問題、解を一つ求める問題、解の個数を求める問題などさまざまです。

最適化問題とは、何らかの制約条件を満たす解(実行可能解といいます)の中で、なんらかの基準で最も良い解(最適解といいます)を求める問題です。実行可能解がグラフなどの組み合わせ的な構造を持つような最適化問題を組み合せ最適化問題といいます。以下では、組み合せ最適化問題の例として、巡回セールスマン問題と配送計画問題を紹介します。

巡回セールスマン問題

今、あるセールスマンが会社を出発していくつかの顧客を訪問してから会社に戻ってくるとします。ただし、会社と顧客の間、顧客どうしの間の移動には、当然コストがかかります。コストとは、移動に掛かる時間や電車代などです。巡回セールス問題とは、どのようにすれば最も低コストで全ての顧客を訪問できるか、その最適な訪問順序を求める問題です。

巡回セールスマン問題に対する入力例
巡回セールスマン問題に対する入力例

単純のため、会社や顧客の間のコストは、建物の絵の間の直線距離であるとしましょう。顧客を訪問する順序はたくさん考えられますが、訪問の順序によって、移動距離が長くなったり短くなったりします。このとき、どのような順序で顧客を訪問すれば移動距離が最も短くてすむでしょうか?

上の図の場合は、次の図のような順序で顧客を訪問するのが最も距離が短くてすみそうです。このように、最もコストが小さくなるような訪問順を求めるのが巡回セールスマン問題です。

最適解
最適解

配送計画問題

配送計画問題は、トラックなどの複数の配送車を使ってデポ(荷物の集積所)にある荷物を顧客に配送するときに、どのトラックがどのような経路で荷物を配送すれば低コストで済むか、その最適な経路を求める問題です。

たとえば、ある宅配業者が3台のトラックを使って、6か所の顧客に荷物を配送する場合を考えてみましょう(次図)。デポと顧客の間、顧客どうしの間の距離は既知であるものとします。また、トラックの積載量には制限がありますので、各トラックは最大2つの顧客に荷物を運べるものとします。

配送計画問題に対する入力例
配送計画問題に対する入力例

トラックの配送経路はたくさん考えられますが、各トラックがどの顧客にどのような経路で配送すれば、トラックの総走行距離が最も短くて済むでしょうか?この入力例の場合は次の図のような経路が最も効率よく荷物を配送できそうです。このように、最もコストの少なくなるような配送経路を求めるのが配送計画問題です。

最適解
最適解

近似アルゴリズム

組み合せ最適化問題は、応用上もとても重要な問題を含みます。たとえば、配送計画問題を効率的に解く方法があれば、宅配業者にとっては配送コストの削減だけでなく、CO2排出量を削減することができ、環境対策にもつながります。

しかし、残念ながら、多くの組み合せ最適化問題はNP-困難と呼ばれるとても難しい部類の問題になります。巡回セールスマン問題や配送計画問題も、最適解を求めるのはとても難しいのです。単純に考えれば、全ての訪問順や配送経路をためしてみて、そのなかで最も良いものを選べばよいのですが、そのようなアルゴリズムで計算しようとすると、最近のコンピュータを使ってもとても時間がかかってしまいます。配送順序は毎日計算しないといけないものですから、何日も掛かって最適解を求めても意味がありません。

そこで、最適解ではないけれど、最適解に近い解(近似解)を効率よく求める研究が数多くなされています。最も良いわけではないけれど、それに近い、良い解が短時間で求められるならば、応用上はそれで十分だろうということです。

近似解を求めるアルゴリズムには、近似率(近似解の精度、どれくらい最適解に近いか)に数学的な保証のあるものと、保証の無いものがあります。保証のあるものは、(精度保証付き)近似アルゴリズムと呼ばれ、ある程度良い解が必ず得られることが保証されています。発見的手法と呼ばれる方法は、解の精度に保証はありませんが、大抵の場合良い解が得られます。

アプレット

こちらに巡回セールスマン問題のアプレットがあります。
巡回セールスマン問題のアプレット

局所探索と呼ばれるアルゴリズムを使って近似解を求めることができます。