以下は私が作成した『アルゴリズムイントロダクション 第4版』の輪読資料です。一部、練習問題や章末問題を解いた結果も載せています。

導入：まえがきと序論

どういう本なのか？

『アルゴリズムイントロダクション 第4版』のまえがきを読んでみると、以下のようなことが書いてある。

引用：『アルゴリズムイントロダクション 第4版』まえがき

それほど前ではないが, 「アルゴリズム」という言葉を聞いたことのある者は, ほとんど確実にコンピュータ科学者か数学者であった. しかし, 現代の生活ではコンピュータが普及してきて, この言葉はもはや特別なものではなくなった. あなたの家庭の周りを見れば, 最もありふれた場所でアルゴリズムが走っているのが発見されるだろう. つまり, 電子レンジ, 洗濯機, そしてもちろんあなたのコンピュータである. あなたは, どの音楽が好きだろうかとか, 運転するときにどの道を選べばよいかなど, アルゴリズムに推薦を求めている. 良いにしろ悪いにしろ, 私たちの社会は有罪判決を受けた犯罪者に対する量刑の提案をアルゴリズムに求めているのだ. あなたを生かし続けることや, あるいは少なくとも殺さないことへの提案さえ, アルゴリズムに委ねている. つまり, あなたの自動車や医療機械のなかの制御システムなのである. 「アルゴリズム」という言葉はニュースのどこかに毎日登場しているようである.

「アルゴリズム」という言葉が日常的なものになったという旨の主張がなされているので軽く調べてみよう。Googleでの検索ワードトレンドがわかるサービス Google トレンド で「algorithm」について調べてみた。

以下はその関連キーワードとして挙がった上位5つである。

Googleトレンド

上位2つの「インスタグラムアルゴリズム」や「YouTube アルゴリズム」というのが目に付く。

2021年の1年間での訪問ユーザー数1は、

  • Instagram：740億人
  • YouTube：4080億人 だったらしく、引用にあるような世界になりつつあるのは間違いなさそうだ。

この本は、そうした身の回りの多く存在するアルゴリズムなるものについての本である。

引用：『アルゴリズムイントロダクション 第4版』まえがき

コンピューターアルゴリズムの現代的な研究を包括的に紹介するものである. （中略） 各章はアルゴリズムや, 設計技法や, 応用分野や, 関連する話題を紹介している. アルゴリズムは, 英語で, ほんの少しプログラミングをしたことのある人なら誰でも読むことのできるように設計された疑似コードで記述されている. 本書はアルゴリズムがどのように挙動するかを描いた 231 個の（多くは複数の部分からなっている）図を含んでいる. （中略） 数学的観点と同様にアルゴリズム設計の工学的課題を議論しているので, 技術的専門家の自己学習にも同じように適している.

したがって、この本はアルゴリズムの「料理本」として使うことができる。ただ、扱う問題によっては、お決まりのアルゴリズムがないこともある。

引用：『アルゴリズムイントロダクション 第4版』p7-p8

本書はアルゴリズムの ”料理本” として使うことができる. しかし, 公表されたアルゴリズムを, 見つけることができない問題に遭遇することもあるだろう. (たとえば, 本書の練習問題や章末問題の多くがその例である.) このような場合に, 読者が自分自身でアルゴリズムを開発し, 正当性を証明し, 効率を解析できるように, 本書ではアルゴリズムの設計と解析の技法も合わせて紹介する.

そうした場合でも自力で対処できる力を養う本としても使えるようだ。また、アルゴリズムだけでなくそれと付随して紹介されることの多い「データ構造」についても扱う。

引用：『アルゴリズムイントロダクション 第4版』p7

本書ではいくつかのデータ構造も紹介する. データ構造 (data structure) は, アクセスと更新を容易にする目的のために, データを蓄積し組織化する方法である. 1つあるいは複数の適切なデータ構造を使用することこそ, アルゴリズム設計の重要な点である. どのデータ構造もすべての目的に対して満足に働くことはない. したがって, いくつかのデータ構造についてその長所と限界を理解することが重要である.

なんのために読むのか？

読む理由は端的に、

  • 面白そう
  • 役に立ちそう

という2点だ。

1つ目は感覚の話で説明のしようがないから置いておくことにして、2つ目の「役に立ちそう」についてもう少しゴニョゴニョと書く。

個人的には、機械学習や深層学習、強化学習は「あきらめの技術」という感じがしている。決まった手続きで解決するのが難しい領域（画像認識や音声認識や言語生成など）に対処するのに機械学習を使うというイメージ。

引用：『アルゴリズムイントロダクション 第4版』 p12

現時点で機械学習が成功しているのは, 主として正しいアルゴリズムが何であるかを人々が真に確認できていないような問題に対してである. コンピュータビジョンや機械翻訳がその顕著な例である. 本書で扱われているほとんどの問題のように人々がちゃんと理解している問題に対しては, ある特定の問題を解くために設計された効率の良いアルゴリズムのほうが, 一般的には機械学習のアプローチより成功している.

人々がちゃんと理解している領域は先人が作った手続き的な解決方法（アルゴリズム）を使って解決したい。なぜなら、

  • 説明可能性が高い
  • 厳密解を出せるのが多い
  • 効率が良い
  • 学習データがなくて良い

という利点があるからだ。馬鹿げた例かもしれないが、

Example

1～10 までの数字を昇順に並べ替えるシステムを作ってください。

というお願いをされたときに、「GPUサーバーぶん回して1週間強化学習させて、精度99%の推定器作りました！」って言ったら、ギャグだと思われると思う。

これは極端な例だとしても、すでに先人が解決してきた「普通の問題」のことを広く知っておいたほうが「車輪の再発明」が防げるのは間違いないはず。

再発明を防ぎ、真に解くべき問題に集中できるという意味で研究の役に立ち、もう少し広い意味では Computer Science の基礎（の一部）を学ぶことでエンジニアリング力を上げることの役にも立つ……はず！

余談

試しに強化学習でソーティングエージェント作ってみた。

RL1

5個の数の並べ替えくらいなら 60秒程度 (5000エピソード) DQNで学習したエージェントで割と正しい並べ替えができる感じ。

