探索候補集合をどのデータ構造で実装するかというのは、最短経路問題における大きなテーマであるだろう。
バイナリヒープ(binary heap)、バケット(bucket) を比べていくと、集合に格納されるポテンシャル値の差がある程度ない場合(この表現を密とする)バケットの方が有効であることがいえるが、疎になるにつれて低速化してしまう。
逆にバイナリヒープは密であってもあまり低速化されないために、一定のグラフ特性を考慮しないソルバー(どのようなグラフに対しても高速)を開発をする場合は、こちらを選択するべきだろう。
しかしバイナリヒープには弱点(最小ポテンシャル点を取り出す操作の際に起きる大量のスワップ操作)があるためにどのようにこの部分を改善していくかがポイントである。
バイナリヒープ(binary heap)、バケット(bucket) を比べていくと、集合に格納されるポテンシャル値の差がある程度ない場合(この表現を密とする)バケットの方が有効であることがいえるが、疎になるにつれて低速化してしまう。
逆にバイナリヒープは密であってもあまり低速化されないために、一定のグラフ特性を考慮しないソルバー(どのようなグラフに対しても高速)を開発をする場合は、こちらを選択するべきだろう。
しかしバイナリヒープには弱点(最小ポテンシャル点を取り出す操作の際に起きる大量のスワップ操作)があるためにどのようにこの部分を改善していくかがポイントである。
※コメント投稿者のブログIDはブログ作成者のみに通知されます