この記事は、「【問題】ピラミッドパズルに挑戦！アルゴリズム思考力の腕試し」の解答・解説です。まだ問題を解いていない方は、以下よりご覧ください。
この問題は、大きな問題を小さな問題に分解して、小さな問題から順に解いていくというアプローチ（動的計画法）で解くことができます。
それでは、「正解」と、アドバンスト問題の解答例「C++で実装したコード」を発表します！
解答
正解は29です。下の図の経路が最適解です。
みなさんは正答できたでしょうか。
できた方は、なぜこの経路が最適なのか、その理由まで考えてみましょう。できなかった方は、これから解説する考え方をぜひ習得してください。
解説
それでは、解説を始めます。
startからgoalへ至る経路は、下の図のように、次の6個のパターンに分けて考えることができます。
0. goalへ至る経路の最後のステップが「startからgoalへの移動」であるもの
1. goalへ至る経路の最後のステップが「1番目の点からgoalへの移動」であるもの
2. goalへ至る経路の最後のステップが「2番目の点からgoalへの移動」であるもの
3. goalへ至る経路の最後のステップが「3番目の点からgoalへの移動」であるもの
4. goalへ至る経路の最後のステップが「4番目の点からgoalへの移動」であるもの
5. goalへ至る経路の最後のステップが「5番目の点からgoalへの移動」であるもの
たとえば4.は、「startから4番目の点まで何らかの方法で進み、その後4番目の点からgoalへ移動する」経路を表します。
もし、startから1,2,3,4,5番目の点に至るまでの最小コストがそれぞれわかっていれば、この問題を解くことができます。つまり、startからgoalに至る最小コストを求めるという「大きな」問題が、startから1,2,3,4,5番目の点に至る最小コストを求めるという「小さな」部分問題へと分解されるのです。
・start(0番目の点)から1番目の点に至る最小コスト
・start(0番目の点)から2番目の点に至る最小コスト
・start(0番目の点)から3番目の点に至る最小コスト
・start(0番目の点)から4番目の点に至る最小コスト
・start(0番目の点)から5番目の点に至る最小コスト
・start(0番目の点)からgoal(6番目の点)に至る最小コスト（もとの問題）
について、順に考えていきましょう。
「startから2番目へと直接移動する方法」と「startから1番目の点へ至ってから2番目の点へと移動する方法」があります。それぞれのコストは
- startから2番目へと直接移動する方法のコストは、38
- startから1番目の点へ至ってから2番目の点へと移動する方法のコストは、3+83=86
下の図のように、3番目の点に至る経路のうち
- startから直接3番目の点に至る経路の最小コストは、0+8=8
- startから1番目の点にいき、1番目の点から3番目の点へと移動する経路の最小コストは、3+4=7
- startから2番目の点にいき、2番目の点から3番目の点へと移動する経路の最小コストは、38+27=65
となります。これらの大小を比較して、startから3番目の点に至る最小コストは7と求められます。この7という数値は今後また活用します。
これまでと同様に考えましょう。
- startから直接4番目の点に至る経路の最小コストは、0+26=26
- startから1番目の点にいき、1番目の点から4番目の点へと移動する経路の最小コストは、3+97=100
- startから2番目の点にいき、2番目の点から4番目の点へと移動する経路の最小コストは、38+62=100
- startから3番目の点にいき、3番目の点から4番目の点へと移動する経路の最小コストは、7+950=957
これらの大小を比較して、startから4番目の点に至る最小コストは26と求められます。この26という数値は今後また活用します。
これまでと同様に考えましょう。
- start から直接 5 番目の点に至る経路の最小コストは、0 + 41 = 41
- start から 1 番目の点にいき、1 番目の点から 5 番目の点へと移動する経路の最小コストは、3 + 5 = 8
- start から 2 番目の点にいき、2 番目の点から 5 番目の点へと移動する経路の最小コストは、38 + 9 = 47
- start から 3 番目の点にいき、3 番目の点から 5 番目の点へと移動する経路の最小コストは、7 + 64 = 71
- start から 4 番目の点にいき、4 番目の点から 5 番目の点へと移動する経路の最小コストは、26 + 2 = 28
これらの大小を比較して、start から 5 番目の点に至る最小コストは 8 と求められます。この 8 という数値は今後また活用します。
いよいよ、startからgoalに至る最小コストを求めます。
- startから直接goalに至る経路の最小コストは、0+31=31
- startから1番目の点にいき、1番目の点からgoalへと移動する経路の最小コストは、3+59=62
- startから2番目の点にいき、2番目の点からgoalへと移動する経路の最小コストは、38+35=73
- startから3番目の点にいき、3番目の点からgoalへと移動する経路の最小コストは、7+32=39
- startから4番目の点にいき、4番目の点からgoalへと移動する経路の最小コストは、26+3=29
startから5番目の点にいき、5番目の点からgoalへと移動する経路の最小コストは、28+88=116
これらの大小を比較して、startからgoalに至る最小コストは29と求められます。つまり、この問題の答えは29です。
アルゴリズムの実装
こうして、ピラミッド上をギザギザに進むコストの最小値が求まりました。
この問題を解いた方の中には「直感で29が最小コストだとわかった」と感じる方もいるかもしれません。しかしながら、ピラミッドの段数が100段、1000段、10000段、......と大きくなると、直感で最適解を求めることは難しくなります。
今回の解説では、「もとの大きな問題を小さな部分問題に分解し、部分問題の解を再活用しながら順に解いていく」という方法で解きました。この方法は動的計画法とも呼ばれるものです。
下のコードは、この動的計画法に基づくアルゴリズムをC++で実装したものです。Nはピラミッドの段数を表す整数値であり、cは点間の移動のコストを表す配列です。c[i][j]はi番目の点からj番目の点へ移動するコストを表します。
#include <iostream>
#include <vector>
using namespace std;
int main() {
int N;
cin >> N;
vector<vector<int>> c(N+1, vector<int>(N+1));
for (int i = 0; i < N; ++i) {
for (int j = i+1; j <= N; ++j) {
cin >> c[i][j];
}
}
// DP
vector<int> dp(N+1, -1); // -1 は未更新であることを表す
dp[0] = 0;
for (int i = 1; i <= N; ++i) {
for (int j = 0; j < i; ++j) {
if (dp[i] == -1) dp[i] = dp[j] + c[j][i];
else dp[i] = min(dp[i], dp[j] + c[j][i]);
}
}
cout << dp[N] << endl;
}
一般に、アルゴリズムのもつ優れた特徴として、特定の問題に対して、想定されるどんなケースに対しても「同じやり方で」答えを導けることが挙げられます。このピラミッドパズルに対しては、段数や数値を変えても、解説で紹介したアルゴリズムによって最適解が求められます。
私たちの住む世界には、アルゴリズムによって支えられたシステムがたくさんあります。カーナビを使えば、現在地がどこであっても、目的地までの経路を示してくれます。このようなアルゴリズムを考案することの楽しさを感じていただけたら幸いです。
1988 年生まれ。2014 年東京大学大学院情報理工学系研究科修士課程修了。修士（情報理工学）。現在、株式会社 NTT データ数理システム顧問、モノグサ株式会社コンテンツアーキテクト。数学や情報科学の諸分野の教材開発や啓蒙活動に従事。「けんちょん」の愛称で親しまれている。著書に『問題解決力を鍛える！アルゴリズムとデータ構造』（講談社）がある。数理最適化や機械学習を活用した数理コンサルティング業務の経験も多数。趣味は競技プログラミング、虫食算作り、国内旅行など。
※本記事に記載されている会社名、製品名はそれぞれ各社の商標および登録商標です。
