Re: [問題] vector<int *> 會有 memory leak 問題嗎?

看板C_and_CPP作者 (藍影)時間14年前 (2011/03/10 08:57), 編輯推噓5(5026)
留言31則, 3人參與, 最新討論串2/5 (看更多)
抱歉昨天有點忙,也在想怎麼詳述我的問題,雖最後硬爆完成, 但為避免日後遇到類似問題,還是整理一下向各位先進請教,請各位先進不吝解惑。 我換了另一個相似之例子出來引出問題 聲明,這問題我想問的是 技巧、演算法(目前是用窮舉法,效率太差了)、資料結構方面。 所有各位版友有意見、經驗盡管提出供小弟做參考。 (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
第一次知道有 #include <algorithm> 提供 next_permutat
03/10 17:08, 1F

03/10 17:09, , 2F
ion 這東西. 很久以前大學寫GA時,自己想這個產生器想許
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
2.1 與 2.2 會不會有交集部份? 也就是你確定 12!/12 是
03/10 17:20, 6F

03/10 17:21, , 7F
對的? (我沒仔細想過, 你覺得是就是了)
03/10 17:21, 7F

03/10 17:22, , 8F
permutation的問題, 要得到全部解, 也只能用窮舉法了吧.
03/10 17:22, 8F

03/10 17:22, , 9F
不會,這部份有確定過,的確是一組解有12種變化。
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
我一直漏掉"使六芒星線上之數字總合完全相等" XDDD
03/10 17:28, 13F

03/10 17:29, , 14F
你可以先試跑 只有產生permutation的程式,重頭跑到底,看
03/10 17:29, 14F

03/10 17:30, , 15F
用不用 next_permutation, 用vector或new , 哪一種較快.
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
謝謝eric~建議,to loveme:目前的確是還找不到規律,所以
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
會不會比較小還沒導過, 實作也比較困難, 像是以邊線 4
03/10 17:37, 22F

03/10 17:38, , 23F
目前12點的case,可以想像成兩個三角形,每點用兩次.
03/10 17:38, 23F

03/10 17:38, , 24F
個點為一群之類的, 或是小三角為一群
03/10 17:38, 24F
這是個好的想法與方向,初步想過的確比較難實做一點,但複雜度的確從 12! 降到 8!*4!, 快了近 50 倍,我會再想想這方法應用與實做是否可行, 謝謝

03/10 17:38, , 25F
但這每點用2次, 應該不適用在更大的問題上.
03/10 17:38, 25F

03/10 17:42, , 26F
原PO可以試著用取出一個點的想法,去拆解問題,想出它的限
03/10 17:42, 26F

03/10 17:43, , 27F
制式. (你應該是應數/純數/純演算法的研究生吧 XD)
03/10 17:43, 27F
讓 ericinttu 失望了,小弟目前本身為商管類組,八竿子與程式摸不著的科系

03/10 17:44, , 28F
permutation+constraints 從古代到現在一直都很好玩 XDD
03/10 17:44, 28F
※ 編輯: tropical72 來自: 180.177.76.142 (03/10 17:49)

03/10 17:56, , 29F
(12*11*10*9) / (4*3*2*1) = 99*5
03/10 17:56, 29F

03/10 17:57, , 30F
不會失望啊, 反正是在做這種問題的, 什麼系所倒還好.
03/10 17:57, 30F

03/10 17:58, , 31F
找到樂趣的話, coding 也很好玩說, 不管是啥問題
03/10 17:58, 31F
文章代碼(AID): #1DU99hiU (C_and_CPP)
討論串 (同標題文章)
文章代碼(AID): #1DU99hiU (C_and_CPP)