1

グラフ描画用の力ベースのアルゴリズムをいじる短いミニプログラムを Python で作成しようとしています。

線が交差する回数を最小限に抑えようとしています。ウィキペディアは、互いに反発するように線に電荷を与えることを提案しています。物理の先生にこれをシミュレートする方法を尋ねたところ、彼女はクーロンの法則を使った微積分を使用すると言いましたが、どのように始めればよいかわかりません。

誰かがこれを行う方法についてヒントを教えてもらえますか? (または、力ベースのグラフ描画アルゴリズムを微調整して、線が交差する回数を最小限に抑える別の方法はありますか?) ヒントを探しているだけです。ソースコードはありません。

誰かが興味を持っている場合に備えて、私のソース コードと、それについて作成したYouTube の動画を提供します。

4

1 に答える 1

1

エッジ交差の数を最小化する項をコスト関数に明示的に含める必要があります。たとえば、交差するエッジのペアごとに固定のペナルティが発生するか、エッジが重み付けされている場合は、2 つの重みの積であるペナルティが発生します。

于 2012-02-20T14:09:52.273 に答える