前言? ? ? ? ? ? ? ? ? ? ??

據(jù)高中化學(xué)必修V介紹，計(jì)算機(jī)設(shè)計(jì)有機(jī)合成可以使用逆向分析法。

這看起來很簡單，只需要“從目標(biāo)產(chǎn)物開始，逐步進(jìn)行反應(yīng)，像一棵樹一樣向下迭代，直到迭代到已有的原料，就找出了合成路線”。

這句話并沒有錯(cuò)，但是這就像你問別人如何去月球，他回答：“坐火箭啊?！?雖然沒有錯(cuò)，可并不具備實(shí)際意義。

事實(shí)上，這是一項(xiàng)諾獎(jiǎng)級別的研究成果，?絕不可能像上面那句話一樣說得那么簡單，在此我將對那句話的具體實(shí)現(xiàn)做一點(diǎn)分析。

我撰寫此文時(shí)沒有查閱任何該問題的相關(guān)資料，說到底這只是一篇心路歷程的記錄，所言真?zhèn)?，還需讀者自行判斷。

預(yù)備知識

圖的定義：

在數(shù)學(xué)中，圖是描述于一組對象的結(jié)構(gòu)，其中某些對象對在某種意義上是“相關(guān)的”。這些對象對應(yīng)于稱為頂點(diǎn)的數(shù)學(xué)抽象（也稱為節(jié)點(diǎn)或點(diǎn)），并且每個(gè)相關(guān)的頂點(diǎn)對都稱為邊（也稱為鏈接或線）。通常，圖形以圖解形式描繪為頂點(diǎn)的一組點(diǎn)或環(huán)，并通過邊的線或曲線連接。 圖形是離散數(shù)學(xué)的研究對象之一。

問題分析

拿到問題第一步，最好是進(jìn)行抽象處理，這個(gè)問題已經(jīng)夠抽象了，所以抽象建模這一步跳過。

第二步，自頂向下將問題逐步分層。

第一層：在「已知任一分子能進(jìn)行的所有反應(yīng)的所有信息」的前提下，進(jìn)行路線設(shè)計(jì)。

第二層：在「已知該分子所有信息」的前提下，推導(dǎo)出該分子能進(jìn)行的所有反應(yīng)及相關(guān)信息（如條件，原料等）

我們發(fā)現(xiàn)第二層的條件十分容易達(dá)到，這意味著該問題已經(jīng)分層完畢。一個(gè)分子對有機(jī)合成分析有用的所有信息，絕大部分體現(xiàn)在它的結(jié)構(gòu)式上，因此我們只需要知道「目標(biāo)產(chǎn)物」的結(jié)構(gòu)式和所有「原料」的結(jié)構(gòu)式即可，而這應(yīng)該是用戶的工作。我們所需要做的，只是設(shè)計(jì)一個(gè)能夠儲存分子結(jié)構(gòu)式的數(shù)據(jù)結(jié)構(gòu)。該數(shù)據(jù)結(jié)構(gòu)需要一些性質(zhì)使我們能方便地進(jìn)行處理，這里不做具體分析，等下文分析時(shí)把所有需求找出來再思考如何設(shè)計(jì)這個(gè)數(shù)據(jù)結(jié)構(gòu)。

第一層：在「已知任一分子能進(jìn)行的所有反應(yīng)的所有信息」的前提下，進(jìn)行路線設(shè)計(jì)

建模：把有機(jī)分子作為結(jié)點(diǎn)，物質(zhì)合成的關(guān)系作為邊（邊的方向即是反應(yīng)進(jìn)行的方向），那么就相當(dāng)于我們已經(jīng)知道了一張有向圖全集（該圖稱作全圖）?，F(xiàn)在給定一個(gè)終點(diǎn)和若干起點(diǎn)，要求我們在這張全圖中找到能從起點(diǎn)到終點(diǎn)的路徑。

容易發(fā)現(xiàn)，全圖是一張一般性的稀疏圖，而我們要找的路徑是DAG（有向無環(huán)圖），不是簡單的樹，會帶來一點(diǎn)麻煩。

算法：以「目標(biāo)產(chǎn)物」為起點(diǎn)進(jìn)行搜索，搜到「原料」為止。

大體是這樣，但細(xì)節(jié)上還需斟酌。

首先一個(gè)分子可能有多個(gè)合成路徑，因此一個(gè)結(jié)點(diǎn)會對應(yīng)多個(gè)獨(dú)立的路徑DAG，為了避免不同的路徑之間互相影響，應(yīng)該采用dfs，搜到一條完整路徑后再回溯（順便移動(dòng)路徑存儲的指針到下一位）搜索其他路徑。

這樣會產(chǎn)生一些缺陷：

• 在搜索過程中，可能出現(xiàn)死循環(huán)。 即從A搜到B時(shí)，又從B搜到A，又從A搜到B……?

• A可以生成B，但B不能生成A。這樣會導(dǎo)致我們找出一條無法實(shí)現(xiàn)的合成路徑。

