「もう休日出勤せずに済む」計画業務の意思決定を支援し、属人化からの脱却を実現する「数理最適化AI」とは？
https://jbpress.ismedia.jp/articles/-/89259

『　製造、物流、小売、サービス業など、あらゆる業種で「計画立案」の難易度が高まっている。
特に製造業では、多品種少量生産、短納期生産への対応、事業環境やニーズの急変などにより、生産計画立案がかつてなく複雑となっている。

その結果、従来の経験と勘に頼った属人的な計画手法では限界を迎えつつあり、需給の不一致、在庫の偏重、利益圧迫といった経営課題が顕在化している。

このような課題を解決するために、日立システムズでは「数理最適化」と呼ばれる技術をコアエンジンに据えたサービスを開発している。
そのコンセプトを、2人のキーパーソンに聞いた。

生産計画が抱える“構造的な3つの課題”

　日本の製造業は、高品質な製品を製造する現場における精度の高い作業や、技術革新の取り込み、環境保全などで世界をリードしている。
　
　しかし、その製造業の強みを左右するのは、技術や設備だけではない。「いつ・何を・どれだけ作るか」という計画の質が、利益やリードタイム、現場の安定性に直結する。

　しかし今、その計画立案こそが、最も複雑化・硬直化している業務の一つとなっている。
　
　日立システムズの水内武氏は、現在の生産計画の現場には3つの課題があると指摘する。

　1つ目は計画立案作業の長時間化だ。
　
　営業部門の販売見込みの急な変更や、調達部門での部材納入のミスや遅延、工場現場の設備トラブルや人員都合による突発的な変更要請など、複数部門との調整で生産計画は何度も見直しを余儀なくされ、要件をまとめるのに数日～数週間を要することもある。

　2つ目は属人化の課題である。
　
　ベテランの経験則や必要なデータがブラックボックス化し、「なぜこの計画になったのか」という判断基準が不明確になっている。
　属人化の弊害は単なる引き継ぎリスクにとどまらない。
　ベテランがリタイアすれば同じ観点での計画立案ができなくなり、組織の柔軟な対応力を損なう要因にもなる。再現性のない意思決定は、組織の機動力を奪うことにもなる。

　そして3つ目が、市場環境の変化に計画が追いつけていない点だという。

「かつての大量生産時代は、単一の計画から多くの製品を生み出せました。

しかし今日では、多品種少量生産へのシフト、需要変動の激化、短納期要求など、市場環境が激変しています。

従来型のExcelや手作業ベースの計画手法では、もはやこの変化に追従できません。

結果として現場の混乱や納期遅延が常態化し、経営への影響は無視できないレベルに達しています」（水内氏）

　同社データサイエンス・エキスパートの中山貴博氏も続ける。

「製品の多品種化が進む中で、生産計画に求められる判断の粒度が年々細かくなっています。

例えば400種類の製品を30日間で生産する場合、それだけで12,000通りの意思決定が必要になります。
もはや人手だけでは限界を超えつつあります」

　生産計画業務は多くの場合、工場長やライン長など現場のキーパーソンが、本業の合間を縫って対応している。
　複雑な生産計画の立案をこなすため、残業や休日出勤などが常態化し、属人的な経験と勘に頼ったブラックボックス化も進みつつある。

　この属人性こそが、計画の精度を低下させ、生産現場に混乱をもたらし、最終的には経営損失へとつながる負の連鎖の起点となっている。
　
　また、納期遅延や品質リスク、製品コストの上昇など影響は多岐にわたる。もはや計画業務は企業全体に関わる「経営課題」へと変質している。

　多くの製造業がこの構造的な問題に気づき、今まさに“新しい計画のかたち”を模索し始めている。

人の経験を超え、意思決定の質を高める──「数理最適化」という革新

　これまで多くの製造業では、生産計画業務の効率化を目的に、“生産スケジューラー”という名のパッケージの導入が行われてきた。
　
　しかし水内氏の元へは「スケジューラーを導入したが、うちの現場には合わない」という声が多く届いていた。

　一見便利に見えるスケジューラーだが、その仕組みには限界がある。

　水内氏はその理由をこう話す。
　
　「従来のスケジューラーは、現場の作業ルールをある程度自動化するツールとして有効ですが、複雑な制約条件やイレギュラーな判断が必要な場面では限界があります。
　
　結果として、『実行可能だが現実的でない』計画が出力されるケースも多く、最終的な計画の精度はやはり人の経験に依存せざるを得ません。
　
　私たちは、計画の根幹を担う『どの製品を、いつ、どれだけ生産するか』という意思決定そのものを、数理的にモデル化・自動化することで、属人性を超えた計画精度と柔軟性を実現できると考えました」

　そこで同社は、「人の判断を支援する」のではなく、「人の経験を数理的に再現・超越する」アプローチを模索した。
　
　数理最適化技術を中核に据え、現場の複雑な制約条件やルールを数式でモデル化し、最適な生産計画を導き出す「生産計画最適化支援サービス」を開発した。

提供：日立システムズ
拡大画像表示

　このサービスでは、顧客企業に蓄積された生産計画のルールやノウハウを徹底的にヒアリングし、それを同社の数理最適化モデルに取り込む。
　
　さらに、システムによる生産計画の提示と意思決定支援、そして導入後の伴走支援まで一体化したサービスである。

人間力と高度な技術力で生成AIや生産スケジューラーとは異なる価値を生みだす

　特に心臓部となる「数理最適化AI」とは何か、中山氏は説明する。

「計画業務におけるルールをお客様にヒアリングし、その要件を当社のデータサイエンティストが数学の連立方程式として記述します。
方程式の数はお客様によって異なりますが、数千～数万にも達することもあります。

それらの膨大な連立方程式を、ソルバーと呼ばれる専用のソフトウェアによって解くことで、最適な生産計画を導きます」

　日本語で表現される生産ルールを連立方程式に翻訳し、ソルバーで解くことで、計画立案を自動化する。
　生成AIに方程式へ翻訳させるアイデアもあるが、高度な数学的知識が求められることから、現在の生成AIの技術水準ではまだ難しい実情がある。
　ここで日立システムズのデータサイエンティストたちが技術力を発揮する。

「数理最適化AIと生成AIは、共に広い意味でAIとして括られますが、両者はそれぞれ得手不得手があります。

生産計画のように明確な判断が求められる領域では、いわゆるハルシネーションのような不確実性を含む生成AIではなく、数理最適化AIが有効です。

そして数理最適化AIの実装には、人の力が必要不可欠です」（中山氏）

拡大画像表示

　つまり本サービスでは、いかに多く顧客の生産計画の決まりごとや慣習を聞き取って、それを数式に落とし込むかが精度のカギを握ることになる。
　
　水内氏はヒアリングにおけるポイントをこう語る。

「お客様に、生産計画における困りごとを、当社が何も知らないゼロのところから伺っていきます。
生産計画において資料があるケースもありますが、資料にはない“現場ならではの判断”やお客様自身も気づかれていないルールも多く存在します」

　企業によって生産計画策定の手順、ルールはさまざまだ。話が脱線したとしても、すべて聞き取って、持ち帰って整理する。その繰り返しが信頼につながり、精度向上の鍵になるという。

「明言されたルールは数式に翻訳できますが、お客様の頭の中にある全てのルールを一度に言語化するのは困難です。

