メッセージをやり取りしない分散アルゴリズム
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/06/28 15:48 UTC 版)
「グラフ彩色」の記事における「メッセージをやり取りしない分散アルゴリズム」の解説
メッセージのやり取りをしない分散アルゴリズム (decentralized algorithm) もある。最適彩色が存在するグラフについて、効率的にそれを求めるアルゴリズムが存在する。この場合、各頂点は隣接する頂点が自分と同じ色かどうかをメッセージをやり取りせずに確認できることを前提とする。例えば無線のチャンネル割り当てなどでは、他の通信機が同じチャンネルを使っているかどうかは容易に検出可能なので、この前提は穏当である。そのような情報があれば、学習するオートマトンが確実なグラフ彩色を見出すのに十分である。
※この「メッセージをやり取りしない分散アルゴリズム」の解説は、「グラフ彩色」の解説の一部です。
「メッセージをやり取りしない分散アルゴリズム」を含む「グラフ彩色」の記事については、「グラフ彩色」の概要を参照ください。
- メッセージをやり取りしない分散アルゴリズムのページへのリンク