「解けない問題」をどう解くか ― 最適化とアルゴリズムの考え方【データサイエンスを支える情報工学入門③】

記事

IT・テクノロジー

2026/08/24 08:46

「データサイエンスを支える情報工学入門」シリーズの最終回です。第1回ではコンピュータとデータベースの基礎を、第2回ではプログラミングとアルゴリズムの基礎を紹介しました。最終回となる今回のテーマは「最適化」です。巨大な選択肢の空間から、条件に合う「必要なもの」を見つけ出すための道具について見ていきます。

現実の問題が抱える「パラメータの組み合わせ爆発」

たとえば、ある部品の「長さ」「幅」「厚さ」「材質」といったパラメータの組み合わせから、「重さ」「価格」「強度」といった結果が決まる場面を考えます。現実の問題は、複数のパラメータの組み合わせによって結果が決まり、しかも膨大な数のパラメータを持つことが普通です。そこで、「望ましい結果を出すパラメータの組み合わせを、どうやって見つければよいか」という問いが生まれます。これが「最適化問題」です。

ここで厄介なのが、パラメータの組み合わせの総数は、容易に爆発してしまうという点です。たとえば、長さ10通り、幅10通り、厚さ5通り、材質5通りだとすると、組み合わせは10×10×5×5=2500通りになります。一般に、n個のパラメータがそれぞれp通りの値を持つなら、その組み合わせはpⁿ通りになります。パラメータが100個、10000個になったら……と考えると、この数がすぐに天文学的な規模になることが想像できると思います。

最適化問題(あるいは、条件を満たすものを見つける「制約充足問題」)は、こうした巨大な空間から必要なものを見つけ出すための道具です。問題の種類もアプローチも数多くありますが、今回は代表的なものをいくつか紹介します。

連続量の最適化問題

パラメータ(設計変数)が連続的な値を取る場合の最適化問題は、次のような形で定式化されます。

minimize f(x), x = (x₁, x₂, ..., xₙ)ᵀ subject to x ∈ F

ここで、f(x)は「目的関数(Objective function)」、xは「パラメータ(設計変数)」、x∈Fは「制約条件(Constraint)」と呼ばれ、Fは「実行可能領域(feasible region)」と呼ばれます。つまりこれは、「パラメータの取りうる値の集合(実行可能領域)Fの中で、パラメータから得られる評価指標(目的関数)f(x)が最小となる状態を見つける問題」ということです。ちなみに「subject to」は「制約下」という意味で、"s.t." と略されることも多い表現です。

たとえば、「−5≤x≤5、−5≤y≤5の範囲の中で、目的関数f(x,y)が最小となる(x, y)を求める」といった問題を考えるとき、この−5≤x≤5、−5≤y≤5という正方形の範囲が「実行可能領域」にあたります。

線形計画問題

目的関数と制約条件がすべて線形方程式(1次式)で記述される問題を「線形計画問題(Linear Programming)」と呼びます。たとえば、

minimize f(x₁, x₂) = −8x₁ − 6x₂ subject to x₁ + x₂ − 4 ≤ 0 **　　　　　　3x₁ + x₂ − 6 ≤ 0** **　　　　　　x₁ ≥ 0, x₂ ≥ 0**

という問題では、f(x₁, x₂)は平面として表現でき、その等高線は直線になります。このとき、解は必ず実行可能領域の「頂点」に存在することが知られています(実行可能領域自体も、直線同士で囲まれた「凸多面体」の形になります)。この性質を利用して、シンプレックス法など、効率のよいアルゴリズムで解くことができます。

非線形最適化と勾配降下法

一方、問題が線形方程式で定式化できない、より一般的な(非線形の)最適化問題では、事情が少し複雑になります。解析的には、微分が0になる点が極値(山や谷の頂点)を持つ、という性質を利用できますが、必ずしも問題が微分できる形になっているとは限りませんし、そもそも数式できれいに書き表せるとも限りません(実務では、数式ではなく、離散的な値の表(データ)として関数が与えられることもあります)。

このような場合によく使われるのが「勾配降下法(最急降下法)」です。これは、今いる場所の傾き(微分・勾配)を見て、値が下っていく方向に少しずつ進んでいき、微分が0になったところで探索を終了する、というアルゴリズムです。1次元であれば単純に左右どちらに進むかを判断するだけですが、多次元になると、一番傾きが大きい方向(最急な方向)に向かって進む、という戦略を取ります。

局所最適解という罠

勾配降下法には、注意すべき大きな落とし穴があります。微分が0になる点が複数ある場合、探索によって「極小値」には辿り着けますが、そこが全体の中で最小の値(大域最適解)であるとは限らない、という問題です。

谷が複数ある地形をイメージしてみてください。探索のスタート地点によっては、本当は他にもっと深い谷(大域最適解)があるにもかかわらず、途中の浅い谷(局所最適解)にはまり込んでしまい、そこで探索が止まってしまうことがあります。

