アルゴリズム設計に欠かせない問題解決のための「還元」 with Clojure

システムエンジニアやプログラマーは、問題解決に取り組むことが主な仕事ですが、
直面する問題解決に取り組む中で、過去に似たような問題に出会っていたことに気が付くことがよくあると思います。
この記事では、問題を別の問題に置き換えて考えることを言語化した、計算理論の世界の「還元」という概念を紹介しようと思います。
紹介の中で使うコードは、今の仕事で使っているClojureで書きました。(Clojureがわからなくても内容は理解できると思います)
また、個人的な解釈を含むので、誤っている場合があります。個人的な解釈については、「～ていそうです」「～と思いました」「～な気がします」みたいな表現になっています。

1. 還元(reduce)

還元(reduce)とは、ある計算問題Aを別の計算問題Bに変換することです。
問題解決においては、

「この問題(A)って要はあの問題(B)なのでは？」

「あの問題(B)さえ解ければ、この問題(A)が解ける」

みたいな動機でよく使われます。
問題Bを解くと問題Aが解けるとわかったとき、「問題Aは問題Bに還元できる」 といいます。
競技プログラミングの問題はまさにこの営みがほとんどを占めていそうです。

還元の例を示します。

問題Aとして「与えられる整数のリストから、差の絶対値が最も小さいペアを一つ選べ。ただし同じ数のペアは選べない。」という問題min-distance-pairがあるとします。

例えばリストが(3, 5, 1, 5, 8, 7)であれば、その答えは差の絶対値が1のペア(7, 8)です。

この問題の解法として、リストの要素のペア全パターンの差を見るのも良いですが、それよりも事前にソートをしておけば、隣同士以外の差を見る必要は無くなるはず(遠くに行くほどその差は大きくなるはず)なので、余計に差を計算しなくて済みます。
よって、min-distance-pairは、問題Bとしてソート問題に還元することができます。

ソート問題については、大抵言語に組み込まれているので自力で解く必要はないです。

以下がClojureによる実装です。min-distance-pairの定義の中でsortを利用しています。

(defn min-distance-pair [col]
  (let [distance (fn [[n m]] (- m n))
        sorted (sort (distinct col))
        pairs (partition 2 1 sorted)]
    (apply min-key distance pairs)))

repl:> (min-distance-pair [3 5 1 5 8 7])
(7 8)

• distinct: https://clojuredocs.org/clojure.core/distinct
• partition: https://clojuredocs.org/clojure.core/partition
• min-key: https://clojuredocs.org/clojure.core/min-key

2. チューリング還元、神託関数

上記の「最小の差の絶対値問題」を解く関数において、ソートが実装されていないとしましょう。
そのまま実行すれば以下のように変数が解決できないエラーが出ます。

Unable to resolve symbol: sort in this context

エラーはストレスの元ですが、でもまぁソート問題は解けるもんとしておこうやぁ。

このように実装されている、されていない(、できないかもしれない)に関わらず『うまく機能するでしょう』と仮定される関数を 神託関数(oracle function)(神託プログラム, 神託機械) と呼びます。

また、ある問題Aを、「神託関数によって解けると仮定された問題B」に還元することをチューリング還元といいます。

3. チューリング還元のプログラミング的なたとえ

チューリング還元は、その定義の「問題」を「プログラム」に置き換えれば「プログラムAをうまく実行するためのプログラムBをインポートしてくること」と言うことができます。上記のプログラムでは標準ライブラリを暗黙的にrequireし、sortを参照してきています。

テストコードでチューリング還元を例えてみます。

自力でクイックソートを実装することになった場合、とりあえずクイックソートが実装されているとしてテストを書きます。

(ns reduction.sort-test
  (:require [clojure.test :refer :all]
            [reduction.sort :refer [quick-sort]]))

(deftest quick-sort-test
  (let [n 100
        random-seq (take n (repeatedly #(rand-int n)))
        actual (quick-sort random-seq)]
    (is (every? 
         (fn [[n m]] (<= n m))
         (partition 2 1 actual)))))

quick-sortさえ正しく実装されれば、quick-sort-testのテストは通ります。(いまは実装していないので、当然このテストは落ちます。)

チューリング還元の話に置き換えるなら、quick-sortが神託関数として仮定され、quick-sort-testはquick-sortにチューリング還元されています。

4. 部分問題への還元

どうせなら上のテストを通してみます。つまり、クイックソートの実装です。
クイックソートも実はちょっと毛色の違ったチューリング還元で実装します。
クイックソートは以下のように定義できます。

1. ある基準(pivot: 軸)となる値を選びます。
2. その基準以下のグループとそれより大きいグループに分けます。
3. それぞれのグループでクイックソートをします。
4. 小さいグループ、基準、大きいグループを結合します。

(defn quick-sort [col]
  (if (empty? col)
    []
    (let [[pivot & xs] col
          smaller-or-equal (filter #(>= pivot %) xs)
          bigger (filter #(< pivot %) xs)]
      (concat (quick-sort smaller-or-equal) [pivot] (quick-sort bigger)))))

クイックソートの定義の中にクイックソートがありますね。これは再帰的な定義を行っているということです。心配しなくても再帰を繰り返していけば、いずれソートは自明な部分(空や、要素が一つのシーケンス)にぶち当たるので、結果、全体的にソートされることになるというわけです。
クイックソートは問題をどのような問題に還元してると言えるでしょうか。

言い回しは不思議ですがクイックソートは、より要素の少ないシーケンスのクイックソートに還元されます。

クイックソートに限らず他の再帰関数や分割統治など、部分問題を解決していくやり方も還元の一つです。

再帰関数は処理手順を追っていくと頭がこんがらがりますが、部分問題への還元を行うものと思えば、思考はまとまるのかなと思います。

まとめ

• ある計算問題Aを別の計算問題Bに変換することを計算理論の世界で「還元」という。
• つまり「問題Bが解けたら、問題Aも解ける」という考え方のこと。
• 問題Bが解ける神託関数を仮定している場合はチューリング還元という。
• チューリング還元は、プログラミングの世界では「プログラムAを完成させるためのプログラムBをインポートしてくる」こと。
• 還元という考え方は、プログラミング活動そのものや単体テスト、再帰関数にも適用できる

さいごに(免責)

還元という考え方はこれ以外にもたくさんの意義があります。紹介したものはほんの一部です(参考文献読み切れてないです)。

この記事は参考書籍「Pythonによる問題解決のためのアルゴリズム設計技法」に沿って、問題解決に向けた還元にスポットを当ててClojureで実装し、独自解釈としてテストコードを扱いました。ある意味では正しい解釈だと思っています。

しかし、参考書籍「計算できるもの、計算できないもの」には『数学者は主として問題がやさしいことを示すために還元を使う。それに対し、理論計算機科学者は主として問題が難しいことをしめすために還元を使う』とあります。読み進めていく中で、やはり還元はあくまで計算理論における計算問題の決定不能の証明や、「困難さ」を示す意義のほうが大きいような気がしている中で今回の記事を書いたことをご承知おきください。

参考書籍:

• 「Pythonによる問題解決のためのアルゴリズム設計技法」
• 「計算できるもの、計算できないもの」