前言                      

据高中化学必修V介绍，计算机设计有机合成可以使用逆向分析法。

这看起来很简单，只需要“从目标产物开始，逐步进行反应，像一棵树一样向下迭代，直到迭代到已有的原料，就找出了合成路线”。

这句话并没有错，但是这就像你问别人如何去月球，他回答：“坐火箭啊。” 虽然没有错，可并不具备实际意义。

事实上，这是一项诺奖级别的研究成果， 绝不可能像上面那句话一样说得那么简单，在此我将对那句话的具体实现做一点分析。

我撰写此文时没有查阅任何该问题的相关资料，说到底这只是一篇心路历程的记录，所言真伪，还需读者自行判断。

预备知识

图的定义：

在数学中，图是描述于一组对象的结构，其中某些对象对在某种意义上是“相关的”。这些对象对应于称为顶点的数学抽象（也称为节点或点），并且每个相关的顶点对都称为边（也称为链接或线）。通常，图形以图解形式描绘为顶点的一组点或环，并通过边的线或曲线连接。 图形是离散数学的研究对象之一。

问题分析

拿到问题第一步，最好是进行抽象处理，这个问题已经够抽象了，所以抽象建模这一步跳过。

第二步，自顶向下将问题逐步分层。

第一层：在「已知任一分子能进行的所有反应的所有信息」的前提下，进行路线设计。

第二层：在「已知该分子所有信息」的前提下，推导出该分子能进行的所有反应及相关信息（如条件，原料等）

我们发现第二层的条件十分容易达到，这意味着该问题已经分层完毕。一个分子对有机合成分析有用的所有信息，绝大部分体现在它的结构式上，因此我们只需要知道「目标产物」的结构式和所有「原料」的结构式即可，而这应该是用户的工作。我们所需要做的，只是设计一个能够储存分子结构式的数据结构。该数据结构需要一些性质使我们能方便地进行处理，这里不做具体分析，等下文分析时把所有需求找出来再思考如何设计这个数据结构。

第一层：在「已知任一分子能进行的所有反应的所有信息」的前提下，进行路线设计

建模：把有机分子作为结点，物质合成的关系作为边（边的方向即是反应进行的方向），那么就相当于我们已经知道了一张有向图全集（该图称作全图）。现在给定一个终点和若干起点，要求我们在这张全图中找到能从起点到终点的路径。

容易发现，全图是一张一般性的稀疏图，而我们要找的路径是DAG（有向无环图），不是简单的树，会带来一点麻烦。

算法：以「目标产物」为起点进行搜索，搜到「原料」为止。

大体是这样，但细节上还需斟酌。

首先一个分子可能有多个合成路径，因此一个结点会对应多个独立的路径DAG，为了避免不同的路径之间互相影响，应该采用dfs，搜到一条完整路径后再回溯（顺便移动路径存储的指针到下一位）搜索其他路径。

这样会产生一些缺陷：

• 在搜索过程中，可能出现死循环。 即从A搜到B时，又从B搜到A，又从A搜到B…… 

• A可以生成B，但B不能生成A。这样会导致我们找出一条无法实现的合成路径。

• 一个分子可能被搜索多次。导致程序效率低。

• 程序在错误的方向上不断迭代搜索，算法不能结束。

• 搜索范围可能太大了。碳碳双键的加成，导致我们可以对任意两个相邻有氢的碳原子逆分析出双键，这会让搜索范围很大膨胀。
  

执行以下的伪代码可以得到路径的DAG，并且代码已克服了前三个缺陷：

对于第四个缺陷，一个想法是可以限制搜索的深度，逐步放宽，避免程序在一条道上走到黑。这种方式用代码实现需要在dfs外再嵌套一层函数，为了伪代码的简洁性，在此就不贴出来，只作说明。

至此，第一层问题已被我们大致解决。（说「大致」是因为这里没有考虑反应的信息储存，没有考虑副反应的影响，只考虑了反应分子的转化关系，而且我只是写出了伪代码，还有待观察真正用代码实现时是否会出现一些意想不到的BUG）。

但还没完，上述代码的第十八行：

牵扯到「问题分析」模块提到的数据结构。这一行代码要求这个储存分子结构的数据结构能够进行判断两个分子是否相等的运算，这是该数据结构的第一个要求。同时这个数据结构还要能判断一个分子是不是无机化合物，这是第二个要求。

第二层：在「已知该分子所有信息」的前提下，推导出该分子能进行的所有反应及相关信息

解决思路是：利用该分子的结构，找出它的所有官能团，再根据官能团找出它能进行的所有反应，我们还能要判断这个反应的逆反应是否能进行。

这里我们不可避免地需要探讨如何在计算机中储存一个分子结构了。无非两条思路：数学模型和物理模型。显然物理模型采用3D建模的方式储存分子结构，便于展示和交互，但不利于逻辑上的处理，因此这里采用数学模型：图 ，或者链表。

又是图。让我想起以前被图论暴打时转过的两句话：

不过想到这次期末考试我180分的成绩里面就有80分是图论贡献的，所以现在我觉得在这两句话后面应该再补一句「但在未来我们会知道：图论，你好事做尽！」。

偏题了，回到数据结构上来。如果用图来表示分子结构，那么结点应该是原子，边即是化学键。寻找官能团就变成了在一张图中寻找一个子图。再结合之前的分析我们可以知道，这个图要能够：1.两张图进行同构判断 2.在一张图中需要特定的子图 3.对图进行修改（删除子图，连接子图）4.判断其是否为有机物

第一点是个非多项式问题，这里不展开分析。

第二点可以判断是否存在。伪代码如下：

第三点，对图进行修改。比如我找到了该分子里有一个端碳上的羟基，它可以发生氧化反应变为醛基，那么我就要把分子结构中的羟基变为醛基，这个例子相对简单，对于酯化、水解、取代等的逆反应，发现都可以用相似的逻辑处理，看起来可行。但是前提是我们要在第二点中找到官能团的位置，而实际上我们刚才之解决了是否存在的问题，这就涉及我们如何表示官能团的位置。观察—OH、—COOH、—O—，—COO—，发现可以用边来表示官能团的位置。

第四点，判断其是否为有机物。很简单，略。

至此，计算机辅助设计合成有机合成路线已被粗略分析完毕，事实上还有很多重要的地方没有讨论到，不过如果要做应该还是可以做一个简易DEMO出来的。