学習曲線はこんな感じ。

training_result

一方で、10個の数の並び替えエージェントを新たに学習させて推論させてみると、全然ダメだった。 500秒程度の学習だと状態空間が割と大きいので全然学習できてない。 学習曲線を見てもダメダメなのが分かる。真面目に取り組むなら巨大な状態空間に対してもっと工夫が必要だろうし、 学習時間ももっとかける必要がありそう。

RL2 RL3 training_result2

補足

機械学習とアルゴリズムを対立するものとして書いてみたけど、 機械学習もアルゴリズムの一種なので、ほんとは対立関係にはない。

モチベーションの部分をほかの言葉で言い換えるなら、 基礎がおろそかなまま機械学習関係の研究をしてて「マズイ」と感じることが増えてきたので基礎を固めたい、という風になると思う。

第1部の概観

第1部は以下のような構成になっている。この記事で扱うのは太字のところ。

  • 第1章：アルゴリズムとそれが現代的コンピュータシステムにおいて占める位置の概観
    • アルゴリズムの定義
    • 例示
    • 高速ハードウェア、GUI、オブジェクト指向、ネットワークと並ぶ重要性の説明
  • 第2章：ソーティングアルゴリズム
    • 疑似コードの書き方
    • 挿入ソート
    • マージソート
    • 実行時間の表記法
  • 第3章：実行時間の表記法・漸近表記法の厳密な定義
    • よくある漸近表記法の定義
    • 例を用いた適用
    • 5通りの漸近表記法の定義
    • 数学的表記法
  • 第4章：分割統治；再帰的アルゴリズムの実行時間を記述するのに有用な漸化式を解く手法
    • 代入法
    • 再帰木
    • マスター法
    • マスター法に関する定理とその証明
  • 第5章：確率的解析と乱択アルゴリズム
    • 入力する確率分布と実行時間の関係
    • 乱択アルゴリズム

第1章：計算におけるアルゴリズムの役割

アルゴリズムってそもそもなに？

🔵Important

アルゴリズムは、ある値または値の集合を入力としてとり、ある値または値の集合である出力を有限時間内に生成する、明確に定義された計算手続きである。したがって、アルゴリズムは入力を出力に変換する計算ステップの系列である。

アルゴリズムは明確に指定された計算問題を解くための道具ともいえる。

計算問題は典型的には以下の要素を指定する。

  • 入力形式
  • 望まれる出力形式

アルゴリズムは任意のサイズのすべての問題インスタンスに対して、上記の指定された入出力関係を実現する計算手続きである。

例を挙げよう。

Example

  • 入力：$n$ 個の数の列 $<a_1,a_2,\cdots,a_n>$
  • 出力：$a_1’\leq a_2’\leq \cdots \leq a_n’$ を満たす入力列の置換（並べ替え）$<a_1’,a_2’,\cdots,a_n’>$

数の列を昇順にソートする問題だ。

具体的には、

  • 入力：$<31, 41, 59, 26, 41, 58>$ が与えられて、
  • 出力：$<26,31,41,41,58,59>$ を返す

となれば、望まれた入出力関係を満たす。

こうした具体的な入力列のことを、ソーティング問題のインスタンスと呼ぶ。一般に問題のインスタンスは、その問題の解を計算するのに必要な（しかも問題の記述で課されたすべての制約を満たす）入力列である。

インスタンスは、ソフトウェア開発での「テストケース」に対応すると思う。

🔘Note

ここで取り上げたソーティング問題は、多くのプラグラムの中間段階に含まれており、コンピュータ科学の基本的な問題といえる。そこで優れたソーティングアルゴリズムが数多く開発された。数多くあるソーティングアルゴリズムの中から適用すべき最適なアルゴリズムを決めるには、

  • ソートすべきデータの個数
  • データがすでにソートされている程度
  • データがとりうる値の範囲
  • コンピュータアーキテクチャ
  • 用いる記憶装置の種類（主記憶、ディスク、テープ）

など、応用先で想定される多くの要因に依存する。

🔵Important

計算問題に対してアルゴリズムが正当であるとは、入力として与えられるすべての問題のインスタンスに対して、有限時間でその計算が終了して停止し、そのインスタンスに対して正しい解を出力することである。正当なアルゴリズムは与えられた計算問題を解くと言う。

つまり、正当でないアルゴリズムは、あるインスタンスに対して

  • 停止しない あるいは
  • 誤った答えを出力する

アルゴリズムである。

実は、正当なアルゴリズムだけが役に立つのかというと、必ずしもそうではない。

たとえば、誤り率を制御できる場合には、正当でないアルゴリズムも役に立つ。この本の第31章（整数論的アルゴリズム）では、誤り率を制御できるアルゴリズムの例として大きな素数を求めるアルゴリズムを扱う。

多腕バンディットの最適腕識別問題における「信頼度固定設定（Fixed Confidence）」とかも誤り率を制御できるアルゴリズムの例になると思う。

アルゴリズムが解ける問題

アルゴリズムが実際に応用できる場面の例

  • ヒトゲノムプロジェクト
    • 目的：人間のDNAに含まれる遺伝子のすべてを解読すること
    • やること１：人間のDNAを構成する30億個の塩基対の列を決定
    • やること２：情報をデータベースに蓄積
    • やること３：データ解析のためのツール開発
    • 第14章（動的計画法）は、DNA列の類似度を決定する問題を含むこれら生物学的問題のいくつかを解決するための方法を扱う
  • インターネット
    • やること１：大量のサイトに対する検索性能の向上
    • やること２：データ転送のための経路発見
    • 第11章（ハッシュ表）と第32章（文字列照合）は特定の情報が存在するページを素早く発見する問題に対する方法を扱う
    • 第22章（単一始点最短経路問題）はデータ転送のための経路発見に役立つ方法を扱う
  • EC サイト
    • やること：クレジットカードやパスワードのような個人情報を秘密裏に管理する
    • 第31章（整数論的アルゴリズム）は、公開鍵暗号とデジタル署名などの基本となるアルゴリズムや整数論を扱う
  • 資源管理
    • 主体例：石油会社、議員候補、航空会社
    • 目的：
      • 利益を最大化する油井の位置を決めること
      • 限りある予算内で、選挙に勝つ可能性を最大化する宣伝の場所を知ること
      • 法令の範囲内で全てのフライトに対する経費を最小化する乗組員のスケジュールを求めること
    • これらは第29章（線形計画法）でモデル化して解ける問題である

