[問題] Letter Lock Picking Puzzle

看板Prob_Solve作者 (喔喔)時間7年前 (2016/11/27 13:31), 編輯推噓3(3推 0噓 10→)
留言13則, 4人參與, 最新討論串1/1
http://puzzles.bostonpython.com/lock.html 從這上面看的 密碼鎖總共有 N 個環，每個環上面有 K 個字母。 同時給定一個字典，字典內每個單字的長度都為 N 。 要如何設計每個環上的字母，使得可以用密碼所表示的單字數量最大。 有比較好的演算法可以解決這問題嗎？ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 24.23.200.172 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1480224680.A.986.html
推
11/28 15:22, , 1F
有趣的問題！想知道 + 1
11/28 15:22, 1F
推
11/28 20:21, , 2F
這跟背包問題有關嗎？
11/28 20:21, 2F
→
11/28 21:24, , 3F
發現不行，因為可能跟別的單字有重複的字母。
11/28 21:24, 3F
→
11/28 21:28, , 4F
想知道 + 1， O( 26^N * 單字數 )
11/28 21:28, 4F
→
11/28 21:41, , 5F
^^^ 錯了，是 O( (26取K)^N * 單字數)
11/28 21:41, 5F
推
12/02 01:08, , 6F
找二分圖是否包含給定大小完全圖似乎是NP-complete
12/02 01:08, 6F
→
12/02 01:09, , 7F
所以應該N=2就很難做了 (假設字母集跟K很大)
12/02 01:09, 7F
→
12/02 10:07, , 8F
看來 balanced biclique problem 可以 reduce 到這問題
12/02 10:07, 8F
→
12/02 10:07, , 9F
而 balanced biclique problem 在 bipartite graph 是 NPC
12/02 10:07, 9F
→
12/03 01:29, , 10F
不過字母集是常數的case可能可以考慮 但我還沒有想法
12/03 01:29, 10F
→
12/03 10:31, , 11F
字母集大小是常數的話窮舉就是 polynomial time 了
12/03 10:31, 11F
→
12/03 18:58, , 12F
沒有吧 窮舉是c^N ?
12/03 18:58, 12F
→
12/03 21:30, , 13F
喔對 我搞錯了
12/03 21:30, 13F
‣ 更多 FRAXIS 的文章
文章代碼(AID): #1OEc-ec6 (Prob_Solve)