実際に、お話が盛り上がってくると次々と課題が挙がってきます。
発散気味になる内容でもいったんは全て受け止めて、持ち帰って論点を整理しながら数式として記述します」（中山氏）

　ただし、生産のルールを数式化するためには、聞いたことだけを反映させれば完了するわけではない。
　
　人間が一般的に当然と思っている決まりごと、例えば1分＝60秒、1ダース＝12個といった情報も、全て取り込まなければ、最適解は計算できない。

「1回のヒアリング内容を基に最適化モデルのプロトタイプを作成し、お客様に見ていただきます。

そこから、隠れていたルールを浮かび上がらせ、数式を調整して精度を上げていきます」（中山氏）

　こうした地道な活動によって、本サービスは生成AIや生産スケジューラーなどとは一線を画す価値を顧客に提供している。

必要生産量と実際生産量の月次差異を77.9%減少

　すでに本サービスを導入し、生産計画プロセスの大幅な効率化と精度の向上を実現している企業が存在する。

　食品メーカーのA社は、約300種類のパック食品を製造、販売している。同社の営業は、各製品の販売見込み数を生産部門に伝え、工場長はそれに基づいて各製品の月別生産計画を立案する。
　品種が多く生産計画は複雑なため、必要な生産量と実際の生産量との間に大きな差が生じ、販売機会の損失を生じていた。

　当初、同社ではこの課題を解決するため、パッケージ製品の生産スケジューラーを導入する検討を行った。
　
　しかしスケジューラーでは、前提となる業務パターンが限定的で同社の複雑な制約条件に対応できず、導入を断念。日立システムズの「生産計画最適化支援サービス」であれば複雑な条件にも対応できると判断し、導入プロジェクトがスタートした。

　PoC（実証実験）では、数理最適化モデルのプロトタイプを作成した。
　
　まず、日立システムズが工場長にヒアリングを実施し、計画手順や制約条件を詳細に確認した。
　それらの情報がデータサイエンティストによって数式化され、その数式を数理最適化モデルに登録していった。

　そのうえで、工場長が自ら作成する計画と、数理最適化AIによる計画との精度の比較を繰り返し、数式のチューニングを進めた結果、PoC開始から約3カ月で、工場長が作る計画を上回る精度を実現した。

　このプロトタイプによって、工場長が5時間かけて行っていた計画業務は30分に短縮された。
　
　また、人の手では2週間分の計画が限界だったのに対し、3カ月先までの計画を可能にした。
　
　当初の課題であり、開発のKPIに設定していた必要生産量と実際の生産量の差は、約7.2万ケース/月から1.5万ケース/月へ、77.9％の大幅減少を実現した。
　
　このようにPoCは予想を大きく上回る成果を挙げ、同社は生産計画最適化支援サービスの本番導入を決定した。

提供：日立システムズ
拡大画像表示

　PoC開始から1年後に本番運用がスタートし、そこからさらに1年が経過している。
　
　これまで工場長1人に依存していた計画業務を、部下が担当できるようになり、工場長は製品品質向上などの業務に注力できるようになった。
　
　また、必要な数量に合わせた生産計画が立案できるため、在庫回転率の向上や保管費の削減などの効果も期待されている。
　
　本番稼働後の運用フェーズにおいても、日立システムズが伴走しながら現場への定着を手厚くサポートしており、導入から運用まで一貫した支援体制を提供している。

　本事例に続く形で、すでにいくつかの企業でPoCが進んでいるという。

「計画」と名が付くあらゆる業務に適用可能

　今後の展開として日立システムズでは、まずはこの「生産計画最適化支援サービス」を、広く製造業の生産計画業務に使ってほしいと考えている。

「生産計画にはお客様固有のルールが存在し、1つのケースをそのまま横展開することはできません。

これが従来のスケジューラーの導入が困難だった理由であり、本サービスが価値を発揮する理由でもあります。

また、数理最適化には運用の難しさもありますが、開発段階で運用を想定することで、実稼働に耐えうるサービスを構築することを重視しています。

例えばInfeasible（実行不能）と呼ばれる特有のエラーがあり、業務停止につながるのですが、このエラーを自動的に解消する技術を発明（特許出願中）し、実際に運用する中で業務停止を未然に防止しております。

こうした取り組みが、当社のサービスの独自性を際立たせ、他にはできない計画のレベルに持っていけると考えています」と中山氏は語る。

　さらに、生産計画最適化支援サービスの思想は、他の領域にも展開できる。
　
　確かに、仕事を見渡せば、生産計画と同様、これまでアナログ作業、職人芸的な個人の能力に頼ってきた計画業務はいくつもある。
　
　それらに本サービスを応用することで、計画の精度向上と、効率化による担当者の慢性的な長時間労働を解消できる可能性は高い。

「要員、在庫発注、配送など、複雑な制約条件がある計画業務は他にもたくさんあります。
将来的には幅広い業務に展開していきたいと考えています」（水内氏）

「お客様のご要望を数式に翻訳する過程で、全く異なる業務の間に数学的な構造の共通性を発見し、テクニックを流用できるケースがあります。
それがデータサイエンティストとしての仕事の醍醐味でもあります」（中山氏）

　顧客の声に耳を傾け、暗黙知まで引き出す傾聴力。複雑な業務ルールを数式に変換する技術力。日立システムズはこれらの強みを活かし、「数理最適化AI」という新たなアプローチで計画業務の属人化からの脱却に挑み続ける。

日立システムズへのお問い合わせはこちら
生産計画最適化支援サービスの詳細・お問い合わせはこちら

＜PR＞』

【技術解説】マルコフモデルと隠れマルコフモデル
https://mieruca-ai.com/ai/markov_model_hmm/

『2018-05-30

執筆：金子冴

今回はマルコフモデルと，マルコフモデルを拡張した隠れマルコフモデルを題材に，それぞれのモデルの解説と2つのモデルの違いについて解説する．

まずはマルコフモデルについて解説しよう．

目次

マルコフ過程とは
マルコフ過程の分類とマルコフ連鎖について
隠れマルコフモデルとは
マルコフモデルと隠れマルコフモデルの違い(応用例)
参考

マルコフ過程とは

マルコフモデルを説明すると言っておきながら，見出しがマルコフ過程となっていることに疑問を抱く人もいるだろう．一般的にマルコフモデルといった場合，マルコフ過程を指す．それでは，マルコフモデル改め，マルコフ過程の概要を確認しよう．

マルコフ過程の概要

“マルコフ過程（マルコフかてい）とは、マルコフ性をもつ確率過程のことをいう。すなわち、未来の挙動が現在の値だけで決定され、過去の挙動と無関係であるという性質を持つ確率過程である。” ? マルコフ過程(wikipedia)

上記の概要にある確率過程とマルコフ性については，定義を確認する必要があるだろう．初めに確率過程について確認する．

確率過程とは
確率過程とは何を指すのだろうか．まずはwikipediaを確認しよう．

“確率論において、確率過程（かくりつかてい、英語: stochastic process）は、時間とともに変化する確率変数のことである。 株価や為替の変動、ブラウン運動などの粒子のランダムな運動を数学的に記述する模型（モデル）として利用している。不規則過程（英語: random process）とも言う。” ? 確率過程(wikipedia)