この本では、こうした具体的な応用場面について詳細には扱わないが、これらの問題に関連した基本的な問題とその技法について扱う。

それなら、どういう問題を扱うのか？

Example

隣接する交差点間の距離が記された道路地図が与えられたとき、1つの交差点から別の交差点までの最短路を求めたい。

自己交差するルートを除外しても、探すルートの数は膨大だ。すべての可能なルートの中から最短のルートをうまく見つけるにはどうすればいいのか。

この本では道路地図を、

  • 第6部：グラフアルゴリズム
  • 付録第B章：集合など

で紹介するグラフとしてモデル化する。このグラフで頂点から頂点への最短経路を求める問題に換言し、効率よく解く方法を考える。

ほかには、

Example

部品の一覧として機械の設計図が与えられている。ある部品はほかのいくつかの部品をその一部として利用しているかもしれない。このとき、各部品がそれを利用するほかのすべての部品よりも前に置かれる順序に並べられた全部品のリストを作りたい。

機械が $n$ 個の部品で構成されているなら、全部で $n!$ 通りの可能な順序がある。階乗は指数よりも速く大きくなるので、全探索をするのは現実的ではない。

この問題はトポロジカルソートの例で、第20章（基本的なグラフアルゴリズム）で扱う。

ほかに、

Example

画像から悪性腫瘍か良性腫瘍かを決めたい。データベースには多くの腫瘍画像があり、そのうちの一部は悪性か良性かがあらかじめわかっている。

この問題は第33章（機械学習のアルゴリズム）のクラスタリングアルゴリズムを利用すれば対応できる。

（＋画像認識の機械学習技術も必要だと思う）

ほかに、

Example

テキストを含むサイズの大きいファイルを、データ節約のために圧縮したい。

多くの圧縮法があるが、

  • 文字列の繰り返しに着目する「LZW圧縮法」
  • 第15章（貪欲アルゴリズム）では「Huffmanコード法」

を扱う。

ここで列挙したものがすべてではないが、これらアルゴリズム的問題は2つの共通点がある。

🔘Note

  1. 解の候補が大量にある。一つひとつ明示的に候補を検証することなく、1つの解、あるいは最良の解を見つけるのは難しい。
  2. 多くの実用的な応用先がある。とくに最短経路はわかりやすい。輸送会社の配送経路、インターネットにおけるパケット転送、カーナビなど色々な応用先がある。

効率が良いとは？

2つの観点

アルゴリズムを考えるうえで「効率の良さ」は重要な指標である。効率が良いとはなんだろうか？2つの観点がある。

🔘Note

  • 時間効率（実行時間が速いか遅いか）
  • 空間効率（使用するメモリ領域が大きいか小さいか）

コンピュータは高速だが無限の速度を持っているわけではない。またメモリも地球上の物質あるいは、宇宙中の物質に限りがある以上無尽蔵ではないし、無料でもない。

したがって、計算時間と計算空間は貴重な限りある資源といえる。ゆえに、時間と空間という資源を効率よく使うアルゴリズムを選ぶ必要がある。

もし仮に、無限の計算速度と無尽蔵のメモリを持ったコンピュータが実現したとして、それでもアルゴリズムを研究する理由が残るだろうか？

引用：『アルゴリズムイントロダクション 第4版』p9-p10

アルゴリズムが停止し, 正しい答を返すことを保証したいという理由があるだけで, 答はイエスである.

実行時間の比較

引用：『アルゴリズムイントロダクション 第4版』p10

同じ問題を解くアルゴリズムの効率が驚くほど違うことがある. そして, ときにはアルゴリズムの差がハードウェアやソフトウェアの差よりもずっと重要になる.

たとえば、以下の2つのソーティングアルゴリズムを比較する。

🔵Important

  1. 挿入ソート：$n$ 個の要素をほぼ $c_1n^2$ 時間をかけてソートする。$c_1$ は $n$ に依存しない定数。つまり、計算時間はほぼ $n^2$ に比例する。
  2. マージソート：$n$ 個の要素をほぼ $c_2 n \log_2 n$ 時間をかけてソートする。$c_2$ は $n$ に依存しない定数。つまり、計算時間はほぼ $n\log_2 n$ に比例する。

普通 $c_1 < c_2$ だが、ある程度 $n$ が大きくなるとその係数の差を相殺し、$\log_2 n$ 対 $n$ となりマージソートが勝つようになる。

アルゴリズムの威力を感じるために、以下の表のような設定で考えてみる。

挿入ソート マージソート
配列数 10,000,000 10,000,000
コンピュータ 高速なA 低速なB
命令実行数 / 秒 10,000,000,000 10,000,000
プログラマ 天才 平均的
命令数 $2n^2$ $50n\log_2 n$

命令数が違うのは、天才プログラマが書いたプログラムはコンピュータ A の上で機械語でうまく書かれていてオーバーヘッドが少ないからで、平均的プラグラマが書いたほうはコンピュータ B の上であまり効率の良くないコンパイラと高級言語を用いて書かれたものでオーバーヘッドが多いからだ。

この設定で 10,000,000 個の数値をソートするのにかかる時間は、

🔘Note

コンピュータ A： $$\frac{2\cdot (10^7)^2 \text{命令}}{10^{10} \text{命令/秒}} = 20,000 \text{秒(5.5時間以上)}$$ コンピュータ B： $$\frac{50\cdot 10^7 \log_2 10^7 \text{命令}}{10^7 \text{命令/秒}}\approx 1163\text{秒(20分未満)}$$

となる。コンピュータが遅い上にプログラムの効率が良くなくても、コンピュータ B は A よりも 17倍も速く問題を解ける！

これは問題のサイズ $n$ が大きくなればなるほどより顕著な差になっていく。

