-
公开(公告)号：CN101488197B
公开(公告)日：2012-07-04
申请号：CN200910078155.6
申请日：2009-02-19
Applicant: 北京大学
Abstract: 本发明涉及一种基于环形DNA的图着色计算方法，该方法包括以下步骤：根据给定颜色种类，获得图对应的顶点着色方案集合；根据所述顶点着色方案集合，在顶点数字序列不相邻但相连的边中，找出两顶点颜色未定的边；利用环形DNA分子计算，使用回溯法对所述找出的两顶点颜色未定的边进行删除非解，获得顶点着色方案真解集。本发明的技术方案将待求解图，利用DNA计算中生物操作中的并行性，并基于环形DNA计算的特点，避免了分子间重组，逐步获得所述待着色图的顶点着色方案集合，从而有机地将优化计算方法、DNA序列的编码、各种生化操作、解的检测问题与解空间规模等有机地结合起来，提高了图着色问题的求解效率。
-
公开(公告)号：CN101488197A
公开(公告)日：2009-07-22
申请号：CN200910078155.6
申请日：2009-02-19
Applicant: 北京大学
Abstract: 本发明涉及一种基于环形DNA的图着色计算方法，该方法包括以下步骤：根据给定颜色种类，获得图对应的顶点着色方案集合；根据所述顶点着色方案集合，在顶点数字序列不相邻但相连的边中，找出两顶点颜色未定的边；利用环形DNA分子计算，使用回溯法对所述找出的两顶点颜色未定的边进行删除非解，获得顶点着色方案真解集。本发明的技术方案将待求解图，利用DNA计算中生物操作中的并行性，并基于环形DNA计算的特点，避免了分子间重组，逐步获得所述待着色图的顶点着色方案集合，从而有机地将优化计算方法、DNA序列的编码、各种生化操作、解的检测问题与解空间规模等有机地结合起来，提高了图着色问题的求解效率。
-
公开(公告)号：CN101256640B
公开(公告)日：2010-06-02
申请号：CN200810085571.4
申请日：2008-03-19
Applicant: 北京大学
Abstract: 本发明涉及计算机技术和生物技术，特别涉及一种基于DNA计算实现图顶点着色的技术，提供一种基于DNA计算实现图顶点着色的方法。基于DNA计算获得包含任意个顶点的图顶点着色方案。包括：将待着色图划分为至少两个子图；根据给定颜色种类，基于DNA计算获得每一个子图对应的顶点着色方案集合，每一种顶点着色方案中任意两个相邻顶点着不同颜色；基于DNA计算逐步合并各子图对应的顶点着色方案，获得所述待着色图的顶点着色方案集合。
-
公开(公告)号：CN101256640A
公开(公告)日：2008-09-03
申请号：CN200810085571.4
申请日：2008-03-19
Applicant: 北京大学
Abstract: 本发明涉及计算机技术和生物技术，特别涉及一种基于DNA计算实现图顶点着色的技术，提供一种基于DNA计算实现图顶点着色的方法和DNA计算系统。基于DNA计算获得包含任意个顶点的图顶点着色方案。包括：将待着色图划分为至少两个子图；根据给定颜色种类，基于DNA计算获得每一个子图对应的顶点着色方案集合，每一种顶点着色方案中任意两个相邻顶点着不同颜色；基于DNA计算逐步合并各子图对应的顶点着色方案，获得所述待着色图的顶点着色方案集合。
-
-
-
Search Results
4
records
(took 0.019 seconds)
