第3章データ構造とアルゴリズム

Reduction Algorithms帰着アルゴリズム

Algorithm designers spend much of their time modeling problems by selecting and adapting relevant data structures and algorithms to represent the problem and a solution in a computer program. This process of modeling often involves modifying an algorithm design pattern so that it can be applied to the problem. But there is also a different approach to algorithm design that solves problems by changing the input data and output data to fit a preexisting problem. Rather than solve the problem directly, a reduction algorithm solves problems by transforming them into other problems (Figure 3.20).

英語のヒント

アルゴリズムの設計者は、多くの時間を問題のモデル化に使う。関連するデータ構造やアルゴリズムを選んで調整し、問題と解法をコンピュータープログラムで表すのである。この過程では、設計パターンをその問題に適用できるように変更することが多い。しかし、入力データと出力データを変え、既存の問題に合わせて解く、別の設計方法もある。帰着アルゴリズムは、問題を直接解く代わりに、ほかの問題へ変換して解く（図3.20）。

1. Preprocess: Transform the input data so that it is acceptable to an algorithm meant for the other problem.

英語のヒント

1. 前処理：別の問題向けのアルゴリズムが受け入れられるように、入力データを変換する。

2. Apply the algorithm meant for the other problem on the preprocessed data.

2. 前処理済みのデータに、別の問題向けのアルゴリズムを適用する。

3. Postprocess: Transform the output of the algorithm meant for the other problem so that it matches the expected output for the original problem.

英語のヒント

3. 後処理：別の問題向けのアルゴリズムの出力を、元の問題で期待する出力に一致するように変換する。

Figure 3.20 A reduction algorithm preprocesses the input data, passes it to another algorithm, and then postprocesses the algorithm’s output to solve the original problem. (attribution: Copyright Rice University, OpenStax, under CC BY 4.0 license)

図3.20 帰着アルゴリズムは、入力データを前処理して別のアルゴリズムに渡し、その出力を後処理して、元の問題を解く。（出典表記：著作権者 Rice University、OpenStax、CC BY 4.0ライセンス）

Consider a slightly different version of the municipal broadband planning problem, where instead of only considering connections (edges), we expand the problem to consider the possibility of installing broadband nodes directly to each address without relying on potentially expensive neighboring connections. That is, all vertices installed with broadband nodes are inter-connected with each other through another broadband network. If we were to run an algorithm for solving the minimum spanning tree problem on this graph directly, then our result would never consider installing broadband nodes directly, since minimum spanning tree algorithms do not consider vertex weights (Figure 3.21).

英語のヒント

自治体のブロードバンド計画を少し変えた問題を考えよう。接続（辺）だけを考えるのではなく、問題を拡張し、高額になるかもしれない隣接地点との接続に頼らず、各住所へ直接ブロードバンドノードを設置する可能性も考える。すなわち、ノードを設置したすべての頂点は、別のブロードバンド網を通じて互いに接続される。このグラフへ最小全域木のアルゴリズムを直接適用すると、ブロードバンドノードの直接設置は、結果にまったく考慮されない。最小全域木のアルゴリズムは、頂点の重みを考慮しないからである（図3.21）。

Figure 3.21 The problem of finding a minimum spanning tree in a graph with vertex weights can be reduced to the problem of finding a minimum spanning tree in a graph without vertex weights. (attribution: Copyright Rice University, OpenStax, under CC BY 4.0 license)

図3.21 頂点に重みのあるグラフで最小全域木を見つける問題は、頂点に重みのないグラフで最小全域木を見つける問題に帰着できる。（出典表記：著作権者 Rice University、OpenStax、CC BY 4.0ライセンス）

We say that this more complicated municipal broadband planning problem reduces to the minimum spanning tree problem because we can design a reduction algorithm consisting of preprocessing and postprocessing procedures.

この、より複雑な自治体のブロードバンド計画は、最小全域木問題に帰着できるという。前処理と後処理からなる帰着アルゴリズムを設計できるからである。

• Preprocess: Introduce an extra vertex that does not represent a real location but connects to every address (vertex) in the city. The edge weight of each connection is the cost of installing the broadband node directly at that location.

・前処理：実際の場所は表さず、市内のすべての住所（頂点）につながる、追加の頂点を導入する。それぞれの接続の辺の重みは、その場所にブロードバンドノードを直接設置する費用とする。

• Postprocess: After computing a minimum spanning tree for the preprocessed graph, remove the extra vertex that we added during the processing step. Any edges connected to the extra vertex represent a direct broadband node installation, while other edges between real locations are just the same network connections that we saw earlier.

英語のヒント

・後処理：前処理したグラフで最小全域木を計算した後、前処理の段階で加えた頂点を取り除く。その追加の頂点につながる辺は、ブロードバンドノードの直接設置を表す。それ以外の、実際の場所同士を結ぶ辺は、前に見たものと同じネットワーク接続である。

Reduction algorithms enable algorithm designers to solve problems without having to modify existing algorithms or algorithm design patterns. Reduction algorithms allow algorithm designers to rely on optimized canonical algorithms rather than designing a solution by composing algorithm design patterns, which can lead to performance or correctness bugs. Reduction algorithms also enable computer scientists to make claims about the relative difficulty of a problem. If we know that a problem A reduces to another problem B, B is as difficult to solve as A.

英語のヒント

帰着アルゴリズムを使えば、既存のアルゴリズムや設計パターンを変更せずに問題を解ける。設計パターンを組み合わせて解を設計すると、性能や正しさのバグを生むことがあるが、帰着を使えば、最適化された標準的なアルゴリズムに頼ることができる。帰着アルゴリズムは、問題の相対的な難しさについて主張することも可能にする。問題Aが別の問題Bに帰着できるとわかれば、Bを解くことはAを解くのと同じくらい難しい。