部分問題を定義し、依存の順に表を埋める — 動的計画法

上の式で表を埋めて印字したものです(Python 3.14.6 / macOS 26.5.2 / arm64、2026-10-07 実行。Docker の python:3.14-slim でも同じ値)。行が kitten の先頭 i 文字、列が sitting の先頭 j 文字です。

           s   i   t   t   i   n   g
     0   1   2   3   4   5   6   7
k    1   1   2   3   4   5   6   7
i    2   2   1   2   3   4   5   6
t    3   3   2   1   2   3   4   5
t    4   4   3   2   1   2   3   4
e    5   5   4   3   2   2   3   4
n    6   6   5   4   3   3   2   3
distance (rows outer): 3
distance (cols outer): 3
distance (reverse order, reading unfilled cells): 1

右下の 3 が答えです。表は 7 × 8 = 56 マスで、初期化済みの行と列を除く 42 マスを1回ずつ、3つのマスを読んで埋めます。

行を外側にしても列を外側にしても 3 です。逆順に埋めると 1 になります。 右下を最初に計算する時点で、上・左・左上はまだ初期値の 0 なので、min(0+1, 0+1, 0+1) = 1 です。

複数の表を結合するクエリでは、どの順に結合するかで実行の費用が変わります。PostgreSQL の optimizer README(master、2026-10-07 取得)は、標準の計画器について次のように書きます。

The join tree is constructed using a "dynamic programming" algorithm: in the first pass (already described) we consider ways to create join rels representing exactly two list items. The second pass considers ways to make join rels that represent exactly three list items; the next pass, four items, etc.

ここでの部分問題は「どの項目の組を結合したか」です。k 項目の結合はそれより少ない項目の結合から作るので、2項目、3項目、4項目と段を上がれば、依存先は前の段で済んでいます。埋める順序が依存の順になっているのが、README の段の並びにそのまま出ています。

ただし表は大きくなります。項目の組は、n 項目なら最大で 2^n − 1 通りです(本教材の算数。12 項目で 4,095)。PostgreSQL 18 の文書は、ある大きさからは網羅的な探索をやめると書いています。

Use genetic query optimization to plan queries with at least this many FROM items involved. (Note that a FULL OUTER JOIN construct counts as only one FROM item.) The default is 12.

for queries with many tables the exhaustive search takes too long, often longer than the penalty of executing a suboptimal plan.

既定では FROM 項目が 12 以上で、GEQO(遺伝的探索)に切り替わります。GEQO について 61.3 節は non-exhaustive search と書きます。文書の言い方では、網羅的な探索にかかる時間のほうが、最適でない計画を実行する不利益より長くなることが多いから、という交換です。

README の引用部分は、各段で候補のうち何を残すかまでは書いていません。本教材もそこには踏み込みません。