前に書いた膜アルゴリズムのブログ で取り上げた巡回セールスマン問題に関するアルゴリズムアニメーションを作りました。貪欲算法で解くと失敗する様子がわかります。 この動画では他にも、頂点(都市)を少し動かしただけで解(巡回路)がガラッと変わる様子も…

グリーディアルゴリズム(greedy algorithm)、直訳して貪欲算法と呼ばれるアルゴリズムのグループがあります。ネットワークアルゴリズムでは最小スパニング木を求めるアルゴリズムが貪欲算法の代表として有名です*1。今回はこれをアニメーションで紹介しまし…

最短路問題は出発点の頂点から他の頂点への重みの和が最小の経路を見つける問題 です。ダイクストラ(Dijkstra)という人が考え出した次のアルゴリズム ダイクストラのアルゴリズム があります。上のアルゴリズムでは簡単のため最短路の長さd(v)だけ求めていま…

鉄道・道路・航空などの交通、通信・電気・ガス・水道などのインフラストラクチャなどなど、我々の生活にネットワークは欠かせません。ネットワークに対して行う処理は多岐にわたり、アルゴリズムの研究と応用の代表的分野になっています。前回に打ち上げた…

お詫び: 「天変地異」のシリーズは私よりもずっと上手に説明しているネットコンテンツが多数あり、私ごときがでしゃばるところでは無いとさとりました。というわけで一回だけで中止します。申し訳ありません。やはり、本業のコンピュータ関連で頑張ります。 …