采纳
优质回帖
-
破防的小蔡 (Amove) • 1 年前 1
超级暴搜，可惜复杂度太高了，下周再来优化~~（要下班了）~~。目前可以跑出大量五个成语
抽象的代码如下
package main import ( "encoding/json" "fmt" "github.com/mozillazg/go-pinyin" "io/ioutil" "sort" ) var words, initWords []Word func DFS(step int, vis map[string]int, ans []string) { if step >= 6 { // 退出 fmt.Println(ans) return } pinyinApp := pinyin.NewArgs() pinyinApp.Style = pinyin.FirstLetter for _, w := range words { wordArray := pinyin.Pinyin(w.Word, pinyinApp) // 试探是否重复 if vis[wordArray[0][0]] > 0 || vis[wordArray[1][0]] > 0 || vis[wordArray[2][0]] > 0 || vis[wordArray[3][0]] > 0 { continue } // 暴搜下一步 vis[wordArray[0][0]]++ vis[wordArray[1][0]]++ vis[wordArray[2][0]]++ vis[wordArray[3][0]]++ ans = append(ans, w.Word) DFS(step+1, vis, ans) vis[wordArray[0][0]]-- vis[wordArray[1][0]]-- vis[wordArray[2][0]]-- vis[wordArray[3][0]]-- ans = ans[:len(ans)-1] } return } type Word struct { Pinyin string `json:"pinyin"` Word string `json:"word"` } func main() { // 读取 JSON 文件 fmt.Println("Start") fileData, err := ioutil.ReadFile("data.json") if err != nil { fmt.Println("无法读取文件:", err) return } // 解码 JSON 数据 err = json.Unmarshal(fileData, &initWords) if err != nil { fmt.Println("解码 JSON 失败:", err) return } // 预处理 pinyinApp := pinyin.NewArgs() pinyinApp.Style = pinyin.FirstLetter for _, w := range initWords { wordArray := pinyin.Pinyin(w.Word, pinyinApp) // 仅保留四字成语 if len(wordArray) != 4 { continue } // 去除本身重复 vis := make(map[string]int) vis[wordArray[0][0]]++ vis[wordArray[1][0]]++ vis[wordArray[2][0]]++ vis[wordArray[3][0]]++ if vis[wordArray[0][0]] > 1 || vis[wordArray[1][0]] > 1 || vis[wordArray[2][0]] > 1 || vis[wordArray[3][0]] > 1 { continue } words = append(words, w) } // 按照拼音排序 sort.Slice(words, func(i, j int) bool { return words[i].Pinyin < words[j].Pinyin }) DFS(0, make(map[string]int), []string{}) fmt.Println("End") }可能存在的优化方案：
-
破防的小蔡 (Amove) • 1 年前
尝试了三个优化：
- 初始化时加入了拼音，去掉了深搜时多次中文转拼音的复杂度。
- 剪枝了多次尝试已经试探过的部分，
tryBehindStep提供记忆 - 采用了清华中文词库，将频率更高的词汇提前，这个实际并没有加速，但是就仅找到一个答案而言好像蛮有用的（如果采用更小的数据集也算优化😋）
部分答案如：坚定不移 敲诈勒索 深恶痛绝 云蒸霞蔚 酒醉饭饱 柔肠百转
这版丑陋的代码：
package main import ( "encoding/json" "fmt" "github.com/mozillazg/go-pinyin" "io/ioutil" ) var words, initWords []string var wordsFirst, wordsFinals [][]string var totalAns int func DFS(step int, tryBehindStep int, vis map[string]int, vowelVis map[string]int, ans []string) { if step >= 6 { // 退出 fmt.Println(ans) totalAns++ return } for ind, w := range words { if ind < tryBehindStep { continue } // 试探首字母是否重复 wordArray := wordsFirst[ind] if vis[wordArray[0]] > 0 || vis[wordArray[1]] > 0 || vis[wordArray[2]] > 0 || vis[wordArray[3]] > 0 { continue } // 试探韵母是否重复 wordArray = wordsFinals[ind] if vowelVis[wordArray[0]] > 0 || vowelVis[wordArray[1]] > 0 || vowelVis[wordArray[2]] > 0 || vowelVis[wordArray[3]] > 0 { continue } // 暴搜下一步 for indF := 0; indF < 4; indF++ { vowelVis[wordsFinals[ind][indF]]++ vis[wordsFirst[ind][indF]]++ } ans = append(ans, w) DFS(step+1, ind+1, vis, vowelVis, ans) // 回溯 for indF := 0; indF < 4; indF++ { vowelVis[wordsFinals[ind][indF]]-- vis[wordsFirst[ind][indF]]-- } ans = ans[:len(ans)-1] } return } func main() { // 读取 JSON 文件 fmt.Println("Start") totalAns = 0 fileData, err := ioutil.ReadFile("good_data.json") if err != nil { fmt.Println("无法读取文件:", err) return } // 解码 JSON 数据 err = json.Unmarshal(fileData, &initWords) if err != nil { fmt.Println("解码 JSON 失败:", err) return } // 预处理 pinyinApp := pinyin.NewArgs() for _, w := range initWords { pinyinApp.Style = pinyin.FirstLetter wordArray := pinyin.Pinyin(w, pinyinApp) // 仅保留四字成语 if len(wordArray) != 4 { continue } // 去除首字母本身重复 vis := make(map[string]int) var firstWords, finalWords []string for i := 0; i < 4; i++ { vis[wordArray[i][0]]++ firstWords = append(firstWords, wordArray[i][0]) } if vis[wordArray[0][0]] > 1 || vis[wordArray[1][0]] > 1 || vis[wordArray[2][0]] > 1 || vis[wordArray[3][0]] > 1 { continue } // 去除韵母本身重复 pinyinApp.Style = pinyin.Finals wordArray = pinyin.Pinyin(w, pinyinApp) vowelVis := make(map[string]int) for i := 0; i < 4; i++ { vowelVis[wordArray[i][0]]++ finalWords = append(finalWords, wordArray[i][0]) } if vowelVis[wordArray[0][0]] > 1 || vowelVis[wordArray[1][0]] > 1 || vowelVis[wordArray[2][0]] > 1 || vowelVis[wordArray[3][0]] > 1 { continue } words = append(words, w) wordsFinals = append(wordsFinals, finalWords) wordsFirst = append(wordsFinals, firstWords) } // 按照拼音排序 // 可能有效的优化 //sort.Slice(words, func(i, j int) bool { // return words[i] < words[j] //}) fmt.Println("有效数据集: ", len(words)) DFS(0, 0, make(map[string]int), make(map[string]int), []string{}) fmt.Println("End.totalAns: ", totalAns) }仍存在的问题：
- 只跑了成语数8000的小数据集，且有限时间内得不到所有答案
- 声母韵母的处理仍然太暴力了，后续仍可以用位运算优化
17 回帖
登录参与讨论
...
-
-
-
-
-
-
-
-
-
-
-
-
破防的小蔡 (Amove) • 1 年前
超级暴搜，可惜复杂度太高了，下周再来优化~~（要下班了）~~。目前可以跑出大量五个成语
抽象的代码如下
package main import ( "encoding/json" "fmt" "github.com/mozillazg/go-pinyin" "io/ioutil" "sort" ) var words, initWords []Word func DFS(step int, vis map[string]int, ans []string) { if step >= 6 { // 退出 fmt.Println(ans) return } pinyinApp := pinyin.NewArgs() pinyinApp.Style = pinyin.FirstLetter for _, w := range words { wordArray := pinyin.Pinyin(w.Word, pinyinApp) // 试探是否重复 if vis[wordArray[0][0]] > 0 || vis[wordArray[1][0]] > 0 || vis[wordArray[2][0]] > 0 || vis[wordArray[3][0]] > 0 { continue } // 暴搜下一步 vis[wordArray[0][0]]++ vis[wordArray[1][0]]++ vis[wordArray[2][0]]++ vis[wordArray[3][0]]++ ans = append(ans, w.Word) DFS(step+1, vis, ans) vis[wordArray[0][0]]-- vis[wordArray[1][0]]-- vis[wordArray[2][0]]-- vis[wordArray[3][0]]-- ans = ans[:len(ans)-1] } return } type Word struct { Pinyin string `json:"pinyin"` Word string `json:"word"` } func main() { // 读取 JSON 文件 fmt.Println("Start") fileData, err := ioutil.ReadFile("data.json") if err != nil { fmt.Println("无法读取文件:", err) return } // 解码 JSON 数据 err = json.Unmarshal(fileData, &initWords) if err != nil { fmt.Println("解码 JSON 失败:", err) return } // 预处理 pinyinApp := pinyin.NewArgs() pinyinApp.Style = pinyin.FirstLetter for _, w := range initWords { wordArray := pinyin.Pinyin(w.Word, pinyinApp) // 仅保留四字成语 if len(wordArray) != 4 { continue } // 去除本身重复 vis := make(map[string]int) vis[wordArray[0][0]]++ vis[wordArray[1][0]]++ vis[wordArray[2][0]]++ vis[wordArray[3][0]]++ if vis[wordArray[0][0]] > 1 || vis[wordArray[1][0]] > 1 || vis[wordArray[2][0]] > 1 || vis[wordArray[3][0]] > 1 { continue } words = append(words, w) } // 按照拼音排序 sort.Slice(words, func(i, j int) bool { return words[i].Pinyin < words[j].Pinyin }) DFS(0, make(map[string]int), []string{}) fmt.Println("End") }可能存在的优化方案：
1 3 0 -
-
-
-
-
破防的小蔡 (Amove) • 1 年前
尝试了三个优化：
- 初始化时加入了拼音，去掉了深搜时多次中文转拼音的复杂度。
- 剪枝了多次尝试已经试探过的部分，
tryBehindStep提供记忆 - 采用了清华中文词库，将频率更高的词汇提前，这个实际并没有加速，但是就仅找到一个答案而言好像蛮有用的（如果采用更小的数据集也算优化😋）
部分答案如：坚定不移 敲诈勒索 深恶痛绝 云蒸霞蔚 酒醉饭饱 柔肠百转
这版丑陋的代码：
package main import ( "encoding/json" "fmt" "github.com/mozillazg/go-pinyin" "io/ioutil" ) var words, initWords []string var wordsFirst, wordsFinals [][]string var totalAns int func DFS(step int, tryBehindStep int, vis map[string]int, vowelVis map[string]int, ans []string) { if step >= 6 { // 退出 fmt.Println(ans) totalAns++ return } for ind, w := range words { if ind < tryBehindStep { continue } // 试探首字母是否重复 wordArray := wordsFirst[ind] if vis[wordArray[0]] > 0 || vis[wordArray[1]] > 0 || vis[wordArray[2]] > 0 || vis[wordArray[3]] > 0 { continue } // 试探韵母是否重复 wordArray = wordsFinals[ind] if vowelVis[wordArray[0]] > 0 || vowelVis[wordArray[1]] > 0 || vowelVis[wordArray[2]] > 0 || vowelVis[wordArray[3]] > 0 { continue } // 暴搜下一步 for indF := 0; indF < 4; indF++ { vowelVis[wordsFinals[ind][indF]]++ vis[wordsFirst[ind][indF]]++ } ans = append(ans, w) DFS(step+1, ind+1, vis, vowelVis, ans) // 回溯 for indF := 0; indF < 4; indF++ { vowelVis[wordsFinals[ind][indF]]-- vis[wordsFirst[ind][indF]]-- } ans = ans[:len(ans)-1] } return } func main() { // 读取 JSON 文件 fmt.Println("Start") totalAns = 0 fileData, err := ioutil.ReadFile("good_data.json") if err != nil { fmt.Println("无法读取文件:", err) return } // 解码 JSON 数据 err = json.Unmarshal(fileData, &initWords) if err != nil { fmt.Println("解码 JSON 失败:", err) return } // 预处理 pinyinApp := pinyin.NewArgs() for _, w := range initWords { pinyinApp.Style = pinyin.FirstLetter wordArray := pinyin.Pinyin(w, pinyinApp) // 仅保留四字成语 if len(wordArray) != 4 { continue } // 去除首字母本身重复 vis := make(map[string]int) var firstWords, finalWords []string for i := 0; i < 4; i++ { vis[wordArray[i][0]]++ firstWords = append(firstWords, wordArray[i][0]) } if vis[wordArray[0][0]] > 1 || vis[wordArray[1][0]] > 1 || vis[wordArray[2][0]] > 1 || vis[wordArray[3][0]] > 1 { continue } // 去除韵母本身重复 pinyinApp.Style = pinyin.Finals wordArray = pinyin.Pinyin(w, pinyinApp) vowelVis := make(map[string]int) for i := 0; i < 4; i++ { vowelVis[wordArray[i][0]]++ finalWords = append(finalWords, wordArray[i][0]) } if vowelVis[wordArray[0][0]] > 1 || vowelVis[wordArray[1][0]] > 1 || vowelVis[wordArray[2][0]] > 1 || vowelVis[wordArray[3][0]] > 1 { continue } words = append(words, w) wordsFinals = append(wordsFinals, finalWords) wordsFirst = append(wordsFinals, firstWords) } // 按照拼音排序 // 可能有效的优化 //sort.Slice(words, func(i, j int) bool { // return words[i] < words[j] //}) fmt.Println("有效数据集: ", len(words)) DFS(0, 0, make(map[string]int), make(map[string]int), []string{}) fmt.Println("End.totalAns: ", totalAns) }仍存在的问题：
- 只跑了成语数8000的小数据集，且有限时间内得不到所有答案
- 声母韵母的处理仍然太暴力了，后续仍可以用位运算优化
0 2 0
尝试了三个优化：
tryBehindStep提供记忆部分答案如：坚定不移 敲诈勒索 深恶痛绝 云蒸霞蔚 酒醉饭饱 柔肠百转
这版丑陋的代码：
仍存在的问题：