Re: [問題] vector<int *> 會有 memory leak 問題嗎?
抱歉昨天有點忙,也在想怎麼詳述我的問題,雖最後硬爆完成,
但為避免日後遇到類似問題,還是整理一下向各位先進請教,請各位先進不吝解惑。
我換了另一個相似之例子出來引出問題
聲明,這問題我想問的是 技巧、演算法(目前是用窮舉法,效率太差了)、資料結構方面。
所有各位版友有意見、經驗盡管提出供小弟做參考。
(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
→
03/10 17:08, , 1F
03/10 17:08, 1F
→
03/10 17:09, , 2F
03/10 17:09, 2F
→
03/10 17:09, , 3F
03/10 17:09, 3F
→
03/10 17:10, , 4F
03/10 17:10, 4F
→
03/10 17:11, , 5F
03/10 17:11, 5F
※ 編輯: tropical72 來自: 180.177.76.142 (03/10 17:19)
推
03/10 17:20, , 6F
03/10 17:20, 6F
→
03/10 17:21, , 7F
03/10 17:21, 7F
→
03/10 17:22, , 8F
03/10 17:22, 8F
→
03/10 17:22, , 9F
03/10 17:22, 9F
→
03/10 17:23, , 10F
03/10 17:23, 10F
→
03/10 17:25, , 11F
03/10 17:25, 11F
總和未必為一定值,這部份有拿來做加速判斷,獨立解總和大多只有那幾個,
但獨立解之間的總合「可能相同,也可能不同」
→
03/10 17:26, , 12F
03/10 17:26, 12F
※ 編輯: tropical72 來自: 180.177.76.142 (03/10 17:28)
推
03/10 17:28, , 13F
03/10 17:28, 13F
→
03/10 17:29, , 14F
03/10 17:29, 14F
→
03/10 17:30, , 15F
03/10 17:30, 15F
→
03/10 17:31, , 16F
03/10 17:31, 16F
→
03/10 17:31, , 17F
03/10 17:31, 17F
→
03/10 17:32, , 18F
03/10 17:32, 18F
→
03/10 17:36, , 19F
03/10 17:36, 19F
→
03/10 17:36, , 20F
03/10 17:36, 20F
→
03/10 17:37, , 21F
03/10 17:37, 21F
→
03/10 17:37, , 22F
03/10 17:37, 22F
推
03/10 17:38, , 23F
03/10 17:38, 23F
→
03/10 17:38, , 24F
03/10 17:38, 24F
這是個好的想法與方向,初步想過的確比較難實做一點,但複雜度的確從
12! 降到 8!*4!, 快了近 50 倍,我會再想想這方法應用與實做是否可行,
謝謝
→
03/10 17:38, , 25F
03/10 17:38, 25F
推
03/10 17:42, , 26F
03/10 17:42, 26F
→
03/10 17:43, , 27F
03/10 17:43, 27F
讓 ericinttu 失望了,小弟目前本身為商管類組,八竿子與程式摸不著的科系
→
03/10 17:44, , 28F
03/10 17:44, 28F
※ 編輯: tropical72 來自: 180.177.76.142 (03/10 17:49)
推
03/10 17:56, , 29F
03/10 17:56, 29F
→
03/10 17:57, , 30F
03/10 17:57, 30F
→
03/10 17:58, , 31F
03/10 17:58, 31F
討論串 (同標題文章)
以下文章回應了本文:
完整討論串 (本文為第 2 之 5 篇):