wikipediaの言葉を借りれば，確率過程とは時間と共に変化する確率変数を指すらしい．では確率変数とは何なのか．

wikipediaによると，確率変数とはランダムな実験により得られ得る全ての結果を指す変数との記述がされていた．私たちがよく使う確率は一義的に値が決まるのとは違い，確率変数は確率に従って定義域内の様々な値を取ることができる．簡単に言い直すと，確率変数は確率を決めるときに利用する数である．

例を挙げて確率変数を理解しよう．

確率変数の例としてよく使われるのはサイコロである．今回は，1から6の目がある6面体のサイコロを考える．この時，出目の取りうる値，つまり確率変数XはX={1,2,3,4,5,6}と表される．他にもコイントスの例を考えてみると，コイントスの結果は「表」「裏」の2択のため，「表=1」「裏=0」と定義した場合，確率変数XはX={1,0}と表せる．

では，確率過程の説明に戻ろう．

定義では，確率過程とは時間と共に変化する確率変数となっていた．先ほど挙げたサイコロやコインの例は，この確率過程に当てはまらないことはわかるだろう．なぜなら，サイコロの目やコインの表裏は時間と共に変化しないからである．ここでいう「時間と共に変化」とは，サイコロを振って出目を確認した後，その1秒後にもう一度見たら出目が変わっているようなことを指す．

確率過程について，例を挙げてみよう．

確率過程の例には，株価の変動が挙げられる．ここで，株価が500円以上の確率が0.4，500円未満の確率が0.6である状況を仮定しよう．この場合，確率はある時点での株価によって決まるが，株価は時間と共に刻一刻と変わっていくため，時間によって確率は変動する．このように時間で変化する確率変数を確率過程と呼ぶ．

確率過程についてはご理解いただけただろうか．ここで，確率過程の定義には出現していないが，確率分布についても解説しておこう．確率分布は，その次に解説するマルコフ性の定義に出現しているため事前に理解しておく必要がある．

確率分布とは

確率分布のwikipediaを確認すると，以下のように説明されている．

“確率分布（かくりつぶんぷ, 英: probability distribution）は、確率変数の各々の値に対して、その起こりやすさを記述するものである。” ? 確率分布(wikipedia)

確率分布には確率変数が離散的な場合と確率変数が連続的な場合が存在するが，ここでは離散的な場合を考える．連続的な場合を理解するためには測度の概念等が必要となるため，ここでは割愛する．
理想的な6面サイコロを考えてみよう．ここでいう理想的とはすべての出目(つまり確率変数)の出る確率が同じことを指す．サイコロには6面存在し，すべての出目が出る確率が同じ場合，各出目の出る確率は1/6となるため，X={1,2,3,4,5,6}とした時，確率分布PXは以下のようになる．

P
(
X

)

1
6
少し難しい例として，理想的な6面サイコロを2回投げた時の出目の和の確率分布を考えてみよう．
出目の和と出目のパターン，その確率は以下の図のようになる．このときの確率の分布を表したものが確率分布となり，確率変数が離散的な場合にはヒストグラムで表されることが多い．

併せて，条件付き確率分布についても簡単に確認しておこう．

条件付き確率分布とは

条件付き確率分布とは事象が2つ存在する場合に一方の事象が発生した場合の，もう一方の事象が発生する確率の分布を指す．

事象Aと事象Bについて，事象Aが発生したときの事象Bの条件付き確率P(B|A)は以下の式で定義される．
この条件付き確率の分布を表したものが，条件付き確率分布である．

P
(
B
|
A

)

P
(
A
∩
B
)
P
(
A
)
確率分布，条件付き確率分布についても理解できたところで，次はマルコフ性について確認しよう．

マルコフ性とは

マルコフ性について，wikipediaで定義を確認しよう．

“マルコフ性（マルコフせい、英: Markov property）とは、確率論における確率過程の持つ特性の一種で、その過程の将来状態の条件付き確率分布が、現在状態のみに依存し、過去のいかなる状態にも依存しない特性を持つことをいう。すなわち、過去の状態が与えられたとき、現在の状態（過程の経路）は条件付き独立である。” ? マルコフ性(wikipedia)

確率過程X(t)についてt>0がマルコフ性を持つとき，数学的に以下の式が成り立つ．

P
r
[
X
(
t
+
h

)

y
|
X
(
s

)

x
(
s
)
,
∀
s
?
t

]

P
r
[
X
(
t
+
h

)

y
|
X
(
t

)

x
(
t
)
]
,
∀
h
>
0
この式からわかる通り，X(t+h)の確率分布はs<tとなるすべてのsの事後確率ではなく，直前(t)のみの事後確率として定義される．

例えば，天気がマルコフ性を持つ場合を仮定してみよう．

一般的に，翌日の天気は今日までの雲の動きを参考に予測される．つまり，翌日の天気を予測するためには，昨日以前の天気の情報も利用する必要がある．しかし，天気がマルコフ性を持つ場合，明日の天気は今日の天気にのみ左右される(昨日より前の天気は関係ない)ため，昨日以前の天気の情報を利用する必要がなくなる．

マルコフ性について理解できただろうか．
それでは，これまでの知識からマルコフ過程のまとめをしよう．

マルコフ過程のまとめ

『マルコフ過程の概要』の項で確認した通り，マルコフ過程はマルコフ性をもつ確率過程のことをいう．マルコフ性は将来(次の)状態の条件つき確率分布は現在状態のみに依存する性質を指し，確率過程は時間と共に変化する確率変数を指す．

マルコフ過程(マルコフモデル)については理解できただろうか．2つ目の大きな題材である隠れマルコフモデルについて解説する前に，マルコフ過程の分類について確認したい．そうすることで，隠れマルコフモデルがより理解しやすくなるためである．
それでは，マルコフ過程の分類とマルコフ連鎖について解説しよう．

マルコフ過程の分類とマルコフ連鎖について

まずは，マルコフ過程の分類について確認しよう．

マルコフ過程の分類

マルコフ過程は以下の7つに分類される．

◆単純マルコフ過程
現在状態のみから将来状態が決定されるマルコフ過程のこと．単にマルコフ過程と呼ぶ場合は，この単純マルコフ過程を指している場合が多い．

◆N階(N重)マルコフ過程
連続したN個の状態から将来状態が決定されるマルコフ過程のこと．N=1のとき，単純マルコフ過程を指す．また，N個の状態を現在状態と定義しなおすことにより，単純マルコフ過程として表現することも可能である．

◆離散時間マルコフ過程
時刻tが離散的な場合のマルコフ過程のこと．一般的に時刻の集合はT={1,2,3,…}と定義する．

◆連続時間マルコフ過程
離散時間マルコフ過程と違い，時刻tが連続的な場合のマルコフ過程のこと．時刻の集合をT=[0,∞)等と定義する．

◆離散マルコフ過程
マルコフ過程の状態空間が離散集合であるマルコフ過程のこと．つまり，状態が離散的でありマルコフ性が成り立つようなマルコフ過程を指す．

◆連続マルコフ過程
離散マルコフ過程と違い，マルコフ過程の状態空間が連続的であるマルコフ過程のこと．
◆時間的に一様なマルコフ過程
状態の推移確率が時間に依らず一定であるようなマルコフ過程のこと．

では，この分類を元にマルコフ連鎖の概要をwikipediaで確認しよう．

