初歩的なグラフの問題 (ID:72934)

名前

ホームページ(ブログ、Twitterなど)のURL (省略可)

本文 >ゲームの追跡ミサイルのアルゴリズムと同じです。 それは違います。 文字列の座標を最初に全部求めて、その点を通る曲線をニュートン補完で求めているので逐次計算とは少し違います。 求めた経路を線形補完してますし。 http://coconut.sys.eng.shizuoka.ac.jp/gnB/06/handout9.pdf かなり親切に書いてる感じですね。 参考になります。 計算量を考えると点の数が増えたとき単純な探索は不可能。 ２点をもっとも高いカロリー量でつなぐ経路の保存は経路上の点一つを一ビットで保存してintの配列として保存しておけば計算量が落ちますね。 経路保存ですが、ワーシャルフロイド法の3重ループの一番内側のループで点を辺でつなげる場合、エネルギー量最大でつなげる経路に共通点があるかのチェックがBit演算になるので早くなります。 N^3Log(32,N)になる野はかなりうれしい感じです。 まあ私が前に書き込んだ方法でウマくいけばですが。 とりあえずベルマンフォード法勉強してみることにします。 よそでも質問しましたがまったく返答がないのでそちらはあきらめてます。 最近メールアドレス変えたときにちょうどパソが壊れまして修理中、それから借りたパソを使ってるのでメール届いてないかもしれません。 せっかく親切にしていただいたのにすいません。