堀山 貴史 (ホリヤマ タカシ)
| 情報科学研究院 情報理工学部門 知識ソフトウェア科学分野 | 教授 |
Last Updated :2025/05/02
■研究者基本情報
Researchmap個人ページ
ホームページURL
研究者番号
- 60314530
J-Global ID
■経歴
経歴
学歴
委員歴
- 2023年06月
情報処理学会 北海道支部, 支部長, 学協会 - 2019年06月 - 2021年05月
電子情報通信学会 会誌編集委員会, 編集特別幹事, 学協会 - 2017年07月 - 2019年03月
埼玉県情報サービス産業協会, 彩の国さいたまICT コンテスト 審査委員長., 学協会 - 2013年08月 - 2019年03月
さいたま市 情報化計画評議会, 評議委員長, 自治体 - 2016年05月 - 2018年04月
情報処理学会 アルゴリズム研究専門委員会, 主査, 学協会 - 2016年04月 - 2018年03月
電子情報通信学会 基礎・境界ソサイエティ, 運営委員, 学協会 - 2014年07月 - 2017年01月
埼玉県情報サービス産業協会, ホームページコンテスト 審査委員長, 学協会 - 2015年06月 - 2016年05月
情報処理学会 論文誌ジャーナル/JIP 編集委員会, 基盤グループ 主査, 学協会 - 2013年06月 - 2015年05月
情報処理学会 論文誌ジャーナル/JIP 編集委員会, 基盤グループ 副査, 学協会 - 2009年06月 - 2015年05月
電子情報通信学会 VLSI設計技術研究専門委員会, 研究専門委員, 学協会 - 2008年06月 - 2010年05月
電子情報通信学会, コンピュテーション研究専門委員会 幹事, 学協会 - 2004年05月 - 2008年04月
情報処理学会アルゴリズム研究専門委員会, 運営委員, 学協会
■研究活動情報
受賞
- 2018年09月, 電子情報通信学会基礎境界ソサイエティ, 貢献賞
- 2016年05月, 電子情報通信学会情報・システムソサイエティ, 情報・システムソサイエティ論文編集活動感謝状
- 2016年05月, 情報処理学会, 感謝状
- 2011年02月, The 9th EATCS/LA Workshop on Theoretical Computer Science, EATCS/LA Best Presentation Award
日本国 - 2001年03月, 電子情報通信学会 学術奨励賞
日本国 - 2000年05月, 日経BP社 LSI IPデザイン・アワード IP賞
中村一博;朱強;丸岡新治;堀山貴史;木村晋二;渡邉勝正, 日本国
論文
- Fast enumeration of all cost-bounded solutions for combinatorial problems using ZDDs
Shin-ichi Minato, Jun Kawahara, Mutsunori Banbara, Takashi Horiyama, Ichigaku Takigawa, Yutaro Yamaguchi
Discrete Applied Mathematics, 360, 467, 486, Elsevier BV, 2025年01月
研究論文（学術雑誌） - Explicit description of viral capsid subunit shapes by unfolding dihedrons
Ryuya Toyooka, Seri Nishimoto, Tomoya Tendo, Takashi Horiyama, Tomohiro Tachi, Yasuhiro Matsunaga
Communications Biology, 7, 1, 2024年12月
研究論文（学術雑誌）, Viral capsid assembly and the design of capsid-based nanocontainers critically depend on understanding the shapes and interfaces of constituent protein subunits. However, a comprehensive framework for characterizing these features is still lacking. Here, we introduce a novel approach based on spherical tiling theory that explicitly describes the 2D shapes and interfaces of subunits in icosahedral capsids. Our method unfolds spherical dihedrons defined by icosahedral symmetry axes, enabling systematic characterization of all possible subunit geometries. Applying this framework to real T = 1 capsid structures reveals distinct interface groups within this single classification, with variations in interaction patterns around 3-fold and 5-fold symmetry axes. We validate our classification through molecular docking simulations, demonstrating its consistency with physical subunit interactions. This analysis suggests different assembly pathways for capsid nucleation. Our general framework is applicable to other triangular numbers, paving the way for broader studies in structural virology and nanomaterial design. - Shortest cover after edit.
Kazuki Mitani, Takuya Mieno, Kazuhisa Seto, Takashi Horiyama
CoRR, abs/2402.17428, 2024年
研究論文（学術雑誌） - Shortest Cover After Edit.
Kazuki Mitani, Takuya Mieno, Kazuhisa Seto, Takashi Horiyama
CPM, 24, 15, 2024年
研究論文（国際会議プロシーディングス） - Lower Bounds for the Thickness and the Total Number of Edge Crossings of Euclidean Minimum Weight Laman Graphs and (2,2)-Tight Graphs.
Yuki Kawakami, Shun Takahashi, Kazuhisa Seto, Takashi Horiyama, Yuki Kobayashi, Yuya Higashikawa, Naoki Katoh
IEICE Trans. Inf. Syst., 107, 6, 732, 740, 2024年
研究論文（学術雑誌） - Theoretical Aspects of Generating Instances with Unique Solutions: Pre-assignment Models for Unique Vertex Cover.
Takashi Horiyama, Yasuaki Kobayashi, Hirotaka Ono 0001, Kazuhisa Seto, Ryu Suzuki
AAAI, 20726, 20734, 2024年
研究論文（国際会議プロシーディングス） - Finding top-k longest palindromes in substrings
Kazuki Mitani, Takuya Mieno, Kazuhisa Seto, Takashi Horiyama
Theoretical Computer Science, 114183, 114183, Elsevier BV, 2023年09月
研究論文（学術雑誌） - Internal Longest Palindrome Queries in Optimal Time
Kazuki Mitani, Takuya Mieno, Kazuhisa Seto, Takashi Horiyama
WALCOM: Algorithms and Computation, 127, 138, Springer Nature Switzerland, 2023年03月, ［査読有り］
論文集(書籍)内論文 - Lower Bounds for the Thickness and the Total Number of Edge Crossings of Euclidean Minimum Weight Laman Graphs and (2,2)-Tight Graphs.
Yuki Kawakami, Shun Takahashi, Kazuhisa Seto, Takashi Horiyama, Yuki Kobayashi, Yuya Higashikawa, Naoki Katoh
CCCG, 191, 196, 2023年
研究論文（国際会議プロシーディングス） - Theoretical Aspects of Generating Instances with Unique Solutions: Pre-assignment Models for Unique Vertex Cover.
Takashi Horiyama, Yasuaki Kobayashi, Hirotaka Ono 0001, Kazuhisa Seto, Ryu Suzuki
CoRR, abs/2312.10599, 2023年
研究論文（学術雑誌） - Enumerating Empty and Surrounding Polygons
TERUI Shunta, YAMANAKA Katsuhisa, HIRAYAMA Takashi, HORIYAMA Takashi, KURITA Kazuhiro, UNO Takeaki
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, to appear, The Institute of Electronics, Information and Communication Engineers, 2023年, ［査読有り］
英語, We are given a set S of n points in the Euclidean plane. We assume that S is in general position. A simple polygon P is an empty polygon of S if each vertex of P is a point in S and every point in S is either outside P or a vertex of P. In this paper, we consider the problem of enumerating all the empty polygons of a given point set. To design an efficient enumeration algorithm, we use a reverse search by Avis and Fukuda with child lists. We propose an algorithm that enumerates all the empty polygons of S in O(n2 |ϵ(S) |)-time, where ϵ(S) is the set of empty polygons of S. Moreover, by applying the same idea to the problem of enumerating surrounding polygons of a given point set S, we propose an enumeration algorithm that enumerates them in O(n2)-delay, while the known algorithm enumerates in O(n2 log n)-delay, where a surrounding polygon of S is a polygon such that each vertex of the polygon is a point in S and every point in S is either inside the polygon or a vertex of the polygon. - Geodesic Folding of Regular Tetrahedron
Seri Nishimoto, Takashi Horiyama, Tomohiro Tachi
Journal for Geometry and Graphics,, 26, 1, 81, 100, 2022年07月, ［査読有り］
研究論文（学術雑誌）, In this paper, we show geometric properties of a family of polyhedra obtained by folding a regular tetrahedron along triangular grids. Each polyhedron is identified by a pair of nonnegative integers. The polyhedron can be cut along a geodesic strip of triangles to be decomposed and unfolded into one or multiple bands. We show that the number of bands is the greatest common divisor of the two integers. By a proper choice of pairs of numbers, a common triangular band that folds into different multiple polyhedra can be created. We construct the configuration of the polyhedron algebraically and numerically through angular and truss models respectively. We discuss the volumes of the obtained folded states and provide relevant open problems regarding the existence of popped-up state. We also show some geometric connections to other art forms. - Efficient Folding Algorithms for Convex Polyhedra
Tonan Kamata, Akira Kadoguchi, Takashi Horiyama, Ryuhei Uehara
DISCRETE & COMPUTATIONAL GEOMETRY, SPRINGER, 2022年07月, ［査読有り］
英語, 研究論文（学術雑誌）, We investigate a folding problem that inquires whether a polygon P can be folded, without overlap or gaps, onto a polyhedron Q for given P and Q. An efficient algorithm for this problem when Q is a box was recently developed. We extend this idea to a class of convex polyhedra, which includes the five regular polyhedra, known as Platonic solids. Our algorithms use a common technique, which we call stamping. When we apply this technique, we use two special vertices shared by both P and Q (that is, there exist two vertices of P that are also vertices of Q). All convex polyhedra and their developments have such vertices, except a special class of tetrahedra, the tetramonohedra. We develop two algorithms for the problem as follows. For a given Q, when Q is not a tetramonohedron, we use the first algorithm which solves the folding problem for a certain class of convex polyhedra. On the other hand, if Q is a tetramonohedron, we use the second algorithm to handle this special case. Combining these algorithms, we can conclude that the folding problem can be solved in pseudo-polynomial time when Q is a polyhedron in a certain class of convex polyhedra that includes regular polyhedra. - Efficient Segment Folding is Hard
Takashi Horiyama, Fabian Klute, Matias Korman, Irene Parada, Ryuhei Uehara, Katsuhisa Yamanaka
Computational Geometry, 104, 101860, Elsevier BV, 2022年06月, ［査読有り］
研究論文（学術雑誌） - {RePair} Grammars Are the Smallest Grammars for Fibonacci Words.
Takuya Mieno, Shunsuke Inenaga, Takashi Horiyama
CPM, 26, 17, 2022年, ［査読有り］
研究論文（国際会議プロシーディングス） - Max-Min 3-dispersion Problems
Takashi Horiyama, Shin-ichi Nakano, Toshiki Saitoh, Koki Suetsugu, Akira Suzuki, Ryuhei Uehara, Takeaki Uno, Kunihiro Wasa
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 303, 305, 313, 2021年11月, ［査読有り］ - Finding well-optimized special quasirandom structures with decision diagram
Kohei Shinohara, Atsuto Seko, Takashi Horiyama, Isao Tanaka
PHYSICAL REVIEW MATERIALS, 5, 11, AMER PHYSICAL SOC, 2021年11月, ［査読有り］
英語, 研究論文（学術雑誌）, The advanced data structure of the zero-suppressed binary decision diagram (ZDD) enables us to efficiently enumerate nonequivalent substitutional structures. Not only can the ZDD store a vast number of structures in a compressed manner, but also a set of structures satisfying given constraints can be extracted from the ZDD efficiently. Here, we present a ZDD-based efficient algorithm for exhaustively searching for special quasirandom structures (SQSs) that mimic the perfectly random substitutional structure. We demonstrate that the current approach can extract only a tiny number of SQSs from a ZDD composed of many substitutional structures (>10(12)). As a result, we find SQSs that are optimized better than those proposed in the literature. A series of SQSs should be helpful for estimating the properties of substitutional solid solutions. Furthermore, the present ZDD-based algorithm should be useful for applying the ZDD to the other structure enumeration problems. - Algorithmic enumeration of surrounding polygons
Katsuhisa Yamanaka, David Avis, Takashi Horiyama, Yoshio Okamoto, Ryuhei Uehara, Tanami Yamauchi
Discrete Applied Mathematics, 303, 305, 313, Elsevier BV, 2021年11月, ［査読有り］
研究論文（学術雑誌） - Longest common subsequence in sublinear space.
Masashi Kiyomi, Takashi Horiyama, Yota Otachi
Information Processing Letters, 168, 106084, 2021年, ［査読有り］
研究論文（学術雑誌） - Optimal reconfiguration of optimal ladder lotteries
Katsuhisa Yamanaka, Takashi Horiyama, Kunihiro Wasa
Theoretical Computer Science, 859, 57, 69, Elsevier BV, 2021年01月, ［査読有り］
研究論文（学術雑誌） - Enumeration of nonequivalent substitutional structures using advanced data structure of binary decision diagram
Kohei Shinohara, Atsuto Seko, Takashi Horiyama, Masakazu Ishihata, Junya Honda, Isao Tanaka
JOURNAL OF CHEMICAL PHYSICS, 153, 10, AIP Publishing, 2020年09月, ［査読有り］
英語, 研究論文（学術雑誌）, A derivative structure is a nonequivalent substitutional atomic configuration derived from a given primitive cell. The enumeration of derivative structures plays an essential role in searching for the ground states in multicomponent systems. However, it is computationally difficult to enumerate derivative structures if the number of derivative structures of a target system becomes huge. In this study, we introduce a novel compact data structure of the zero-suppressed binary decision diagram (ZDD) for enumerating derivative structures much more efficiently. We show its simple applications to the enumeration of structures derived from the face-centered cubic and hexagonal close-packed lattices in binary, ternary, and quaternary systems. The present ZDD-based procedure should contribute to computational approaches based on derivative structures in physics and materials science. - Rigid foldability is NP-hard.
Hugo Alves Akitaya, Erik D. Demaine, Takashi Horiyama, Thomas C. Hull, Jason S. Ku, Tomohiro Tachi
Journal of Computational Geometry, 11, 1, 93, 124, 2020年, ［査読有り］
研究論文（学術雑誌） - Efficient Algorithm for Box Folding.
Koichi Mizunashi, Takashi Horiyama, Ryuhei Uehara
Journal of Graph Algorithms and Applications, 24, 2, 89, 103, 2020年, ［査読有り］
研究論文（学術雑誌） - Efficient Folding Algorithms for Regular Polyhedra.
Tonan Kamata, Akira Kadoguchi, Takashi Horiyama, Ryuhei Uehara
Proceedings of the 32nd Canadian Conference on Computational Geometry(CCCG), 121, 127, 2020年
研究論文（国際会議プロシーディングス） - Implicit Enumeration of Topological-Minor-Embeddings and Its Application to Planar Subgraph Enumeration.
Yu Nakahata, Jun Kawahara, Takashi Horiyama, Shin-ichi Minato
In Proceedings of the 14th International Conference and Workshops on Algorithms and Computation (WALCOM 2020), 12049, 211, 222, Springer, 2020年, ［査読有り］
英語, 研究論文（国際会議プロシーディングス） - Geodesic Folding of Tetrahedron
Seri Nishimoto, Takashi Horiyama, Tomohiro Tachi
Symmetry: Art and Science, 11th Congress and Exhibition, 2019年11月 - Sequentially Swapping Colored Tokens on Graphs
Katsuhisa Yamanaka, Erik D. Demaine, Takashi Horiyama, Akitoshi Kawamura, Shin-ichi Nakano, Yoshio Okamo, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, Takeaki Uno
Journal of Graph Algorithms and Applications, 23, 1, 3, 27, 2019年01月, ［査読有り］ - Ecient Segment Folding is Hard.
Takashi Horiyama, Fabian Klute, Matias Korman, Irene Parada, Ryuhei Uehara, Katsuhisa Yamanaka
Proceedings of the 31st Canadian Conference on Computational Geometry(CCCG), 177, 183, 2019年
研究論文（国際会議プロシーディングス） - Efficient Algorithm for Box Folding.
Koichi Mizunashi, Takashi Horiyama, Ryuhei Uehara
WALCOM: Algorithms and Computation - 13th International Conference, WALCOM 2019, Guwahati, India, February 27 - March 2, 2019, Proceedings, 277, 288, Springer, 2019年, ［査読有り］
研究論文（国際会議プロシーディングス） - Max-Min 3-Dispersion Problems
Takashi Horiyama, Shin-ichi Nakano, Toshiki Saitoh, Koki Suetsugu, Akira Suzuki, Ryuhei Uehara, Takeaki Uno, Kunihiro Wasa
Lecture Notes in Computer Science, 104-A, 9, 291, 300, Springer International Publishing, 2019年
論文集(書籍)内論文 - Enumerating All Spanning Shortest Path Forests with Distance and Capacity Constraints
Yu NAKAHATA, Jun KAWAHARA, Takashi HORIYAMA, Shoji KASAHARA
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E101.A, 9, 1363, 1374, Institute of Electronics, Information and Communications Engineers (IEICE), 2018年09月01日, ［査読有り］
英語, 研究論文（学術雑誌） - Rep-Cubes: Dissection of a Cube into Nets.
Dawei Xu, Jinfeng Huang, Yuta Nakane, Tomoo Yokoyama, Takashi Horiyama, Ryuhei Uehara
IEICE Transactions, 101-A, 9, 1420, 1430, 2018年09月, ［査読有り］
研究論文（学術雑誌） - Ladder-Lottery Realization
Katsuhisa Yamanaka, Takashi Horiyama, Takeaki Uno, Kunihiro Wasa
The proceedings of the 30th Canadian Conference on Computational Geometry (CCCG 2018), 61, 67, 2018年08月, ［査読有り］, ［国際誌］
英語, 研究論文（国際会議プロシーディングス） - Swapping colored tokens on graphs
Katsuhisa Yamanaka, Takashi Horiyama, J. Mark Keil, David Kirkpatrick, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara, Yushi Uno
Theoretical Computer Science, 729, 1, 10, Elsevier B.V., 2018年06月12日, ［査読有り］
英語, 研究論文（学術雑誌）, We investigate the computational complexity of the following problem. We are given a graph in which each vertex has an initial and a target color. Each pair of adjacent vertices can swap their current colors. Our goal is to perform the minimum number of swaps so that the current and target colors agree at each vertex. When the colors are chosen from {1,2,…,c}, we call this problem c-COLORED TOKEN SWAPPING since the current color of a vertex can be seen as a colored token placed on the vertex. We show that c-COLORED TOKEN SWAPPING is NP-complete for c=3 even if input graphs are restricted to connected planar bipartite graphs of maximum degree 3. We then show that 2-COLORED TOKEN SWAPPING can be solved in polynomial time for general graphs and in linear time for trees. Besides, we show that, the problem for complete graphs is fixed-parameter tractable when parameterized by the number of colors, while it is known to be NP-complete when the number of colors is unbounded. - Exact Algorithms for the Max-Min Dispersion Problem
Toshihiro Akagi, Tetsuya Araki, Takashi Horiyama, Shin-ichi Nakano, Yoshio Okamoto, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara, Takeaki Uno, Kunihiro Wasa
Proc. of the 12th International Frontiers of Algorithmics Workshop (FAW 2018), Lecture Notes in Computer Science, 10823, 263, 272, Springer International Publishing, 2018年03月, ［査読有り］
論文集(書籍)内論文 - Rigid Foldability is NP-Hard.
Hugo A. Akitaya, Erik D. Demaine, Takashi Horiyama, Thomas C. Hull, Jason S. Ku, Tomohiro Tachi
CoRR, abs/1812.01160, 2018年
研究論文（学術雑誌） - Isomorphism Elimination by Zero-Suppressed Binary Decision Diagrams.
Takashi Horiyama, Masahiro Miyasaka, Riku Sasaki
Proceedings of the 30th Canadian Conference on Computational Geometry(CCCG), 360, 366, 2018年
研究論文（国際会議プロシーディングス） - Computational Complexity of Robot Arm Simulation Problems.
Tianfeng Feng, Takashi Horiyama, Yoshio Okamoto, Yota Otachi, Toshiki Saitoh, Takeaki Uno, Ryuhei Uehara
Combinatorial Algorithms - 29th International Workshop, IWOCA 2018, Singapore, July 16-19, 2018, Proceedings, 177, 188, Springer, 2018年, ［査読有り］
研究論文（国際会議プロシーディングス） - Sankaku-tori: An old Western-japanese game played on a point set
Takashi Horiyama, Takashi Iizuka, Masashi Kiyomi, Yoshio Okamoto, Ryuhei Uehara, Takeaki Uno, Yushi Uno, Yukiko Yamauchi
Journal of Information Processing, 25, 708, 715, Information Processing Society of Japan, 2017年08月01日, ［査読有り］
英語, 研究論文（学術雑誌）, We study a combinatorial game named '‘sankaku-tori’' in Japanese, which means '‘triangle-taking’' in English. It is an old pencil-and-paper game for two players played in Western Japan. The game is played on points on the plane in general position. In each turn, a player adds a line segment to join two points, and the game ends when a triangulation of the point set is completed. The player who completes more triangles than the other wins. In this paper, we formalize this game and investigate three restricted variants of this game. We first investigate a solitaire variant
for a given set of points and line segments with two integers t and k, the problem asks if you can obtain t triangles after k moves. We show that this variant is NP-complete in general. The second variant is the standard two player version, but the points are in convex position. In this case, the first player has a nontrivial winning strategy. The last variant is a natural extension of the second one
we have the points in convex position but one point inside. Then, it turns out that the first player has no winning strategy. - Common developments of three incongruent boxes of area 30
Dawei Xu, Takashi Horiyama, Toshihiro Shirakawa, Ryuhei Uehara
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 64, 1, 12, ELSEVIER SCIENCE BV, 2017年08月, ［査読有り］
英語, 研究論文（学術雑誌）, We investigate common developments that can fold into plural incongruent orthogonal boxes. Recently, it was shown that there are infinitely many orthogonal polygons that fold into three boxes of different size. However, the smallest one that folds into three boxes consists of 532 unit squares. From the necessary condition, the smallest possible surface area that can fold into two boxes is 22, and the smallest possible surface area for three different boxes is 46. For the area 22, it has been shown that there are 2,263 common developments of two boxes by exhaustive search. However, the area 46 is too huge to search. In this paper, we focus on the polygons of area 30, which is the second smallest area of two boxes that admits to fold into two boxes of size 1 x 1 x 7 and 1 x 3 x 3. Moreover, when we fold along diagonal lines of rectangles of size 1 x 2, this area 30 may admit to fold into a box of size root 5 x root 5 x root 5. The results are summarized as follows. There exist 1,080 common developments of two boxes of size 1 x 1 x 7 and 1 x 3 x 3. Among them, there are nine common developments of three boxes of size 1 x 1 x 7, 1 x 3 x 3, and root 5 x root 5 x root 5. Interestingly, one of nine such polygons folds into three different boxes 1 x 1 x 7, 1 x 3 x 3, and root 5 x root 5 x root 5 in four different ways. (C) 2017 Elsevier B.V. All rights reserved. - On the Enumeration of Chequered Tilings in Polygons
Hiroaki Hamanaka, Takashi Horiyama, Ryuhei Uehara
Proc. of Bridges 2017 conference, 423, 426, 2017年07月, ［査読有り］ - Foreword.
Takashi Horiyama
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 100-A, 9, 1763, 1763, 2017年
研究論文（学術雑誌） - Generating All Patterns of Graph Partitions Within a Disparity Bound
Jun Kawahara, Takashi Horiyama, Keisuke Hotta, Shin-ichi Minato
WALCOM: ALGORITHMS AND COMPUTATION, WALCOM 2017, 10167, 119, 131, SPRINGER INTERNATIONAL PUBLISHING AG, 2017年, ［査読有り］
英語, 研究論文（国際会議プロシーディングス）, A balanced graph partition on a vertex-weighted graph is a partition of the vertex set such that the partition has k parts and the disparity, which is defined as the ratio of the maximum total weight of parts to the minimum one, is at most r. In this paper, a novel algorithm is proposed that enumerates all the graph partitions with small disparity. Experimental results show that five millions of partitions with small disparity for some graph with more than 100 edges can be enumerated within ten minutes. - Rep-cubes: Unfolding and Dissection of Cubes.
Dawei Xu, Takashi Horiyama, Ryuhei Uehara
Proceedings of the 29th Canadian Conference on Computational Geometry, CCCG 2017, July 26-28, 2017, Carleton University, Ottawa, Ontario, Canada, 62, 67, 2017年, ［査読有り］
研究論文（国際会議プロシーディングス） - Complexity of tiling a polygon with trominoes or bars
Takashi Horiyama, Takehiro Ito, Keita Nakatsuka, Akira Suzuki, Ryuhei Uehara
Discrete & Computational Geometry, 58, 3, 686, 704, 2017年, ［査読有り］ - Sequentially Swapping Colored Tokens on Graphs
Katsuhisa Yamanaka, Erik D. Demaine, Takashi Horiyama, Akitoshi Kawamura, Shin-ichi Nakano, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, Takeaki Uno
Proc. of WALCOM: ALGORITHMS AND COMPUTATION, WALCOM 2017, LNCS 10167, 1, 435, 447, SPRINGER INTERNATIONAL PUBLISHING AG, 2017年, ［査読有り］
英語, 研究論文（国際会議プロシーディングス）, We consider a puzzle consisting of colored tokens on an nvertex graph, where each token has a distinct starting vertex and a set of allowable target vertices for it to reach, and the only allowed transformation is to "sequentially" move the chosen token along a path of the graph by swapping it with other tokens on the path. This puzzle is a variation of the Fifteen Puzzle and is solvable in O(n(3)) token-swappings. We thus focus on the problem of minimizing the number of token-swappings to reach the target token-placement. We first give an inapproximability result of this problem, and then show polynomial-time algorithms on trees, complete graphs, and cycles. - Deciphering Time Scale Hierarchy in Reaction Networks.
Nagahata Y, Maeda S, Teramoto H, Horiyama T, Taketsugu T, Komatsuzaki T
The journal of physical chemistry. B, 120, 8, 1961, 1971, AMER CHEMICAL SOC, 2016年03月, ［査読有り］
英語, 研究論文（学術雑誌）, Markovian dynamics on complex reaction networks are one of the most intriguing subjects in a wide range of research fields including chemical reactions, biological physics, and ecology. To represent the global kinetics from one node (corresponding to a basin on an energy landscape) to another requires information on multiple pathways that directly or indirectly connect these two nodes through the entire network. In this paper we present a scheme to extract a hierarchical set of global transition states (TSs) over a discrete time Markov chain derived from first-order rate equations. The TSs can naturally take into account the multiple pathways connecting any pair of nodes. We also propose a new type of disconnectivity graph (DG) to capture the hierarchical organization of different time scales of reactions that can capture changes in the network due to changes in the observation. The crux is the introduction of the minimum conductance cut (MCC) in graph clustering, corresponding to the dividing surface across the network having the "smallest" transition probability between two disjoint subnetworks (superbasins on the energy landscape) in the network. We present a new combinatorial search algorithm for finding this MCC. We apply our method to a reaction network of Claisen rearrangement of allyl vinyl ether that consists of 23 nodes and 66 links (saddles on the energy landscape) connecting them. We compare the kinetic properties of our DG to those of the transition matrix of the rate equations and show that our graph can properly reveal the hierarchical, organization of time scales in a network. - Continuous Folding of Regular Dodecahedra
Takashi Horiyama, Jin-ichi Itoh, Naoki Katoh, Yuki Kobayashi, Chie Nara
DISCRETE AND COMPUTATIONAL GEOMETRY AND GRAPHS, JCDCGG 2015, 9943, 120, 131, SPRINGER INT PUBLISHING AG, 2016年, ［査読有り］
英語, 研究論文（国際会議プロシーディングス）, Itoh and Nara [3] discussed with Kobayashi the continuous flattening of all Platonic polyhedra; however, a problem was encountered in the case of the dodecahedron. To complete the study, we explicitly show, in this paper, a continuous folding of a regular dodecahedron following the ideas in [3]. - Common unfolding of regular tetrahedron and Johnson-Zalgaller solid
Yoshiaki Araki, Takashi Horiyama, Ryuhei Uehara
Journal of Graph Algorithms and Applications, 20, 1, 101, 104, Brown University, 2016年, ［査読有り］
英語, 研究論文（学術雑誌）, In this paper, we investigate the common unfolding between regular tetrahedra and Johnson-Zalgaller solids. More precisely, we investigate the sets of all edge developments of Johnson-Zalgaller solids that fold into regular tetrahedra. We show that, among 92 Johnson-Zalgaller solids, only J17 (gyroelongated square dipyramid) and J84 (snub disphenoid) have some edge developments that fold into a regular tetrahedron, and the remaining Johnson-Zalgaller solids do not have any such edge development. - Box Pleating is Hard
Hugo A. Akitaya, Kenneth C. Cheung, Erik D. Demaine, Takashi Horiyama, Thomas C. Hull, Jason S. Ku, Tomohiro Tachi, Ryuhei Uehara
DISCRETE AND COMPUTATIONAL GEOMETRY AND GRAPHS, JCDCGG 2015, 9943, 167, 179, SPRINGER INT PUBLISHING AG, 2016年, ［査読有り］
英語, 研究論文（国際会議プロシーディングス）, Flat foldability of general crease patterns was first claimed to be hard for over twenty years. In this paper we prove that deciding flat foldability remains NP-complete even for box pleating, where creases form a subset of a square grid with diagonals. In addition, we provide new terminology to implicitly represent the global layer order of a flat folding, and present a new planar reduction framework for grid-aligned gadgets. - Convex Configurations on Nana-kin-san Puzzle.
Takashi Horiyama, Ryuhei Uehara, Haruo Hosoya
8th International Conference on Fun with Algorithms, FUN 2016, June 8-10, 2016, La Maddalena, Italy, 20:1-20:14, 14, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016年, ［査読有り］
研究論文（国際会議プロシーディングス） - 正4 面体と立方体の共通の展開図に関する研究
白川俊博, 堀山貴史, 上原隆平
日 本折紙学会, 折り紙の科学, 4, 1, 45, 54, 2015年03月, ［査読有り］ - Common Developments of Three Incongruent Boxes of Area 30
Dawei Xu, Takashi Horiyama, Toshihiro Shirakawa, Ryuhei Uehara
THEORY AND APPLICATIONS OF MODELS OF COMPUTATION (TAMC 2015), 9076, 236, 247, SPRINGER-VERLAG BERLIN, 2015年, ［査読有り］
英語, 研究論文（国際会議プロシーディングス）, We investigate common developments that can fold into plural incongruent orthogonal boxes. Recently, it was shown that there are infinitely many orthogonal polygons that folds into three boxes of different size. However, the smallest one that folds into three boxes consists of 532 unit squares. From the necessary condition, the smallest possible surface area that can fold into two boxes is 22, which admits to fold into two boxes of size 1x1x5 and 1x2x3. On the other hand, the smallest possible surface area for three different boxes is 46, which may admit to fold into three boxes of size 1x1x11, 1x2x7, and 1x3x5. For the area 22, it has been shown that there are 2,263 common developments of two boxes by exhaustive search. However, the area 46 is too huge for search. In this paper, we focus on the polygons of area 30, which is the second smallest area of two boxes that admits to fold into two boxes of size 1x1x7 and 1x3x3. Moreover, when we admit to fold along diagonal lines of rectangles of size 1x2, the area may admit to fold into a box of size root 5x root 5x root 5. That is, the area 30 is the smallest candidate area for folding three different boxes in this manner. We perform two algorithms. The first algorithm is based on ZDDs, zero-suppressed binary decision diagrams, and it computes in 10.2 days on a usual desktop computer. The second algorithm performs exhaustive search, however, straightforward implementation cannot be run even on a supercomputer since it causes memory overflow. Using a hybrid search of DFS and BFS, it completes its computation in 3 months on a supercomputer. As results, we obtain (1) 1,080 common developments of two boxes of size 1x1x7 and 1x3x3, and (2) 9 common developments of three boxes of size 1x1x7, 1x3x3, and root 5 x root 5 x root 5. - Common Unfolding of Regular Tetrahedron and Johnson-Zalgaller Solid.
Yoshiaki Araki, Takashi Horiyama, Ryuhei Uehara
WALCOM: Algorithms and Computation - 9th International Workshop, WALCOM 2015, Dhaka, Bangladesh, February 26-28, 2015. Proceedings, 8973, 294, 305, Springer, 2015年, ［査読有り］
英語, Common unfolding of a regular tetrahedron and a Johnson-Zalgaller solid is investigated. More precisely, we investigate the sets of all edge unfoldings of Johnson-Zalgaller solids. Among 92 Johnson-Zalgaller solids, some of edge unfolding of J17 and J84 admit to fold into a regular tetrahedron. On the other hand, there are no edge unfolding of the other Johnson-Zalgaller solids that admit to fold into a regular tetrahedron.WALCOM: Algorithms and Computation, 9th International Workshop, WALCOM 2015, Dhaka, Bangladesh, February 26-28, 2015. Proceedings - Swapping colored tokens on graphs
Katsuhisa Yamanaka, Takashi Horiyama, David Kirkpatrick, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara, Yushi Uno
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 9214, 619, 628, Springer Verlag, 2015年, ［査読有り］
英語, 研究論文（国際会議プロシーディングス）, We investigate the computational complexity of the following problem. We are given a graph in which each vertex has the current and target colors. Each pair of adjacent vertices can swap their current colors. Our goal is to perform the minimum number of swaps so that the current and target colors agree at each vertex. When the colors are chosen from {1, 2,..., c}, we call this problem c-COLORED TOKEN SWAPPING since the current color of a vertex can be seen as a colored token placed on the vertex. We show that c-COLORED TOKEN SWAPPING is NP-complete for every constant c ≥ 3 even if input graphs are restricted to connected planar bipartite graphs of maximum degree 3. We then show that 2-COLORED TOKEN SWAPPING can be solved in polynomial time for general graphs and in linear time for trees. - Base-object location problems for base-monotone regions
Jinhee Chun, Takashi Horiyama, Takehiro Ito, Natsuda Kaothanthong, Hirotaka Ono, Yota Otachi, Takeshi Tokuyama, Ryuhei Uehara, Takeaki Uno
Theoretical Computer Science, 555, 71, 84, ELSEVIER SCIENCE BV, 2014年10月, ［査読有り］
英語, 研究論文（学術雑誌）, A base-monotone region with a base is a subset of the cells in a pixel grid such that if a cell is contained in the region then so are the ones on a shortest path from the cell to the base. The problem of decomposing a pixel grid into disjoint base-monotone regions was first studied in the context of image segmentation. It is known that for a given pixel grid and base-lines, one can compute in polynomial time a maximum-weight region that can be decomposed into disjoint base-monotone regions with respect to the given baselines (Chun et al., 2012 [4]). We continue this line of research and show the NP-hardness of the problem of optimally locating k base-lines in a given n x n pixel grid. We then present an O (n(3))-time 2-approximation algorithm for this problem. We also study two related problems, the k base-segment problem and the quad-decomposition problem, and present some complexity results for them. (C) 2013 Elsevier B.V. All rights reserved. - Computational Complexity of Piano-Hinged Dissections
Zachary Abel, Erik D. Demaine, Martin L. Demaine, Takashi Horiyama, Ryuhei Uehara
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, E97A, 6, 1206, 1212, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, 2014年06月, ［査読有り］
英語, 研究論文（学術雑誌）, We prove NP-completeness of deciding whether a given loop of colored right isosceles triangles, hinged together at edges, can be folded into a specified rectangular three-color pattern. By contrast, the same problem becomes polynomially solvable with one color or when the target shape is a tree-shaped polyomino. - Sankaku-Tori: An Old Western-Japanese Game Played on a Point Set
Takashi Horiyama, Masashi Kiyomi, Yoshio Okamoto, Ryuhei Uehara, Takeaki Uno, Yushi Uno, Yukiko Yamauchi
FUN WITH ALGORITHMS, 8496, 230, 239, SPRINGER-VERLAG BERLIN, 2014年, ［査読有り］
英語, 研究論文（国際会議プロシーディングス）, We study a combinatorial game named "sankaku-tori" in Japanese, which means "triangle-taking" in English. It is an old pencil-and-paper game for two players played in Western Japan. The game is played on points on the plane in general position. In each turn, a player adds a line segment to join two points, and the game ends when a triangulation of the point set is completed. The player who completes more triangles than the other wins. In this paper, we consider two restricted variants of this game. In the first variant, the first player always wins in a nontrivial way, and the second variant is NP-complete in general. - Computational Complexity of Piano-Hinged Dissections (コンピュテーション)
ABEL ZACHARY, DEMAINE ERIK D., DEMAINE MARTIN L., HORIYAMA TAKASHI, UEHARA RYUHEI
電子情報通信学会技術研究報告 = IEICE technical report : 信学技報, 113, 50, 33, 38, 一般社団法人電子情報通信学会, 2013年05月17日
英語, In one of the first papers about the complexity of puzzles, Robertson and Munro [12] proved that a generalized form of the then-popular Instant Insanity puzzle is NP-complete. Here we study several variations of this puzzle, exploring how the complexity depends on the piece shapes and the allowable orientations of those shapes. - The Number of Different Unfoldings of Polyhedra.
Takashi Horiyama, Wataru Shoji
Algorithms and Computation - 24th International Symposium(ISAAC), 623, 633, Springer, 2013年
研究論文（国際会議プロシーディングス） - Enumeration of region partitioning for evacuation planning based on ZDD
Atsushi Takizawa, Yasufumi Takechi, Akio Ohta, Naoki Katoh, Takeru Inoue, Takashi Horiyama, Jun Kawahara, Shin-Ichi Minato
Proc. of the 11th International Symposium on Operations Research and its Applications in engineering, technology and management, 64, 71, Institution of Engineering and Technology, 2013年, ［査読有り］
英語, 研究論文（国際会議プロシーディングス）, Japanese cities always have risks of large-scale earthquakes. Thus, it is very important to establish crisis management systems against large-scale disasters such as big earthquakes, and tsunamis to secure evacuation centers for evacuees. In this respect, it is extremely important to provide sufficient evacuation centers and to appropriately partition the whole region into small areas, such that a unique evacuation center is located in each area and the people living in the area can easily evacuate to the center. However, it is hard to find an optimal region partitioning, due to the uncertainty, such as a fire or collapsed buildings. In this research, we propose a method to enumerate all partitioning patterns using Zero-suppressed Binary Decision Diagram (ZDD) that satisfy several conditions. We apply the proposed method to Kamigyo Ward of Kyoto City, Japan. © 2013 IET. - Base location problems for base-monotone regions
Jinhee Chun, Takashi Horiyama, Takehiro Ito, Natsuda Kaothanthong, Hirotaka Ono, Yota Otachi, Takeshi Tokuyama, Ryuhei Uehara, Takeaki Uno
WALCOM: Algorithms and Computation, 7th International Workshop, WALCOM 2013, Kharagpur, India, February 14-16, 2013. Proceedings, 7748, 53, 64, Springer, 2013年, ［査読有り］
英語, The problem of decomposing a pixel grid into base-monotoneregions was first studied in the context of image segmentation. It is known that for a given n × n pixel grid and baselines, one can compute in O(n^3) time a maximum-weight region that can be decomposed into disjoint base-monotone regions [Chun et al. ISAAC 2009]. To complement this fact, we first show the NP-hardness of the problem of optimally locating k baselines in a given pixel grid. Next we present an O(n^3)-time 2-approximation algorithm for this problem. We also study some polynomial-time solvable cases, and variants of the problem.WALCOM: Algorithms and Computation, 7th International Workshop, WALCOM 2013, Kharagpur, India, February 14-16, 2013. Proceedings - Automatic Multi-Stage Clock Gating Optimization Using ILP Formulation
Xin Man, Takashi Horiyama, Shinji Kimura
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, E95A, 8, 1347, 1358, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, 2012年08月, ［査読有り］
英語, 研究論文（学術雑誌）, Clock gating is supported by commercial tools as a power optimization feature based on the guard signal described in HDL (structural method). However, the identification of control signals for gated registers is hard and designer-intensive work. Besides, since the clock gating cells also consume power, it is imperative to minimize the number of inserted clock gating cells and their switching activities for power optimization. In this paper, we propose an automatic multi-stage clock gating algorithm with ILP (Integer Linear Programming) formulation, including clock gating control candidate extraction, constraints construction and optimum control signal selection. By multi-stage clock gating, unnecessary clock pulses to clock gating cells can be avoided by other clock gating cells, so that the switching activity of clock gating cells can be reduced. We find that any multi-stage control signals are also single-stage control signals, and any combination of signals can be selected from single-stage candidates. The proposed method can be applied to 3 or more cascaded stages. The multi-stage clock gating optimization problem is formulated as constraints in LP format for the selection of cascaded clock-gating order of multi-stage candidate combinations, and a commercial ILP solver (IBM CPLEX) is applied to obtain the control signals for each register with minimum switching activity. Those signals are used to generate a gate level description with guarded registers from original design, and a commercial synthesis and layout tools are applied to obtain the circuit with multi-stage clock gating. For a set of benchmark circuits and a Low Density Parity Check (LDPC) Decoder (6.6k gates, 212 F.F.s), the proposed method is applied and actual power consumption is estimated using Synopsys NanoSim after layout. On average, 31% actual power reduction has been obtained compared with original designs with structural clock gating, and more than 10% improvement has been achieved for some circuits compared with single-stage optimization method. CPU time for optimum multi-stage control selection is several seconds for up to 25k variables in LP format. By applying the proposed clock gating, area can also be reduced since the multiplexors controlling register inputs are eliminated. - Packing Trominoes is NP-Complete, #P-Complete and ASP-Complete.
Takashi Horiyama, Takehiro Ito, Keita Nakatsuka, Akira Suzuki, Ryuhei Uehara
Proceedings of the 24th Canadian Conference on Computational Geometry(CCCG), 211, 216, 2012年
研究論文（国際会議プロシーディングス） - Power Optimization of Sequential Circuits Using Switching Activity Based Clock Gating
Xin Man, Takashi Horiyama, Shinji Kimura
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, E93A, 12, 2472, 2480, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, 2010年12月, ［査読有り］
英語, 研究論文（学術雑誌）, Clock gating is the insertion of control signal for registers to switch off unnecessary clock signals selectively without violating the functional correctness of the original design so as to reduce the dynamic power consumption Commercial EDA tools usually have a mechanism to generate clock gating logic based on the structural method where the con trol signals specified by designers are used and the effectiveness of the clock gating depends on the specified control signals In the research we focus on the automatic clock gating logic generation and propose a method based on the candidate extraction and control signal selection We formalize the control signal selection using linear formulae and devise an optimization method based on BDD The method is effective for circuits with a lot of shared candidates by different registers The method is applied to counter circuits to check the co relation with power simulation results and a set of benchmark circuits 19 1-71 9% power reduction has been found on counter circuitsafter layout and 2 3-18 0% cost reduction on benchmark circuits - Generation of Polyiamonds for p6 Tiling by the Reverse Search.
Takashi Horiyama, Shogo Yamane
Computational Geometry, Graphs and Applications - 9th International Conference(CGGA), 96, 107, Springer, 2010年
研究論文（国際会議プロシーディングス） - Enumeration of Polyominoes for p4 Tiling.
Takashi Horiyama, Masato Samejima
Proceedings of the 21st Annual Canadian Conference on Computational Geometry(CCCG), 29, 32, 2009年
研究論文（国際会議プロシーディングス） - Fine-Grained Power Gating Based on the Controlling Value of Logic Elements
Lei Chen, Takashi Horiyama, Yuichi Nakamura, Shinji Kimura
IEICE Trans. Fundamentals of Electronics, Communications and Computer Sciences, E91-A, 12, 3531, 3538, 2008年12月, ［査読有り］ - Enumeration of Tsume-Shogi diagrams by the reverse method
Takashi Horiyama, Hiro Ito, Kazuo Iwama, Jun Kawahara
INTERNATIONAL CONFERENCE ON INFORMATICS EDUCATION AND RESEARCH FOR KNOWLEDGE-CIRCULATING SOCIETY, PROCEEDINGS, 193, +, IEEE COMPUTER SOC, 2008年, ［査読有り］
英語, 研究論文（国際会議プロシーディングス）, With the advances of modern computer technologies and elaborated algorithm design methodologies, it becomes important to enumerate all feasible solutions for given constraints. In this paper, we propose algorithms for enumerating Tsume-Shogi diagrams (i.e., Shogi. mating problems) by the reverse method. Conventional algorithms always take the principle 'generate candidate diagrams and sieve them by Tsume-Shogi solvers,' which tends to require lengthy execution time. In our approach, the reverse method enables us to enumerate all diagrams without using Tsume-Shogi solvers. We can sieve the candidates easily and quickly, since the), are generated in the ascending order according to the number of necessary moves for mating the defender's king. We have implemented the proposed algorithms, and enumerated all diagrams with several restrictions (e.g., those with only four knights). From this result, we prove many results for knight diagrams, e.g., i) the maximum number of moves is 11, ii) it is 13 for additional mate free, iii) it is 7 if at least one piece is in hand of the attacker, and iv) the maximum pieces in hand of the attacker is two. - Bit-Length Optimization Method for High-Level Synthesis Based on Non-Linear Programming Technique
Nobuhiro Doi, Takashi Horiyama, Masaki Nakanishi, Shinji Kimura
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E89-A, 12, 3427, 3434, 一般社団法人電子情報通信学会, 2006年12月, ［査読有り］
英語, 研究論文（学術雑誌）, High-level synthesis is a novel method to generate a RT-level hardware description automatically from a high-level language such as C, and is used at recent digital circuit design. Floating-point to fixed-point conversion with bit-length optimization is one of the key issues for the area and speed optimization in high-level synthesis. However, the conversion task is a rather tedious work for designers. This paper introduces automatic bit-length optimization method on floating-point to fixed-point conversion for high-level synthesis. The method estimates computational errors statistically, and formalizes an optimization problem as a non-linear problem. The application of NLP technique improves the balancing between computational accuracy and total hardware cost. Various constraints such as unit sharing, maximum bit-length of function units can be modeled easily, too. Experimental result shows that our method is fast compared with typical one, and reduces the hardware area. - Finite-state online algorithms and their automated competitive analysis
Takashi Horiyama, Kazuo Iwama, Jun Kawahara
In Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC 2006), 4288, 71, 80, 2006年12月, ［査読有り］
英語, 研究論文（国際会議プロシーディングス） - How to collect balls moving in the Euclidean plane
Yuichi Asahiro, Takashi Horiyama, Kazuhisa Makino, Hirotaka Ono, Toshinori Sakuma, Masafumi Yamashita
DISCRETE APPLIED MATHEMATICS, 154, 16, 2247, 2262, ELSEVIER SCIENCE BV, 2006年11月, ［査読有り］
英語, 研究論文（学術雑誌）, In this paper, we study how to collect n balls moving with a fixed constant velocity in the Euclidean plane by k robots moving on straight track-lines through the origin. Since all the balls might not be caught by robots, differently from Moving-target TSP, we consider the following 3 problems in various situations: (i) deciding if k robots can collect all n balls; (ii) maximizing the number of the balls collected by k robots; (iii) minimizing the number of the robots to collect all n balls. The situations considered in this paper contain the cases in which track-lines are given (or not), and track-lines are identical (or not). For all problems and situations, we provide polynomial time algorithms or proofs of intractability, which clarify the tractability-intractability frontier in the ball collecting problems in the Euclidean plane. (c) 2006 Published by Elsevier B.V. - Density condensation of Boolean formulas
Youichi Hanatani, Takashi Horiyama, Kazuo Iwama
Discrete Applied Mathematics, 154, 16, 2263, 2270, 2006年11月01日, ［査読有り］
英語, 研究論文（学術雑誌）, The following problem is considered: given a Boolean formula f, generate another formula g such that: (i) If f is unsatisfiable then g is also unsatisfiable. (ii) If f is satisfiable then g is also satisfiable and furthermore g is "easier" than f. For the measure of this easiness, we use the density of a formula f which is defined as (the number of satisfying assignments)/2n, where n is the number of Boolean variables of f. In this paper, we mainly consider the case that the input formula f is given as a 3-CNF formula and the output formula g may be any formula using Boolean AND, OR and negation. Two different approaches to this problem are presented: one is to obtain g by reducing the number of variables and the other by increasing the number of variables, both of which are based on existing SAT algorithms. Our performance evaluation shows that, a little surprisingly, better SAT algorithms do not always give us better density-condensation algorithms. © 2006 Elsevier B.V. All rights reserved. - An Optimization Method in Floating-point to Fixed-point Conversion using Positive and Negative Error Analysis and Sharing of Operations
N. Doi, T. Horiyama, M. Nakanishi, S. Kimura
Proc. of the 12th Workshop on Synthesis And System Integration of Mixed Information technologies(SASIMI 2004), 466, 471, 2004年10月, ［査読有り］
英語, 研究論文（国際会議プロシーディングス） - Reasoning with ordered binary decision diagrams
T Horiyama, T Ibaraki
DISCRETE APPLIED MATHEMATICS, 142, 1-3, 151, 163, ELSEVIER SCIENCE BV, 2004年08月, ［査読有り］
英語, 研究論文（学術雑誌）, We consider problems of reasoning with a knowledge-base, which is represented by an ordered binary decision diagram, for two cases of general and Horn knowledge-bases. Our main results say that both finding a model of a knowledge-base and deducing from a knowledge-base can be done in linear time for a general knowledge-base, but that abduction is NP-complete even for a Horn knowledge-base. Then, we consider abduction when its assumption set consists of all propositional literals (i.e., an answer for a given query is allowed to include any positive literals), and show that it can be done in polynomial time if the knowledge-base is Horn, while it remains NP-complete for the general case. Some other solvable cases are also discussed. (C) 2004 Elsevier B.V. All rights reserved. - How to collect balls moving in the euclidean plane
Yuichi Asahiro, Takashi Horiyama, Kazuhisa Makino, Hirotaka Ono, Toshinori Sakuma, Masafumi Yamashita
Electronic Notes in Theoretical Computer Science, 91, 229, 245, 2004年02月16日, ［査読有り］
英語, 研究論文（国際会議プロシーディングス）, In this paper, we study how to collect n balls moving with constant velocities in the Euclidean plane by k robots moving on straight track-lines through the origin. Since all the balls might not be caught by robots, differently from Moving-Target TSP, we consider the following 3 problems in various situations: (i) deciding if k robots can collect all n balls, (ii) maximizing the number of the balls collected by k robots, and (iii) minimizing the number of the robots to collect all n balls. The situations considered here contain the cases in which track-lines are given (or not), and track-lines are identical (or not). For all problems and situations, we provide polynomial time algorithms or proofs of intractability, which clarify the tractability- intractability frontier in the ball collecting problems in the Euclidean plane. © 2004 Elsevier B.V. All rights reserved. - Density condensation of Boolean formulas
Youichi Hanatani, Takashi Horiyama, Kazuo Iwama
Proc. of the 6th International Conference on Theory and Application of Satisfiability Testing, Lecture Notes in Computer Science, 2919, 69, 77, SPRINGER-VERLAG BERLIN, 2004年, ［査読有り］
英語, 研究論文（学術雑誌）, The following problem is considered: Given a Boolean formula f, generate another formula g such that: (i) If f is unsatisfiable then g is also unsatisfiable. (ii) If f is satisfiable then g is also satisfiable and furthermore g is "easier" than f. For the measure of this easiness, we use the density of a formula f which is defined as (the number of satisfying assignments) / 2(n), where n is the number of Boolean variables of f. In this paper, we mainly consider the case that the input formula f is given as a 3-CNF formula and the output formula g may be any formula using Boolean AND, OR and negation. Two different approaches to this problem axe presented: One is to obtain g by reducing the number of variables and the other by increasing the number of variables, both of which are based on existing SAT algorithms. Our performance evaluation shows that, a little surprisingly, better SAT algorithms do not always give us better density-condensation algorithms. This is a preliminary report of the on-going research. - Minimization of Fractional Wordlength on Fixed-Point Conversion for High-Level Synthesis
N. Doi, T. Horiyama, M. Nakanishi, S. Kimura
In. Proc. of Asia and South Pacific Design Automation Conference 2004 (ASP-DAC 2004), 80, 85, 2004年01月, ［査読有り］
英語, 研究論文（国際会議プロシーディングス） - Bit Length Optimization of Fractional Part on Floating to Fixed Point Conversion for High-Level Synthesis
N. Doi, T. Horiyama, M. Nakanishi, S. Kimura, K. Watanabe
IEICE Trans. Fundamentals, E86-A, 12, 3184, 3191, 一般社団法人電子情報通信学会, 2003年12月, ［査読有り］
英語, 研究論文（学術雑誌）, In the hardware synthesis from a high-level language such as C, the bit length of variables is one of the key issues for the area and speed optimization. Usually, designers are required to optimize the bit-length of each variable manually using the time-consuming simulation on huge-data. In this paper, we propose an optimization method of the fractional bit length in the conversion from floating-point variables to fixed-point variables. The method is based on error propagation and the backward propagation of the accuracy limitation. The method is fully analytical and fast compared to simulation based methods. - Finding essential attributes from binary data
E Boros, T Horiyama, T Ibaraki, K Makino, M Yagiura
ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE, 39, 3, 223, 257, SPRINGER, 2003年11月, ［査読有り］
英語, 研究論文（学術雑誌）, We consider data sets that consist of n-dimensional binary vectors representing positive and negative examples for some ( possibly unknown) phenomenon. A subset S of the attributes ( or variables) of such a data set is called a support set if the positive and negative examples can be distinguished by using only the attributes in S. In this paper we study the problem of finding small support sets, a frequently arising task in various fields, including knowledge discovery, data mining, learning theory, logical analysis of data, etc. We study the distribution of support sets in randomly generated data, and discuss why finding small support sets is important. We propose several measures of separation ( real valued set functions over the subsets of attributes), formulate optimization models for finding the smallest subsets maximizing these measures, and devise efficient heuristic algorithms to solve these ( typically NP-hard) optimization problems. We prove that several of the proposed heuristics have a guaranteed constant approximation ratio, and we report on computational experience comparing these heuristics with some others from the literature both on randomly generated and on real world data sets. - Bit Length Optimization of Fractional Parts on Floating to Fixed Point Conversion for High-Level Synthesis
N. Doi, T. Horiyama, M. Nakanishi, S. Kimura, K. Watanabe
Proc. of 12th Workshop on Synthesis And System Integration of Mixed Information technologies (SASIMI2003), 129, 136, 2003年04月, ［査読有り］
英語, 研究論文（国際会議プロシーディングス） - Translation among CNFs, characteristic models and ordered binary decision diagrams
Takashi Horiyama, Toshihide Ibaraki
Information Processing Letters, 85, 4, 191, 198, ELSEVIER SCIENCE BV, 2003年02月, ［査読有り］
英語, 研究論文（学術雑誌）, We consider translation among conjunctive normal forms (CNFs), characteristic models, and ordered binary decision diagrams (OBDDs) of Boolean functions. It is shown in this paper that Horn OBDDs can be translated into their Horn CNFs in polynomial time. As for the opposite direction, the problem can be solved in polynomial time if the ordering of variables in the resulting OBDD is specified as an input. In case that such ordering is not specified and the resulting OBDD must be of minimum size, its decision version becomes NP-complete. Similar results are also obtained for the translation in both directions between characteristic models and OBDDs. We emphasize here that the above results hold on any class of functions having a basis of polynomial size. (C) 2002 Elsevier Science B.V. All rights reserved. - An On-Chip High Speed Serial Communication Method Based on Independent Ring Oscillators
S. Kimura, T. Hayakawa, T. Horiyama, M. Nakanishi, K. Watanabe
Proc. of International Solid-State Circuits Conference (ISSCC2003), 390, 391, 2003年02月, ［査読有り］
英語, 研究論文（国際会議プロシーディングス） - Look up table compaction based on folding of logic functions
S Kimura, A Ishii, T Horiyama, M Nakanishi, H Kajihara, K Watanabe
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, E85A, 12, 2701, 2707, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, 2002年12月, ［査読有り］
英語, 研究論文（学術雑誌）, The paper describes the folding method of logic functions to reduce the size of memories to keep the functions. The folding is based on the relation of fractions of logic functions. If the logic function includes 2 or 3 same parts, then only one part should be kept and other parts can be omitted. We show that the logic function of I-bit addition can be reduced to half size using the bit-wise NOT relation and the bit-wise OR relation. The paper also introduces 3-1 LUT's with the folding mechanism. A full adder can be implemented using only one 3-1 LUT with the folding. Multi-bit AND and OR operations can be mapped to our LUT's not using the extra cascading circuit but using the carry circuit for addition. We have also tested the mapping capability of 4 input functions to our 3-1 LUT's with folding and carry propagation mechanisms. We have shown the reduction of the area consumption when using our LUT's compared to the case using 4-1 LUT's on several benchmark circuits. - Folding of Logic Functions and Its Application to Look Up Table Compaction
S. Kimura, T. Horiyama, M. Nakanishi, H. Kajihara
Proc. of International Conference on Computer Aided Design (ICCAD2002), 694, 698, 2002年11月, ［査読有り］
英語, 研究論文（国際会議プロシーディングス） - Ordered binary decision diagrams as knowledge-bases
Takashi Horiyama, Toshihide Ibaraki
Artificial Intelligence, 136, 2, 189, 213, ELSEVIER SCIENCE BV, 2002年04月, ［査読有り］
英語, 研究論文（学術雑誌）, We consider the use of ordered binary decision diagrams (OBDDs) as a means of realizing knowledge-bases, and show that, from the view point of space requirement, the OBDD-based representation is more efficient and suitable in some cases, compared with the traditional CNF-based and/or model-based representations. We then present polynomial time algorithms for the two problems of testing whether a given OBDD represents a unate Boolean function, and of testing whether it represents a Horn function. (C) 2002 Published by Elsevier Science B.V. - Translation among CNFs, characteristic models and ordered binary decision diagrams
Takashi Horiyama, Toshihide Ibaraki
Proc. of the 12th Annual International Symposium on Algorithms and Computation, Lecture Notes in Computer Science, 2223, 231, 243, SPRINGER-VERLAG BERLIN, 2001年12月, ［査読有り］
英語, 研究論文（学術雑誌）, We consider translation among conjunctive normal forms (CNFs), characteristic models, and ordered binary decision diagrams (OBDDs) of Boolean functions. It is shown in this paper that Horn OBDDs can be translated into their CNFs in polynomial time. As for the opposite direction, the problem can be solved in polynomial time if the ordering of variables in the resulting OBDD is specified as an input. In case that such ordering is not specified and the resulting OBDD must be of minimum size, its decision version becomes NP-complete. Similar results are also obtained for the translation in both directions between characteristic models and OBDDs. We emphasize here that the above results holds on any class of functions having a basis B with \B\ = d. - Speech Recognition Chip for Monosyllables
Kazuhiro Nakamura, Qiang Zhu, Shinji Maruoka, Takashi Horiyama, Shinji Kimura, Katsumasa Watanabe
Proc. of the 6th Asia and South Pacific Design Automation Conference, 396, 399, 2001年01月, ［査読有り］ - A Real-time 64-Monosyllable Recognition LSI with Learning Mechanism
Kazuhiro Nakamura, Qiang Zhu, Shinji Maruoka, Takashi Horiyama, Shinji Kimura, Katsumasa Watanabe
Proc. of the 6th Asia and South Pacific Design Automation Conference, 31, 32, 2001年01月, ［査読有り］ - Reasoning with ordered binary decision diagrams
Takashi Horiyama, Toshihide Ibaraki
Proc. of the 11th Annual International Symposium on Algorithms and Computation, Lecture Notes in Computer Science, 1969, 120, 131, SPRINGER-VERLAG BERLIN, 2000年12月, ［査読有り］
英語, 研究論文（学術雑誌）, We consider problems of reasoning with a knowledge-base, which is represented by an ordered binary decision diagram (OBDD), for two special cases of general and Horn knowledge-bases. Our main results say that both finding a, model of a knowledge-base and deducing from a knowledge-base. can be done in linear time for general case, but that abduction is NP-complete even if the knowledge-base is restricted to be Horn. Then, we consider the abduction when its assumption set consists of all propositional literals (i.e., an answer for a given query is allowed to include any positive literals), and show that it can be done in polynomial time if the knowledge-base is Horn, while it remains NP-complete for the general case. Some other solvable cases axe also discussed. - New Graph Calculi for Planar Non-3-Colorable Graphs,
Youichi Hanatani, Takashi Horiyama, Kazuo Iwama, Suguru Tamaki
IEICE Trans. Fundamentals of Electronics, Communications and Computer Sciences, E91-A, 9, 2301, 2307, 2000年09月, ［査読有り］ - Finding Essential Attributes in Binary Data.
Endre Boros, Takashi Horiyama, Toshihide Ibaraki, Kazuhisa Makino, Mutsunori Yagiura
Proc. of the 2nd International Conference on Intelligent Data Engineering and Automated Learning, Lecture Notes in Computer Science, 1983, 133, 138, Springer, 2000年, ［査読有り］
研究論文（国際会議プロシーディングス） - Ordered binary decision diagrams as knowledge-bases
Takashi Horiyama, Toshihide Ibaraki
Proc. of the 10th Annual International Symposium on Algorithms and Computation, Lecture Notes in Computer Science, 1741, 83, 92, SPRINGER-VERLAG BERLIN, 2000年, ［査読有り］
英語, 研究論文（学術雑誌）, We propose to make use of ordered binary decision diagrams (OBDDs) as a means of realizing knowledge-bases. We show that the OBDD-based representation is more efficient and suitable in some cases, compared with the traditional CNF-based and/or model-based representations in the sense of space requirement. We then consider two recognition problems of OBDDs, and present polynomial time algorithms for testing whether a given OBDD represents a unate Boolean function, and whether it represents a Horn function. - A High-Speed Reduced-Size Adder Under Left-to-Right Input Arrival.
Naofumi Takagi, Takashi Horiyama
IEEE Transactions on Computers, 48, 1, 76, 80, 1999年, ［査読有り］
研究論文（学術雑誌） - Exponential Lower Bounds on the Size of Variants of OBDD Representing Integer Division
Takashi Horiyama, Shuzo Yajima
IEICE Trans. Inf. & Syst, E81-D, 8, 793, 800, 1998年08月, ［査読有り］ - Exponential Lower Bounds on the Size of OBDDs Representing Integer Divistion.
Takashi Horiyama, Shuzo Yajima
Proc. of the 8th Annual International Symposium on Algorithms and Computation, Lecture Notes in Computer Science, 1350, 163, 172, Springer, 1997年, ［査読有り］
研究論文（国際会議プロシーディングス）
その他活動・業績
- Enumeration of Non-isomorphic Unordered Trees with Degree Sequence Constraints
Shuhei Denzumi, Takashi Horiyama, Kazuhiro Kurita, Atsuki Nagao, Kazuhisa Seto, Kunihiro Wasa, 情報処理学 会, アルゴリズム研究会, 192, 11, 1, 6, 2023年05月 - ZDD を用いた最適円 筒あみだくじの列挙
岩崎善泰, 堀山貴史, 松井泰子, 野崎雄太, 脊戸和寿, 山中克久, 情報処理学会, アルゴリズム研究会, 192, 3, 1, 8, 2023年03月 - あみだくじと菱形タイリングの列挙
堀山貴史, 科学研究費補助金学術 変革領域(B) 組合せ遷移の展開に向けた計算機科学・工学・数学によるアプローチ の融合, 第34 回セミナー, 2023年01月, ［招待有り］ - 自己同型写像の断片を用いた代表元の反復抽出によ る同型性の除去
高橋孔平, 脊戸和寿, 堀山貴史, 電子情報通信学会技術研究報告, 122, 294, 51, 58, 2022年12月 - 最小重み Laman グラフの総交点数と厚みの下界の改良
河上悠輝, 高橋駿, 脊戸和寿, 堀山貴史, 小林祐貴, 東川雄哉, 加藤直樹, 第35 回回路とシステムワークショッ プ, 191, 196, 2022年08月 - 文字列中の異なる閉文字列の数え上げと 最大個数について
高橋駿, 脊戸和寿, 堀山貴史, 三重野琢也, 夏のLAシンポジウム, 2022年07月 - 区間最長回文クエリに対する時間最適 アルゴリズム
三谷和暉, 脊戸和寿, 堀山貴史, 三重野琢也, 夏のLAシンポジウム, 2.1, 2.8, 2022年07月 - 最小重み Laman グラフの総交点数と厚みの下界の改良
河上悠輝, 高橋駿, 脊戸和寿, 堀山貴史, 小林祐貴, 東川雄哉, 加藤直樹, 夏のLAシンポジウム, 4.1, 4.7, 2022年07月 - 複数の多面体の共通の展開図について
堀山貴史, 科学研究費補助金学術 変革領域(A) 社会変革の源泉となる革新的アルゴリズム基盤の創出と体系化, AFSA コロキウム, 2022年07月, ［招待有り］ - 正四面体の測地線折り
西本清里, 堀山貴史, 舘知宏, 第32 回折り紙の科学・数学・ 教育研究集会, 2022年06月 - Solving Rep-tile by Computers
Mutsunori Banbara, Kenji Hashimoto, Takashi Horiyama, Shin-ichi Minato, Kakeru Nakamura, Masaaki Nishino, Masahiko Sakai, Ryuhei Uehara, Yushi Uno, Norihito Yasuda, 14th Gathering 4 Gardner Conference, 2022年04月 - レプ・タイルの定式化を用いた各種ソルバの性能比較
番原睦則, 橋本健二, 堀山貴史, 湊真一, 中村駆, 西野正彬, 酒井正彦, 上原隆平, 宇野, 裕之, 安田宜仁, 第16 回組合せ ゲーム・パズル研究集会, 2022年03月 - ZDD の区間メモ化探索 技法によるコスト制約組合せ問題の高速な解列挙
湊真一, 番原睦則, 堀山貴史, 川原純, 瀧川一学, 山口勇太郎, 情報処理学会, アルゴリズム研究会, 1, 8, 2022年03月 - 45度系格子パターンにおける局 所平坦折り可能な展開図の数え上げとZDDによる列挙
榎本優大, 河上悠輝, 脊戸和寿, 堀山貴史, 三谷純, 冬のLAシンポジウム, 6.1, 6.12, 2022年02月 - フィボナッチ文字列の最小文法は RePair 文法
三重野琢也, 稲永俊介, 堀山貴史, 冬のLAシンポジウム, 20.1, 20.3, 2022年02月 - あみだくじと菱形タイリングの列挙
堀山貴史, 人工知能学会, 第119 回 人工知能基本問題研究会, 1, 2022年01月, ［招待有り］ - Interval-Memoized Backtracking on ZDDs for Fast Enumeration of All Lower Cost Solutions.
Shin-ichi Minato, Mutsunori Banbara, Takashi Horiyama, Jun Kawahara, Ichigaku Takigawa, Yutaro Yamaguchi 0005, CoRR, abs/2201.08118, 2022年01月 - ポリオミノ と格子凸多角形による多層タイル張り
千田皐汰, Erik Demaine, Martin Demaine, David Eppstein, Adam Hesterberg, 堀山貴史, John Iacono, 伊藤大雄, Stefan Langerman, 上原隆平, 宇野裕之, 電子情報通信学会技術研究報告, 121, 218, 11, 18, 2021年10月 - Solving Rep-tile by Computers: Performance of Solvers and Analyses of Solutions.
Mutsunori Banbara, Kenji Hashimoto, Takashi Horiyama, Shin-ichi Minato, Kakeru Nakamura, Masaaki Nishino, Masahiko Sakai, Ryuhei Uehara, Yushi Uno, Norihito Yasuda, CoRR, abs/2110.05184, 2021年10月 - ZDD による45 度系格子パターンにおける局 所平坦折り可能な展開図の列挙
榎本優大, 脊戸和寿, 堀山貴史, 三谷純, 第29 回折り紙の科学・数学・教育研究集会, 2021年06月 - 動的計画法に基づくSimple Polygonization 列挙アルゴリズムの実験的評価
中畑裕, 堀山貴史, 湊真一, 山中克久, 情報処理学会, アルゴリズム研究会, 1, 8, 2021年03月 - コスト制約つき組合せ問題に対するZDDを用いた高速な解列挙手法
湊真一, 番原睦則, 堀山貴史, 川原純, 瀧川一学, 山口勇太郎, 電子情報通信学会技術研究報告, 120, 276, 8, 15, 2020年12月 - 覆面算を列挙するオートマトンの効率的な構築手法
渡部航也, ヘンリアンディプタラマ, 吉仲亮, 堀山貴史, 篠原歩, 電子情報通信学会技術研究報告,, 120, 276, 16, 23, 2020年12月 - 正多面体の折り判定問題の多項式時間解法
上原隆平, 門口あきら, 鎌田斗南, 堀山貴史, 第29 回折り紙の科学・数学・教育研究集会, 2020年12月 - Sorting by Five Prefix Reversals
Tetsuya Araki, Takashi Horiyama, Shin-ichi Nakano, Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno, Katsuhisa Yamanaka, 情報処理学会, アルゴリズム研究会, 1, 7, 2020年09月 - Polyhedral Forms from Folding Geodesic Strips
Seri Nishimoto, Takashi Horiyama, Tomohiro Tachi, Virtual Technical Meeting of the Society of Engineering Science, 2020年09月 - Compiling Crossing-free Geometric Graphs with Connectivity Constraint for Fast Enumeration, Random Sampling, and Optimization.
Yu Nakahata, Takashi Horiyama, Shin-ichi Minato, Katsuhisa Yamanaka, CoRR, abs/2001.08899, 2020年01月
英語, 機関テクニカルレポート，技術報告書，プレプリント等 - Implicit Enumeration of Topological-Minor-Embeddings and Its Application to Planar Subgraph Enumeration.
Yu Nakahata, Jun Kawahara, Takashi Horiyama, Shin-ichi Minato, CoRR, abs/1911.07465, 2019年11月
英語, 機関テクニカルレポート，技術報告書，プレプリント等 - Enumeration with Isomorphism Elimination
Takashi Horiyama, The 3rd International Workshop on Enumeration Problems & Applications, 2019年10月, ［招待有り］ - Decomposing a Graph into Unigraphs.
Takashi Horiyama, Jun Kawahara, Shin-ichi Minato, Yu Nakahata, CoRR, abs/1904.09438, 2019年
英語, 機関テクニカルレポート，技術報告書，プレプリント等 - The Complexity of Ladder-Lottery Realization Problem (回路とシステム)
YAMANAKA KATSUHISA, HORIYAMA TAKASHI, UNO TAKEAKI, WASA KUNIHIRO, 電子情報通信学会技術研究報告 = IEICE technical report : 信学技報, 118, 295, 1, 6, 2018年11月12日
電子情報通信学会, 英語 - The Complexity of Ladder-Lottery Realization Problem (システム数理と応用)
YAMANAKA KATSUHISA, HORIYAMA TAKASHI, UNO TAKEAKI, WASA KUNIHIRO, 電子情報通信学会技術研究報告 = IEICE technical report : 信学技報, 118, 296, 1, 6, 2018年11月12日
電子情報通信学会, 英語 - フロンティア法によるDAGの非巡回縮約の列挙
中畑 裕, 鈴木 浩史, 石畠 正和, 堀山 貴史, 人工知能学会全国大会論文集, JSAI2018, 4K1OS16a03, 4K1OS16a03, 2018年
有向非巡回グラフ（DAG）は計算機科学における基本的な構造である． 応用において，DAGをより小さなDAGに縮約する問題は，命令セット拡張問題等のために重要である． 本研究では，DAGが与えられたとき，いくつかの辺を選んで縮約した結果がDAGとなるような辺の選び方をすべて列挙するアルゴリズムを提案する． 提案手法はフロンティア法に基づき，所望の辺部分集合の族を表現するデータ構造ZDDを構築するアルゴリズムである．, 一般社団法人 人工知能学会, 日本語 - 非同型な2端子直並列グラフの列挙とランダムサンプリング
伝住周平, 堀山貴史, 栗田和宏, 中畑裕, 鈴木浩史, 和佐州洋, 山崎一明, 電子情報通信学会技術研究報告, 118, 216(COMP2018 9-20)(Web), 2018年 - On the base-line location problem for the maximum weight region decomposable into base-monotone shapes (New Trends in Algorithms and Theory of Computation)
Horiyama Takashi, Ito Takehiro, Ono Hirotaka, Otachi Yota, Uehara Ryuhei, Uno Takeaki, 数理解析研究所講究録, 1799, 123, 129, 2012年06月
京都大学数理解析研究所, 英語 - アスペクト比を固定した最小の周囲長方形について (アルゴリズムと計算理論の新展開)
小林 有, 堀山 貴史, 数理解析研究所講究録, 1799, 65, 66, 2012年06月
京都大学数理解析研究所, 日本語 - いかなる辺展開でも正多面体は重なりを持たない (計算機科学とアルゴリズムの数理的基礎とその応用)
堀山 貴史, 庄子 亘, 数理解析研究所講究録, 1744, 159, 160, 2011年06月
京都大学, 英語 - 秘密分散を用いた安全な Vickrey オークション
杉本 琢磨, 堀山 貴史, 電子情報通信学会技術研究報告. COMP, コンピュテーション, 110, 232, 19, 25, 2010年10月08日
Vickreyオークションでは,第一価格を入札した者が,第二価格で商品を落札する.このオークションは,入札者に対し誘因両立性を持つことが知られている.一方,入札者のプライバシーに配慮して,各入札者の入札額や誰が落札したかを入札者には伏せたまま実行する場合には,競売人が落札者に対して第二価格を偽ることができる.本研究では,秘密分散を用いることで,競売人の不正を許さず,全体の半分未満の参加者がsemi-honestな参加者として結託したとしても情報を漏らさない情報理論的に安全なプロトコルを提案する.このプロトコルは,入札者が直接情報のやり取りを行うことで,第三者機関を必要としないことが特長である.さらに,第一価格入札者が複数存在した場合のタイブレークの方法,オークションの結果が正当であり競売人による不正が無かったことを入札者に納得させる方法を提案する., 一般社団法人電子情報通信学会, 日本語 - 1-D-5 最長路問題と最大経路差問題 : その解法とJR大都市近郊区間大回りへの応用(離散・組合せ最適化(2))
堀山 貴史, 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 2009, 80, 81, 2009年09月09日
公益社団法人日本オペレーションズ・リサーチ学会, 日本語 - 最長路問題とJR大都市近郊区間大回りへの応用
堀山 貴史, 樋口 康介, 電子情報通信学会技術研究報告. COMP, コンピュテーション, 109, 108, 17, 21, 2009年06月22日
最長路問題は、各辺に非負整数の距離が与えられた無向グラフに対し、始点s、終点t間のシンプルなパスで、その上の距離の総和が最大となるものを求める問題である。最長路問題は、効率的な多項式時間アルゴリズムが古くから知られている最短路問題とは異なった性質を持つ。例えば、各辺に関連付けられた距離の正負を反転させた最短路問題を解くことで最長路が得られるように一見思われるが、負の閉路(距離の総和が負となる閉路)が存在するため、最短路問題のアルゴリズムを適用することはできない。本研究では、最長路問題、s-t最長路問題、全点対最長路問題を定式化し、全探索および0-1整数計画法に基づく厳密最適化アルゴリズムを提案する。また、JR大都市近郊区間の大回りをベンチマークとして利用し、各手法の実装および評価を与える。, 一般社団法人電子情報通信学会, 日本語 - Enumeration of Polyominoes for p4 Isohedral Tiling by the Reverse Search
T. Horiyama, M. Samejima, Proc. of the 2nd Asian Association for Algorithms and Computation Annual Meeting, (to appear), 2009年 - Enumeration of Polyominoes for p4 Isohedral Tiling by the Reverse Search
T. Horiyama, M. Samejima, Proc. of the 2nd Asian Association for Algorithms and Computation Annual Meeting, (to appear), 2009年 - Fine-grained power gating based on the controlling value of logic gates (VLSI設計技術)
Chen Lei, Horiyama Takashi, Nakamura Yuichi, KIMURA Shinji, 電子情報通信学会技術研究報告. VLD, VLSI設計技術, 108, 23, 19, 24, 2008年05月09日
Leakage power dissipation of logic gates has become an increasingly important problem. A novel fine-grained power gating approach based on the controlling value of logic gates is proposed for leakage power reduction. In the method, sleep signals of the power-gated blocks are extracted based on the probability of the controlling value of logic gates without any extra control logic. A basic algorithm and a probability-based heuristic algorithm have been developed to implement this method. The steady maximum delay constraint has also been introduced to handle the delay overhead. Experiments on the ISCAS'85 benchmarks show the effectiveness of our algorithms and the effect on the extra delay., 一般社団法人電子情報通信学会, 英語 - Fine-grained power gating based on the controlling value of logic gates (システムLSI設計技術)
Lei Chen, Takashi Horiyama, Yuichi Nakamura, Shinji Kimura, 情報処理学会研究報告システムLSI設計技術（SLDM）, 2008, 38, 55, 60, 2008年05月01日
Leakage power dissipation of logic gates has become an increasingly important problem. A novel fine-grained power gating approach based on the controlling value of logic gates is proposed for leakage power reduction. In the method sleep signals of the power-gated blocks are extracted based on the probability of the controlling value of logic gates without any extra control logic. A basic algorithm and a probability-based heuristic algorithm have been developed to implement this method. The steady maximum delay constraint has also been introduced to handle the delay overhead. Experiments on the ISCAS'85 benchmarks show the effectiveness of our algorithms and the effect on the extra delay.Leakage power dissipation of logic gates has become an increasingly important problem. A novel fine-grained power gating approach based on the controlling value of logic gates is proposed for leakage power reduction. In the method, sleep signals of the power-gated blocks are extracted based on the probability of the controlling value of logic gates without any extra control logic. A basic algorithm and a probability-based heuristic algorithm have been developed to implement this method. The steady maximum delay constraint has also been introduced to handle the delay overhead. Experiments on the ISCAS'85 benchmarks show the effectiveness of our algorithms and the effect on the extra delay., 一般社団法人情報処理学会, 英語 - Density Condensation of Boolean Formulas Based on Covering Codes
T. Horiyama, A. Sato, Proc. of the 1st Asian Association for Algorithms and Computation Annual Meeting, 1, 28, 2008年 - 平面グラフにおける Hajos Calculus の複雑さについて
花谷 陽一, 堀山 貴史, 岩間 一雄, 玉置 卓, 電子情報通信学会技術研究報告. COMP, コンピュテーション, 107, 219, 43, 50, 2007年09月13日
The planar Hajos calculus is the Hajos calculus with the restriction that all the graphs that appear in the construction (including a final graph) must be planar. We prove that the planar Hajos calculus is polynomially bounded iff the Hajos calculus is polynomially bounded., 一般社団法人電子情報通信学会, 英語 - Truthful Auctions with Limited Range of Bids
T. Horiyama, K. Iwama, D. Sumita, Proc. of the 5th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, 5, 53, 61, 2007年 - 二段組合せ回路の最大動作率について(計算理論とアルゴリズムの新展開)
阿武 孝文, 堀山 貴史, 岩間 一雄, 数理解析研究所講究録, 1489, 188, 194, 2006年05月
京都大学, 日本語 - 非線形方程式と整数解の探索に基づく高位合成向けビット長最適化
土井 伸洋, 堀山 貴志, 中西 正樹, 木村 晋二, 情報処理学会研究報告システムLSI設計技術（SLDM）, 2005, 27, 133, 138, 2005年03月18日
ハードウェア設計においては浮動小数点演算の固定小数点演算化が面積速度の点から重要であるが，変換においては演算誤差を考慮してビット最適化が必要であることから，人手による変換は困難であった．そこで我々はビット長最適化問題を非線形問題へ帰着させて解く自動化手法の研究を行っている．一般的な非線形計画法では探索により整数解を求める方法を示す．This paper presents bit-length optimization technique for high-level synthesis based on non-linear programming and searching integer solutions. The results of the bit-length optimization based on non-linear programming are real values, and these values are converted to integer with round-up for hardware implementation. In this paper, we show a method to search integer solutions under the constrains of the real solution. The experimental results shows the advantage of searching based method., 一般社団法人情報処理学会, 日本語 - 非線形方程式と整数解の探索に基づく高位合成向けビット長最適化
土井 伸洋, 堀山 貴史, 中西 正樹, 木村 晋二, 電子情報通信学会技術研究報告. CPSY, コンピュータシステム, 104, 738, 43, 48, 2005年03月11日
ハードウェア設計においては浮動小数点演算の固定小数点演算化が面積や速度の点から重要であるが, 変換においては演算誤差を考慮したビット長最適化が必要であることから, 人手による変換は困難であった.そこで我々はビット長最適化問題を非線形問題へ帰着させて解く自動化手法の研究を行なっている.一般的な非線形計画法では解が実数となるため, ビット長最適化においては解の切上げが必要であった.そこで本稿では, 実数解の制約のもとで, 探索により整数解を求める方法を示す., 一般社団法人電子情報通信学会, 日本語 - 抽象解釈手法に基づく変数の相互関係解析とそのデータパス最適化への応用
土井 伸洋, 堀山 貴史, 中西 正樹, 木村 晋二, 情報処理学会研究報告システムLSI設計技術（SLDM）, 2004, 56, 41, 46, 2004年05月28日
Cプログラムからのハードウェア合成においてはビット長最適化をはじめとするさまざまなハードウェア向け最適化が必要である．このためにはプログラム中の変数がとりうる値やデータフローを推測することが必要で，静的解析手法が使われることが多いが，精度などの点で不十分な点がある．本稿ではソフトウエア検証の分野で注目されている抽象解釈（Abstract Interpretation）手法に基づくプログラムの解析と，データパス最適化への応用について述べる．Various optimization techniques such as bit-length optimization are required for hardware generation from C programs. The value range analysis and dataflow analysis are effective for such optimization and static pro gram analysis methods have been used. The static methods, however, have several problems such as the preciseness, the overestimation, etc. In this paper, we describe a program analysis method based on abstract interpretation and its application for datapath optimization., 一般社団法人情報処理学会, 日本語 - オンライン問題の競合比解析の自動化について (計算機科学基礎理論の新展開)
正西 申悟, 堀山 貴史, 岩間 一雄, 数理解析研究所講究録, 1375, 68, 77, 2004年05月
京都大学, 英語 - 守備特訓に喘ぐ外野手のための捕球経路問題 (計算機科学基礎理論の新展開)
佐久間 俊慎, 小野 廣隆, 山下 雅史, 朝廣 雄一, 牧野 和久, 堀山 貴史, 数理解析研究所講究録, 1325, 8, 14, 2003年05月
京都大学, 日本語 - 論理関数の畳み込み機構を導入した省面積FPGAの実現と評価
梶原 裕嗣, 中西 正樹, 堀山 貴史, 木村 晋二, 渡邉 勝正, 情報処理学会研究報告システムLSI設計技術（SLDM）, 2003, 7, 37, 42, 2003年01月28日
論理関数の畳み込み機構を導入した新しい省面積FPGAの機構とその実現手法を提案し，LSI実現での面積および遅延の評価を示す．配線構造としては，広く用いられているislandスタイルに基づいている．複数のベンチマーク回路での評価により，通常の4-1LUTと比較して，最大で32.4％，平均でも12％の面積削減が可能であることがわかった．The paper describes an area efficient FPGA architecture based on LUTs with logic function folding. Each LUT is a 3-1 LUT but is enhanced to implement a full adder function with only one LUT. The area of our 3-1 LUT is about 56% compared to that of a simple 4-1 LUT. In the paper, we measure not only the LUT area but also the area of routing resource. We adopt the well-known island style-architecture for the routing mechanism, and find that the total FPGA area can be saved up to 32.4% and on average 12% by the experiments on several benchmark circuits compared to FPGA architecture based on 4-1 LUTs., 一般社団法人情報処理学会, 日本語 - A-3-25 論理関数の重ね合わせに基づく加減算向きLUT
石井 淳, 梶原 裕嗣, 中西 正樹, 堀山 貴史, 木村 晋二, 渡邉 勝正, 電子情報通信学会総合大会講演論文集, 2002, 104, 104, 2002年03月07日
一般社団法人電子情報通信学会, 日本語 - Deduction and Abduction with Ordered Binary Decision Diagrams (計算機科学の基礎理論:21世紀の計算パラダイムを目指して)
堀山 貴史, 茨木 俊秀, 数理解析研究所講究録, 1148, 175, 180, 2000年04月
京都大学, 英語 - Ordered Binary Decision Diagrams Representing Knowledge-Bases (Models of Computation and Algorithms)
堀山 貴史, 茨木 俊秀, 数理解析研究所講究録, 1093, 93, 98, 1999年04月
京都大学, 英語 - Knowledge-Base Representation and Recognition of Positive/Horn Functions on Ordered Binary Decision Diagrams
HORIYAMA T., Technical Report of IEICE, 98, 17, 24, 1999年 - 除算を表現する二分決定グラフの指数下界
堀山 貴史, 矢島 脩三, 全国大会講演論文集, 53, 175, 176, 1996年09月04日
The size of an OBDD largely depends on the variable ordering. It is important to clarify the lower bounds of OBDDs representing arithmetic functions. In this report, we investigate a lower bound of the size of OBDDs representing integer division. More precisely, we focus on each bit of the output of the n-bit / n-bit division, and prove that the size of OBDDs representing the i-th bit is Ω(2^<(n-2)/8>). We also prove the same lower bound on ∨V-OBDDs, ∧-OBDDs and ⊕ -OBDDs. To prove this lower bound, we introduce a strong fooling set, which has a more restricted property than a fooling set., 英語
共同研究・競争的資金等の研究課題
- 無限平面上の離散構造列挙と類似度設計による結晶の表面構造探索
科学研究費助成事業
2023年04月01日 - 2028年03月31日
久保山 哲二, 草場 彰, 堀山 貴史, 宇野 毅明, 平田 耕一
日本学術振興会, 基盤研究(B), 学習院大学, 23H03461 - 組合せ剛性工学の実現に向けた理論基盤構築
科学研究費助成事業
2024年04月01日 - 2027年03月31日
東川 雄哉, 加藤 直樹, 照山 順一, 堀山 貴史, Sljoka Adnan, 安田 修悟, 小林 祐貴
日本学術振興会, 基盤研究(B), 兵庫県立大学, 23K28040 - 組合せ剛性工学の実現に向けた理論基盤構築
科学研究費助成事業
2023年04月01日 - 2027年03月31日
東川 雄哉, 加藤 直樹, 照山 順一, 堀山 貴史, Sljoka Adnan, 安田 修悟, 小林 祐貴
日本学術振興会, 基盤研究(B), 兵庫県立大学, 23H03350 - タイリング理論と分子科学の協働によるウイルス外殻構造の新たな設計原理の探究
科学研究費助成事業
2023年06月30日 - 2026年03月31日
松永 康佑, 舘 知宏, 堀山 貴史
日本学術振興会, 挑戦的研究(萌芽), 埼玉大学, 23K18105 - 列挙や数え上げなどを統一的に扱うための基盤技術
科学研究費助成事業
2022年04月01日 - 2026年03月31日
堀山 貴史, 伝住 周平, 和佐 州洋, 栗田 和宏, 脊戸 和寿, 中畑 裕
列挙、数え上げ、サンプリングなどのアルゴリズムは、互いに深く関連しつつも、それぞれ独自の技法が必要とされることが多い。ここで、同じ制約条件のもとで、つまり同じ解空間において、解の列挙、数え上げなどタイプの異なるアルゴリズムそれぞれを個別に設計する状況を見つめ直し、アルゴリズム設計者が頭の中に持つ解空間に関する理解をもとにアルゴリズムを導出する過程を明らかにすることで、列挙、数え上げ、サンプリングなどのアルゴリズム設計を統一的に扱うための指針を与えることを本研究課題の目的としている。
本研究課題の研究者のみならず、課題外の連携研究者との議論も通して、列挙や数え上げなどのアルゴリズム設計の過程の再検討を行った。具体的には、たとえば、グラフの同型性の観点から代表元のみを列挙する同型性の除去について、ZDD (Zero-Suppressed Binary Decision Disgrams; 零抑制型二分決定グラフ) を用いるアプローチの検討を行った。制約条件を満たす解集合をうまく区分し、それらの区分された解集合相互の関係を表す方法を検討する際に、非同型なものを漏れなく重複なく求められる保証を与える必要があり、具体的なアルゴリズム設計を通して、アルゴリズム設計とアイデア記述に関する知見を得た。また、列挙と深い関連を持つ組合せ遷移問題も含めて、関連分野への応用に関する検討を行った。具体的には、たとえば、45度系格子パターン上での折り紙の展開図の列挙と数え上げの技法についてである。この問題では、縦横および斜め45度方向の格子上のみに折り線の位置を限定し、各頂点で平坦に折ることのできる局所平坦性を制約として、展開図の列挙または数え上げを行っている。また、格子の規則性から、回転および鏡映反転による同型性を考慮する必要があり、応用上の要請だけでなく、本研究課題の方向性にも沿った研究成果である。
日本学術振興会, 基盤研究(B), 北海道大学, 23K24806 - 列挙や数え上げなどを統一的に扱うための基盤技術
科学研究費助成事業 基盤研究(B)
2022年04月01日 - 2026年03月31日
堀山 貴史, 伝住 周平, 和佐 州洋, 栗田 和宏, 脊戸 和寿, 中畑 裕
日本学術振興会, 基盤研究(B), 北海道大学, 22H03549 - 計算折紙と細胞折紙技術による細胞の立体構造の最適化
科学研究費助成事業 基盤研究(B)
2022年04月01日 - 2025年03月31日
繁富 香織, 上原 隆平, 堀山 貴史
日本学術振興会, 基盤研究(B), 北海道大学, 22H01423 - 研究領域「革新的アルゴリズム基盤」の組織運営と研究推進
科学研究費助成事業 学術変革領域研究(A)
2020年11月19日 - 2025年03月31日
湊 真一, 宇野 毅明, 安田 宜仁, 堀山 貴史, 河原林 健一, 山下 茂, 牧野 和久, 上原 隆平, 瀧本 英二, 玉置 卓
2020年度の4か月間は、研究領域全体の組織立ち上げ準備の期間として位置づけ、本研究領域の目標や活動の方向性に関する参加メンバの意識合わせ、階層的な組織構成の整備と定例会議体制の設定、メーリングリストやSNS等による内部連絡体制・文書共有システムの整備、研究領域のwebサイトの立ち上げと広報資料の作成、連携拠点オフィスの確保と必要な什器や機材の整備、事務系/技術系スタッフの必要人数の精査と採用、研究領域全体で利用する大型計算サーバなどの共用設備の精査と購入計画の策定実施、十分な応募件数の公募班を集めるための広報活動と審査体制の整備、本研究領域の外部評価者の人選と依頼、等の共通的な業務を実施した。
2020年度の研究領域全体に関わるイベントとしては、全ての計画班の代表者・分担者を対象とした「内部向けキックオフ領域集会」を12月9日に開催したこと、および本研究領域に関心を持つ可能性がある全ての研究者を対象として対外向けの「スタートアップシンポジウム」を1月7日に開催した他、新設した京都寺町三条サテライトラボや既存の東京神田サテライトラボと各研究者が所属する研究機関をリモートで接続する体制を整え、小規模な研究打合せや運営会議を必要に応じて随時実施した。これらの活動実績により本研究領域全体の情報交換を円滑に行う体制が整いつつある。
以上の活動は、新型コロナの感染状況に応じて、対面と遠隔を適切に組合わせながら実施した。
日本学術振興会, 学術変革領域研究(A), 京都大学, 20H05961 - 大規模離散構造の理解と革新的アルゴリズム基盤の創出
科学研究費助成事業 学術変革領域研究(A)
2020年11月19日 - 2025年03月31日
堀山 貴史, 湊 真一, 上原 隆平, 宇野 裕之, 竹田 正幸, 番原 睦則, 松井 泰子
情報化社会におけるデータの規模の拡大や組合せの複雑化などにより、理論と実用の両方の観点から、問題が内包する大規模離散構造を利用したアルゴリズムの設計技法が求められている。本研究では、これまで個別の分野において個々のアイデアに基づいて設計されてきたアルゴリズムの成功事例を理論計算機科学の観点から改めて観察することで、大規模離散構造を理解し、その構造をどのように利用しているかを整理する。このケースワークをもとに、指数関数的な壁に立ち向かうアルゴリズム設計のための方法論を新たに体系化することで、理論と実装が一体となって大規模離散構造処理のための革新的アルゴリズム基盤技術へと昇華することを目指している。このために、具体的には、二分決定グラフ (BDD; Binary Decision Diagram) やその亜種の零抑制型二分決定グラフ (ZDD; Zero-suppressed BDD) のアルゴリズム、逆探索による列挙アルゴリズム、グラフ探索アルゴリズム、文字列処理アルゴリズム、論理式の充足可能性判定問題 (SAT; satisfiability problem) の充足解探索アルゴリズムなどの、指数関数的に大きな解空間を持つ問題における場合分けや数え上げ、列挙、索引化などが必要とされる分野を対象に、ケースワークを始めた。ここには、計算量理論の観点から、解を求めるための計算複雑さだけでなく、遷移問題も視野に入れている。こうした取り組みとして、具体的には、たとえば、与えられた点集合に対して自己交差のない多角形を求める単純多角形化問題において、逆探索の観点からの列挙だけでなく、ZDD 構築に用いられるフロンティア法の設計技法に着想を得て、問題の解空間の構造を把握する試みなどがある。
日本学術振興会, 学術変革領域研究(A), 北海道大学, 20H05964 - 離散構造処理系に基づく列挙と最適化の統合的技法の研究
科学研究費助成事業 基盤研究(A)
2020年04月01日 - 2025年03月31日
湊 真一, 堀山 貴史, 瀧川 一学, 川原 純, 番原 睦則, 山口 勇太郎
本年度の研究実績の概要は以下の通りである。
(i) 列挙と最適化の統合的アルゴリズム技法の研究と体系化：グラフの最短路問題のように、組合せ問題のアイテムにコストが定義されているときに、コスト総和が所与の閾値以下となるような実行可能解を列挙することは、多くの実用的な応用を持つ汎用的で重要な問題である。このような一般的なコスト制約つき組合せ問題に対して、ZDDを用いて大量の解を高速に全列挙する手法を考案した。実験の結果、実用的な規模の例題に対して、数百万通りの解集合を表すZDDを1秒以内で構築することができた。本研究結果は研究代表者自らが筆頭著者として国内研究会で発表し、今後、国際会議または論文誌での発表を目指して準備を進めている。
(ii) 離散構造処理系の基盤アルゴリズムの実装とソフトウェアの整備：BDD/ZDDをベースとする離散構造処理系のアルゴリズムは、原則として「BDDパッケージ」と呼ばれるソフトウェアライブラリとして公開されている。今年度に開発した高速列挙アルゴリズムの実装もこのパッケージに追加し、整備を進めている。
(iii) 関連分野との連携および応用分野への発展：ERATOや基盤(S)プロジェクトで形成された研究者コミュニティを可能な範囲で維持し、研究者が集まり最新の技術情報を交換する「場」を確保することを目的として、2020年9月17日に「基盤(A) プロジェクト近況報告＆自由討論会」と呼ぶオンラインワークショップを企画した。最終的に48名の研究者が参加して活発な討論が行われ、研究者コミュニティの活性化に貢献した。
日本学術振興会, 基盤研究(A), 京都大学, 20H00605 - タイリングによるウイルス外殻のボトムアップ設計
科学研究費助成事業 挑戦的研究(萌芽)
2020年07月30日 - 2023年03月31日
松永 康佑, 舘 知宏, 堀山 貴史
本研究はウイルス外殻の構造について、Casper and Klugの準等価理論による展開図を近似して正二十面体を作るアプローチとは対照的に、そもそも球面上を敷き詰めることのできる部品構造(コートタンパク構造)のパターンは何か?というタイリングの観点からウイルス外殻を調べ、外殻構造の構成とデザイン原理の理解を深化させることを目的とする。去年度は球面上のタイリングについて考察し、平面を埋め尽くすためのタイリング理論でわかっている部品構造の対象軸のうち6回対称軸を5回対称軸とみなすことで正二十面体のタイリングへと近似することを考案した。これを用いて準等価理論でT1に分類される外殻構造を観察したところ、外見上は4つの異なるタイリングへ分類できることがわかった。本年度は、去年度に主に外見だけで行ったT1外殻構造のタイリング分類を更に定量化するための研究を行った。まず一つ目に、外殻を構成するコートタンパク質モノマーの不斉炭素原子のデカルト座標を点群として発生させ、去年考案した正二十面体のタイリングを満たす平面を点群へフィッティングし分類するプログラムを開発した。実際に、T1外殻構造の一つのテストデータを定量的に分類できるようになった。二つ目として、剛体ドッキングプログラムを用いてコートタンパクのホモ二量体のドッキング計算を行い、得られたドッキングスコアとホモ二量体のスクリュー軸の関係を調べた。あるT1外殻構造では、スクリュー軸が3回対称軸と2回対称軸となるホモ二量体構造のスコアの成績が良かった一方で、別のT1外殻構造では5回対称軸と2回対称軸の成績が良かった。これは考案したタイリング分類の傾向と一致しており、タイリング分類が単なる見た目の分類だけでなく、構造の安定性とも関わっていることが示唆された。
日本学術振興会, 挑戦的研究(萌芽), 埼玉大学, 20K21380 - 細胞の形状形成への計算折り紙の応用
科学研究費助成事業 挑戦的研究(開拓)
2020年04月01日 - 2022年03月31日
上原 隆平, 堀山 貴史, 繁富 香織
本研究テーマでは，微小サイズの細胞の立体構造の構築について，実際の細胞折り紙による実験を通じて理論モデルを構築し，細胞にとっての折りやすさを評価することが目的であった．そしていくつかの条件において細胞での折りの実験を行った．こうした実験結果を踏まえ，物理的な制約を考慮した妥当な「折りやすさの指標」を与えるモデルの候補をいくつか考案した．実験データと考案した理論モデルの間の妥当性については現在検証を進めており，今後論文として公表する準備を進めている．特に数理的な側面から，物理的な制約を取り入れた理論モデルをある程度構築できたことが本研究の最大の意義であると考えられる．
日本学術振興会, 挑戦的研究(開拓), 北陸先端科学技術大学院大学, 20K20311 - 幾何図形の列挙のための同型性に関する研究
科学研究費助成事業 基盤研究(C)
2018年04月01日 - 2021年03月31日
堀山 貴史
計算幾何学においてさまざまな問題に横断的に現れる重要な課題である同型性について研究を行い、幾何図形の列挙において同型性を除去するためのアルゴリズムの設計とその応用を試みた。提案アルゴリズムは BDD (二分決定グラフ) や ZDD (零抑制型BDD) に基づく列挙手法である。BDD/ZDD のトップダウン構築法であるフロンティア法による列挙と組み合わせることで、列挙に要する時間を大幅に高速化し、メモリ使用量も大幅に削減できる。たとえば、d 次元超立方体の展開図の列挙の計算機実験では、フロンティア法のみを用いた従来法に比べて 300倍以上の高速化と 3,000倍以上の省メモリ化を達成している。
日本学術振興会, 基盤研究(C), 18K11153 - 量子プロトコル理論の線的展開
科学研究費助成事業 基盤研究(A)
2016年04月01日 - 2021年03月31日
小柴 健史, 西村 治道, ルガル フランソワ, 田中 圭介, 河内 亮周, 安永 憲司, 松本 啓史, 堀山 貴史, 小林 弘忠
量子状態の初期化が容易でない量子計算を定式化したDQC1モデルなどの計算能力を究明することにより，万能でない量子計算モデルでさえ量子超越性を達成し得ることを示した。量子分散アルゴリズムに関しては，標準的な分散計算モデルにおいて「全対最短経路問題」などの幾つかの基本的問題について，古典プロトコルよりも効率的に動作する量子分散プロトコルを開発した。量子暗号プロトコルである秘匿代理量子計算において，古典クライアントでは，完全秘匿性を達成不可能であることを示した。量子性の古典的検証可能性に，報酬概念を導入することで，ゲーム理論的な形での解決という新しい方向性を見出した。
日本学術振興会, 基盤研究(A), 16H01705 - 離散構造処理系の基盤アルゴリズムの研究
科学研究費助成事業 基盤研究(S)
2015年05月29日 - 2020年03月31日
湊 真一, 有村 博紀, 瀧川 一学, 宇野 毅明, 堀山 貴史, 津田 宏治, 鷲尾 隆
研究成果の概要（和文）：本研究では，離散構造処理系のコアとなる基盤アルゴリズムを構築し，高性能な基盤ソフトウェアを応用分野の研究者や技術者に提供することを目指した．主な成果の例として，①全国都道府県の隣接ブロック組合せの総数（約1098億通り）を初めて明らかにし，(独)統計センターから国民にデータを公開した，②異分野横断の交流から難関国際会議（AAAI,WWW,KDD,INFOCOM,AISTATS,SDM他）に採択される研究成果を多数生み出した，等が挙げられる．
日本学術振興会, 基盤研究(S), 15H05711 - 直観幾何学の確立とその計算機科学，建築工学および数学教育との連携の推進
科学研究費助成事業 基盤研究(B)
2015年07月10日 - 2019年03月31日
伊藤 仁一, 浪川 幸彦, 瀧澤 重志, 堀山 貴史
主要な４つのテーマ（A)多面体の連続的折り畳み，(B)建築工学との連携，(C)数学教育との連携，(D)直観幾何学の確立，に対して以下のようにバランスよく成果を上げることが出来た．
（A)新しい多面体の連続的平坦折り畳みとそれを高次元正多面体の２次元面の和集合②も拡張した．（B)コクセターのねじれ正多面体を剛性を持つように変えることを示した．（C)数学教育関連の研究会を開催し,直観幾何学の有用性を示すとともに,動的幾何ソフトを用いての教材開発を行った．（D)研究集会「直観幾何学」を継続し,直観幾何学という名前の認知度を高めることが出来た．更に,直観幾何学と言えるようないくつもの研究を進めた．
日本学術振興会, 基盤研究(B), 15KT0020 - 幾何図形の列挙とその応用
科学研究費助成事業 基盤研究(C)
2015年04月01日 - 2018年03月31日
堀山 貴史
BDD (二分決定グラフ), ZDD (零抑制型BDD) や逆探索といった列挙の要素技術を統合し、幾何図形の列挙のためのアルゴルズム設計論について研究を行うと共に、様々な分野への応用を試みた。まず、直方体の展開図の列挙に注力し、正方形展開の概念を導入することで、直方体の正方形展開図を表す ZDD を効率的に構築するアルゴリズムを提案した。さらに、逆方向からの検討も行った。すなわち、与えられた直交多角形を直方体に折ることができるのか、また直方体に折れる場合にはその折り線を与えるアルゴリズムを提案した。応用面では、選挙区の区割りの問題や、菱形タイリングの列挙などに取り組んだ。
日本学術振興会, 基盤研究(C), 埼玉大学, 15K00008 - 多面的アプローチの統合による計算限界の解明
科学研究費助成事業 新学術領域研究(研究領域提案型)
2012年06月28日 - 2017年03月31日
渡辺 治, 浅野 孝夫, 茨木 俊秀, 今井 浩, 戸田 誠之助, 丸岡 章, 湊 真一, 牧野 和久, 河原林 健一, 浅野 哲夫, 加藤 直樹, エイビス デビッド, 徳山 豪, 山下 茂, 瀧本 英二, 堀山 貴史, 森 立平
本課題の目的は，計算限界の解明を目指す新学術領域研究の総括班活動である。本領域では，革新的な計算の活用の鍵となる計算の理解の深化のため，計算限界に関する研究を数理科学の多様な観点から行うことを目指した。多様な観点からの研究が力を発揮するには，領域の研究者ならびに世界の研究者との研究連携が必須である。本総括課題では，その研究連携を促進させるため，研究者招聘と活用，研究ワークショップの開催などを実施した。若手育成のために，秋学校や学生勉強会などを実施した。また，国際会議の主催，専門家へのセミナーなど，本領域の成果の公表や波及のための事業を行った。
日本学術振興会, 新学術領域研究(研究領域提案型), 東京工業大学, 24106001 - 計算限界解析法から革新的データ構造化技術への展開
科学研究費助成事業 新学術領域研究(研究領域提案型)
2012年06月28日 - 2017年03月31日
徳山 豪, 宇野 毅明, 堀山 貴史, 渋谷 哲朗, 定兼 邦彦, 山中 克久
新学術領域研究ELCで開発した計算限界の解明手法を活用・展開し、ビッグデータ時代を切り開く革新的なデータ構造の開発とそのための理論基盤を築くことを目的として研究を行った。主な成果としては、①高速な検索や加工アルゴリズムを持つ圧縮データ構造理論の推進と、②圧縮データ構造などのゲノムや社会的な巨大データへの適用、③ゼロサプレス決定木（ZDD)に関する技法の開発と、その適用に必要な離散構造解析と高性能アルゴリズムの開発、さらにZDDを用いた離散列挙の幾何学列挙や化学構造列挙への応用の開発、④データ研磨と呼ぶ新たなデータクラスタリングの手法とその応用がある。 多くの後継プロジェクトにつながった。
日本学術振興会, 新学術領域研究(研究領域提案型), 東北大学, 24106007 - データの巨大化から生じる不完全情報への対処に主眼をおいた近似計算
科学研究費助成事業 基盤研究(A)
2013年04月01日 - 2016年03月31日
岩間 一雄, エイビス デイビッド, 宮崎 修一, 玉置 卓, 伊藤 大雄, 堀山 貴史, 吉田 悠一, 岡本 和也, 脊戸 和寿, 川原 純, 上野 賢哉
不完全情報をいかに扱うかが現代アルゴリズムの大きな課題になっている．
本研究では「データの巨大化から生じる不完全情報に対処するための近似計算における，できるだけ一般性の高いアルゴリズム設計理論の体系化」を目的として研究を行った．
結果として，グラフ問題，アルゴリズム的ゲーム理論，乱化に関する基礎理論の様々な問題において，情報の不完全性を克服できるアルゴリズムの設計と解析に成功した．
日本学術振興会, 基盤研究(A), 京都大学, 25240002 - 幾何図形の列挙に関する研究
科学研究費助成事業 基盤研究(C)
2012年04月01日 - 2015年03月31日
堀山 貴史
BDD (二分決定グラフ), ZDD (零抑制型BDD) や逆探索といった列挙の要素技術を統合し、幾何図形の列挙のためのアルゴルズム設計論について研究を行った。多面体の展開図については、フロンティア法に基づくZDD構築手法と同型な展開図の除去手法の組合せにより、高速な列挙ができることを示した。また、この展開図の列挙手法について、一般展開（辺のみでなく面を切り開くことも許した展開図）への拡張について考察した。さらに、任意の多面体に対し、個々の展開図を列挙することなく、本質的に異なる展開図の個数を求める手法を開発した。
日本学術振興会, 基盤研究(C), 埼玉大学, 24500008 - 空間的な情報補填を可能にするアルゴリズムの研究
科学研究費助成事業 基盤研究(A)
2010年 - 2012年
岩間 一雄, エイビス デイビッド, 宮崎 修一, 玉置 卓, 伊藤 大雄, 加藤 直樹, 徳山 豪, 山下 雅史, 渡辺 治, 堀山 貴史, 川原 純, 森住 大樹, 伊藤 大雄
不完全情報をいかに扱うかが現代アルゴリズムの大きな課題になっている.本研究では「空間的な情報の不完全性を克服できるアルゴリズムに関して,その設計技法と評価手法を含めた総合的体系を作り上げること」を目的として研究を行った.結果として,グラフ問題,アルゴリズム的ゲーム理論,乱化に関する基礎理論の様々な問題において,空間的な情報の不完全性を克服できるアルゴリズムの設計と解析に成功した.
日本学術振興会, 基盤研究(A), 京都大学, 22240001 - 計算機援用によるアルゴリズムの性能保証
科学研究費助成事業 若手研究(B)
2008年 - 2010年
堀山 貴史
本研究の成果は、主に以下の3つからなる。(1)逆算法による詰将棋の列挙アルゴリズムを設計し、与えられた駒に対する最長手数に関する証明が可能となった。(2)逆探索により、p4タイリング(90度回転によるタイリング)およびp6タイリング (60度回転によるタイリング)の基本図形を生成するアルゴリズムを設計した。(3)正多面体の展開図の列挙アルゴリズムを設計し、「正多面体の任意の展開図は重なりを持たない」との定理を証明することで数百年に渡る未解決問題を解決した。
日本学術振興会, 若手研究(B), 埼玉大学, 20700005 - 情報補填を可能にするアルゴリズムの設計と解析
科学研究費助成事業 基盤研究(A)
2007年 - 2009年
岩間 一雄, 加藤 直樹, 伊藤 大雄, 宮崎 修一, 玉置 卓, 杉原 厚吉, 徳山 豪, 山下 雅史, 渡辺 治, 堀山 貴史, 杉原 厚吉, 徳山 豪, 山下 雅史, 渡辺 治
入力情報の不完全性をいかに克服する(情報を補填する)かが現代アルゴリズムの大きな課題となっている,本研究では,そのようなアルゴリズムが有すべき性質を厳密に議論し,具体的な設計技法と評価手法を含めた体系を作り上げることを目的として,研究を行った.結果として,オンライン,ネットワーク,マッチング,確率,幾何,分散等多岐にわたる分野で効率よいアルゴリズムの開発に成功した.
日本学術振興会, 基盤研究(A), 京都大学, 19200001 - 離散アルゴリズムの性能保証自動化パラダイム
科学研究費助成事業 若手研究(B)
2005年 - 2007年
堀山 貴史
情報化社会の大規模化と多様化は、計算機による処理能力の向上と処理対象への柔軟な適応によるところが大きい。これは、コンピュータの処理速度の向上に顕著に見られるハードウェアの進歩に加えて、ソフトウェアのアルゴリズム革新に支えられている。ここに、アルゴリズムの設計と性能保証があらゆる分野の基礎として重視されてきている。アルゴリズムの性能保証には、理論的な性能解析が必要不可欠であるが、アルゴリズム設計と同じく人手で行っており、設計者の職人芸的なセンスに依存するところが大きい。本研究の主題は、アルゴリズムの理論的性能解析に計算機を援用することにある。これにより、定型的作業の負荷を減らし、思考の抽象度を高めることによる生産性の向上が期待できる。
本年度は、アルゴリズム的ゲーム理論の立場から、オークションのアルゴリズムの性能解析に関して検討を行った。具体的には、音楽ファイルなどの複製コストが無視できるほど小さく無限供給可能な商品に対する1ラウンド秘密入札オークションを対象とし、誘因両立性を持つアルゴリズムを設計した。また、入札の最高額と最低額の比rに関する競合比解析を提案し、本アルゴリズムの競合比がln r+1となることを示した。同様の観点から既存アルゴリズムの競合比をrの関数として解析し、小さなrに関しては提案アルゴリズムの競合比が常に良いことを示した。
日本学術振興会, 若手研究(B), 17700014 - ネットワーク問題のモデル化とアルゴリズムの研究
科学研究費助成事業 特定領域研究
2004年 - 2007年
伊藤 大雄, 岩間 一雄, 増澤 利光, 宮崎 修一, 堀山 貴史
グラフは接続関係を表現する抽象モデルとして有用であり, 古くから盛んに研究されている数学的対象である. 本特定領域研究では, ネットワークや計算機上での問題をグラフ問題としてモデル化し, そのアルゴリズム開発の研究を行った. その結果、密な部分グラフ発見問題, 供給点配置問題, 頂点被覆問題, 巡回セールスマン問題, 自己安定化問題, 安定マッチング問題などの様々な実用的問題について, 効率的なアルゴリズムを得ることができた.
日本学術振興会, 特定領域研究, 京都大学, 16092215 - 工学的評価基準に基づく離散アルゴリズムの品質保証技術に関する研究
科学研究費助成事業 基盤研究(B)
2004年 - 2006年
岩間 一雄, 伊藤 大雄, 宮崎 修一, 堀山 貴史
離散アルゴリズムの評価基準は、漸近的な計算時間がほとんど唯一のものとされてきた。しかし、これは評価尺として適切でない場合もしばしば指摘され、様々な角度からアルゴリズムを評価する動きが高まってきた。たとえば、困難な組合せ問題を近似アルゴリズムで解く時の近似度や、将来の入力が分からないオンライン問題に対するアルゴリズムの良さをオフラインアルゴリズムの性能との比較で議論する競合比は、現在最も重要視されている尺度である。本研究では、このような新しい各種尺度を、「工学的評価基準」としてとらえ、そのもとで高性能なアルゴリズムを開発する。ネットワークアルゴリズム、マッチングアルゴリズム、SATアルゴリズムの観点から研究を進めた。以下、代表低な成果である安定結婚問題と頂点被覆問題について述べる。
安定結婚問題の拡張として、希望リストに同順位と不完全指定を許した問題においては最大サイズの安定マッチングを求める問題はNP困難であることが知られている。この問題では、2-近似アルゴリズムは自明である。これまで知られている最良の近似度は2-c/$\sqrt{n}$であったが、我々は初めて2よりも厳密によい近似度である1.8-近似アルゴリズムを達成した。
NP困難問題の一つである頂点被覆問題(VC)が2-ε近似可能か否かは極めて重要性の高い未解決問題であり、その近似不可能性が強く信じられている。我々は密なグラフ上のVCを考え、近似度2を大きく下回る2/(1+Δ/d)の近似アルゴリズムを開発した。ここで、Δはグラフの最大次数、dは平均次数を表す。もしもより良い近似率を達成する結果が存在するならば、一般のVCにおいて2-εの近似度が得られるため、我々の結果が最適である。
日本学術振興会, 基盤研究(B), 京都大学, 16300002 - データの論理的解析に基づく効率的な知識獲得手法とその応用
科学研究費助成事業 若手研究(B)
2002年 - 2004年
堀山 貴史
情報化社会の発達にともない、クレジットカードや各種検査の結果などの多種多様なデータを、大量かつ容易に集めることができるようになってきている。このため、集められた膨大なデータからその傾向や規則性などの有用な情報を得ることを目的とした知識獲得の研究の重要性がさまざまな分野で指摘されている。本研究では、データと対応づけした論理関数を媒介として、データの持つ論理的内容を知識として抽出することを目指している。
今年度は、まず、二分決定グラフ(Ordered Binary Decision Diagrams)を知識表現の手段として用いた知識ベース処理について、計算複雑さに関する考察とアルゴリズム設計を行った。具体的には、OBDDを用いた手法では演繹(deduction)が任意の論理関数に対して線形時間で可能となることを示した。仮説推論(abduction)は任意の論理関数に対してはNP-hardとなるが、扱う関数をHorn関数に限定することで、仮説に任意のリテラルを取りえるような説明を求める多項式時間アルゴリズムを示した。また、証明システムの複雑さと密接に関連するHajos calculusに着目し、その平面グラフ版の問題について考察を行った。Hajos calculusは3彩色不能なグラフを生成する非決定性のプロセスである。本研究では、3彩色不能な平面グラフのみを生成できる生成則を2種類提案し、それぞれの規則の健全性と完全性を証明した。また、その規則間の多項式時間模倣性を示した。
また、自律学習機構を備えたハードウェアへの知識獲得手法の適用の基礎的な問題として、高位言語からハードウェア記述の自動合成を行う高位合成における、浮動小数点数のビット長最適化を扱った。誤差解析において正方向の誤差と負方向の誤差を独立して考慮し、また、非線形最適化ソルバーを利用してビット長最適化問題を解く手法を提案し、シミュレーションによる手法よりも良好な結果を得た。
日本学術振興会, 若手研究(B), 京都大学, 14780219 - 工学的評価基準による離散アルゴリズムの高品質化に関する研究
科学研究費助成事業 基盤研究(B)
2001年 - 2003年
岩間 一雄, 宮崎 修一, 伊藤 大雄, 岡部 寿男, 堀山 貴史
離散アルゴリズムの良さの評価基準として、長期間に渡って、漸近的な計算時間がほとんど唯一のものとされてきた。しかし、この漸近的計算時間が評価尺度として適切でない場合が多いこともしばしば指摘され、様々な角度からアルゴリズムを評価する動きが高まってきた。たとえば、困難な組合せ問題を近似アルゴリズムで解く時の近似率や、将来の入力が分からないオンライン問題を解く時の競合比などである。我々は、このような新しい各種尺度を「工学的評価基準」としてとらえ、この視点のもとで高性能なアルゴリズムを開発する方法論について研究を行った。
結婚安定問題は多項式時間で解くことができると知られていたが、これを一般化し、希望リストに同順位を許した場合や希望リストを完全に指定しない場合にも多項式時間アルゴリズムを示した。同順位と不完全指定を同時に許した場合にはNP困難となるが、この場合に自明な近似率2を切る初めてのアルゴリズムを示した。
充足可能性問題では、局所探索系とバックトラック系の2つのアルゴリズムを相補的に組み合わせることにより、3-SATを1.324^n時間で解くアルゴリズムを構築した。また、与えられた論理式の充足可能性を保存したまま解の密度を濃縮した論理式を求める、論理式の濃縮問題に取り組んだ。
他に、オンラインアルゴリズム、ネットワークアルゴリズム、量子アルゴリズムの各テーマにおいて、アルゴリズムの高品質化に取り組んだ。
日本学術振興会, 基盤研究(B), 京都大学, 13480081 - メタヒューリスティクスによる汎用問題解決システムの構築
科学研究費助成事業 基盤研究(B)
2001年 - 2003年
茨木 俊秀, 堀山 貴史, 野々部 宏司, 柳浦 睦憲, 阿瀬 始
情報化とネットワーク化の進む現代社会では、解決すべき問題はますます大規模かつ複雑化している。これらの問題はさまざまな形態をとって現れるが、数学的にモデル化すると、本質的には最適化問題、それも組合せ的性質を持つ最適化問題がその核となっている場合が多い。本研究の目的は、このような組合せ最適化問題の形に記述されるものを対象とした汎用問題解決エンジンを構築することである。本アプローチの基本的な考え方は、まず、できるだけ広い対象をカバーするように標準問題を選び、それらに対して、効率が高く頑健性と汎用性に富む近似アルゴリズムを開発するというものである。アルゴリズムはすべてメタヒューリスティスの枠組に従っている。これらの中には、すでに企業において生産管理システムなどに組み込まれ定常的に利用されているものもあり、実用性の意味で高い評価を受けている。選ばれた標準問題は以下の通りである。
・制約充足問題(Constraint Satisfaction Problem,CSP)
・最大充足可能性問題(MAXimum SATisfiability problem,MAXSAT)
・資源制約スケジューリング問題(Resouce Constrained Project Scheduling Problem,RCPSP)
・一般化割当問題(Generalized Assignment Problem, GAP)、多資源一般化割当問題(Multi-Resource GAP,MRGAP)
・集合カバー問題(Set Coverlng Problem,SCP)
・配送計画問題(Vehicle Routing Problem,VRP)
・2次元詰込み問題(2-dimensional Packing Problem,2PP)
・1次元カッティングストック問題(1-dimensional Cutting STock Problem,1CSTP)
・2次元カッティングストック問題(2-dihensional Cutting Stock Problem,2CSTP)
・データからの特徴抽出問題(Feature Extraction from Data,FED)
日本学術振興会, 基盤研究(B), 京都大学, 13558027 - 環境適応型のハードウェアとソフトウェアの構成手法に関する研究
科学研究費助成事業 基盤研究(B)
1999年 - 2001年
渡邉 勝正, 堀山 貴史, 高木 一義, 木村 晋二, 中西 正樹
本研究は,環境に適応したハードウェアとソフトウェアの構成手法をテーマとしている.すなわち,対象とする情報システムの設計と構成をハードウェアとソフトウェアの両面から捉えて,環境に適応して自律的に構成を変化できるシステムの構築法を研究の目的としている.
3年間を通じて,次のような側面から,具体的な提案と設計,および,実装を行なった.
(1)環境に適応可能なシステムの構成法について,アクティブソフトウェアの記述と構成,対話型プログラミング環境でのオブジェクトの自発的機能やその拡張性について提案を行ない,具体例の実装を進め,構成法の有効性を示した.(2)環境に適応可能なハードウェアの実現手法として,再構成可能な機構を持つLSIの構成例として,動的に命令列を変更できるJavaプロセッサの構成法の研究,および,視線推定のLSIと不特定対象者の対顔判定LSIの設計を行った.これらは,ハードウェア向きアルゴリズムを確立して,実時間処理による適応可能性を示した.(3)ハードウェアの合成と検証については,二分決定グラフ(BDD)の制約演算に基づく新しい像計算法について研究を進め,アルゴリズムの高速性と大規模な回路への適応可能性を示した.(4)外界の情報を取捨選択し、環境適応に必要な知識を獲得する問題について、順序付き二分決定グラフ(OBDD)を利用する手法を提案し、従来手法で用いられる特徴モデルや論理式とOBDDとを相互に変換するアルゴリズムを設計した。(5)量子計算は,その特徴である量子並列性により,環境の動的特性を一度に把握して,処理できる.新しい量子計算モデルとして,非決定性量子有限オートマトンを取り上げて,その計算能力を,従来の計算モデルの能力と比較する研究等を行なった.
3年間の研究の結果,新しい情報システムの設計と開発にあたり,ハードウェアとソフトウェアを統合して,環境の変化に適応する能力をもつシステムの構成機構を明らかにした.これらの研究成果の詳細は,研究報告書としてまとめている.
日本学術振興会, 基盤研究(B), 奈良先端科学技術大学院大学, 11480068 - メタヒューリスティクスによる計算困難問題の解決に関する研究
科学研究費助成事業 特定領域研究(B)
1998年 - 2000年
茨木 俊秀, 野々部 宏司, 堀山 貴史, 柳浦 睦憲, 品野 勇治
実社会に現れる組合せ最適化問題の解法として,局所探索を基盤にタブー探索,遺伝アルゴリズム,アニーリング法など,いわゆるメタヒューリスティクスと称される手法が種々提案され,精度の高い近似解を効率よく求めるために大きな成果を上げつつある.本研究の目的は,組合せ最適化問題に対しメタヒューリスティクスに基づく汎用性の高い高性能アルゴリズムを開発することで,実用性の高いソフトウェアを構築することである.具体的には,反復局所探索法,タブー探索およびその変形を中心に,探索空間や近傍の影響を考慮しながら設計を進めた.
ここで,ターゲットとすべき組合せ最適化問題としては,現実に現れる様々な問題を一括して扱える汎用性の高い問題が望ましい.しかしその一方で,アルゴリズムの性能を高めるためには,個々の問題の特殊構造を活かすことが必要である.そこで本研究では,以下に挙げる問題を標準問題として用意し,これらに対するアルゴリズムの開発を行った:
・(重み付き)制約充足問題((Weighted)Constraint Satisfaction Problem),
・一般化割当問題(Generalized Assignment Problem),
・資源制約スケジューリング問題(Resource Constrained Project Scheduling Problem),
・集合被覆問題(Set Covering Problem),
・切断問題(Cutting Stock Problem),
・配送計画問題(Vehicle Routing Problem),
・長方形詰込み問題(Rectangle Packing Problem).
これらの問題はいずれも代表的な組合せ最適化問題であるが,本研究では,複雑な条件を有する現実問題も扱うことができるようアルゴリズムの適用範囲を拡げることに重点をおき,問題の定式化を行った.
本研究で得られたアルゴリズムは,世界中で広く用いられているベンチマーク問題に対し,従来の最良解を更新するなど,その有効性が確認されている.また,現実問題に対しても良質の解を求めることに成功しており,幾つかのアルゴリズムは,すでに実用的な応用で利用されている.
日本学術振興会, 特定領域研究(B), 京都大学, 10205211 - -
競争的資金 - -
競争的資金