2024年時点では少なくとも17分おきに1億回以上の検索が行われ、24秒毎に1億個以上の電子メールが送られている。こうした巨大な $n$ に対処できるようなアルゴリズムを考えることは、いかにコンピュータの性能が上がったとしても重要だとわかる。

NP完全問題

時間効率の観点において、妥当な時間で実行できるアルゴリズムが知られていないような問題がある。そうした問題は「NP完全問題」として知られ、第34章で扱う。

NP完全問題に対して効率の良いアルゴリズムは今のところ見つかっていない。そして、効率の良いアルゴリズムが存在しないということが証明されている、というわけでもない。効率の良いアルゴリズムが存在するかどうか誰も知らないという現状だ。

しかし、NP完全問題には以下の面白い性質があることがわかっており、それが一部のコンピュータ科学者や数学者を虜にしている。

🔘Note NP完全問題の族は、もしある1つのNP完全問題に対して効率の良いアルゴリズムが見つかれば、すべてのNP完全問題に対して効率の良いアルゴリズムが存在する。

Q. そんな厄介な怪物のような問題を知って何になるのか？ →　A. 徒労を避けることができる。

たとえば、以下のような例を考える。

Example

中央配送センターを持つトラック運送会社を考えよう。毎日、中央配送センターでトラックに荷物を積み込み、いくつかの場所に荷物を送り届ける。1日の終わりには次の日の集荷に備えるためにトラックは中央配送センターに戻ってこなければならない。会社はコスト削減のために、トラックの総走行距離が最小になるように配送順序を決めたい。

このような仕事を頼まれたとする。これに厳密な最適解を与えるシステムの構築をやるぞ！と意気込んで取り組み始めると、その労力の多くは徒労に終わる。

というのもこの問題は「巡回セールスパーソン問題」として知られるNP完全問題だからだ。この問題を解く効率の良いアルゴリズムは知られていない。

しかし、ある仮定の下では、最短の場合に近い距離を持つルートを与える効率の良いアルゴリズムが存在する。数学的な問題とは違ってこのような現実の仕事への応用の場合、厳密に最適解である必要はない。近似的な最適解で十分のはずだ。このような近似的な解を与える「近似アルゴリズム」については第35章で扱う。

並列化

コンピュータの頭脳であるプロセッサの性能が計算速度を決める。2004年頃まではプロセッサのクロック周波数を上げることで性能向上を図ってきた。

しかし、プロセッサのクロック周波数は頭打ちになっている。

プロセッサのクロック周波数推移 出典：Computer Architecture: A Quantitative Approach 6th Edition

頭打ちになっている原因は、物理的制約によるものだ。

引用：『アルゴリズムイントロダクション 第4版』p9

電力密度はクロック速度の増加に対して線形以上の速度で増加するので, クロック速度が十分に速くなれば, チップが融け出すリスクを背負い込むことになるのである.

そうしたリスクを避けるために、プロセッサを製造する企業は、1クロックで計算できる量そのものを増やす方向で性能向上を図るようになった。どのように？マルチコア化によって。

マルチコアコンピュータはシングルチップ上の複数の逐次コンピュータとみなすことができる。これはある種の「並列コンピュータ」といえる。

このコンピュータから最大の性能を引き出すためには、並列性を考慮したアルゴリズムを設計する必要があり、それは第26章（並列アルゴリズム）で説明される。

最近では、GPUを使った並列プログラミングも普通のものとなっている。GPUはマルチコアの怪物で、浮動小数点演算を高速に並列して演算することができるプロセッサだ。もともとはゲームなどのグラフィックス処理のために作られたものだが、その並列処理能力の高さからAI分野の研究でよく用いられるようになった。

GPU 出典：1. Introduction — CUDA C++ Programming Guide

並列処理が輝く計算例として挙がるのが、行列積や連立方程式の解法であるヤコビ法など。ほかにも独立な反復処理がいっぱいあるような計算の場合は並列計算に向いている。

どうやってGPUを活用するのか？Pytorchを使って torch.nn.DataParallel などで割と簡単に並列処理の性能を引き出せるようになっている。Python に慣れている人にとってはかなりお気楽。

もっとキリキリとGPUを活用したいぞ！という場合は、NVIDIA社が開発した並列コンピューティングプラットフォームであるCUDAで、C言語を拡張した「CUDA C」を使ってプログラムをすることができる。

オンライン処理

この本のほとんどの例では、アルゴリズムが実行を始めるとき、すべての入力が利用可能であることを前提にしている。

しかし実社会での応用上は、入力が絶えずやってきては、すぐに出ていく、というような状況が多い。たとえば、インターネットにおけるトラフィックは、今やってきたパケットがこの先どこに到着するかを知らずに現在の状態に基づいてルーティングしなければならない。

🔘Note

開始時点ですべての入力が揃わず、後から到着する入力を受け取るようなアルゴリズムは、オンラインアルゴリズムと呼ばれる。

こうしたアルゴリズムについては第27章（オンラインアルゴリズム）で扱う。

「多腕バンディットアルゴリズム」もオンラインアルゴリズムの一種だ。

アルゴリズムとほかの技術

「実行時間の比較」で示した例は、ハードウェアと同様にアルゴリズムが技術であることを示している。

引用：『アルゴリズムイントロダクション 第4版』 p11

システム全体の効率は高速なハードウェアを選択することと同程度に効率の良いアルゴリズムを選択することに依存している.

簡単な Web アプリケーションなどではアルゴリズムの中身を明示的に必要としない場合も多いが、大規模なものや凝ったものとなるとアルゴリズムが必要になってくる。

たとえば、旅行計画を手助けする Web サービスを考える。その実現のためには、

  • 高速なハードウェア（サーバとクライアントPC・スマートフォン）
  • GUI
  • 広域ネットワーク
  • オブジェクト指向システム

などがかかわってくる。そしてそれに加えて、

  • ルートの発見
  • 地図の表現
  • 番地の補間

などの操作に対してはアルゴリズムが必要になる。

