Design and evaluation of adaptive algorithms

自适应算法是一种发现数据特征并对数据采用最佳解的方法的方法。在本研究中，我们研究了图同构、排序和合并、最短路径和三维分配的自适应算法。在排序和归并方面，我们对所谓的归并排序进行了改进，提出了一种只需要少量内存的快速算法。对于最短路径，我们提出了一个硬件算法。对于图同构，我们注意到了预处理的效果，并研究了它们之间的关系。提出了分层图预处理方法，可以快速确定同构关系。对于三维分配，我们提出了一种将不完善部件组合成可靠系统的方法。

An adaptive algorithm is a methodology which finds the characteristics of the data and applys the best method of solution for the data. In the present research we investigated adaptive algorithms for graph isomorphism, sort and merge, shortest path, and three dimensional assignment. As for sort and merge, we improved the so cal led merge-sort and proposed a new fast algorithm that requires only a few memory.As for the shortest path, we proposed a hardware algorithm.As for the graph isomorphism, we noticed the effect of preprocessing and investigated the relation. We proposed the layered graph preprocessing which determines the isomorphism quickly.As for the three dimensional assignment, we proposed a method of combining imperfect components to make a reliable system.