一个搜索问题的求解

     这是一个模拟竞赛的题目中的一部分。大二下，或是大三上的时候做的，具体时间已经记得不太清楚了。期间提出的一个启发式算法极大的提高了一个搜索的效率，尤为有成就感。即使到现在，在算法方面，也很少有这种拉风的感觉。贴过来，体验一下这种拉风的感觉。嘿嘿。（这个竞赛是和老典和YB一起做的，里面自然有许多许多他们的劳动成果，呵呵，非常的感谢他们，说真的，合作非常的愉快，让我到今天都还记得这种纯粹的快乐，很难得）

  问题重述<o:p></o:p>

DNA限制性图谱是遗传生物学中的重要问题。由于在对其研究中需要将很长的DNA分子切开以便分段测量，所以就需考虑如何把这些片段重新排序以使原先DNA分子的信息（排列顺序）不丢失。<o:p></o:p>

传统方法PDP，采用限制性酶，按照需要在限制性位点把DNA切成多个片段。通过实验测得任意两个限制性位点（即切点）之间片段的长度。<o:p></o:p>

但是要把DNA分子在任意两个限制性位点处切开，对当今实验技术来说有相当难度。现采用简化的部分消化方法SPDP，方法如下：<o:p></o:p>

首先DNA分子被复制成n+1份，前n个复制品中的每一个在一个限制性位点处被切开，最后一个复制品在所有的限制性位点处被切开。分别将得到的2n 个片段长度（称为第一组数据）和n+1个片段长度（称为第二组数据）。在没有误差的前提下，第一组数据中2n个长度可以分成n对，每对的和都等于DNA分子的总长度；第二组数据中n+1个长度的和也等于DNA分子的总长度。现在的问题是如何只根据这两组数据，恢复出原先DNA分子中各片段的排列顺序。

                 假设<o:p></o:p>

1．本文实现的DNA重构不包含原先DNA内全部信息，即只保证各片段的前后次序，而不保证个片段之间首尾正确相连；<o:p></o:p>

2．问题一给定的数据测量无误差；<o:p></o:p>

3．只要都符合两组数据的排列方式，皆为可能的正确排列；<o:p></o:p>

4．在问题二中，数据误差的出现服从以真值为均值的正态分布；如果有两个或两个以上的数据测量带有误差，则它们出现的概率是相互独立的；<o:p></o:p>

5．若第二组数据中有相等的数据，则在求得片段的排列中，这些相等的数据可以互换而实际得出DNA其他的排列方式，本文对这种因互换而衍生出来的排列不作考虑（只考虑长度因素）。<o:p></o:p>

 

其他模型的建立与求解，分析统统略过吧。只对这个算法感兴趣。

算法描述：双向交叉搜索算法<o:p></o:p>

由于单向搜索法在探索许多步后，可能无法再往后继续搜索而不得不后退，从而浪费了不少时间，这是单向搜索在时间方面仍不是很令人满意的根本原因。为得到更快的求解速度，现将单向搜索改成双向，设计出双向交叉搜索算法。<o:p></o:p>

名词解释：<o:p></o:p>

1．序列：n+1个DNA片段在DNA分子的排列；<o:p></o:p>

2．前向第x个元素：从前端数起第x个元素；<o:p></o:p>

后向第x个元素：从后端数起第x个元素；<o:p></o:p>

3．当前可匹配的DNA片段：在以形成的序列里加入该片段，如果在该片段处切开，能够得到第一组数据中的某两个数据，并且这一对数据在前面的步骤中还没有得到过；<o:p></o:p>

4．已试探的不匹配的DNA片段：在第i步中已找不到当前可匹配的DNA 片段，退回第i-1步时，将该步骤的DNA片段标记为已试探的不可匹配的DNA片段； <o:p></o:p>

双向交叉搜索算法：<o:p></o:p>

1．第一步：选取第一组数据中最小的数据作为第一个DNA片段的长度；<o:p></o:p>

2．第二步：除去已用的DNA片段，在其他所有的DNA片段中寻找能够成为序列中最后一个元素的DNA片段。如有多个，则记录下来；同时选取第一个可匹配的片段作为当前已找到的DNA片段；<o:p></o:p>

3．第三步：除去已用的DNA片段，在其他所有的DNA片段中寻找能够成为序列中第二个元素的DNA片段。如有多个，则记录下来，同时选取第一个可匹配的片段作为当前已找到的DNA片段；如果找不到当前可匹配的DNA序列，则退回上一步，试探其他可匹配的序列；<o:p></o:p>

4．…<o:p></o:p>

5．i．  第i步：除去已用的DNA片段，除去已试探的不可匹配的DNA片段，在其他所有的DNA片段中寻找能够成为序列中前向第ceil(i/2)个元素（i为奇数时）（后向第（ceil(i/2)）个元素，i为偶数）的DNA片段。如有多个，则记录下来，同时选取第一个可匹配的片段作为当前已找到的DNA片段；如果找不到当前可匹配的DNA序列，则退回第(i-1)步，试探其他可匹配的序列；<o:p></o:p>

i+1  …<o:p></o:p>

n+1. 第n+1步：已找到一个序列，记录该序列。<o:p></o:p>

以上n+1步即为寻找一个DNA排列的过程，当找到一个排列后，若想寻找<o:p></o:p>

其他的排列，只需退回一步，同时把该过程的最后一个DNA片段标记为已试探的不可匹配的DNA片段，直至搜索完所有的可能排列。<o:p></o:p>

 

   呵呵。感觉搞数模这段时光也挺让人怀念的，在一起就事论事，很单纯的去想解决些问题，体会这种挑战问题的兴趣。而且，现在看看这些大二大三时写的代码，一些想法和文章，都还是觉得挺不错的，都有那么点新意。三人的合作真的很好，算法与问题分析方面一起讨论，然后一个负责信息的收集与分析，一个负责算法实现与模拟，一个负责论文撰写与文字修饰。性格也比较互补，而且一女两男，哈哈，搭配合适，呵呵～！和谐团队啊！

    这个帖子，仅为自娱自乐下。不发表。