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

[tropical72 (藍影)]

抱歉昨天有點忙，也在想怎麼詳述我的問題，雖最後硬爆完成，
但為避免日後遇到類似問題，還是整理一下向各位先進請教，請各位先進不吝解惑。
我換了另一個相似之例子出來引出問題

聲明，這問題我想問的是 技巧、演算法(目前是用窮舉法,效率太差了)、資料結構方面。
所有各位版友有意見、經驗盡管提出供小弟做參考。


(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
→ ericinttu:第一次知道有 #include <algorithm> 提供 next_permutat
→ ericinttu:ion 這東西. 很久以前大學寫GA時,自己想這個產生器想許
→ ericinttu:久... 後來才想出一個簡便又不會重覆的方法
→ ericinttu:原歸正題, 你是要紀錄所有不重覆的解嗎?
→ tropical72:是的,所以想說用窮舉法可以刪除很多不必要的東西.
※ 編輯: tropical72      來自: 180.177.76.142       (03/10 17:19)
推 ericinttu:2.1 與 2.2 會不會有交集部份? 也就是你確定 12!/12 是
→ ericinttu:對的? (我沒仔細想過, 你覺得是就是了)
→ ericinttu:permutation的問題, 要得到全部解, 也只能用窮舉法了吧.
→ tropical72:不會,這部份有確定過,的確是一組解有12種變化。
→ ericinttu:窮舉的好或壞, 就看怎麼過濾重覆解的手法了.
→ loveme00835:總和是不是為一個定值?
總和未必為一定值,這部份有拿來做加速判斷,獨立解總和大多只有那幾個,
但獨立解之間的總合「可能相同，也可能不同」
→ tropical72:也如您所言,目前加速部份的確限於過濾之加速.
※ 編輯: tropical72      來自: 180.177.76.142       (03/10 17:28)
推 ericinttu:我一直漏掉"使六芒星線上之數字總合完全相等" XDDD
→ ericinttu:你可以先試跑 只有產生permutation的程式,重頭跑到底,看
→ ericinttu:用不用 next_permutation, 用vector或new , 哪一種較快.
→ ericinttu:當然,假如之前有定論了,就跳過上一行吧.
→ loveme00835:如果總和跟點數間有規律, 就可以瞬砍一大半了, 感覺不
→ loveme00835:是那麼容易用複雜度為多項式程度的解法完成
→ tropical72:謝謝eric~建議,to loveme:目前的確是還找不到規律,所以
→ tropical72:想請教各位版友是否有類似經驗或想法.
→ loveme00835:剛剛有想過把點分成幾個小群去重組, 但是出來的組合數
→ loveme00835:會不會比較小還沒導過, 實作也比較困難, 像是以邊線 4
推 ericinttu:目前12點的case,可以想像成兩個三角形,每點用兩次.
→ loveme00835:個點為一群之類的, 或是小三角為一群
這是個好的想法與方向,初步想過的確比較難實做一點,但複雜度的確從
12! 降到 8!*4!, 快了近 50 倍,我會再想想這方法應用與實做是否可行,
謝謝

→ ericinttu:但這每點用2次, 應該不適用在更大的問題上.
推 ericinttu:原PO可以試著用取出一個點的想法,去拆解問題,想出它的限
→ ericinttu:制式. (你應該是應數/純數/純演算法的研究生吧 XD)
讓 ericinttu 失望了,小弟目前本身為商管類組,八竿子與程式摸不著的科系

→ ericinttu:permutation+constraints 從古代到現在一直都很好玩 XDD
※ 編輯: tropical72      來自: 180.177.76.142       (03/10 17:49)
推 ericinttu:(12*11*10*9) / (4*3*2*1) = 99*5
→ ericinttu:不會失望啊, 反正是在做這種問題的, 什麼系所倒還好.
→ loveme00835:找到樂趣的話, coding 也很好玩說, 不管是啥問題