如果得到指定个数的球的不同的平面图形组合？

[fnan]

代码： 全选

与此同时，先了解一下结构：
a 1 o   2   o    3   o   4  o o o 5  o o   o   o o
b   |       |        |       \|/     | |  / \  | |
c   o-o   o-o-o    o-o-o    o-o-o    o-o-o---o-o-o
d                    |       /|\       |  \ /    |
e                    o      o o o      o   o     o
f                                          |
g                                        o-o-o
h                                          |
i                                          o  

#这些结构也允许？

这些结构好奇怪，隶属不同球？规则的不规则的都行

#结构绝对自由无限制的话很快就无穷组合了，程序就会失去意义的，内存也很快耗尽。

[njutwc]

xiooli现在在做什么?好像很少来了.

我很奇怪, 为什么不考虑3维的情况.

忙论文呢，三维好办，只要有二维就行。

[njutwc]

代码： 全选

与此同时，先了解一下结构：
a 1 o   2   o    3   o   4  o o o 5  o o   o   o o
b   |       |        |       \|/     | |  / \  | |
c   o-o   o-o-o    o-o-o    o-o-o    o-o-o---o-o-o
d                    |       /|\       |  \ /    |
e                    o      o o o      o   o     o
f                                          |
g                                        o-o-o
h                                          |
i                                          o  

#这些结构也允许？

这些结构好奇怪，隶属不同球？规则的不规则的都行

#结构绝对自由无限制的话很快就无穷组合了，程序就会失去意义的，内存也很快耗尽。

是吧，那就做点限制，比如至少有个三元环

[fnan]

是吧，那就做点限制，比如至少有个三元环

有个三元环后又变成无限制像第五结构那样，会陷入无穷循环。

[njutwc]

是吧，那就做点限制，比如至少有个三元环

有个三元环后又变成无限制像第五结构那样，会陷入无穷循环。

你自己看着办，一般来说异构体足够多的话，根据力学原理和化学原理，有软件可以自动优化到某具体结构滴，前提是有大量的异构体。

[fnan]

是吧，那就做点限制，比如至少有个三元环

有个三元环后又变成无限制像第五结构那样，会陷入无穷循环。

你自己看着办，一般来说异构体足够多的话，根据力学原理和化学原理，有软件可以自动优化到某具体结构滴，前提是有大量的异构体。

#也是，先看着办。(以前发过用python写的小游戏，翻出来回忆一下python,有段时间可能未有进展）

[tangboyun]

没有键角、原子半径、最多成键数的约束阿，而且没有定义何为“不同结构”，

如果只论顶点和边数的话，那就是纯数学问题了，要考虑实际的应用的话，问题必须要有约束。

我没有仔细考虑，不过一个简单的算法如下：
1、需要给定约束，先枚举键角和边数的所有可能，然后生成所有可能的组合。比如5个球，那么键角最大360/5，最小为60，。（边等长）
2、对生成的所有组合检测是否合法（需要约束）
3、检查各个顶点的属性、比如有2条边，键角多少，3条边，键角多少。之后比较两个顶点和边的集合是否相同。剔除步骤2的重复项

以碳原子为例，令键角最大为180，最小60，最多成键4对，你需要写的部分：
1、一个组合生成器，生成给定碳原子数的组合（最大理论边数上界确定），从每个组合最多边数的顶点作为起始点开始生成各个不同组合（这是个排列问题，每次迭代都从剩下的顶点数和边数里扣）。（这部分很容易写）
2、组合合法性检测。（这部分比较难，约束条件是不能有多余边和顶点）
3、一个排序算法，把第二步生成的组合做成分检测。比如5个碳原子，就是数据结构就是每个碳原子的边和键角组成情况。排序后剔除重复成分。（在这步里，无法区分空间上的异构体，举个例子，邻二甲苯、间二甲苯、对二甲苯，都是一个成分。）这部分非常容易写。
4、顶点的组装。这步很难。算法可以分2块。
第一块是基本骨架和修饰基团的分离，找到成分里的基本骨架，比如环或者链。修饰基团，比如异丙基之类的。
第二块是在基本骨架上枚举所有的修饰基团位点，剔除对称的同构体。这里难点在于设计数据结构，然后找到对称的边或者顶点或者轴，确定可以安插的位点。


