最小完全ハッシュ関数を用いたグリッドグラフ上の効率的なパス数え上げ

この論文をさがす

抄録

正方形を縦横それぞれn分割してできる(n+1)×(n+1)グリッドグラフにおいて、対角の2頂点を結ぶパスの数はnに対して急激に増大する。例えばn=10に対しては1024もの数となり、もはや一つずつ列挙するようなことはできない大きさである。これまでにKnuthのアルゴリズムに基づく方法でn=21までのパス数が計算されているが、我々はグリッドグラフの性質を利用して計算速度と使用メモリを大幅に改善し、n=23までの計算に成功した。

収録刊行物

詳細情報

  • CRID
    1572261552802909440
  • NII論文ID
    110009550141
  • NII書誌ID
    AN1009593X
  • 本文言語コード
    ja
  • データソース種別
    • CiNii Articles

問題の指摘

ページトップへ