Dynamic Programming

A technique for solving search problems. When different solutions in the search space have a common subproblem, the solution of the subproblem is stored in memory to increase efficiency by preventing the same subproblem from being solved repeatedly. For example, when searching for the shortest route from Tokyo to Fukuoka, the shortest route from Osaka to Fukuoka is obtained as a result of searching a certain route (solution of the subproblem). In this case, if you reach Osaka while searching for another route, you do not need to calculate the shortest route to Fukuoka again because you already know it. This is the basic idea of ​​dynamic programming. Even if the same subproblem appears combinatorially and would take exponential calculation time with simple depth-first search or breadth-first search algorithms, dynamic programming can sometimes calculate it in polynomial time, which is extremely effective. Dijkstra's algorithm, a well-known algorithm for finding the shortest route in a graph, is a good example of dynamic programming.

[Hiroshi Maruyama April 16, 2019]

Source: Shogakukan Encyclopedia Nipponica About Encyclopedia Nipponica Information | Legend

探索問題を解くための技法の一つ。探索空間中の異なる解が共通の部分問題をもつ場合に、その部分問題の解をメモリー上に蓄えることによって、同じ部分問題が繰り返し解かれないようにすることで効率をあげる。たとえば、東京から福岡までの最短経路を求める際、ある経路の探索の結果、大阪から福岡までの最短経路が得られたとする（部分問題の解）。この場合、別の経路の探索中に大阪に達したら、その後福岡までの最短経路はすでにわかっているので、あらためて計算する必要がない。これが動的計画法の基本的な考え方である。同じ部分問題が組合せ的に現れるために、単純な深さ優先探索や幅優先探索アルゴリズムでは指数関数的な計算時間がかかる場合でも、動的計画法によって多項式時間で計算できることがあり、その効果は絶大である。グラフの最短経路を求めるアルゴリズムとしてよく知られるダイクストラ法は、動的計画法のよい例である。

［丸山　宏　2019年4月16日］

出典　小学館　日本大百科全書(ニッポニカ)日本大百科全書(ニッポニカ)について　情報 | 凡例