On the average length of lexicographic paths

A bound is given for the average length of a lexicographic path, a definition that is motivated by degeneracies encountered when using the randomized simplex method.     

Determining molecular structures and conformations directly from electron diffraction using a genetic algorithm.

A global optimization strategy, based upon application of a genetic algorithm (GA), is demonstrated as an approach for determining the structures of molecules possessing significant conformational flexibility directly from gas-phase electron diffraction data. In contrast to the common approach to molecular structure determination, based on trial-and-error assessment of structures available from quantum chemical calculations, the GA approach described here does not require expensive quantum mechanical calculations or manual searching of the potential energy surface of the sample molecule, relying instead upon simple comparison between the experimental and calculated diffraction pattern derived from a proposed trial molecular structure. Structures as complex as all-trans retinal and p-coumaric acid, both important chromophores in photosensing processes, may be determined by this approach. In the examples presented here, we find that the GA approach can determine the correct conformation of a flexible molecule described by 11 independent torsion angles. We also demonstrate applications to samples comprising a mixture of two distinct molecular conformations. With these results we conclude that applications of this approach are very promising in elucidating the structures of large molecules directly from electron diffraction data.     

A genetic algorithm for structure-based de novo design

Genetic algorithms have properties which make them attractive in de novo drug design. Like other de novo design programs, genetic algorithms require a method to reduce the enormous search space of possible compounds. Most often this is done using information from known ligands. We have developed the ADAPT program, a genetic algorithm which uses molecular interactions evaluated with docking calculations as a fitness function to reduce the search space. ADAPT does not require information about known ligands. The program takes an initial set of compounds and iteratively builds new compounds based on the fitness scores of the previous set of compounds. We describe the particulars of the ADAPT algorithm and its application to three well-studied target systems. We also show that the strategies of enhanced local sampling and re-introducing diversity to the compound population during the design cycle provide better results than conventional genetic algorithm protocols.     

两种计算吸光光度法同时测定钙镁

研究了在pH10．5的硼砂-氢氧化钾缓冲溶液和乙醇的增敏作用条件下，偶氮氯膦Ⅰ与钙、镁的吸收特性，建立了多波长光度法同时测定钙和镁的方法。采用两种矩阵算法对试验数据进行处理，并对结果进行比较和分析。钙和镁含量在0～25μg／25ml范围内用计算法Ⅱ能得到准确结果。     

Critical exponents,hyperscaling, and universal amplitude ratios for two- and three-dimensional self-avoiding walks

We make a high-precision Monte Carlo study of two- and three-dimensional self-avoiding walks (SAWs) of length up to 80,000 steps, using the pivot algorithm and the Karp-Luby algorithm. We study the critical exponentsv and 2 ₄ – as well as several universal amplitude ratios; in particular, we make an extremely sensitive test of the hyperscaling relationdv = 2 ₄ –. In two dimensions, we confirm the predicted exponentv=3/4 and the hyperscaling relation; we estimate the universal ratios <R _g ² >/<R _e ² >=0.14026±0.00007, <R _m ² >/<R _e ² >=0.43961±0.00034, and ^*=0.66296±0.00043 (68% confidence limits). In three dimensions, we estimatev=0.5877±0.0006 with a correctionto-scaling exponent ₁=0.56±0.03 (subjective 68% confidence limits). This value forv agrees excellently with the field-theoretic renormalization-group prediction, but there is some discrepancy for ₁. Earlier Monte Carlo estimates ofv, which were 0.592, are now seen to be biased by corrections to scaling. We estimate the universal ratios <R _g ² >/<R _e ² >=0.1599±0.0002 and ^*=0.2471±0.0003; since ^*>0, hyperscaling holds. The approach to ^* is from above, contrary to the prediction of the two-parameter renormalization-group theory. We critically reexamine this theory, and explain where the error lies. In an appendix, we prove rigorously (modulo some standard scaling assumptions) the hyperscaling relationdv = 2 ₄ – for two-dimensional SAWs.     

并行“冒泡”排序算法的改进

并行“冒泡”排序算法的改进黄干平（武汉大学计算机科学系,武汉,４３００７２）关键词排序,并行算法,冒泡中国法分类号ｗ３０１．６ＰＢＳＭ并行排序算法是对ＫａｚｕｈｉｒｓＳａｄｏ和ＹｏｓｈｉｈｉｄｅＩｇａｒａｓｈ的并行“冒泡’书ｒ序算法’“的改进,其并行...     

A new heuristic algorithm solving the linear ordering problem

The linear ordering problem is an NP-hard combinatorial problem with a large number of applications. Contrary to another very popular problem from the same category, the traveling salesman problem, relatively little space in the literature has been devoted to the linear ordering problem so far. This is particularly true for the question of developing good heuristic algorithms solving this problem.In the paper we propose a new heuristic algorithm solving the linear ordering problem. In this algorithm we made use of the sorting through insertion pattern as well as of the operation of permutation reversal. The surprisingly positive effect of the reversal operation, justified in part theoretically and confirmed in computational examples, seems to be the result of a unique property of the problem, called in the paper the symmetry of the linear ordering problem. This property consists in the fact that if a given permutation is an optimal solution of the problem with the criterion function being maximized, then the reversed permutation is a solution of the problem with the same criterion function being minimized.     

Approximate minimum-cost multicommodity flows in\tilde O(ɛ −2 KNM) timetime

We show that an ε-approximate solution of the cost-constrainedK-commodity flow problem on anN-nodeM-arc network,G can be computed by sequentially solving O(K(? ^?2+logGK) logGM log (G? ^?1 GK)) single-commodity minimum-cost flow problems on the same network. In particular, an approximate minimum-cost multicommodity flow can be computed in $\tilde O$ (G? ^?2 GKNM) running time, where the notation Õ(·) means “up to logarithmic factors”. This result improves the time bound mentioned by Grigoriadis and Khachiyan [4] by a factor ofM/N and that developed more recently by Karger and Plotkin [8] by a factor of? ^?1. We also provide a simple $\tilde O$ (NM)-time algorithm for single-commodity budget-constrained minimum-cost flows which is $\tilde O$ (? ^?3) times faster than the algorithm developed in the latter paper.