マルコフ連鎖の概要

“マルコフ連鎖（マルコフれんさ、英: Markov chain）とは、確率過程の一種であるマルコフ過程のうち、とりうる状態が離散的（有限または可算）なもの（離散状態マルコフ過程）をいう。また特に、時間が離散的なもの（時刻は添え字で表される）を指すことが多い（他に連続時間マルコフ過程というものもあり、これは時刻が連続である）。

マルコフ連鎖は、未来の挙動が現在の値だけで決定され、過去の挙動と無関係である（マルコフ性）。

各時刻において起こる状態変化（遷移または推移）に関して、マルコフ連鎖は遷移確率が過去の状態によらず、現在の状態のみによる系列である。” ? マルコフ連鎖(wikipedia)
概要にもある通り，マルコフ連鎖とはマルコフ過程のうち状態が離散，かつ時間が離散なものを指す場合が多い．分類では離散時間マルコフ過程，離散マルコフ過程に該当するマルコフ過程がマルコフ連鎖に該当する．

次にマルコフ連鎖の定義について確認する．

マルコフ連鎖の定義

マルコフ連鎖の定義は，マルコフ性の定義とよく似ている．違うのは時刻が離散的であることより，時刻を添え字で表している点である．

ここで，確率変数Xiの取りうる値は連鎖の状態空間と呼ばれる．マルコフ連鎖は有向グラフで表され，グラフの各ノードは確率変数，エッジはノード間の遷移確率を表す．

P
r
(
X
n
+

1

x
|
X

n

x
n
,
…
,
X

1

x
1
,
X

0

x
0

)

P
r
(
X
n
+

1

x
|
X

n

x
n
)
ここで，代表的なマルコフ連鎖である単純マルコフ連鎖とN階マルコフ連鎖について確認しよう．

単純マルコフ連鎖とN階マルコフ連鎖

ここでいう単純とは，将来状態が現在状態のみから決まることを指す．つまり『マルコフ連鎖の定義』の項で紹介した定義式こそ，単純マルコフ連鎖を表す式である．

対してN階とは，将来状態が現在状態を含むN個の状態から決まることを指す．その場合，定義式は以下のようになる．

P
r
(
X
n
+

1

x
|
X

n

x
n
,
…
,
X

1

x
1
,
X

0

x
0

)

P
r
(
X
n
+

1

x
|
X

n

x
n
,
X
n
?

1

x
n
?
1
,
…
,
X
n
?
N
+

1

x
n
?
N
+
1
)

単純マルコフ連鎖について，少し掘り下げて理解していこう．

例として，マルコフ連鎖上で成り立つ天気が以下の状態遷移図で表される場合を考える．ここで，各ノードは天気，エッジはある天気からある天気への遷移確率とする．例えば，以下の図でいえば「晴れ」からそれぞれの天気に遷移する確率は，「晴れ」が50%，「曇り」が約33%，「雨」が約16%となる．

この状態遷移を行列W(Weatherの頭文字)として表現すると以下のようになる．

あるタイミングtでの天気をwtT=(x1,x2,x3)と表現するとしよう．ここで，x1は晴れの確率，x2は曇りの確率，x3は雨の確率とする．上付き文字のTは転置を表しているため，実際のwtは3行1列の行列である．

現在観測できている時刻tの天気が晴れの場合，wtT=(1,0,0)となる．

次の時刻t+1の天気wt+1が知りたいときは，状態遷移行列Wと現在の天気wtをかけ合わせることで求められる．

つまり，wt+1=W・wt=(1/2,1/6,1/6)となるため，次の日が「晴れ」の確率が50%，「曇り」の確率が約16%，「雨」の確率が約16%であるとわかる．

次に，時刻t+2の天気が知りたいときは，状態遷移行列Wと時刻t+1の天気wt+1をかけ合わせればよい．

つまり，wt+2=W・wt+1=W・W・wt=(1/3,2/9,2/9)となる．

ここから，初期状態の天気をw0とすると，ある時刻tの天気はwt+n=Wn・wtで計算できることがわかる．

上記のWnをt→∞として求めると，状態遷移の定常分布を求めることができる．

定常分布とは，無限回遷移した場合にそれぞれの状態にたどり着く確率のことを指す．

ここでは計算を割愛するが，今回の例で定常分布を求めると，無限回遷移したときにそれぞれの天気になる確率がわかる．このように，単純マルコフ連鎖の定常分布は状態遷移を行列に表すことで容易に計算することが可能となる．

単純マルコフ連鎖については理解いただけただろうか．それでは，本題の隠れマルコフモデルについて解説しよう．

隠れマルコフモデルとは

名前からわかる通り，マルコフモデルとは違い隠れマルコフモデルは何かが隠れているのだろうと推測できる．では，何が隠れているのだろうか？

ではいつも通り，まずは隠れマルコフモデルの定義を確認しよう．

隠れマルコフモデル(Hidden Markov Model;HMM)の概要

“隠れマルコフモデル（かくれマルコフモデル、英語: Hidden Markov Model）は確率モデルのひとつであり、観測されない（隠れた）状態をもつマルコフ過程である。” ? 隠れマルコフモデル(wikipedia)

単純マルコフ連鎖では状態が直接観測可能であったため，状態の遷移確率のみをパラメータとしていた．

一方，隠れマルコフモデルにおいては状態が直接観測されず，出力のみが観測される．

ここで確認しておきたいのは，「状態」と「出力」の違いである．先ほどまで用いていた天気の例では，「状態(=晴れ，曇り，雨)」がそのまま「出力」となっているため，隠れマルコフモデルの説明には適さない．

ここでは，新たに例を挙げて，隠れマルコフモデルについて確認しよう．

あるところに散歩が好きな一人暮らしのマルコフ少年と，マルコフ少年の母のマルコフ母がおり，2人が住む場所はとても遠いと仮定する．

マルコフ少年は自分の住んでいる街の天気を元に，散歩をどうするか(「長距離」，「短距離」，「散歩なし」)を決めており，その結果のみを毎日マルコフ母に電話している．

なお，マルコフ少年が散歩する確率は，マルコフ少年の住む街の天気によって以下のように決定する．

また，マルコフ少年の住む街の天気は以下のように状態遷移するとしよう．

このとき，マルコフ母はマルコフ少年が住む街の天気(状態)を知ることができないため，隠れた状態となっている．しかし，マルコフ少年の散歩の結果(出力)は知ることができる．

このようなモデルのことを，隠れマルコフモデルと呼ぶ．

隠れマルコフモデルでは，パラメータとして遷移確率と出力確率の2種類をとる．

遷移確率とは，状態から状態に遷移する確率を表し，上記の例でいえば天気の状態遷移確率がこれに当たる．出力確率とは，ある状態で出力が得られる確率を表し，上記の例でいえば「晴れの時に長距離散歩する確率」や「雨の時に散歩しない確率」がこれに当たる．
隠れマルコフモデルから可能な推定

隠れマルコフモデルから推定可能なものとその際に使用するアルゴリズムを紹介する．

「状態」の推定

最も想像しやすいのは，隠れマルコフモデルで隠されている「状態」の推定であろう．今回の例でいえば，マルコフ少年が住む街の天気の状態遷移確率，天気と散歩の関係(確率)，マルコフ少年が報告した散歩の結果から，マルコフ母がマルコフ少年の住む街の天気を推測する．

