权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Discrete System Theory and Large-Scale Optimization Methods Based on Binary Decision Diagrams and

基于二元决策图的离散系统理论和大规模优化方法

基本信息

批准号：
09480050
负责人：
IMAI Hiroshi
金额：
$ 9.47万
依托单位：
the University of Tokyo
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (B).
财政年份：
1997
资助国家：
日本
起止时间：
1997 至 2000
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-09480050/
关键词：
graph network matroid Tutte polynomial discrete system network reliability binary decision diagram Jones polynomial Tutte 多項式 Jones 多項式 Trtte多項式

项目摘要

In this research, we aimed at proposing a unified approach to discrete system theory based on binary decision diagrams, and developing a prototype system for the unified system. By our results, we can now represent the whole moderate-scale discrete structure in a implicit and compact manner, which could not be done by the existing methods. We applied our approach to network reliability computation and also computing the Jones polynomial of a knot. These computation problems are known to be #P-hard, but, with our methods, moderate-size problems can be solved rigorously in practice. For example, the network reliability function of a grid of 14x14 can be computed. We also explore fundamental theory of binary decision diagrams, by investigating the difference in size when a monotone Boolean function is represented directly and when it is represented by their prime implicants.New approaches have also been demonstrated, one is based on algebraic approach, and the other is based on quantum approach. Concerning the algebraic approach, Grobner bases are fully investigated for network flow problems. Concerning the quantum approach, we investigate a quantum analog of binary decision diagrams in order to investigate the computational power of quantum computing. These new results will be published soon.

在本研究中，我们的目的是提出一个统一的方法，离散系统理论的基础上二叉决策图，并开发一个原型系统的统一系统。通过我们的结果，我们现在可以表示整个中等规模的离散结构，在一个隐式和紧凑的方式，这不能通过现有的方法。我们应用我们的方法来计算网络的可靠性，也计算琼斯多项式的结。这些计算问题是已知的#P-hard，但是，与我们的方法，中等规模的问题可以在实践中严格解决。例如，可以计算14 x14网格的网络可靠性函数。我们还探讨了二元判定图的基本理论，通过研究一个单调布尔函数直接表示和用它们的素蕴涵表示时的大小差异，并提出了新的方法，一种是基于代数方法，另一种是基于量子方法。关于代数方法，Grobner基充分研究了网络流问题。关于量子方法，我们研究了二进制决策图的量子模拟，以研究量子计算的计算能力。这些新结果将很快公布。