また、以下のようなほかの先端技術、

  • 先端的なコンピュータアーキテクチャとチップ製造技術
  • 簡単に利用できる GUI
  • オブジェクト指向システム
  • 統合された Web 技術
  • 有線および無線の高速ネットワーク
  • 機械学習
  • モバイル端末

それ自体の開発にもアルゴリズムが使われている。

引用：『アルゴリズムイントロダクション 第4版』p12

アルゴリズムに関する知識と技術をしっかりと身に着けていることが, 真の技能をもったプログラマとしての資格の 1 つである. 現代の計算技術を用いると, アルゴリズムを知らなくてもいくつかの仕事は達成できる. しかし, アルゴリズムの優れた知識があれば, はるかに多くの仕事を達成できる.

練習問題

練習問題 1.1-4

上で述べた最短路問題と巡回セールスパーソン問題の類似点を説明せよ. また, 相違点は何か？

類似点

  1. グラフ上の問題: どちらも地点（ノード）と地点間の接続（エッジ）、および移動にかかるコスト（重み）で構成されるグラフを対象とする。
  2. 経路探索: グラフ上のノードを結ぶ「経路」を見つけることが目的。
  3. コスト最小化: 見つけるべき経路は、その経路に含まれるエッジのコスト（距離、時間など）の合計が最小となるもの。最適化問題の一種。
  4. 応用分野: どちらも物流、交通、ネットワーク設計、ロボットの経路計画など、現実世界の様々な分野で応用されている。

相違点

特徴 最短路問題 (Shortest Path Problem) 巡回セールスパーソン問題 (TSP)
目的 指定された2点間の最もコストの小さい経路を見つける。 指定された全ての点をちょうど1回ずつ訪問し、出発点に戻る経路で総コストが最小のものを見つける。
訪問するノード 始点と終点のみが指定される。途中のノードは通る必要はない。 指定された全てのノードを必ず訪問する必要がある。
経路の形状 通常、始点から終点への単純なパスを求める。 出発点に戻ってくる閉路を求める。
計算複雑性 比較的効率的に解ける。ダイクストラ法やベルマン・フォード法など、多項式時間で解けるアルゴリズムが存在する（Pに属する）。 最適解を求めるのは非常に難しいNP困難な問題。点の数が増えると計算時間が爆発的に増加するため、厳密解を求めるのが困難な場合が多く、近似解法が用いられる。
主な制約 始点と終点が指定される。 全ての指定ノードを1回だけ訪問し、出発点に戻る必要がある。

最短路問題とTSPは、グラフ上でコスト最小の経路を探すという点で似ているが、「どのノードを通る必要があるか」と「経路が閉じているか開いているか」という点で根本的に異なる。この違いが、問題の計算複雑性に大きな差（多項式時間 vs NP困難）を生み出している。最短路問題は特定の2点間の効率的な移動を求めるのに対し、TSPは全ての指定地点を効率的に巡回するルートを求める、より複雑な問題と言える。

練習問題 1.2-2

同じコンピュータ上で挿入ソートとマージソートの実装を比較する. サイズ $n$ の入力に対して, 挿入ソートの実行には $8n^2$ ステップかかり, 一方, マージソートの実行には $64n\log_2 n$ ステップかかるとする. 挿入ソートがマージソートに優る $n$ の値を調べよ.

以下の不等式を満たす $n$ の範囲を求めればよい。 $$8n^2<64n\log⁡_2 n$$

解析的に求めることはできないので逐次代入して大小比較して求める。以下のコードで求めた。


import math

def insertion_sort_steps(n):
  """挿入ソートのステップ数を計算する関数"""
  if n <= 0:
      return 0
  return 8 * n**2

def merge_sort_steps(n):
  """マージソートのステップ数を計算する関数"""
  # n=1 の場合は log2(1)=0 なので 0 ステップとする
  if n <= 1:
    return 0
  # n>1 の場合のみ計算
  return 64 * n * math.log2(n)

def find_n_values_revised():
  """挿入ソートがマージソートに優るnの値を調べる関数"""
  n_values = []
  # n=1 では挿入ソートは優位ではない (8 > 0)

  # n=2 から探索を開始
  n = 2
  while True:
    insertion_steps = insertion_sort_steps(n)
    merge_steps = merge_sort_steps(n)

    if insertion_steps < merge_steps:
      n_values.append(n)
      n += 1
    else:
      # 条件を満たさなくなったらループを終了
      break
  return n_values

if __name__ == "__main__":
  n_superior_values = find_n_values_revised() 

  print("挿入ソートがマージソートに優るnの値:")
  if not n_superior_values:
    print("該当するnの値はありません")
  else:
    # 結果をリストで表示
    print(n_superior_values)
    # 結果を範囲で表示
    if len(n_superior_values) > 1 and all(n_superior_values[i] == n_superior_values[0] + i for i in range(len(n_superior_values))):
        print(f"つまり、{n_superior_values[0]} から {n_superior_values[-1]} までの整数")

これを実行すると、挿入ソートがマージソートに優る $n$ の範囲は 2 から 43 までとわかる。

練習問題 1.2-3

同じコンピュータ上で, 実行時間が $100n^2$ のアルゴリズムが, 実行時間が $2^n$ のアルゴリズムより高速に実行できる最小の $n$ の値を求めよ.

以下の不等式を満たす最小の整数 $n\geq1$ を見つければよい。 $$100n^2<2^n$$

これも大した $n$ の大きさにはならないので順番に試して調べる。

import math

def algorithm_a_cost(n):
  """アルゴリズムAの実行時間 (100n^2) を計算する関数"""
  if n < 0:
    return float('inf')
  return 100 * (n**2)

def algorithm_b_cost(n):
  """アルゴリズムBの実行時間 (2^n) を計算する関数"""
  if n < 0:
    return float('inf')
  try:
    return 2**n
  except OverflowError:
    # 念のため、非常に大きなnに対するエラー処理
    print(f"警告: n={n} で 2^n の計算中にオーバーフローの可能性")
    return float('inf')

