第3章データ構造とアルゴリズム
Brute-Force Algorithms総当たりアルゴリズム
Solving a combinatorial problem involves identifying the best candidate solution out of a space of many potential solutions. Each solution to a combinatorial problem is represented as a complex data type. Many applications that involve simulating and comparing different options can be posed as combinatorial problems.
英語のヒント
組合せ問題を解くには、多くの可能な解の空間から、最良の解候補を見つける必要がある。組合せ問題のそれぞれの解は、複雑なデータ型として表される。異なる選択肢をシミュレーションして比較する多くの用途は、組合せ問題として定式化できる。
• Route planning in online mapping asks, “Out of all the possible routes from point A to point B, which route is the shortest?” (Shortest paths problem)
・オンライン地図の経路計画では、「A地点からB地点への、すべての可能な経路のうち、どれが最短か」を問う。（最短経路問題）
• Municipal broadband planning asks, “Out of all the possible ways to connect every real-world address to the Internet, which network of connections is the cheapest to build?” (Minimum spanning trees problem)
英語のヒント
・自治体のブロードバンド計画では、「現実にあるすべての住所をインターネットへ接続する、すべての可能な方法のうち、どの接続網が最も安く構築できるか」を問う。（最小全域木問題）
• The interval scheduling problem is a combinatorial problem involving a list of scheduled tasks with the goal of finding the largest non-overlapping set of tasks that can be completed.
英語のヒント
・区間スケジューリング問題は、予定された作業のリストを扱う組合せ問題である。目標は、時間が重ならず、実行できる作業の集合のうち、最大のものを見つけることである。
Rather than searching for a single element, combinatorial problems focus on finding candidate solutions that might be represented as a list of navigation directions, network connections, or task schedules. And unlike sorting, where the output should be a sorted list, combinatorial problems often attempt to quantify or compare the relative quality of solutions in order to determine the best candidate solution out of a space of many potential solutions. Even if our route plan is not the “best” or shortest route, it can still be a valid solution to the problem.
英語のヒント
組合せ問題では、単一の要素を探すのではなく、道順、ネットワーク接続、作業予定のリストなどで表される解候補を見つけることに注目する。また、出力が整列済みのリストであるべき整列問題とは異なり、多くの可能な解の空間から最良の候補を選ぶために、解の相対的な良さを数量化したり比較したりすることが多い。経路計画が「最良」や最短でなくても、その問題の有効な解ではあり得る。
A brute-force algorithm solves combinatorial problems by systematically enumerating all potential solutions in order to identify the best candidate solution. For example, a brute-force algorithm for generating valid credit card numbers might start by considering a credit card number consisting of all zeros, then all zeros except for a one in the last digit place, and so forth, to gradually explore all the possible values for each digit place.
英語のヒント
総当たりアルゴリズムは、最良の解候補を特定するために、すべての可能な解を体系的に列挙して、組合せ問題を解く。たとえば、有効なクレジットカード番号を生成する総当たりアルゴリズムなら、すべての桁が0の番号から始め、次は最後の桁だけが1で、ほかは0の番号、というように、各桁のあり得る値を順にすべて調べることが考えられる。
Brute-force algorithms exist for every combinatorial problem, but they are not typically used because of runtime issues. To systematically enumerate all potential solutions, a brute-force algorithm must generate every possible combination of the input data. For example, if a credit card number has sixteen digits and each digit can have any value between zero and nine, then there are 1016 potential credit card numbers to enumerate. The combinatorial explosion is the exponential number of solutions to a combinatorial problem that makes brute-force algorithms unusable in practice. Despite continual improvements to how quickly computers can execute programs, exponential time brute-force algorithms are impractical except for very small problem input data.
英語のヒント
すべての組合せ問題に総当たりアルゴリズムは存在するが、実行時間の問題から、通常は使われない。可能な解をすべて体系的に列挙するには、入力データから作れるあらゆる組合せを生成しなければならない。たとえばクレジットカード番号が16桁で、各桁が0から9までの値を取るなら、列挙すべき候補は1016個となる。組合せ爆発とは、組合せ問題の解が指数関数的な数となり、総当たりアルゴリズムを実際には使えなくすることである。コンピューターの実行速度は継続的に向上しているが、指数時間の総当たりアルゴリズムは、問題の入力データがごく小さい場合を除いて、実用的ではない。
INDUSTRY SPOTLIGHT産業の現場から
Protein Foldingタンパク質の折り畳み
Proteins are one of the fundamental building blocks of biological life. The 3-D shape of a protein defines what it does and how it works. Given the string of a protein’s amino acids, a protein-folding problem asks us to compute the 3-D shape of the resulting protein.
英語のヒント
タンパク質は、生物を構成する基本的な要素の1つである。タンパク質の3次元の形状は、それが何をし、どう働くかを決める。タンパク質を構成するアミノ酸の列を与えられたとき、タンパク質の折り畳み問題では、できあがるタンパク質の3次元の形状を計算する。
Protein folding has been studied since the first images of their structures were created in 1960. In 1972, Christian Anfinsen won the Nobel Prize in Chemistry for his research into the “protein-folding problem,” which involved algorithms to predict the structure of proteins. Because of the huge number of possible formations of proteins, computational studies and algorithms are better able to predict the structures. Given that a brute-force algorithm cannot solve this problem in a reasonable amount of time, computational biologists have developed algorithms that generate high-quality approximations or potential solutions that typically are not quite correct, but run in a more reasonable amount of time. Modern protein-folding algorithms, such as Google’s DeepMind AlphaFold machine-learning algorithm,4 use machine learning to identify protein-folding patterns from millions of input amino acid sequences and corresponding output 3-D conformations. Rather than utilizing a simple rule for selecting the next element to include in the solution, these machine learning algorithms learn highly complicated rulesets from subtle patterns present in the data.
英語のヒント
タンパク質の折り畳みは、その構造が1960年に初めて画像化されて以来、研究されてきた。1972年、クリスチャン・アンフィンセンは、タンパク質の構造を予測するアルゴリズムに関わる「タンパク質の折り畳み問題」の研究で、ノーベル化学賞を受賞した。タンパク質が取り得る形は膨大なため、計算による研究やアルゴリズムのほうが構造を予測しやすい。総当たりアルゴリズムでは、この問題を妥当な時間内に解けないことから、計算生物学者は、通常は完全には正しくなくても、より妥当な時間で計算できる、良質な近似解や解候補を生成するアルゴリズムを開発してきた。Google DeepMindの機械学習アルゴリズムAlphaFold4など、現代のタンパク質折り畳みアルゴリズムは、何百万もの入力アミノ酸配列と、それに対応する出力の3次元立体構造から、機械学習で折り畳みパターンを見いだす。解に次に含める要素を選ぶ単純な規則を使う代わりに、データ内の微妙なパターンから、非常に複雑な規則の集まりを学ぶ。
Improving our understanding of protein folding can lead to massive improvements only in medical health contexts such as drug and vaccine development, but also enable us to design biotechnologies such as enzymes for composting plastic waste, and even limit the impact of global warming by sequestering greenhouse gases from the atmosphere.5 In 2024, the Nobel Prize Committee recognized the impact of this work by granting the Chemistry prize to Demis Hassabis and John M. Jumper for their work on DeepMind and Alphafold6 , as well as David Baker for using a similar tool, Rosetta, to create entirely new proteins.