ZDDを用いた最適円筒あみだくじの列挙

• Item type: SIG Technical Reports(1)
• 公開日: 2023-03-10
• タイトル: ZDDを用いた最適円筒あみだくじの列挙
• タイトル / 言語: en
• タイトル: ZDD-Based Enumeration of All Optimal Cyclic Ladder Lotteries
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 北海道大学
• 著者所属: 北海道大学
• 著者所属: 東海大学
• 著者所属: 広島大学
• 著者所属: 北海道大学
• 著者所属: 岩手大学
• 著者所属(英): en
• 著者所属(英): Hokkaido University
• 著者所属(英): en
• 著者所属(英): Hokkaido University
• 著者所属(英): en
• 著者所属(英): Tokai University
• 著者所属(英): en
• 著者所属(英): Hiroshima University
• 著者所属(英): en
• 著者所属(英): Hokkaido University
• 著者所属(英): en
• 著者所属(英): Iwate University
• 著者名: 岩崎, 善泰; 堀山, 貴史; 松井, 泰子; 野崎, 雄太; 脊戸, 和寿; 山中, 克久
• 著者名(英): Yoshiyasu, Iwasaki; Takashi, Horiyama; Yasuko, Matsui; Yuta, Nozaki; Kazuhisa, Seto; Katsuhisa, Yamanaka
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: あみだくじは，n 本の縦線および隣り合う縦線同士をつなぐ 0 本以上の横棒からなる．また，円筒あみだくじは，あみだくじにおいて左端と右端の縦線をつなぐ横棒も許したものである．与えられた π = (π1, π2,..., πn) に対し，左から k 番目の縦線の上端にある各数 k を πk 番目の縦線の下端に出力する円筒あみだくじのうち，最小本数の横棒からなるものを，π の最適円筒あみだくじと呼ぶ．Nozaki，Wasa，Yamanaka は，与えられた πに対し，変位ベクトル（最適円筒あみだくじの各 k が左または右に縦線何本分だけ移動すべきかを示すベクトル）を列挙し，各変位ベクトルに対して逆探索により最適円筒あみだくじを列挙する逆探索に基づく手法を提案した．本研究では，零抑制型二分決定グラフ (ZDD: Zero-Suppressed Binary Decision Diagram) による最適円筒あみだくじの列挙アルゴリズムを提案する．このアルゴリズムでは，左右の変位ベクトル（各 k が左右にそれぞれ縦線何本分だけ移動すべきかを示すベクトル）のペアに対し，対応するすべての最適円筒あみだくじの集合を表す ZDD を，フロンティア法の枠組みを利用してトップダウンに構築する．また，提案アルゴリズムを実装し，計算機実験の結果を示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: A ladder lottery, known as an Amidakuji in Japan, is a network composed of n vertical lines (simply, called lines) and zero or more horizontal bars (called bars) connecting two adjacent lines. In a cyclic ladder lottery, bars are allowed to connect the leftmost and rightmost lines. For a given π = (π1, π2,..., πn), a cyclic ladder lottery is called optimal if it has the minimum number of bars and every number-k on the top of the k-th line (from the left) goes down to the bottom of the πk-th line. Nozaki, Wasa, and Yamanaka proposed two enumeration algorithms based on the framework of the reverse search: the first one enumerates all displacement vectors (whose k-th element indicates how many lines number-k goes left or right) of optimal cyclic ladder lotteries for π, and the second one enumerates all optimal cyclic ladder lotteries for each of those vectors. In this report, we propose an algorithm that enumerates all optimal cyclic ladder lotteries by using Zero-suppressed Binary Decision Diagrams (ZDDs). We construct a ZDD representing the family of all optimal cyclic ladder lotteries for a given pair of left and right displacement vectors, where we separate a displacement vector into the two for moving left and right, respectively. We construct the resulting ZDD in a top-down manner based on the framework of the frontier-based search. We also implement the proposed algorithm and show the experimental results.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2023-AL-192, 号 3, p. 1-8, 発行日 2023-03-10
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会