def find_min_n_faster():
  """100n^2 < 2^n を満たす最小の正の整数nを見つける関数"""
  n = 1
  while True:
    cost_a = algorithm_a_cost(n)
    cost_b = algorithm_b_cost(n)

    print(f"n = {n}: Cost A (100*n^2) = {cost_a}, Cost B (2^n) = {cost_b}")

    # アルゴリズムAの方が高速 (コストが小さい) かどうかをチェック
    if cost_a < cost_b:
      print(f"-> n={n} で 100n^2 < 2^n が初めて成り立ちました。")
      return n

    # 次のnを試す
    n += 1

# --- メインの実行部分 ---
if __name__ == "__main__":
  print("100n^2 < 2^n を満たす最小の整数 n を探します...")
  min_n = find_min_n_faster()

  if min_n is not None:
    print(f"\n結論: 実行時間が 100n^2 のアルゴリズムが 2^n のアルゴリズムより高速になる最小の整数 n は {min_n} です。")
  else:
    print("\n条件を満たす n は見つかりませんでした（または探索範囲を超えました）。")

実行時間が $100n^2$ のアルゴリズムが $2^n$ のアルゴリズムより高速になる最小の整数 $n$ は 15 と求まる。

章末問題

章末問題 1-1 実行時間の比較

以下の表の各関数 $f(n)$ と時間 $t$ に対して, アルゴリズムが問題を解くのに $f(n)$ マイクロ秒かかるとき, $t$ 時間で解くことができる最大の問題サイズ $n$ を求めよ.

1秒 1分 1時間 1日 1ヶ月 1年 1世紀
$\log_2 n$
$\sqrt{n}$
$n$
$n\log_2 n$
$n^2$
$n^3$
$2^n$
$n!$
  • 1ヶ月＝31日
  • 1年＝365日
  • 1世紀＝365 × 100 + 25 = 36525日 として計算する。

$f(n)$ マイクロ秒 = $f(n) * 10^{−6}$ 秒なので、 $$f(n) \leq t \times 10^6$$ を満たす最大の $n$ を求めればよい。

$n\log_2 n$ と $n!$ 以外は明示的に $$n \leq \cdots$$ の形で表せるので即座に求まる。ただ、$\log_2 n$ は桁が大きすぎて Python だと扱いきれないので、桁数だけ求めた。

$n\log_2 n$ と $n!$ は上記のような式にできないので、二分探索を使って数値的に求めた。

1秒 1分 1時間 1日 1ヶ月 1年 1世紀
$\log_2 n$ E+301030 E+18061800 E+1083707985 E+26008991626 E+806278740387 E+9493281943260 E+949978419116566
$\sqrt{n}$ 1.00E+12 3.60E+15 1.30E+19 7.46E+21 7.17E+24 9.95E+26 9.96E+30
$n$ 1.00E+06 6.00E+07 3.60E+09 8.64E+10 2.68E+12 3.15E+13 3.16E+15
$n\log_2 n$ 6.27E+04 2.80E+06 1.33E+08 2.76E+09 7.42E+10 7.98E+11 6.87E+13
$n^2$ 1000 7745 60000 293938 1636581 5615692 56176151
$n^3$ 100 391 1532 4420 13887 31593 146679
$2^n$ 19 25 31 36 41 44 51
$n!$ 9 11 12 13 15 16 17

追記（2025/4/15）

桁でっけぇ～。

組み合わせ爆発のヤバさを感じられる動画としてこういう有名なのもありますね。

第2章：さあ、始めよう

挿入ソート

挿入ソートは、ソーティング問題を解く単純なアルゴリズムである。

Example | ソーティング問題

  • 入力：$n$ 個の数の列 $<a_1,a_2,\cdots,a_n>$
  • 出力：$a_1’\leq a_2’\leq \cdots \leq a_n’$ を満たす入力列の置換（並べ替え）$<a_1’,a_2’,\cdots,a_n’>$

ソートされる数値をキーとも呼ぶ。入力は $n$ 個の要素を持つ配列の形で与えられる。数値をソートしたい場合、それらの数値は付属データと呼ばれるほかのデータに付随するキーであることが多い。キーと付属データがレコードを構成する。

たとえば、年齢、GPA、履修科目数など多くの付随するデータを持つ学生のレコードからなるスプレッドシートを考えてみる。

学生レコード

年齢をキーにして並べ替えると、

年齢順になった学生レコード

こんなふうに付随するデータも一緒に移動する。

この本ではアルゴリズムを記述するのに、疑似コードを用いる。疑似コードと実用コードとの大きな相違点は、疑似コードは以下のソフトウェア工学的な観点に無関心で、アルゴリズムの本質を伝えるためのものになっているということだ。

🔘Note | ソフトウェア工学的な観点

  • データの抽象化
  • モジュール性
  • エラーの取り扱い

さて、挿入ソートの話を始める。

挿入ソートは、トランプで手札をソートするときに多くの人が実行しているソーティングアルゴリズムである。山札から新しくとってきたカードをすでにソート済みの手札の正しい位置に挿入する。すると常に手元にはソート済みのカードがあることになる。これは、少数の要素を効率よくソートできるのが利点だ。

挿入ソートを UNO でしている動画

https://youtu.be/Dxvk2iTdzwY

挿入ソートのgif

アルゴリズムっぽく言うなら、

  1. まず左手を空にする
  2. 山札から最初のカードをとって左手に持つ
  3. 次に右手で山から一枚カードを取る
  4. そのカードを左手のカード群の右から順に大小比較して、挿入すべき位置を見つける
  5. 挿入すべき位置にとってきたカードを置く
  6. 3から5を繰り返す

みたいな感じだ。

これを疑似コードにすると以下のようになる。

INSERTION-SORT(A,n)

1.for i = 2 to n
2.    key = A[i]
3.    // A[i] をソート済みの部分配列 A[1:i-1] に挿入する
4.    j = i - 1
5.    while j > 0 かつ A[j] > key
6.        A[j+1] = A[j]
7.        j = j - 1
8.    A[j+1] = key

ソートする値を格納する配列 $A$ とソートする値の個数 $n$ を引数としてとる。$A[1:n]$ は配列 $A$ の場所 $A[1]$ から $A[n]$ の間に格納されている値の配列のことを指す。

