第3章データ構造とアルゴリズム
INDUSTRY SPOTLIGHT産業の現場から
Delivery Logistics配送の物流
Companies such as Amazon, FedEx, UPS, and others that rely on logistics to deliver goods to various locations seek to optimize the sequence of stops to save costs. The only way to achieve this would be to rely on an optimal algorithm for the traveling salesperson problem. The TSP aims to find the minimum distance tour that visits all the vertices such that no vertex is visited more than once. But this is not a perfect match for real-world delivery logistics. Fuel or battery efficiency, for example, is not just about distance traveled, but also the speed of travel, the time spent idling, and even the way that the route is organized. In the United States, where vehicles drive on the right side of the road, safety can be improved by reducing the number of left-hand turns across the divider. Drivers might also want to take breaks during a trip. Modeling all these factors requires carefully formulating the problem and considering the limits of TSP.
英語のヒント
Amazon、FedEx、UPSなど、さまざまな場所への商品の配送を物流に頼る企業は、費用を節約するため、立ち寄る順番を最適化しようとする。これを実現する唯一の方法は、巡回セールスマン問題の最適なアルゴリズムに頼ることであろう。TSPは、どの頂点も2回以上訪れずに、すべての頂点を訪れる、最小距離の巡回路を求める。しかし、これは現実の配送物流に完全には一致しない。たとえば燃料や電池の効率は、移動距離だけでなく、速度、アイドリング時間、経路の組み方にも左右される。車両が右側通行する米国では、道路の中央の分離部分を横切る左折を減らせば、安全性を高められる。運転者は途中で休憩したいかもしれない。これらの要因をすべてモデル化するには、問題を慎重に定式化し、TSPの限界を検討する必要がある。
How do we know if a problem is NP-complete? Earlier, we introduced reduction as an algorithm paradigm that is not only useful for solving problems, but also for relating the difficulty of problems. A reduction from a difficult problem A to another problem B proves that B is as difficult as A. It turns out that all NP-complete problems can be reduced to all the others, so an algorithm for solving any NP-complete problem solves every NP-complete problem.
英語のヒント
問題がNP完全かどうかは、どうすればわかるだろうか。先に、問題を解くだけでなく、問題の難しさを関連付けるのにも役立つアルゴリズムの考え方として、帰着を紹介した。難しい問題Aから問題Bへの帰着は、BがAと同じくらい難しいことを証明する。実は、すべてのNP完全問題は互いに帰着できる。そのため、どれか1つのNP完全問題を解くアルゴリズムは、すべてのNP完全問題を解く。
LINK TO LEARNING学習リンク
The longest paths problem and the traveling salesperson problem are just two examples of NP-complete problems. Visit A Graph of NP-Complete Reductions (https://openstax.org/r/76NPCompReuct) to visualize many NP-complete problems and their relationships to each other. For example, the longest paths problem (LPT) and the traveling salesperson problem (TS) both reduce to Hamiltonian paths (HP). In turn, Hamiltonian paths (HP) reduce to vertex cover (VC) which reduces to 3-satisfiability (3-SAT).
英語のヒント
最長経路と巡回セールスマン問題は、NP完全問題の2つの例にすぎない。「NP完全問題の帰着のグラフ」（https://openstax.org/r/76NPCompReuct）で、多くのNP完全問題と、その相互関係を可視化してみよう。たとえば最長経路問題（LPT）も巡回セールスマン問題（TS）も、ハミルトン路（HP）へ帰着する。続いて、ハミルトン路（HP）は頂点被覆（VC）へ、頂点被覆は3充足可能性（3-SAT）へ帰着する。
P versus NPP対NP
Longest paths and TSP are just two among thousands of NP-complete problems for which we do not have efficient algorithms. The question of P versus NP asks whether it is possible to design a deterministic polynomial-time algorithm for solving any—and therefore all—of NP-complete problems. There are two possible answers to the question of P versus NP:
最長経路とTSPは、効率的なアルゴリズムのない数千のNP完全問題のうち、2つにすぎない。P対NP問題は、NP完全問題のどれか1つ、したがってすべてを解く、決定性多項式時間アルゴリズムを設計できるかを問う。答えには、次の2つの可能性がある。
• If P = NP, then there is a deterministic polynomial-time algorithm for solving all NP-complete problems.
・P = NPなら、すべてのNP完全問題を解く、決定性多項式時間アルゴリズムが存在する。
• If P ≠ NP, then there are NP-complete problems that cannot be solved with a deterministic polynomial-time algorithm.
・P ≠ NPなら、決定性多項式時間アルゴリズムでは解けないNP完全問題が存在する。
Most theoretical computer scientists believe that P ≠ NP; in other words, it is impossible to design a deterministic polynomial-time algorithm for longest paths, TSP, or any other NP-complete problem. However, they do not have any definite proof that P = NP or P ≠ NP. An efficient algorithm for any one NP-complete problem would not only directly solve routing and logistics problems but would also enable massive advancements in drug discovery through scientific simulation, for instance. It would also break essentially all modern Internet security and password systems—among thousands of other problems.
英語のヒント
理論計算機科学者の多くは、P ≠ NPだと考えている。言い換えると、最長経路、TSP、その他のどのNP完全問題に対しても、決定性多項式時間アルゴリズムを設計するのは不可能だと考えている。しかし、P = NPとP ≠ NPのどちらにも、確かな証明はない。NP完全問題のどれか1つに効率的なアルゴリズムが見つかれば、経路や物流の問題を直接解くだけでなく、たとえば科学的シミュレーションによる創薬も大幅に進められるだろう。また、現在のインターネットのセキュリティーやパスワードのシステムを、事実上すべて破ることにもなる。これらを含め、数千もの問題に関わる。