Algorithm - Algorithm (English spelling)

A procedure for calculations and problem solving. It is a procedure that guarantees that if you follow a set procedure, you will eventually get an answer, and that answer is correct. An example is Euclidean algorithm for finding the greatest common divisor. However, when considering the amount of calculations and memory capacity, it does not mean that it is realistically feasible. Often, NP-complete problems require resources (calculation time and memory capacity) that increase exponentially with the number of elements n , so they are often unsolvable in reality, as the calculation time is longer than the lifespan of the universe or the memory capacity is greater than the number of molecules in the universe.

Therefore, it is not enough for an algorithm to simply provide the correct answer; the problem is the amount of calculation required. For example, the best sorting algorithms for sorting large amounts of data (by size or alphabetically) are those that can be calculated on the order of n log( n ) for n elements, and in some cases n ² algorithms are also widely used.

In artificial intelligence (AI), pseudo-algorithms called heuristics are often used. These are solutions that are efficient on average, but in some cases may be incorrect or not optimal. However, they are often sufficient for daily life. For example, when searching for a route using a car navigation system, it is acceptable for the search result to be a few percent longer than the shortest route (in reality, the shortest route of the car navigation system is not necessarily the fastest, as it depends on traffic conditions).

In addition, finding the optimal solution to the "traveling salesman problem," which determines the best order in which to visit a number of cities, takes time proportional to n !, making it impossible to perform realistic calculations even for around 20 cities.

Generally, even for problems that require a huge amount of calculation, if the optimal solution is not required, there are several heuristics that can be calculated realistically. Methods for finding approximate solutions using neural networks are also known.

[Hideyuki Nakajima July 19, 2019]

Source: Shogakukan Encyclopedia Nipponica About Encyclopedia Nipponica Information | Legend

計算や問題解決の手順のこと。定められた手続に従って計算していけばいつかは答えが得られ、それが正解であることが保証されている手続である。最大公約数を求めるユークリッドの互除法などがその例。ただし計算量や記憶容量の問題を考えたときに、それが現実的に実行可能であることは意味しない。よくいわれるNP完全問題は、要素の数nに対して指数関数的に資源（計算時間や記憶容量のこと）が増加するので、計算時間が宇宙の寿命より長かったり、メモリー容量が宇宙の分子の数より大きかったりして、現実的には解けないことが多い。

　したがってアルゴリズムは正解が求められるというだけでは不足で、その計算量が問題とされる。たとえば大量のデータを整列する（大きさの順とかアルファベット順とかで並べ替える）「ソート」のアルゴリズムは、要素数nに対しnlog（n）のオーダーで計算できるものが最善であり、場合によってはn²のものも多用されている。

　人工知能（AI）などでは、ヒューリスティクスとよばれる擬似アルゴリズムが使われることが多い。これは、平均的には効率よく解を求められるが、場合によっては間違っていたり、最適の解ではなかったりすることがあるというものである。しかし、日常生活を送るうえではこれで十分なことが多い。たとえば、カーナビゲーションで経路探索を行った場合、最短経路より数％長い探索結果が出てしまうことなどは許容されるであろう（実際、交通状況に依存するので、カーナビの最短経路がもっとも早いとは限らない）。

　また、多くの都市をどの順で回れば最適かという「巡回セールスマン問題」の最適解を求めるにはn!に比例する時間がかかり、20都市程度でも現実的な計算はできない。

　一般的に計算量が膨大になる問題でも、最適解でなくてよければ、現実的に計算可能なヒューリスティクスはいくつかある。ニューラルネットワークを使って近似解を求める方法も知られている。

［中島秀之　2019年7月19日］

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