INSERTION-SORT が終了したとき、配列 $A[1:n]$ には元の複数の値がソートされた順序で格納されている。

Example

手続き INSERTION-SORT を列 $<5,2,4,5,1,3>$ からなる配列 $A$ 上で実行するときの様子を図で示したい。

Figure2.2

出典：『アルゴリズムイントロダクション 第4版』図2.2

各箱の上にある数が対応する配列のインデックスであり、箱の中の数がその場所に格納されている値である。また図の(a)~(f)は以下に対応する。

  • (a)~(e)：疑似コードの第1行～8行の for ループ
  • (f)：最終的に得られるソート済み配列

各繰り返しでは、青い箱に $A[i]$ から取り出したキーを保持し、そのキーをその左側に置かれたオレンジの網掛けの箱に保持されている値のそれぞれと第5行の判定文で比較する。右側に向かっている矢印は値が第6行で一つ右に移されることを示し、左側に向かっている矢印は第8行でキーが移動する場所を示す。

🔵Important

インデックス $i$ は左手に挿入しようとしている「現在のカード」を表す。ループインデックス $i$ を持つ for ループの繰り返しの直前では、$A[1:i-1]$ の要素からなる部分配列が現在左手にあるソート済みの札に対応し、残りの部分配列 $A[i+1:n]$ はまだテーブルに残されているカードの山に対応している。実際、$A[1:i-1]$ が格納する要素は、元々 $1$ 番目から $i-1$ 番目までにあった要素であるが、今ではすでにソートされている。$A[1:i-1]$ が持つこれらの性質をループ不変式として定式化する。

ループ不変式

Note | ループ不変式とは

ループの各反復の開始時（または終了時）において、常に真（成り立つ）と期待される条件や性質のこと

これを踏まえて、挿入ソートの部分列が持つ性質を定式化すると以下のようになる。

🔵Important | 挿入ソートの部分列が持つ性質（ループ不変式）

第1～8行の for ループの各繰り返しが開始されるときには、部分配列 $A[1:i-1]$ には開始時点で $A[1:i-1]$ に格納されていた要素がソートされた状態で格納されている。

アルゴリズムの正当性を理解するためにループ不変式を利用する。ループ不変式を使うには、ループ不変式に対する次の3つの性質を示す必要がある。

🔘Note | 3つの性質

  • 初期条件：ループの実行開始直前ではループ不変式は真である。
  • ループ内条件：ループのある繰り返しの直前でループ不変式が真ならば、次の繰り返しの直前でも真である。
  • 終了条件：ループは停止する。そして、ループが停止した時、通常そのループが停止した理由とともに、アルゴリズムが正しいことを示すのに役立つ有用な性質が、その不変式から得られる。

ループ不変式の証明は、数学的帰納法の形をしている。ある性質が成り立つことを示すために、基底段階と帰納段階を証明する。

なぜループ不変式で定式化するのか？

  • 正当性の証明: 上記の3つの性質を示すことで、ループが何回繰り返されようとも、最終的に正しい結果を導くことを数学的に（あるいは論理的に）証明できる。
  • アルゴリズムの理解: ループ不変式を考えることで、ループが何をしているのか、どのようにして最終的な目標に向かっているのかを深く理解する助けになる。
  • アルゴリズムの設計: 正しいループ不変式を念頭に置いてアルゴリズムを設計することで、バグの少ない、目的を達成するコードを書きやすくなる。
  • デバッグ: ループが期待通りに動かない場合、ループ不変式がどの段階（初期、維持、終了）で破綻しているかを調べることで、バグの原因特定に役立つ。

引用：『アルゴリズムイントロダクション 第4版』p17

ループ不変式を用いて正当性の証明を試みるので, 最も重要なのは第3の性質である. 多くの場合, ループ不変式を, ループを停止に導いた条件と一緒に用いる. 典型的な数学的帰納法は帰納段階を無限に適用するが, ここではループが停止するとループ不変式の “帰納” が停止する.

🔘Note

  • 初期条件：$i=2$ の直前でループ不変式が成立していることを示す。部分配列は $A[1:i-1]=A[1:1]=A[1]$ となる。これは 1 要素からのみなる配列で、常にソートされている。よって最初の繰り返しの直前においてループ不変式は真である。
  • ループ内条件：各繰り返しでループ不変式が真なものとして維持されることを示す。直観的には、for ループの各繰り返しでは $A[i]$ を入れるべき場所が見つかるまで $A[i-1],A[i-2],\ldots$ をそれぞれ1つ右に移して空いた場所に $A[i]$ の値を挿入することである。部分配列 $A[1:i]$ はもともと $A[1:i]$ に格納されていた要素から構成されているが、すでにソートされている。for ループの次の繰り返しのために $i$ を 1増やすとループ不変式が維持される。きちんと形式的に示すためには while ループに対するループ不変式も定式化し、それも示す必要があるがこの時点ではそこまでの形式的な取り扱いをせずとりあえず良しとして、for ループについてループ不変式が成立することを証明できたと考えることにする。
  • 終了条件：ループの停止を示す。ループ変数 $i$ は初期値が $2$ で各繰り返しで $1$ ずつ増える。第1行目で $i$ の値が $n$ を超えればループは停止する。つまり、$i$ が $n+1$ も等しくなった時、ループは停止する。ループ不変式の中で $i$ に $n+1$ を代入すると、部分配列 $A[1:n]$ には開始時点で $A[1:n]$ に格納されていた要素が格納されているが、これらの要素はすでにソートされている。

以上からアルゴリズムは妥当であるとわかる。

疑似コードのお約束

