-- / --
--
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

10 / 31
Thu

昨日作った A* アルゴリズムが重いとか言いましたが、 ちょっと手を加えただけでかなり軽くなりました。

まず、 プログラムのミスで、 通れないところまで通れるものとして計算していました。 これを修正したことによって、 経路探索量が減って、 軽くなりました。 こういうエラーにならないミスが怖いんですよね・・・。

それと、 ノードリストからスコアが最も低いノードを取り出す処理を改良しました。 昨日のプログラムは、 処理を書くのが面倒だったので、 こんな感じで適当に書いてありました。

fun shortest(): StarNode {
  return _nodes.sort{it.getScore()}.first()
}

これはひどい。 スコア最小のノードを取得するだけでいいのに、 配列をソートしちゃってます。 ソートは最悪の場合 O(n2) のオーダーですから、 重いに決まってますね。 平均的には O(n ln n)) でしたっけ?

ということで、 きちんとコードを書きました。

fun shortest(): StarNode {
  var shortest: Int = 2147483647
  var shortestIndex: Int = 0
  _nodes.forEachWithIndex() {(i: Int, node: StarNode): Unit ->
    val score: Int = node.getScore()
    val status: Boolean = node.getStatus()
    if (score < shortest && status) {
      shortest = score
      shortestIndex = i
    }
  }
  return _nodes[shortestIndex]

これなら O(n) のオーダーです。

直したのはこの 2 点だけですが、 これでかなり速くなりました。 計測したわけではないので詳しくは分かりませんが、 半分くらいの時間で計算できるようになった気がします。

スポンサーサイト

comment ×0
コメント
管理者にだけ表示を許可する
 
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。