• 一個(gè)分子可能被搜索多次。導(dǎo)致程序效率低。

• 程序在錯(cuò)誤的方向上不斷迭代搜索，算法不能結(jié)束。

• 搜索范圍可能太大了。碳碳雙鍵的加成，導(dǎo)致我們可以對任意兩個(gè)相鄰有氫的碳原子逆分析出雙鍵，這會讓搜索范圍很大膨脹。
  

執(zhí)行以下的偽代碼可以得到路徑的DAG，并且代碼已克服了前三個(gè)缺陷：

對于第四個(gè)缺陷，一個(gè)想法是可以限制搜索的深度，逐步放寬，避免程序在一條道上走到黑。這種方式用代碼實(shí)現(xiàn)需要在dfs外再嵌套一層函數(shù)，為了偽代碼的簡潔性，在此就不貼出來，只作說明。

至此，第一層問題已被我們大致解決。（說「大致」是因?yàn)檫@里沒有考慮反應(yīng)的信息儲存，沒有考慮副反應(yīng)的影響，只考慮了反應(yīng)分子的轉(zhuǎn)化關(guān)系，而且我只是寫出了偽代碼，還有待觀察真正用代碼實(shí)現(xiàn)時(shí)是否會出現(xiàn)一些意想不到的BUG）。

但還沒完，上述代碼的第十八行：

牽扯到「問題分析」模塊提到的數(shù)據(jù)結(jié)構(gòu)。這一行代碼要求這個(gè)儲存分子結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)能夠進(jìn)行判斷兩個(gè)分子是否相等的運(yùn)算，這是該數(shù)據(jù)結(jié)構(gòu)的第一個(gè)要求。同時(shí)這個(gè)數(shù)據(jù)結(jié)構(gòu)還要能判斷一個(gè)分子是不是無機(jī)化合物，這是第二個(gè)要求。

第二層：在「已知該分子所有信息」的前提下，推導(dǎo)出該分子能進(jìn)行的所有反應(yīng)及相關(guān)信息

解決思路是：利用該分子的結(jié)構(gòu)，找出它的所有官能團(tuán)，再根據(jù)官能團(tuán)找出它能進(jìn)行的所有反應(yīng)，我們還能要判斷這個(gè)反應(yīng)的逆反應(yīng)是否能進(jìn)行。

這里我們不可避免地需要探討如何在計(jì)算機(jī)中儲存一個(gè)分子結(jié)構(gòu)了。無非兩條思路：數(shù)學(xué)模型和物理模型。顯然物理模型采用3D建模的方式儲存分子結(jié)構(gòu)，便于展示和交互，但不利于邏輯上的處理，因此這里采用數(shù)學(xué)模型：圖 ，或者鏈表。

又是圖。讓我想起以前被圖論暴打時(shí)轉(zhuǎn)過的兩句話：

不過想到這次期末考試我180分的成績里面就有80分是圖論貢獻(xiàn)的，所以現(xiàn)在我覺得在這兩句話后面應(yīng)該再補(bǔ)一句「但在未來我們會知道：圖論，你好事做盡！」。

偏題了，回到數(shù)據(jù)結(jié)構(gòu)上來。如果用圖來表示分子結(jié)構(gòu)，那么結(jié)點(diǎn)應(yīng)該是原子，邊即是化學(xué)鍵。尋找官能團(tuán)就變成了在一張圖中尋找一個(gè)子圖。再結(jié)合之前的分析我們可以知道，這個(gè)圖要能夠：1.兩張圖進(jìn)行同構(gòu)判斷 2.在一張圖中需要特定的子圖 3.對圖進(jìn)行修改（刪除子圖，連接子圖）4.判斷其是否為有機(jī)物

第一點(diǎn)是個(gè)非多項(xiàng)式問題，這里不展開分析。

第二點(diǎn)可以判斷是否存在。偽代碼如下：

第三點(diǎn)，對圖進(jìn)行修改。比如我找到了該分子里有一個(gè)端碳上的羥基，它可以發(fā)生氧化反應(yīng)變?yōu)槿┗?，那么我就要把分子結(jié)構(gòu)中的羥基變?yōu)槿┗@個(gè)例子相對簡單，對于酯化、水解、取代等的逆反應(yīng)，發(fā)現(xiàn)都可以用相似的邏輯處理，看起來可行。但是前提是我們要在第二點(diǎn)中找到官能團(tuán)的位置，而實(shí)際上我們剛才之解決了是否存在的問題，這就涉及我們?nèi)绾伪硎竟倌軋F(tuán)的位置。觀察—OH、—COOH、—O—，—COO—，發(fā)現(xiàn)可以用邊來表示官能團(tuán)的位置。

第四點(diǎn)，判斷其是否為有機(jī)物。很簡單，略。

至此，計(jì)算機(jī)輔助設(shè)計(jì)合成有機(jī)合成路線已被粗略分析完畢，事實(shí)上還有很多重要的地方?jīng)]有討論到，不過如果要做應(yīng)該還是可以做一個(gè)簡易DEMO出來的。