การใช้งานตัวแก้ปัญหาสำหรับเกมคำศัพท์ Boggle สุดคลาสสิก! เคยแข่งขันในเกม Boggle ที่เข้มข้นโดยคิดว่าคุณใช้คำศัพท์ที่เป็นไปได้หมดแล้วบนกระดานหรือไม่? ไม่คิดอีกต่อไป!
ด้วยไฟล์พจนานุกรมที่คุณเลือกและกระดานที่มีขนาดที่กำหนดเอง คุณจะมีคำศัพท์ภาษาอังกฤษทั้งหมดที่มีอยู่ในกระดาน Boggle ของคุณในเวลาอันรวดเร็ว! (ในคอมพิวเตอร์ของฉัน อัลกอริธึมทำงานใน < 3 วินาทีบนบอร์ดขนาด 50x50!!) หากคุณต้องการใช้พจนานุกรมอื่นนอกเหนือจากที่ฉันให้ไว้ ซึ่งก็ไม่มีปัญหา เพียงตรวจสอบให้แน่ใจว่าแต่ละคำถูกคั่นด้วยการขึ้นบรรทัดใหม่
เมื่อนำทางไปยังไดเร็กทอรีโปรเจ็กต์รูทแล้ว ให้ใช้คำสั่งต่อไปนี้ในเทอร์มินัล:
Mac OS X gradlew -PmainClass=Boggle solve
Windows gradlew.bat -PmainClass=Boggle solve
สมมติว่าไฟล์ Boggle.java ไม่ได้ถูกแก้ไข โปรแกรมนี้จะค้นหาคำทั้งหมดที่อยู่ในบอร์ดต่อไปนี้:
Solving:
a r m
b e s
n i m
arsine
rabies
bismer
bersim
barmen
miners
minbar
abime
abies
abner
resin
bines
bisme
biers
benim
besin
besra
berms
bears
bearm
braes
barse
bares
barms
smear
serab
smear
nears
inerm
mines
miner
miser
arse
aren
ares
arms
rems
reim
rein
reis
rems
rabi
mems
mein
mear
mrem
bine
bise
bien
bier
beni
berm
bear
brei
bren
bars
bare
barm
ears
sime
sine
sier
semi
serb
sera
sear
nims
nies
near
inbe
mise
mien
mems
mear
aes
aer
abn
abr
ars
are
arb
arm
rem
rei
ren
res
reb
rem
rea
rms
rab
mem
men
mer
mea
mrs
bim
bin
bis
ben
bes
ber
bra
bae
bar
ems
ems
ers
era
ear
sim
sin
sie
sib
sem
sei
sen
sem
ser
sea
nim
nis
nib
nei
neb
nea
ism
ise
ism
iba
min
mis
mib
men
mem
mer
mea
ดังที่คุณคงจินตนาการได้ การค้นพจนานุกรมเพื่อตรวจสอบว่าลำดับตัวอักษรที่เป็นไปได้ทุกตัวเป็นคำภาษาอังกฤษหรือไม่นั้นถือเป็นงานที่ค่อนข้างลำบาก ปรากฎว่าสำหรับบอร์ดขนาดใดๆ nxn จะมีค่าสูงสุด n^2 x (n^2)! ลำดับตัวอักษรที่เป็นไปได้ที่ต้องตรวจสอบความถูกต้อง สิ่งนี้พังเร็วมากอย่างเห็นได้ชัด - บอร์ดขนาด 3 x 3 ธรรมดาต้องการการตรวจสอบความถูกต้องสูงสุด 3265920 และนี่ไม่ใช่ขนาดของบอร์ดเกรงกลัวจริงด้วยซ้ำ! แล้วฉันจะทำอย่างไร? ฉันหมายถึงว่าแม้แต่การแก้บอร์ด ขนาด 8 x 8 ก็ต้องใช้การคำนวณสูงสุดประมาณ 10^90 ครั้ง! ฉันคงทำอะไรที่ฉลาดมากที่นี่ ปรากฎว่ามีวิธีที่มีประสิทธิภาพมากกว่าอย่างเหลือเชื่อ จุดสำคัญของอัลกอริธึมการแก้ปัญหาจะหมุนรอบโครงสร้างข้อมูลเฉพาะที่เรียกว่า Trie ด้วยสตริงที่มีความยาว n Trie สามารถบอกเราได้ว่าสตริงที่เรากำลังค้นหามีอยู่ในพจนานุกรมของเราในเวลา O(n) (เชิงเส้น) หรือไม่! นี่เป็นการปรับปรุงอย่างมากจากการรันการค้นหาแบบไบนารี่สำหรับคำที่เป็นไปได้แต่ละคำในไฟล์พจนานุกรม ในความเป็นจริง Trie สามารถตรวจสอบได้ว่าการเพิ่มตัวอักษรลงในสตริงที่มีอยู่จะส่งผลให้มีคำอื่นที่ถูกต้องในเวลาคงที่หรือไม่! นี่คือสิ่งที่ทำให้อัลกอริทึมทำงานได้รวดเร็ว: เราทำการค้นหาในเชิงลึกก่อนจากตัวอักษรแต่ละตัวบนกระดาน เพิ่มตัวอักษรที่อยู่ติดกันให้กับคำปัจจุบันที่เราสร้างขึ้น และผนวกเข้ากับผลลัพธ์ของเราหากให้ผลลัพธ์เป็นคำที่มีอยู่ ในพจนานุกรมของเรา หาก ณ จุดใดจุดหนึ่งเราไปถึงสตริงที่ไม่ใช่คำนำหน้าของคำอื่นใด เราจะย้อนกลับไปยังคำนำหน้าที่ถูกต้องใกล้เคียงที่สุดและดำเนินการต่อ ของเจ๋งมาก!
ประสิทธิภาพรันไทม์ต้องแลกมาด้วยต้นทุน ไฟล์พจนานุกรมที่ฉันใช้มีขนาดประมาณ 5 เมกะไบต์ ดังนั้นความต้องการพื้นที่ในการรวบรวมทุกคำลงในพจนานุกรม Trie จึงค่อนข้างใหญ่มาก จริงๆ แล้วการสร้าง Trie จากพจนานุกรมเป็นสิ่งที่ใช้เวลานานที่สุดจึงจะสำเร็จ โดยมีความเร็วในการดำเนินการโดยเฉลี่ยประมาณ 2.2 วินาทีบนคอมพิวเตอร์ของฉัน หากเรามองในแง่ดี การสร้างพจนานุกรม Trie ต้องใช้เวลาและพื้นที่คงที่โดยคำนึงถึงขนาดของกระดานที่เรากำลังแก้ไข ตามมาด้วยองค์ประกอบเดียวที่น่ากังวลคือรันไทม์ของอัลกอริธึมการแก้ปัญหาของเรา ซึ่งได้รับการพิสูจน์แล้วว่ามีประสิทธิภาพในการแก้บอร์ดที่มีขนาดสูงสุด 50 x 50 ในเวลาน้อยกว่า 3 วินาที หากคุณสนใจขอบเขตที่จำกัด อัลกอริธึมใช้เวลาประมาณ 77 วินาทีในระบบของฉันในการค้นหาวิธีแก้ปัญหาสำหรับบอร์ด ขนาด 250 x 250
