@techreport{oai:ipsj.ixsq.nii.ac.jp:00231865, author = {前田, 惠太 and 岩崎, 巧実 and 藤岡, 祐太 and 塩田, 拓海 and 斎藤, 寿樹}, issue = {2}, month = {Jan}, note = {本研究では,無向グラフ G 上の始点 s から終点 t までの長さ l の s-t パスを数え上げる問題に対する分割統治法によるアルゴリズムの効率的な実装について議論する.この分割統治法に基づくアルゴリズムでは,s,t とは異なる頂点 v を経由する s-t パスの数を頂点 s から v へのパスの数と v から t までのパスの数をかけ合わせることで計算する.ただし,ここで s-v パスと v-t パスに共通の頂点を持たせてはいけない.一方,ゼロサプレス型二分決定グラフ (ZDD) は組合せ集合をコンパクトに表現することができるデータ構造で,組合せ集合における効率的な演算体型が数多く提供されている.また,ZDD を用いることで,各組合せに重みをもたせた組合せ多重集合を表現できることが知られている.本研究では,ZDD における組合せ多重集合の新たな演算である素集合結合演算を提案し,それを用いることで,分割統治法によるパスの数え上げアルゴリズムを提案する.分割統治法における 2 種類の分割方法によるアルゴリズムの実装方法について示し,それらの実装における効率性を計算機実験により示す.}, title = {ZDDを用いた分割統治法によるパス数え上げアルゴリズム}, year = {2024} }