如何找到最大可能的答案，以解決真正的大問題？

首先，這不是一個家庭作業問題。自1988年以來，我一直沒有做過功課！如何找到最大可能的答案，以解決真正的大問題？

我具有長度N
我具有13個字符的最大可供選擇的單詞列表。
可以有相同的字母

考慮的話，這13個字符會拼的最可能的單詞列表的倍數。我可以扔出去的話，使困難要解決的問題，例如：

speedometer has 4 e's in it, something MOST words don't have, 
so I could toss that word due to a poor fit characteristic, or it might just 
go away based on the algorithm

我已經看了@信分佈，我已經建立的話（逐個字母）的圖表。有一些我錯過了，或者這個問題比我想象的要困難得多。如果可能的話，我寧願不要完全蠻力，但我現在正在談論這一點。

遺傳算法浮現在腦海中，但我從來沒有嘗試過他們....

好像我需要一種方式來得分基於其與它的字樣其他字母關聯的每個字母。 ...

來源

2011-04-14 boatcoder

有趣的問題！我同意@antti說它可能是NP完全的，但是如果給出一個26個字母的字母表，那麼選擇13是26c13 = 10,400,600，這對於通過暴力測試來說應該是實用的。 – 2011-04-14 05:52:08

我不理解你對你說出來的單詞的評論......爲什麼不把所有的單詞都扔掉，那麼問題就會變得微不足道（開玩笑），但是真正的僵硬的問題陳述會讓我們更容易幫助。 – 8steve8 2011-04-14 09:12:33

我想拼出最可能的單詞，但我不必拼出全部拼寫。所以從列表中刪除單詞不是問題，拼寫最可能的單詞是問題。由於一個4 e的單詞會佔用30％的字母，因此這個單詞顯然會被扔掉，因爲4 e因爲字母空間的耗盡而阻止了其他單詞的拼寫。 – boatcoder 2011-04-14 13:06:02

我可以拿出最好的是分支和綁定。做一個「中間狀態」數據包括您已經使用了（用複數）

快報結構
字符數你仍然可以在使用
快報仍可
言猶您的列表
言猶在列表（以前的一組數）
是不可能在這種狀態下的字數數
字數那些已經涵蓋你所選擇的字母

你會開始

空集
{A，B，...，Z}
你的整個列表
ň

將該數據結構放入隊列。

在每一步

Pop an item from the queue 
Split into possible next states (branch) 
Bound & delete extraneous possibilities

從一個狀態，我會產生可能的下一狀態如下：

For each letter L in the set of letters left 
    Generate a new state where: 
     you've added L to the list of chosen letters 
     the least letter is L 
     so you remove anything less than L from the allowed letters

因此，舉例來說，如果你的遺留的集爲{W， X，Y，Z}，我會生成一個狀態，W加到我的選擇中，{W，X，Y，Z}仍然可能，一個X作爲我的選擇，{X，Y，Z}仍然可能（但不是W），一個Y作爲我的選擇，{Y，Z}仍然可能，另一個Z作爲我的選擇，{Z}仍然有可能。

做所有各種會計找出新的狀態。

每個州至少有「您選擇的字母已涵蓋的字數」單詞，並且最大數字加上「仍在您的列表中的字數」。在所有狀態中，找到最高的最小值，並刪除任何狀態的最大值。

對速度表不需要特殊處理。

我無法想象這會很快，但它會工作。可能存在一些優化（例如，將列表中的每個單詞存儲爲發生數量AZ的數組，並將具有相同結構的單詞組合在一起：AB的2個發生次數...... T => BAT和標籤）。如何排序並記錄最小值和最大值也可能會有所幫助。可能不足以形成漸近差異，但也許對於一個足夠大的問題來使它在合理的時間內運行，而不是在極端的時間。

來源

2011-04-15 05:41:08 Michael

這聽起來像一個艱難的組合問題。給你一個詞的字典D，你可以選擇N個字母（可能有重複）來儘可能多地覆蓋/生成儘可能多的單詞。我99.9％肯定它可以被證明是一般的NP完全優化問題（假設可能是字母表，即包含超過26個項目的字母集合），通過減少SETCOVER來達到它，但是我將離開實際的減少作爲練習讀者:)

假設這很難，你有常規途徑：

分支和約束
隨機搜索
近似算法

來源

2011-04-14 05:31:46

點擊設置可能更相關，但是這與SetCover無關。 – 2011-04-14 06:24:37

總的暴力強制應該有效，但實施會變得相當混亂。

而不是像速度計一樣拋出單詞，只有當字符出現在單詞中時才能生成關聯圖（不管它出現的次數是多少，因爲它不應該影響最後的13個字符的最佳選擇）。這也會使得它比總暴力更簡單。

評論歡迎。 :)

來源

2011-04-14 06:00:26 Khemka

刪除包括字母大小在內的每個參數的界限時，從最大覆蓋問題出發很容易保留目標，這是NP難度並且難以近似的比率優於（e - 1）/ e ≈0.632。它是固定參數在字母大小通過蠻力處理。

我同意尼克約翰遜的蠻力建議;在最壞的情況下，只有（13 + 26 - 1）選擇（26 - 1）多集，這隻有大約50億。如果將每個字母的多樣性限制在可能有用的範圍內，這個數字會變得更小。即使速度太慢，您也應該能夠回收數據結構。

來源

2011-04-14 13:35:44 zxc

我完全不理解這個「我最多有13個字符可供選擇，」。如果你有1000個單詞的列表，那麼你的意思是你必須減少到只有13個字符？！

基於我（MIS）的認識的幾點思考：

如果只處理英朗的話，那麼你可以跳過元音輔音，因爲是一樣的描述。我們的大腦可以填充元音 - 又名短信/推特語言:)

也許對於1-3個字母的單詞，剝離元音將失去太多的信息。但仍然：

spdmtr HS 4「SNT，smthng MST WRDS dn't HV，S CLD TSS THT WRD dt的PR英尺 chrctrstc，室溫mght JST克 WY BSD第n lgrthm

詞幹會縮短詞彙量。首先，先去掉元音，然後去掉元音。然後做一個直方圖....

來源

2011-04-15 19:00:42

實際上，我們的目標是想出13個字母，而不是用來拼出儘可能多的單詞。我不想混淆一個句子。我知道我無法用13個字母拼出列表中的所有單詞，但是我想找到最好的13個單詞拼寫儘可能多的單詞。 – boatcoder 2011-04-16 21:57:03

如何找到最大可能的答案，以解決真正的大問題？

回答

相關問題