仔细写实现细节没太大意思的，先考虑如何用伪码把要做的事阐述清楚，如果有说不清楚的地方，说明给定的规范还不够详细。当伪码能写清楚的时候。。。其他都是找码农的问题了。算法设计最难的部分事实上是定义问题。。。当然只是个人经验。

至于编程语言的话，个人觉得这类问题，函数编程语言要比过程式方便很多，可以更方便的对行为或者模式建模，比如Lisp或者Haskell（所以人工智能研究基本都是使用函数式语言），用脚本求解是找死。。。

[fnan]

语言方面可以遇到瓶颈再说，验证算法细节后转为合适语言也可以，实际使用python速度可能太差。
不过lz的想法不太现实，大概了解了下资料，不多不少以15个球为例：
单是树图（无圈连通图）就有n^(n-2)种--- 15 ^13=1946195068359375
需要的时间只怕以年为单位。

[zsneoks]

如果这是一个纯数学问题的话，那就用递归的方法。
需要考虑的问题就是：
每添加一个新球有多少种可能？（是当前球数的函数）
如果再考虑球的全同性话，那么除以一个总球数的排列数就行了。

[zsneoks]

规则说得很不清楚。
一定要有环吗？根据你给的例子看不是。
那四个球可不可以中心一个周围连着三个与之相连?为什么你的例子中没有这种情况。
如果有限制规则你得把规则说清楚啊。

[fnan]

LZ的意思是没有规则，可能性是天文数字，不管什么语言什么算法，都是白搭。

[njutwc]

语言方面可以遇到瓶颈再说，验证算法细节后转为合适语言也可以，实际使用python速度可能太差。
不过lz的想法不太现实，大概了解了下资料，不多不少以15个球为例：
单是树图（无圈连通图）就有n^(n-2)种--- 15 ^13=1946195068359375
需要的时间只怕以年为单位。

是呀，我也觉得这样可能不靠谱，原子多的话，我看文献都是用的遗传算法这样的，很少有人用穷举法

[njutwc]

LZ的意思是没有规则，可能性是天文数字，不管什么语言什么算法，都是白搭。

穷举法找结构当然没有规则可言，只要符合纯数学结构就行，原子数少的话的确可以穷举出来，多了电脑空间吃不消，初步估计原子在8个的时候，可能要吃掉上百GB的空间

[tangboyun]

LZ的意思是没有规则，可能性是天文数字，不管什么语言什么算法，都是白搭。

穷举法找结构当然没有规则可言，只要符合纯数学结构就行，原子数少的话的确可以穷举出来，多了电脑空间吃不消，初步估计原子在8个的时候，可能要吃掉上百GB的空间

穷举，只要能保证一次遍历所有可能，内存之类不是问题，因为可以做成流水线。好处是结果可以即时呈现，时间少，出来结果也少罢了。

生成器----->筛------>顶点分配 ，边生成边构建就是了，技术上不难做到，你的难题在于根本没有越束。

遗传算法是个局部寻优搜索，无法搜索所有可行空间，你是要找最优解而不是全部解么？你看，你的问题又变了。

且不论染色体如何编码，你的Obj函数怎么写呢？（也就是如何衡量优劣的准则在哪里呢？）你的 问题原先是个 yes or no的问题，遗传算法是个渐进逼近，obj func的返回值需要是个连续值，我也挺想问问Goldberg，你这个问题，怎么用遗传算法去逼近的。。。

如果问题退化到一个实际的化学应用,并且你只需要“部分解”的话，那么可能对所有基本化学基团建立个表来组合更实际些。在基本骨架上，加上小部分的修饰位点很容易。

[fnan]

穷举，只要能保证一次遍历所有可能，内存之类不是问题，因为可以做成流水线。好处是结果可以即时呈现，时间少，出来结果也少罢了。

#时间是问题，难道想知道cpu连续运行多久会变成化石？
有个算法，设G为n阶全图 ：每个点vi的度d(vi)=n-1 , 总边数E=n*(n-1) , 使E每次循环减一，每减一历遍所有可以挪动的地方，直到d(vi)=1,就得到所有可能.

如果问题退化到一个实际的化学应用,并且你只需要“部分解”的话，那么可能对所有基本化学基团建立个表来组合更实际些。在基本骨架上，加上小部分的修饰位点很容易。

#正解。