この本で用いる疑似コードについての約束事がいくつかあるので列挙する。

  • 字下げはブロック構造を示す。begin, end 文や中括弧のようなブロック構造を示す指示子の代わりに字下げを用いる。
  • ループ構造 while, for, repeat-until と条件分岐 if-else の解釈は C, C++, Java, Python, JavaScript とほとんど同じである。C++, Java と違う点は、本書のループインデックスはループを出た後も値を持ち続ける点である。
  • for ループで用いるキーワード to はループインデックスの値を繰り返しのたびに 1 ずつ増加させるときに用いる。キーワード downto は 1 ずつ減少させるときに用いる。ループインデックスの値を 1 以外の値で変化させるときは by の後に記述することによってその変化量を示す。
  • 記号 “//” は注釈
  • グローバル変数は明示することなしには用いない。
  • 配列要素は角括弧でくくったものを指定することでアクセスする。この本ではインデックスは 1 始まりである。記号 “:” は部分配列を表す。また、この記法は配列の限界を表すのにも用いる。
  • 複合データを属性から構成されるオブジェクトとして組織する。そして、多くのオブジェクト指向言語に取り入れられている構文を用いて特定の属性にアクセスする。たとえば、オブジェクト $x$ が属性 $f$ を持つなら、この属性は $x.f$ とあらわす。
  • 配列やオブジェクトを表す変数は、その配列やオブジェクトを表すデータへのポインタである。$y=x$ を実行すると、オブジェクト $x$ のすべての属性 $f$ について $y.f$ は $x.f$ と等しくなる。さらに、$x.f=3$ を実行すると、そのあとは $x.f=3$ が成立するばかりでなく $y.f=3$ も成立する。つまり、代入 $y=x$ の結果、$y$ と $x$ は同じオブジェクトを指すようになる。
  • 属性を表現する表記法を「直列につなぐ」ことができる。たとえば、属性 $f$ が、属性 $g$ を持つあるタイプのオブジェクトへのポインタであるとする。このとき、$x.f.g$ は暗に $(x.f).g$ という意味である。つまり、代入 $y=x.f$ が実行されたとすると、$x.f.g$ は $y.g$ と等しいということである。
  • ポインタがどのオブジェクトも指さないことがある。この時、ポインタは特別な値 NIL をとる。
  • 引数（パラメータ）は手続きに値で引き渡される。呼び出された手続はその引数の自分用のコピーを受け取り、呼び出された手続が、ある値をその引数に代入してもその変化は呼び出した手続きからは見えない。オブジェクトを引数として渡すと、そのオブジェクトが表すデータへのポインタだけがコピーされ、そのオブジェクトの属性はコピーされない。たとえば、呼び出された手続の引数を $x$ とするとき、呼び出された手続き内の代入文 $x=y$ は呼び出した手続きから見えないが、代入文 $x.f=3$ は見える。同様に、配列もポインタで渡す。したがって、配列全体ではなくその配列を指すポインタだけが渡され、配列の個々の要素の変化は、呼び出した手続きから見える。
  • return 命令は呼び出した手続きが呼び出しを実行した場所に制御を直ちに戻す。大半の return 命令には呼び出した手続きに戻す値が定められている。疑似コードでは 1つの return 命令で複数の値を戻すことができる。
  • ブール演算子 “かつ（and）” と “または（or）” はショートサーキット演算子である。つまり、式 “$x$ かつ $y$” の評価では $x$ の評価をまず行う。仮に $x$ が FALSE ならばこの式全体が TRUE になることはないので $y$ を評価する必要がない。一方で、$x$ が TRUE なら式全体の値を確定させるために $y$ の値も評価しなければならない。「or」も同様である。ショートサーキット演算子を使うことで、「$x\neq NIL$ かつ $x.f=y$ 」といった式を $x$ が NIL のときの $x.f$ の評価の仕方を気にすることなく書くことができる。
  • キーワード error は、正しくない条件の下で手続きが呼び出されたためにエラーが発生したことを示し、この手続きは直ちに停止する。呼び出した手続きがこのエラーを取り扱う責任があるので、取られる処置を記述することはない。

練習問題

練習問題 2.1-1

図2.2を手本にして、数列 $<31,41,59,26,41,58>$ を含む配列上での INSERTION-SORT の動作を説明せよ。

挿入ソートの図

練習問題 2.1-3

INSERTION-SORT 手続きは単調増加順でソートする。これを書き換えて単調減少順でソートするようにせよ。

INSERTION-SORT-DECREASING(A, n)

1. for i = 2 to n
2.     key = A[i]
3.     // A[i] を単調減少順でソート済みの部分配列 A[1:i-1] に挿入する
4.     j = i - 1
5.     while j > 0 かつ A[j] < key   // 変更点: key より小さい要素を右に動かす
6.         A[j+1] = A[j]
7.         j = j - 1
8.     A[j+1] = key

練習問題 2.1-4

以下の探索問題を考えよう。

  • 入力：配列 $A[1:n]$ に格納された $n$ 個の数列 $<a_1,a_2,\ldots,a_n>$ と、ある値 $x$
  • 出力：$x=A[i]$ となるインデックス $i$、または $x$ が $A$ の中に存在しないときは特別な値 NIL 線形探索の疑似コードを書け。線形探索は $x$ を探しながら配列を最初から最後まで順に走査するアルゴリズムである。
LINEAR-SEARCH(A, x)

1. for i = 1 to n
2.     if A[i] == x
3.         return i
4. return NIL

練習問題 2.1-5

$n$ 要素配列 $A[0:n-1]$ と $B[0:n-1]$ に蓄えられた2つの $n$ ビットの2進数の和を求める問題を考える。ここで、配列の各要素は 0 または 1 であり、$a=\sum_{i=0}^{n-1}A[i]\cdot 2^i$, $\sum_{i=0}^{n-1}B[i]\cdot 2^i$ である。この2つの整数の和 $c=a+b$ を2進数として $(n+1)$ 要素配列 $C[0:n]$ に蓄える。ここで、$c=\sum_{i=0}^{n}C[i]\cdot 2^i$ である。入力として大きさ $n$ の配列 $A$ と $B$ をとり、その和を格納する配列 $C$ を返す手続き ADD-BINARY-INTEGERS を記せ。

ADD-BINARY-INTEGERS(A, B)

1. C[0:n] を作成
2. carry = 0
3. for i = 1 to n-1
4.     sum = A[i] + B[i] + carry
5.     C[i] = sum % 2
6.     carry = floor(sum / 2)
7. C[n] = carry
8. return C

  1. 出典 Digital 2022: Global Overview Report — DataReportal – Global Digital Insights ↩︎