作者tropical72 (蓝影)
看板C_and_CPP
标题Re: [问题] vector<int *> 会有 memory leak 问题吗？
时间Thu Mar 10 16:57:09 2011
抱歉昨天有点忙，也在想怎麽详述我的问题，虽最後硬爆完成，
但为避免日後遇到类似问题，还是整理一下向各位先进请教，请各位先进不吝解惑。
我换了另一个相似之例子出来引出问题
声明，这问题我想问的是 技巧、演算法(目前是用穷举法,效率太差了)、资料结构方面。
所有各位版友有意见、经验尽管提出供小弟做参考。
(1) 问题述叙
六芒星之交点、端点共有 12 个点，在这 12 个点里面放入 12 个相异数字，
找出这 12 数字之排法，使六芒星线上之数字总合完全相等。
说明图如连结所示
http://ppt.cc/yUL3
这里标记是以最上方为 array[0]，顺时针方向
依序填入 array[1], array[2]..., array[11]
程式最终「并不是要求得所有合条件之解」，
而是要求「所有独立之解，即所有解不可经由 旋转、顺逆时 而得来」。
文字说明有点难，以下 (2) 点说明何谓 旋转、顺逆时 而来之解
虽表面上要试的解是 12! 组解，但分析之後实际要试的解是 12!/(6*2) 组而已。
声明，六芒星只是一个说明，实际上可能会有 12 芒星、18 芒星，会一直扩下去。
(2) 解集合说明
目前之解为将 array[12] 做排列，判断总合是否相等，这样共有 12! 种解法。
但这实属 「环状排列」 问题，实际上真正的排法根本不到 12! 这麽多，
(2.1) 顺逆时针算同一组:
以 0-1-2-3-4-5-6-7-8-9-10-11 为例，这是顺时针，若以逆时针来看
0-11-10-9-8-7-6-5-4-3-2-1 这和上面是同一组。
(2.2) 转一个端点也算同一组：
六芒星有六个端点，
以 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11 为例，转一次变成
10-11-0 -1 -2 -3 -4 -5 -6 -7 -8 -9 ，再转一次变成
8 -9 -10-11-0 -1 -2 -3 -4 -5 -6 -7 ，
这样等於是一个解有 6 种变化 (转法)
根据 (2.1) (2.2) ，可知实际上要去试的组数是 12!/(6*2)
※ 第一个问题 : 请问有没有办法只穷举这 12!/(6*2) 组解，而不是完全穷举 12! 之解
(3) 目前去找「不重覆解」之解法
先提出一个重要的概念，目前求出之「独立解」组数并不多，以下为我目前的演算法
begin
初始化独立解 SOL_SET 为空
(a) 试目前之数列 s
(b) 目前之数列 s 为一组可行解
(b.1) 自 SOL_SET 里判断是否为独立解 ? 是-> (b.2), 否->(c)
(b.2) 加入 SOL_SET 里
(c) s 为最後一组数列 ? 是-> 结束, 否 -> (d)
(d) 取得下组数列, 回到步骤 (a)
end
由於观查得知 SOL_SET 之数目并不多，第二个问题便产生
※ 请问 SOL_SET 该用何种资料结构？
我想过的是
vector< int* >, vector< vector<int> >,
list< int* >, list< vector<int> >,
最後挑用 vector< int* >，所以才会问是否会有 memory leak 之问题
而暴力穷举法时，目前使用的是 #include <algorithm> 里面之 next_permutation
速度上是否会差很多？
这问题实在很长，谢谢各位版友耐心看完，
有任何意见请不吝指导，或给 keyword 也行!!
小弟感激不尽 !!
--
YouLoveMe() ? LetItBe() : LetMeFree();
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 180.177.76.142
1F：→ ericinttu:第一次知道有 #include <algorithm> 提供 next_permutat 03/10 17:08
2F：→ ericinttu:ion 这东西. 很久以前大学写GA时,自己想这个产生器想许 03/10 17:09
3F：→ ericinttu:久... 後来才想出一个简便又不会重覆的方法 03/10 17:09
4F：→ ericinttu:原归正题, 你是要纪录所有不重覆的解吗? 03/10 17:10
5F：→ tropical72:是的,所以想说用穷举法可以删除很多不必要的东西. 03/10 17:11
※ 编辑: tropical72 来自: 180.177.76.142 (03/10 17:19)
6F：推 ericinttu:2.1 与 2.2 会不会有交集部份? 也就是你确定 12!/12 是 03/10 17:20
7F：→ ericinttu:对的? (我没仔细想过, 你觉得是就是了) 03/10 17:21
8F：→ ericinttu:permutation的问题, 要得到全部解, 也只能用穷举法了吧. 03/10 17:22
9F：→ tropical72:不会,这部份有确定过,的确是一组解有12种变化。 03/10 17:22
10F：→ ericinttu:穷举的好或坏, 就看怎麽过滤重覆解的手法了. 03/10 17:23
11F：→ loveme00835:总和是不是为一个定值? 03/10 17:25
总和未必为一定值,这部份有拿来做加速判断,独立解总和大多只有那几个,
但独立解之间的总合「可能相同，也可能不同」
12F：→ tropical72:也如您所言,目前加速部份的确限於过滤之加速. 03/10 17:26
※ 编辑: tropical72 来自: 180.177.76.142 (03/10 17:28)
13F：推 ericinttu:我一直漏掉"使六芒星线上之数字总合完全相等" XDDD 03/10 17:28
14F：→ ericinttu:你可以先试跑 只有产生permutation的程式,重头跑到底,看 03/10 17:29
15F：→ ericinttu:用不用 next_permutation, 用vector或new , 哪一种较快. 03/10 17:30
16F：→ ericinttu:当然,假如之前有定论了,就跳过上一行吧. 03/10 17:31
17F：→ loveme00835:如果总和跟点数间有规律, 就可以瞬砍一大半了, 感觉不 03/10 17:31
18F：→ loveme00835:是那麽容易用复杂度为多项式程度的解法完成 03/10 17:32
19F：→ tropical72:谢谢eric~建议,to loveme:目前的确是还找不到规律,所以 03/10 17:36
20F：→ tropical72:想请教各位版友是否有类似经验或想法. 03/10 17:36
21F：→ loveme00835:刚刚有想过把点分成几个小群去重组, 但是出来的组合数 03/10 17:37
22F：→ loveme00835:会不会比较小还没导过, 实作也比较困难, 像是以边线 4 03/10 17:37
23F：推 ericinttu:目前12点的case,可以想像成两个三角形,每点用两次. 03/10 17:38
24F：→ loveme00835:个点为一群之类的, 或是小三角为一群 03/10 17:38
这是个好的想法与方向,初步想过的确比较难实做一点,但复杂度的确从
12! 降到 8!*4!, 快了近 50 倍,我会再想想这方法应用与实做是否可行,
谢谢
25F：→ ericinttu:但这每点用2次, 应该不适用在更大的问题上. 03/10 17:38
26F：推 ericinttu:原PO可以试着用取出一个点的想法,去拆解问题,想出它的限 03/10 17:42
27F：→ ericinttu:制式. (你应该是应数/纯数/纯演算法的研究生吧 XD) 03/10 17:43
让 ericinttu 失望了,小弟目前本身为商管类组,八竿子与程式摸不着的科系
28F：→ ericinttu:permutation+constraints 从古代到现在一直都很好玩 XDD 03/10 17:44
※ 编辑: tropical72 来自: 180.177.76.142 (03/10 17:49)
29F：推 ericinttu:(12*11*10*9) / (4*3*2*1) = 99*5 03/10 17:56
30F：→ ericinttu:不会失望啊, 反正是在做这种问题的, 什麽系所倒还好. 03/10 17:57
31F：→ loveme00835:找到乐趣的话, coding 也很好玩说, 不管是啥问题 03/10 17:58