その際にはビタビアルゴリズムという動的計画法の一種であるアルゴリズムが使用され，取りうる状態のパターンから最も尤もらしいパターンを選び出すことができる．

パラメータ(遷移確率と出力確率)の推定

隠れマルコフモデルでは，「出力」から遷移確率と出力確率を推定することも可能である．その際にはバウム＝ウェルチアルゴリズムというフォワードバックワードアルゴリズムの一種であるアルゴリズムが採用され，主に音声や遺伝子などの系列データを解析するために使用される．

最後に，マルコフモデルと隠れマルコフモデルの違いについて，応用例をもとに確認しよう．

マルコフモデルと隠れマルコフモデルの違い(応用例)

マルコフモデルの応用例

マルコフモデルは，天気予報や証券の取引の場面に応用されている．天気予報の分野では，例に挙げた通り状態遷移行列を用いてn日後の天気wt+nが推測できることを確認した．また，定常分布を計算して求めることで，限りなく未来の天気について，それぞれの天気になる確率を求めることができる．

また，Googleで使用されている，ウェブページの重要度を決定するアルゴリズムであるPageRankでもマルコフモデルが使用されている．これも天気と同様にユーザが各ページに遷移する確率から定常分布を求めることで，最後にユーザが開いているページを推測し，重要度を決めている．

このように，マルコフモデルでは「状態」と「出力」が判明しているため，状態遷移行列から無限遷移後の存在確率を求めることが可能である．

隠れマルコフモデルの応用例

マルコフモデルと隠れマルコフモデルの違いといえば，「状態」が隠れているかいないかであろう．

では，「状態」が隠れていることのメリットは何なのだろうか．

実際には，「状態」が隠れていることではなく状態が推測できるというメリットの方が大きい．

隠れマルコフモデルを使用する分野の一つに音声認識分野がある．

音声信号に対して隠れマルコフモデルを当てはめ，音声認識や音声合成に応用されている．

例えば，音声認識では与えられた音声から任意の単語列を推測する際に隠れマルコフモデルが使用されている．それにより，個人差が生まれやすい「発声法」等の音声パターンの変動を確率モデルで捉えることができ，数学的，統計的に処理することが可能となる．

参考
【書籍】
・金 明哲:テキストデータの統計科学入門(2009)．
・北 研二:言語と計算ー４　確率的言語モデル(1999)．

【Webサイト】
・マルコフ過程 ? wikipedia
・確率過程 ? wikipedia
・確率分布 ? wikipedia
・条件付き確率 ? wikipedia
・マルコフ性 ? wikipedia
・隠れマルコフモデル ? wikipedia
・マルコフ連鎖の話
・マルコフ連鎖モンテカルロ法入門-１
・隠れマルコフモデルの大雑把な解説
・隠れマルコフモデルによる音声認識と音声合成

Category: 技術解説 自然言語処理 』

https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%8E%E3%82%A4%E3%81%AE%E5%A1%94

　※　今日は、こんな所で…。

『出典: フリー百科事典『ウィキペディア（Wikipedia）』

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方）
出典検索?: “ハノイの塔” – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL（2017年7月）

8つの円盤のハノイの塔

ハノイの塔（ハノイのとう、英: Tower of Hanoi）は、パズルの一種。 バラモンの塔または ルーカスタワー（英: Lucas’ Tower）[注 1]とも呼ばれる。

ルール

以下のルールに従ってすべての円盤を右端の杭に移動させられれば完成。

3本の杭と、中央に穴の開いた大きさの異なる複数の円盤から構成される。

最初はすべての円盤が左端の杭に小さいものが上になるように順に積み重ねられている。

円盤を一回に一枚ずつどれかの杭に移動させることができるが、小さな円盤の上に大きな円盤を乗せることはできない。

n {\displaystyle n} 枚の円盤すべてを移動させるには最低 2 n − 1 {\displaystyle 2^{n}-1} [注 2]回の手数がかかる[1]。

解は、次のように再帰的に考えることができる。

塔を「一番下にある円盤」と「残りの円盤群」というように分けてみる。

そして、まず「残りの円盤群」を移動させ、次に「一番下にある円盤」を移動し、その上にまた「残りの円盤群」を動かせばよい。

解が再帰的な構造をしているということから、この解の手順を表示させるという問題は、再帰的なコンピュータ・プログラムの単純な例題として多用されている。

ただし支配数がメルセンヌ数[注 3]なので、同じく再帰の例題として多用されるフィボナッチ数[注 4]のように、 n {\displaystyle n} が大きくなると結果も膨大となる。

解き方

3本の棒にA,B,Cの名前を付ける。

最初Aに n 個の円盤があり、Cにすべての円盤を移動させるとすると、次のようにする。

n = 1のときは自明であるから、n > 1の場合、

上から n − 1 個目までの円盤を何らかの方法でAからBに移動する。

残った1枚をAからCに移動する。

Bにある円盤を何らかの方法でBからCに移動する。

ここで、1は最初Aに n − 1 個の円盤があり、Bにすべての円盤を移動させるという問題ととらえることができる。

そこで、次のようにする。

上から n − 2 個目までの円盤を何らかの方法でAからCに移動する。

残った1枚をAからBに移動する。

Cにある円盤を何らかの方法でCからBに移動する。

3も同様にして行うことができ、「何らかの方法」の部分を分解していくと解ける[1]。

実用的な解法

再帰的でない解き方として、以下のような手順がある[1]。人間が解く場合にも利用可能である。

いちばん小さい円盤とそれ以外の円盤を交互に動かす。

いちばん小さい円盤は常にB→C→A→B(nが偶数の場合)またはC→B→A→C(nが奇数の場合)の順に動かす。

いちばん小さな円盤以外の円盤を動かす場面では、動かせる方法は1通りしかない。

このような単純なアルゴリズムで表記されるにもかかわらず、実際には 2n − 1 [注 2]手かかる。

棒が4本以上の場合の最小手数は三角数を用いて計算できることが知られている。

2進数による解析

初期状態から n 回動かした状態は、n の2進数表記から、一意的に求めることができる。
すべて左端の棒にある状態からすべて右端の棒に移動させる場合、各円盤の位置は以下のように求められる。

n を2進数で書き表す。

最上位が一番大きい円盤、以下順に対応し1の位が一番小さい円盤に対応する。

最上位が0のとき、一番大きい円盤がまだ動いておらず、1の時には移動済みである。
各桁の数字を一つ上の位と比べる。

    同じ値の場合
        その円盤は一回り大きい円盤の上に乗っている（同じ棒上にある）。

    異なっている場合

        その数字が0の場合
            下から奇数番目の場合、一回り大きい物の右隣にある。
            下から偶数番目の場合、一回り大きい物の左隣にある。

        その数字が1の場合
            下から奇数番目の場合、一回り大きい物の左隣にある。
            下から偶数番目の場合、一回り大きい物の右隣にある。

ただし、左端の棒の左隣は右端、右端の棒の右隣は左端とする。

2進数の演算を利用すると、n 番目の移動を簡単に表記することができる。

C言語の表記を用いると n 番目の移動は、「(n&(n-1))%3 番目の棒にある円盤を ((n|(n-1))+1)%3 番目の棒に移動する」となる。

