2019年10月23日

JavaScriptの情報共有

アルゴリズムwith JavaScript_2

皆さんこんにちは
今回も少しづつJavaScriptについて勉強した事を共有しようと思います。
前回の内容は簡単なアルゴリズムについてお伝えしましたが、
アルゴリズムは私たちの生活と密接なサービスにも使われています。
実際、我々はアルゴリズムに囲まれて生きている。と言っても過言ではありません。
今回は日常で使われるサービスとそのサービスを実現するアルゴリズムについて簡単に調べてみようと思います。

第一:検索アルゴリズム

日常のさまざまなアルゴリズムのうち代表的なものは検索アルゴリズムです。
例としてグーグルやヤフーなどがあります。
これらの検索サイトにキーワードを検索するとすぐにキーワードに関連するウェブページ目録が表示されます。
検索アルゴリズムとは一体どんなものなのでしょうか?
グーグルなど使う検索アルゴリズムは大部分非公開なのでそのシステムについての部分は詳しく分かりません。 しかし基本的な接近方法と言えるものはあります。

基本的なアルゴリズムが二つありますが、線形探索と二分探索です。

■線形探索
最初のアルゴリズムは線形検索です。 線形検索は、複数のデータから探そうとするデータが出てくるまで、最初から順番に検索するアルゴリズムであり、リニアサーチといいます。
このアルゴリズムには欠点がありますが、データ量が多くなるほど欲しいデータを探すまでに時間がかかるということです。

■二分探索
二つ目のアルゴリズムは、二分探索です。
二分探索は検索範囲を半分に分けて希望のデータを探すまで検索し続けるというアルゴリズムです。

その際、データはある基準に従って昇順(小さいものから順へ)や降順(大きいものから順へ)に並べ替えられていなければなりません。

線形検索より効率的なアルゴリズムですが、二分探索はデータの大小関係を利用するため、並べ替えのないデータや大小関係が定義されないデータは検索できないのが欠点です。

第二:敬老アルゴリズム

経路を探す時、グーグル地図など地図サービスを使いますよね。
当たり前のように利用しているサービスでしょうが、これも経路検索アルゴリズムを使います。

経路検索とは、出発地点から到着地点に到達するまでの経路を発見する処理を言います。
グーグルマップなどの地図で経路を検索すると様々な経路候補が表示されますが、このように最短経路だけでなくコストが2番目、3番目の経路を検索することも非常にレベルの高いアルゴリズムが必要です。

ここで私たちは簡単に最短経路を求める有名なアルゴリズム、デイストラアルゴリズムがありますが、デイストラアルゴリズムは近い問題から次々に解決し、解決された結果を元に次の問題を解決するアルゴリズムです。

今日は簡単に生活で使うサービスを元にするアルゴリズムについて調べてみました。
文字だけで説明していては理解しにくい部分もあるので気になったら検索して絵を見ることをお勧めします。
今回はここまでアルゴリズムの勉強す共有を終わります。
長文を読んでくださってありがとうございます。