约束可满足问题，广泛存在于科学研究和工程实践中。如人力资源配置问题、农作物布局优化问题、工程设计方案优化问题和资源分配优化问题等，都属于约束可满足问题。这类问题的特点是在特定的约束条件下，寻找问题的解。此类问题的解决往往能带来很高的社会或经济价值。目前还没有高效的精确求解算法，由于这类问题通常可约化为典型的约束可满足问题，如最小顶点覆盖问题。因此可对典型约束可满足问题进行深入的理论研究，以寻找问题求解的新思路和新方法。　　如何求解约束可满足问题是研究约束可满足问题的核心。对于最小顶点覆盖等典型约束可满足问题，当问题规模较大时，传统的电子计算机求解算法很难实现精确求解。基于生化反应的 DNA计算，是一种非传统的高性能计算方法。它具有高度的并行性，并行操作数目超过1018，能在多项式时间内精确求解NP难问题。这为约束可满足问题的精确求解提供了新的思路和方法。另外，受自然界生化反应的启发，科学家提出了化学反应优化算法，研究发现，该方法在近似求解NP问题时，往往能跳出局部极值的限制，比遗传算法、禁忌算法等启发式算法具有更加良好的分布性。基于此，通过分析基于生化反应的 DNA计算和化学反应优化算法特征，本文研究了利用 DNA计算和化学反应优化智能算法来求解典型约束可满足问题的关键技术，提出了若干相关算法，研究表明这些算法表现出了良好的性能和扩展性。论文的主要研究工作如下：　　提出了一种基于分治法的N皇后问题DNA计算算法　　(1)N皇后问题是一种典型的约束可满足问题。研究表明，基于粘贴模型求解该问题的 DNA计算算法，可以在多项式时间内精确求解此问题，但参与反应的DNA链数是指数级的，这将导致求解过程中误解率较高，难以求解大规模问题的求解计算等问题。针对这些问题，本文提出了一种结合分治法，基于扩展粘贴模型来求解N皇后问题的 DNA计算算法。通过算法分析和模拟实验表明：本算法的DNA链数是亚指数级的，将DNA链数从Ο(n n)减少至Ο(n n/2)，同时减少生物操作数，降低了误解率，测试试管数由所需的 O(n)减少至O(1)。　　(2)提出了一种基于DNA自组装模型来求解最小顶点覆盖问题的DNA计算算法。　　尽管基于扩展粘贴模型，利用分治法可以以亚指数的 DNA链数求解N皇后问题，但由于参与生化反应的是 DNA单链分子，其误解率依然较高。为此，本文提出了一种基于DNA自组装模型来求解最小顶点覆盖问题的DNA计算算法。自组装模型是近年 DNA计算领域提出的一种计算模型，具有降低问题求解过程中生化操作和生化解误解率等优点。本文描述了编码方案、问题求解算法以及进行了模拟实验。实验表明，本算法能快速精确求解出最小顶点覆盖问题。同时算法通过减少计算过程中操作步骤数，降低了生化解的错误率，提高了生化解的准确性，算法的生化实验复杂度低，具有良好的易操作性。　　(3)提出一种利用连接分子与自组装模型求解N皇后问题的DNA计算算法　　最小顶点覆盖问题的约束条件单一。针对具有多约束条件下的N皇后问题，本文研究了基于自组装模型的 DNA计算算法。N皇后问题具有四个约束条件，即棋盘行、列和两个对角线上不能存在皇后冲突。本文通过设计连接分子，巧妙地利用它将多个约束条件组合在一起从而实现了基于自组装模型的N皇后问题求解 DNA计算算法。模拟实验表明，本方法是有效的，且具有良好的扩展性。算法使用的tiles分子块种类为Θ(2n)，生化操作复杂性为Θ(1)，其中n为皇后的个数。　　(4)提出了一种基于混合CRO求解N皇后问题的算法　　利用 DNA计算在多项式时间内可以精确求解典型约束可满足问题，其实质是利用 DNA计算的巨大并行性并利用穷举方法从而实现求解计算，参与计算的DNA分子链数或 tiles分子数是指数级或亚指数级的。尽管许多科学家也提出了许多改善生化反应中产生错误解的方法，然而，针对规模较大的问题求解时，目前 DNA计算依然无法将误解率减少到可以接受的水平。智能启发式算法依然是约束可满足问题一种高效的近似求解算法。化学反应优化算法是近年提出来的一种智能启发式算法，该算法能避免搜索陷入局部最优，具有提高问题搜索空间的优点，局部最优搜索是基于贪婪法的快速搜索算法，该算法具有收敛速度快等优点。因此本文将这两个算法融入到一起，设计了混合 CRO算法来求解N皇后问题。实验分析表明，跟其它启发式算法相比，本算法具有良好的分布性和收敛速度，能提高N皇后问题求解的效率。