なお、メルセンヌ数は二進数では全ての桁の位を占める数が1になるから、前述の二進数演算による解析は、全ての棒に与えられた枚数n分の二進メルセンヌ数桁との因果関係を明らかにしている。これは次項のパリティとグレイ・コード解法にも大きく関与しているといえる。

グレイコードによる解法

ハノイの塔の解答とグレイ・コードによる数字の表記は近い位置にある。

グレイコードによって表記された数字の一番下の桁に一番小さい円盤、次の数字に二番目の円盤というようにすべての桁と円盤を対応付けたとき、数字が変化することによって変わるビットに対応する円盤を動かすことで解答が求められる。

この方法では動かす円盤がわかるだけでどの棒に動かすべきかは求められないが、円盤同士のパリティを考えることにより移動先も定まる（偶数番目同士、奇数番目同士の円盤は重ならない）。

前述の通り、全ての桁と円盤を対応付ける事は、その桁に対応したメルセンヌ数に支配される事と等しい。

由来

ハノイの塔は、フランスの数学者エドゥアール・リュカが1883年に発売したゲーム『ハノイの塔』がルーツである。

パッケージには「Li-sou-stian大学勤務のシャム出身のN. Claus教授によりトンキンからもたらされたゲーム」と書かれているが、Li-Sou-Stian大学はリュカが働いていたリセ・サン＝ルイ (Saint-Louis) 校のアナグラム、シャム出身のN. Claus (N. Claus de Siam) はアミアン出身のリュカ (Lucas d’Amiens) のアナグラムであるため、すべてはリュカの創作だと思われている。

同梱のリーフレットには、次のような伝説があると書かれていた。

インドのガンジス河の畔のヴァラナシ（ベナレス）に、世界の中心を表すという巨大な寺院がある。そこには青銅の板の上に、長さ1キュビット、太さが蜂の体ほどの3本のダイヤモンドの針が立てられている。そのうちの1本には、天地創造のときに神が64枚の純金の円盤を大きい円盤から順に重ねて置いた。これが「ブラフマーの塔」である。司祭たちはそこで、昼夜を通して円盤を別の柱に移し替えている（移し変えのルールの説明は省略）。そして、全ての円盤の移し替えが終わったときに、世界は崩壊し終焉を迎える。

パッケージではハノイの塔となっていたが、リーフレットではブラフマーの塔となっていた。ハノイはトンキンの中心都市、ブラフマーはヒンドゥー教や仏教における創造神である。

この話には多くのヴァリエーションが生まれた。たとえば、ダイヤモンドの針のかわりに大理石の柱が立っているなどである。

64枚の円盤を移動させるには、最低でも

（264 − 1）回 = 18,446,744,073,709,551,615 回 = 1844京6744兆737億955万1615回

かかり、1枚移動させるのに1秒かかったとすると、最低でも約5845億年かかる（なお、ビッグバンは今から約137億年前に発生したとされている）。

日本におけるハノイの塔

日本では1907年（明治40年）に書かれた書物『世界遊戯法大全』で紹介されている。その中では何回移動させればいいかなど数学的考察もしっかり書かれている。

脚注
[脚注の使い方]

注釈

^ 考案者のリュカの英語音名
^ a b この公式は、メルセンヌ数の定義式そのものでもあり、つまり、与えられた円盤 n {\displaystyle n} 枚数時における最小手数はメルセンヌ数 Mn のn項目に等しいという事である。よって本パズルはメルセンヌ数に支配されたものといえる。
^ メルセンヌとリュカとは素数研究者という共通点がある。
^ リュカはフィボナッチ数の研究者の一人であり、その同伴数列（リュカ数）の一般項公式を与えた人物でもある。さらに、フィボナッチ数、メルセンヌ数、リュカ数、これらの数列は全て二階線形回帰数列という分野に属する（元から再帰的性質を持った）数列である。

出典

^ a b c 奥村晴彦『C言語による最新アルゴリズム事典』技術評論社、1991年、216–217頁頁。ISBN 4-87408-414-1。

外部リンク

Weisstein, Eric W. "Tower of Hanoi". mathworld.wolfram.com (英語).
ハノイの塔 オリジナルパッケージの写真

カテゴリ:

パズルエドゥアール・リュカ

最終更新 2024年1月23日 (火) 03:26 （日時は個人設定で未設定ならばUTC）。
テキストはクリエイティブ・コモンズ 表示-継承ライセンスのもとで利用できます。追加の条件が適用される場合があります。詳細については利用規約を参照してください。』

ユークリッドの互除法
https://ja.wikipedia.org/wiki/%E3%83%A6%E3%83%BC%E3%82%AF%E3%83%AA%E3%83%83%E3%83%89%E3%81%AE%E4%BA%92%E9%99%A4%E6%B3%95

　※　今日は、録画しといた「コンピュータとソフトウエア」の「第９回　アルゴリズム」というものを、視聴した。

　※　そこで取り上げられていたもの、２つを紹介する。

　※　.gifアニメが、２つ載っているんだが、貼ろうとしても「権限がありません。」なんで、サイトに飛んで、見てくれ…。

　※　と思ったが、「画像のリンクをコピー」で、うまくいったようだ…。

『出典: フリー百科事典『ウィキペディア（Wikipedia）』

この記事は英語版の対応するページを翻訳することにより充実させることができます。（2024年5月）
翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。

252と105のためのユークリッドの互除法のアニメーション。

クロスバーは、最大公約数（GCD）である21の倍数を表す。
それぞれのステップにおいて、1つの番号がゼロになるまで、より少ない数はより大きな数から引かれる。

残りの数は、GCD。

ユークリッドの互除法（ユークリッドのごじょほう、英: Euclidean Algorithm）は、2 つの自然数の最大公約数を求める手法の一つである。

2 つの自然数 a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。

この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。

明示的に記述された最古のアルゴリズムとしても知られ、紀元前300年頃に記されたユークリッドの『原論』第 7 巻、命題 1 から 3 がそれである[注釈 1]。

例

(問題) 1071 と 1029 の最大公約数を求める。

1071 を 1029 で割った余りは 42

1029 を 42 で割った余りは 21

42 を 21 で割った余りは 0

よって、最大公約数は21である。

証明

a, b は自然数で a ≠ 0 とする。 b を a で割った商を q、剰余を r とすると

b = qa + r

今、d0 を a と r の両方を割り切る自然数とする。

このとき d0 は積 qa を割り切るから、和 qa + r も割り切るが、qa + r は b に等しい。

したがって、d0 は a とb を割り切る。すなわち a と r の公約数はすべてb と aの公約数である。

逆に、d1 を b と a の両方を割り切る自然数とする。

d1 は qa を割り切るから差 b – qa を割り切るが、b – qa は r に等しい。したがって、d1 は a とrを割り切る。言い換えると b と a の公約数はすべてa と r の公約数である。

したがって、b と a の公約数全体の集合は a と r の公約数全体の集合に等しく、特に b と a の最大公約数は a と r の最大公約数でなければならない。

手続き的記述（※　番組の中では、こっちが紹介されてた。）

ユークリッドの互除法の仕組みは、この図のように最大公約数を求める対象の２つの整数を幅と高さに設定した長方形内での赤色の斜めの直線の描画過程によっても表現できる。
赤色の斜めの直線の描画は、はじめはその長方形内を描画範囲とし、その角から内部に向け、かつ、その辺に対して45度の差を持たせて開始する。

