blog2019-04-11【忘却のJava#4】組み合わせ最適化問題を解くプログラムをJavaで書く(1)今回は大学時代に研究書いていたC言語のコードをJavaで書いてみたいと思います。その前にC言語で当時のプログラムを動かすところまで事前準備でやっておきます。実際にJavaコード書くのは次回の予定です。組み合わせ最適化問題とは?ある問題において、ある制約の下で選べる組み合わせの中で、最良の組み合わせを選ぶ問題です。Problem)組み合わせ最適化問題の一つとして最小全域木問題があります。えられた重み付き無向グラフ中の頂点全てを含むような木のことです。Wikipedia最小全域木とは:例えば数のようなものが最小全域木です。右:最小全域木Kruskalのアルゴリズム最小全域木の最適解を導くことができるアルゴリズムのうちの1つです。その時点で最も重みの小さい辺を閉路ができないように追加していき、部分木を順次拡大させていくことで最終的には最小全域木になるといったものです。詳しくは以下の【参考】をみてみてください。Wikipediaこれを題材にしてC言語で書いたものをJavaで書いてみようと思ってます。今回はその前に昔を思い出しながらCで書いたプログラムを実行するところまでやってみます。事前準備C言語のプログラムのコンパイラであるgccをインストールしておきます。gccCのコード久しぶりにCのコード見ましたが、printf()とかputs()が懐かしい。あとQuickSortをちゃんと書いてるのとか軽く感動。Kruskalの中ではUnion-Findというロジックを使ってます。graph.o実行結果こんな感じで最適解を求めることができます。この"Graph"問題の最小全域木は"Tree"で最小の重みは40という結果です。#3】Vue.jsでカレンダーを表示してみる月別アーカイブはてなブログをはじめよう!wingfairさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。