さらに厄介な罠として、次の2つのケースも紹介されていました。

微分が0になる点が、1点ではなく「一意に定まらない」ケース(平らな尾根や谷筋が続いていて、その範囲全体で微分が0になってしまう場合)

微分が0になるが、それが最小でも極小でもない「鞍点(あんてん)」と呼ばれるケース(ある方向から見ると山、別の方向から見ると谷になっている、馬の鞍のような形状の点)

こうした罠があるからこそ、最適化はスタート地点の選び方や、アルゴリズムの工夫が重要になってくるわけです。

求解法の種類

計算機で非線形最適化問題を解くには、様々な方法があります。

最急降下法:先ほど紹介した、傾きに沿って降りていく基本的な方法

ニュートン法とその発展:2次微分の情報も使って、より効率的に最適解に近づく方法

逐次二次計画法:問題を2次関数で近似しながら反復的に解く方法

これらの手法の性能は、収束の安定性(ちゃんと解に辿り着けるか)や収束速度(どれだけ早く辿り着けるか)で評価されます。素早く解に辿り着こうとして大股で探索すると、目的の場所を行き過ぎてしまい、かえって振動してしまう(行ったり来たりを繰り返してなかなか収束しない)、というトレードオフがあるのも実務上重要なポイントです。

離散最適化問題

ここまでは、パラメータが連続的な値を取る場合を見てきましたが、パラメータの取りうる値が連続ではなく、離散量(飛び飛びの値)である場合の最適化問題も存在します。すべてのパラメータの組み合わせの中から、最も良いもの(最適解)を求めるのが目的です。

離散量なので、パラメータの組み合わせは(数はとても多くても)高々有限個です。「では、がんばって全部探せばいいのでは?」と思うかもしれません。実際、すべてのパラメータの組み合わせを調べる方法は「全探索」(力づく=brute-force、と言ったりもします)と呼ばれ、もし全探索ができるのであれば、確実に最適解が見つかります。

ですが、ここでも組み合わせ爆発が牙を剥きます。たとえば100個のパラメータが、それぞれ100通りの値を取れる場合、組み合わせは10²⁰⁰通りにもなります。仮に1秒間に100億回(=10¹⁰回)計算できる、非常に高性能な計算機があったとしても、全探索にかかる時間は10²⁰秒、つまり約3×10¹²年(3兆年)にもなってしまいます。宇宙の年齢(138億年)と比べても、途方もない時間です。だからこそ、離散最適化問題でも「効率よく解を見つける方法」が必要になるわけです。

グラフによる問題の表現

離散最適化の問題を考えるうえで、非常に重要な道具になるのが「グラフ」です。ここでいうグラフとは、関数のグラフ(y=f(x)のような曲線のグラフ)とは違い、有限個の要素(ノード、頂点、節点)と、それらの関係(エッジ、辺)からなる構造のことを指します。要素の関係を記述したものがグラフであり、必ずしも図として描く必要はなく、行列などでも表現できます。

グラフには、次のような種類があります。

重み付きグラフ:エッジが数値(距離、料金、時間など)を持つグラフ

有向グラフ:エッジが方向を持つグラフ(方向がないものは「無向グラフ」と呼ばれる)

グラフを使うと、現実の様々な問題を表現できます。たとえば「あるノードからあるノードへの経路で、重みの合計が最小となる経路を見つける」問題は「最短経路問題」と呼ばれます。一方、「すべてのノードを通り、重みの合計が最小となる経路を見つける」問題(巡回セールスマン問題に近い問題)は、多項式時間で解くことができない、非常にコストの高い問題として知られています。配送経路問題など、現実の問題の多くはこのようにグラフで表現することが可能です。

ダイクストラ法を実際に解いてみる