描画範囲の辺の途中に当たれば、その内部へ直角反射するように角度を変える。

赤色の斜めの直線が反射後に描画範囲の向かいの辺と異なる辺の途中に当たる場合、描画範囲の長辺の長さを短辺の長さで割ると余りが生じる状態となっており、直前の反射地点を足掛かりに描画範囲を垂直に区切ってその範囲を絞りこむ。 （区切られて出来た小さいほうの範囲を以後の描画範囲とする）

（除数および被除数の変更に相当） 赤色の斜めの直線が描画範囲の角に到達した場合、描画範囲の長辺の長さを短辺の長さで余りなく割れる状態となっており、描画の終了となり、最後にして最小の描画範囲の短辺の長さが最大公約数となる。

手続き的に記述すると、次のようになる。

入力を m, n (m ≧ n) とする。

n = 0 なら、 m を出力してアルゴリズムを終了する。

m を n で割った余りを新たに n とし、更に 元のnを新たにm とし 2. に戻る。

上記の手順は「n, m に対して剰余の演算を行うことができる」という仮定だけに依っているので、整数環だけではなく任意のユークリッド整域においても同様にして最大公約因子を求めることができる。

拡張された互除法

整数 m, n の最大公約数 (英: Greatest Common Divisor) を gcd(m,n) と表すときに、（拡張された）ユークリッドの互除法を用いて、mx + ny = gcd(m, n) の解となる整数 x, y の組を見つけることができる。

上の例の場合、m = 1071, n = 1029 のとき、

1071 = 1 × 1029 + 42
1029 = 24 × 42 + 21
42 = 2 × 21

であるから、gcd(1071, 1029) = 21 であり、

21 = 1029 − 24 × 42 
= 1029 − 24 × (1071 − 1 × 1029)
= −24 × 1071 + 25 × 1029

となるので、x = −24, y = 25 である。

特に、m, n が互いに素（最大公約数が 1）である場合、mx + ny = 1 の整数解を (x, y) とすると、mx + ny = c は任意の整数 c に対して整数解 (cx, cy) をもつことが分かる。

一般に、 m = r 0 , n = r 1 {\displaystyle m=r_{0},n=r_{1}} において、ユークリッドの互除法の各過程を繰り返して

r 0 = k 0 r 1 + r 2     ( 0 < r 2 < r 1 ) {\displaystyle r_{0}=k_{0}r_{1}+r_{2}\ \ (0<r_{2}<r_{1})}
r 1 = k 1 r 2 + r 3     ( 0 < r 3 < r 2 ) {\displaystyle r_{1}=k_{1}r_{2}+r_{3}\ \ (0<r_{3}<r_{2})}
r 2 = k 2 r 3 + r 4     ( 0 < r 4 < r 3 ) {\displaystyle r_{2}=k_{2}r_{3}+r_{4}\ \ (0<r_{4}<r_{3})}
. . . {\displaystyle ...}
r h − 1 = k h − 1 r h + 0 {\displaystyle r_{h-1}=k_{h-1}r_{h}+0}

が得られるとき、

( r 0 r 1 ) = ( k 0 1 1 0 ) ( r 1 r 2 ) {\displaystyle {\begin{pmatrix}r_{0}\\r_{1}\\\end{pmatrix}}={\begin{pmatrix}k_{0}&1\\1&0\\\end{pmatrix}}{\begin{pmatrix}r_{1}\\r_{2}\\\end{pmatrix}}}
( r 1 r 2 ) = ( k 1 1 1 0 ) ( r 2 r 3 ) {\displaystyle {\begin{pmatrix}r_{1}\\r_{2}\\\end{pmatrix}}={\begin{pmatrix}k_{1}&1\\1&0\\\end{pmatrix}}{\begin{pmatrix}r_{2}\\r_{3}\\\end{pmatrix}}}
( r 2 r 3 ) = ( k 2 1 1 0 ) ( r 3 r 4 ) {\displaystyle {\begin{pmatrix}r_{2}\\r_{3}\\\end{pmatrix}}={\begin{pmatrix}k_{2}&1\\1&0\\\end{pmatrix}}{\begin{pmatrix}r_{3}\\r_{4}\\\end{pmatrix}}}
. . . {\displaystyle ...}
( r h − 1 r h ) = ( k h − 1 1 1 0 ) ( r h 0 ) {\displaystyle {\begin{pmatrix}r_{h-1}\\r_{h}\\\end{pmatrix}}={\begin{pmatrix}k_{h-1}&1\\1&0\\\end{pmatrix}}{\begin{pmatrix}r_{h}\\0\\\end{pmatrix}}}

すなわち

( r 0 r 1 ) = ( k 0 1 1 0 ) ( k 1 1 1 0 ) ( k 2 1 1 0 ) ( k 3 1 1 0 ) . . . ( k h − 1 1 1 0 ) ( r h 0 ) {\displaystyle {\begin{pmatrix}r_{0}\\r_{1}\\\end{pmatrix}}={\begin{pmatrix}k_{0}&1\\1&0\\\end{pmatrix}}{\begin{pmatrix}k_{1}&1\\1&0\\\end{pmatrix}}{\begin{pmatrix}k_{2}&1\\1&0\\\end{pmatrix}}{\begin{pmatrix}k_{3}&1\\1&0\\\end{pmatrix}}...{\begin{pmatrix}k_{h-1}&1\\1&0\\\end{pmatrix}}{\begin{pmatrix}r_{h}\\0\\\end{pmatrix}}}

ここで

K i = ( k i 1 1 0 ) {\displaystyle K_{i}={\begin{pmatrix}k_{i}&1\\1&0\\\end{pmatrix}}} とおくと、 | K i | = − 1 {\displaystyle |K_{i}|=-1} であるから K i − 1 {\displaystyle K_{i}^{-1}}は存在して
( k h − 1 1 1 0 ) − 1 ( k h − 2 1 1 0 ) − 1 . . . ( k 2 1 1 0 ) − 1 ( k 1 1 1 0 ) − 1 ( k 0 1 1 0 ) − 1 ( r 0 r 1 ) = ( r h 0 ) {\displaystyle {\begin{pmatrix}k_{h-1}&1\\1&0\\\end{pmatrix}}^{-1}{\begin{pmatrix}k_{h-2}&1\\1&0\\\end{pmatrix}}^{-1}...{\begin{pmatrix}k_{2}&1\\1&0\\\end{pmatrix}}^{-1}{\begin{pmatrix}k_{1}&1\\1&0\\\end{pmatrix}}^{-1}{\begin{pmatrix}k_{0}&1\\1&0\\\end{pmatrix}}^{-1}{\begin{pmatrix}r_{0}\\r_{1}\\\end{pmatrix}}={\begin{pmatrix}r_{h}\\0\\\end{pmatrix}}}

これらの過程において、 m = r 0 , n = r 1 {\displaystyle m=r_{0},n=r_{1}}、ユークリッドの互除法により、 r h = gcd ( m , n ) {\displaystyle r_{h}=\gcd(m,n)}であるから、 K i − 1 = ( 0 1 1 − k i ) {\displaystyle K_{i}^{-1}={\begin{pmatrix}0&1\1&-k_{i}\\end{pmatrix}}}を考慮すると、