最短経路問題を解く代表的なアルゴリズムが「ダイクストラ法(Dijkstra's algorithm)」です。実際に、次のような有向グラフの例で、頂点Aから他のすべての頂点への最短経路長を求めてみましょう。

グラフの構成(有向・重み付き):A→B(6)、A→C(8)、A→D(18)、B→E(11)、C→D(9)、E→F(3)、F→D(4)、F→C(7)

ダイクストラ法では、各頂点についてAからの「暫定の最短距離」を記録する配列(Distance)と、Distanceが小さい順に自動でソートされる特殊なデータ構造「プライオリティキュー(Priority Queue)」を使います。最初は、A自身の距離を0、それ以外の頂点への距離をすべて「無限大(未確定)」として初期化します。

1回目の反復:プライオリティキューからAを取り出します(距離0で確定)。Aに隣接する頂点B, C, Dの距離を更新します。

Distance[B] = Distance[A] + Edge(A,B) = 0 + 6 = 6

Distance[C] = Distance[A] + Edge(A,C) = 0 + 8 = 8

Distance[D] = Distance[A] + Edge(A,D) = 0 + 18 = 18

2回目の反復:残りの中で最も距離が小さいB(距離6)を取り出し、確定させます。Bに隣接する頂点Eの距離を更新します。

Distance[E] = Distance[B] + Edge(B,E) = 6 + 11 = 17

3回目の反復:残りの中で最も距離が小さいC(距離8)を取り出し、確定させます。Cに隣接する頂点Dの距離を更新します。

Distance[D] = Distance[C] + Edge(C,D) = 8 + 9 = 17(それまでの18より小さいので更新)

4回目の反復:残りの中で最も距離が小さいE(距離17)を取り出し、確定させます。Eに隣接する頂点Fの距離を更新します。

Distance[F] = Distance[E] + Edge(E,F) = 17 + 3 = 20

5回目の反復:D(距離17)を取り出します。Dに隣接する(Dから出ていく)頂点はないため、これ以上の更新はなく、Distance[D]=17で確定します。

6回目の反復:F(距離20)を取り出します。Fに隣接する頂点もないため、Distance[F]=20で確定します。プライオリティキューが空になったところで、すべての頂点への最短距離が求まりました。

最終的な結果は、A=0、B=6、C=8、D=17、E=17、F=20 です。「毎回、その時点で一番近い(距離が小さい)未確定の頂点を確定させ、そこから伸びる辺の距離を更新していく」という操作を繰り返すだけで、全体の最短経路が求まってしまう、というのがダイクストラ法の面白いところです。

ダイクストラ法の特徴

ダイクストラ法は「最良優先探索」の一種で、近くになるものの中で一番良いものを優先して探索していく方法です(幅優先探索の一種ともいえます)。計算量はだいたい (V+E) log V(Vは頂点数、Eは辺の数)程度で済むため、比較的効率よく解けるアルゴリズムです。

ただし、ダイクストラ法には「負の重み(マイナスの距離)には対応できない」という制約があります。カーナビなどの様々な経路決定に実際に使われているアルゴリズムで、その改良版として「A*(エースター)アルゴリズム」というものも存在します。

それでも解けないときは:発見的手法(ヒューリスティック)

離散最適化の問題の中には、これまで紹介したような厳密なアルゴリズムでは、計算時間が爆発してしまって現実的に解けないものもあります。そうした場合に使われるのが「発見的手法(ヒューリスティック)」です。

ヒューリスティックとは、最適解とは限らないものの、最適解っぽいものを探す方法です。必ず何らかの答えを出してくれますが、その答えがどのくらい最適解に近いかは分かりません。時間をかければ良い答えに近づく(はず)ですが、最適解に到達できる保証はない、という性質を持ちます。それでも、最適化アルゴリズムの計算時間が爆発してしまうような場面では、非常に有効な選択肢になります。「最適な答えを出してくれるが1週間かかる人」と「適当にそれっぽい答えを1日で出してくれる人」のどちらに仕事を頼むか、という例えがしっくりくる考え方です(なお、最初に紹介した「必ず有限回数で解が得られる」という厳密な意味での「アルゴリズム」とは、本来は対になる概念ですが、実務上は「ヒューリスティックなアルゴリズム」と呼ばれることもあります)。

ヒューリスティックの代表例としては、何らかの安定状態に落ち着く物理現象や、群れの挙動を模擬して安定状態を求める、次のような手法が紹介されていました。

進化的ベース:遺伝的アルゴリズム(Genetic Algorithm, GA)。生物の進化(選択・交叉・突然変異)を模した手法

物理ベース:焼きなまし法(Simulated Annealing, SA) 。金属を冷却しながら安定した結晶構造に落ち着かせる「焼きなまし」という物理現象を模した手法

群ベース:蟻コロニー最適化(Ant Colony Optimization, ACO) 、粒子群最適化(Particle Swarm Optimization, PSO) 。アリの集団やイワシの群れなど、多数の個体が協調しながら良い解を見つけていく群れの挙動を模した手法

まとめ:3回シリーズを振り返って

3回にわたって、コンピュータの基本的な仕組みとデータベース、プログラミングとアルゴリズムの基礎、そして最適化という、データサイエンスを実務として支える情報工学の基礎を見てきました。

「多数のパラメータからなる膨大なデータから、必要な情報をどうやって探し出すか」という問いは、この3回を通じて繰り返し登場したテーマだったように思います。データベースでは大量のデータをどう構造化して蓄積するか、アルゴリズムではデータ数に対して処理時間がどう増えるか、そして最適化ではパラメータの種類が増えたときにどう対応するか、というように、視点は違えど「規模が大きくなったときにどう立ち向かうか」という一貫した問題意識でつながっていることに、あらためて気づかされました。

数式やアルゴリズムの手順は細かく見えますが、根っこにあるのは「闇雲に全部を試すのではなく、賢く探す」という、とてもシンプルな発想です。IT エンジニアを目指すうえで、こうした「なぜその手法が必要とされるのか」という背景の理解は、単に手法を暗記するよりもずっと大切なことだと感じます。この記事が、情報工学の基礎を学ぶきっかけになれば嬉しいです。