( 0 1 1 − k h − 1 ) ( 0 1 1 − k h − 2 ) . . . ( 0 1 1 − k 2 ) ( 0 1 1 − k 1 ) ( 0 1 1 − k 0 ) ( m n ) = ( gcd ( m , n ) 0 ) {\displaystyle {\begin{pmatrix}0&1\\1&-k_{h-1}\\\end{pmatrix}}{\begin{pmatrix}0&1\\1&-k_{h-2}\\\end{pmatrix}}...{\begin{pmatrix}0&1\\1&-k_{2}\\\end{pmatrix}}{\begin{pmatrix}0&1\\1&-k_{1}\\\end{pmatrix}}{\begin{pmatrix}0&1\\1&-k_{0}\\\end{pmatrix}}{\begin{pmatrix}m\\n\\\end{pmatrix}}={\begin{pmatrix}\gcd(m,n)\\0\\\end{pmatrix}}}

となる。

( x y u v ) = ( 0 1 1 − k h − 1 ) ( 0 1 1 − k h − 2 ) . . . ( 0 1 1 − k 2 ) ( 0 1 1 − k 1 ) ( 0 1 1 − k 0 ) {\displaystyle {\begin{pmatrix}x&y\\u&v\\\end{pmatrix}}={\begin{pmatrix}0&1\\1&-k_{h-1}\\\end{pmatrix}}{\begin{pmatrix}0&1\\1&-k_{h-2}\\\end{pmatrix}}...{\begin{pmatrix}0&1\\1&-k_{2}\\\end{pmatrix}}{\begin{pmatrix}0&1\\1&-k_{1}\\\end{pmatrix}}{\begin{pmatrix}0&1\\1&-k_{0}\\\end{pmatrix}}}

とおき、ユークリッドの互除法の各過程で得られた k 0 {\displaystyle k_{0}}, k 1 {\displaystyle k_{1}}, k 2 {\displaystyle k_{2}}等を用いて、右辺を計算すれば、左辺の x {\displaystyle x}, y {\displaystyle y} が求まり、これはベズーの等式

m x + n y = gcd ( m , n ) {\displaystyle mx+ny=\gcd(m,n)}

を満たす[6]。

計算量

割って余りを取るという操作を最悪でも小さいほうの十進法での桁数の約 5 倍繰り返せば、最大公約数に達する（ラメの定理）。

最大公約数を求めるのに素因数分解すればよいと思うかもしれないが、この定理は（m, n が大きいときには）素因数分解をするよりもユークリッドの互除法によるほうがはるかに速いということを述べている。

実際、計算複雑性理論においては最大公約数を求めることは「容易な問題」として知られており、素因数分解は「困難な問題」であろうと考えられている。

入力された2つの整数のうち小さいほうの整数 n の桁数を d とすれば、ユークリッドの互除法では O(d) 回の除算で最大公約数が求められる。

桁数 d は O(log n) なので、ユークリッドの互除法では O(log n) 回の除算で最大公約数が求められる。

連分数

上の例で出てきた、1071 と 1029 の最大公約数を求める過程は、次のように表せる。

1071 = 1029 × 1 + 42 , 1029 = 42 × 24 + 21 , 42 = 21 × 2. {\displaystyle {\begin{aligned}1071&=1029\times 1+42,\\1029&=42\times 24+21,\\42&=21\times 2.\end{aligned}}}

すなわち、

1071 1029 = 1 + 42 1029 , 1029 42 = 24 + 21 42 , 42 21 = 2. {\displaystyle {\begin{aligned}{\frac {1071}{1029}}&=1+{\frac {42}{1029}},\\{\frac {1029}{42}}&=24+{\frac {21}{42}},\\{\frac {42}{21}}&=2.\end{aligned}}}

したがって、

1071 1029 = 1 + 1 24 + 1 2 {\displaystyle {\frac {1071}{1029}}=1+{\frac {1}{24+{\frac {1}{2}}}}}

このように、 n と m (n > m) の最大公約数を求める際のユークリッドの互除法の割り算の商は、有理数 n/m の連分数展開になっている。

脚注
[脚注の使い方]
注釈

^ 『原論』第7巻では、1 を単位と定義し、2 以上の自然数を数と定義している[1]。
定義

    単位とは存在するもののおのおのがそれによって 1 とよばれるものである。
    数とは単位から成る多である。
ユークリッドの互除法は以下の命題 1 から 3 において述べられている。

命題
    二つの不等な数が定められ、常に大きい数から小さい数が引き去られるとき、もし単位が残されるまで、残された数が自分の前の数を割り切らないならば、最初の 2 数は互いに素であろう[2]。
    互いに素でない 2 数が与えられたとき、それらの最大公約数を見いだすこと[3]。
    これから次のことが明らかである。すなわちもしある数が二つの数を割り切るならば、それらの最大公約数をも割り切るであろう。これが証明すべきことであった[4]。
    互いに素でない三つの数が与えられたとき、それらの最大公約数を見いだすこと[5]。

出典

^ ユークリッド & 中村ほか 1996, p. 149.
^ ユークリッド & 中村ほか 1996, pp. 150f.
^ ユークリッド & 中村ほか 1996, p. 151.
^ ユークリッド & 中村ほか 1996, p. 152.
^ ユークリッド & 中村ほか 1996, pp. 152f.
^ 岩堀 1983.

参考文献

岩堀長慶『2次行列の世界』岩波書店〈数学入門シリーズ 4〉、1983年4月22日。ISBN 4-00-007634-5。
    岩堀長慶『2次行列の世界』岩波書店〈新装版 数学入門シリーズ〉、2015年3月6日。ISBN 978-4-00-029834-6。
ハイベア、メンゲ 編『ユークリッド原論』中村幸四郎・寺阪英孝・伊東俊太郎・池田美恵訳・解説、共立出版。 - 全13巻の最初の邦訳。
    （ハードカバー）1971年7月。ISBN 4-320-01072-8
        （抜粋）『世界の名著9』 池田美恵訳 中央公論社 1972年
    （縮刷版）1996年6月。ISBN 4-320-01513-4
    （追補版）2011年5月。ISBN 978-4-320-01965-2
ハイベア、メンゲ 編『エウクレイデス全集』 （全5巻）、東京大学出版会。 - 「エウクレイデス全集」の世界初の近代語訳。
    第2巻 原論VII－X、斎藤憲 訳・解説、2015年8月。ISBN 978-4-13-065302-2

関連項目

ベズーの等式
ユークリッド環
モジュラ逆数

外部リンク

『ユークリッドの互除法の証明と不定方程式』 - 高校数学の美しい物語
日本大百科全書(ニッポニカ)『ユークリッドの互除法』 - コトバンク
Weisstein, Eric W. "Euclidean Algorithm". mathworld.wolfram.com (英語).
Hazewinkel, Michiel, ed. (2001), “Euclidean algorithm”, Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4

典拠管理データベース: 国立図書館 ウィキデータを編集

ドイツ

カテゴリ:

エウクレイデス数学のエポニム合同算術初等数学初等整数論数論アルゴリズム数学に関する記事

最終更新 2024年5月22日 (水) 12:02 （日時は個人設定で未設定ならばUTC）。
テキストはクリエイティブ・コモンズ 表示-継承ライセンスのもとで利用できます。追加の条件が適用される場合があります。詳細については利用規約を参照してください。

』