ฉันจะเพิ่มประสิทธิภาพการแก้ปัญหาแบบเดรัจฉานของฉันสำหรับปัญหานี้ได้อย่างไร
ฉันกำลังแก้ไขปัญหาตามที่อธิบายไว้ด้านล่าง ฉันใช้กำลังดุร้ายฉันมาถึงจุดที่การแก้ปัญหาเป็นสิ่งต้องห้ามดังนั้นฉันจึงต้องเพิ่มประสิทธิภาพให้มากขึ้น (ถ้าเป็นไปได้) แน่นอนว่าจะดียิ่งขึ้นหากมีวิธีที่ดีกว่าในการแก้ปัญหา (ไม่ใช่การบังคับแบบเดรัจฉาน)
มีอะไรที่ฉันสามารถทำได้เพื่อปรับปรุงโซลูชันของฉันหรือข้อมูลอ้างอิงที่ฉันสามารถตรวจสอบได้ (ปัญหาที่คล้ายกัน ฯลฯ )
ปัญหา
เราเริ่มต้นด้วยกระดานสี่เหลี่ยม แต่ละเซลล์สามารถอยู่ในสถานะ N และสถานะเริ่มต้นสำหรับแต่ละเซลล์เป็นแบบสุ่ม (0 <= state <N) สำหรับแต่ละเซลล์ นอกจากนี้เรายังมีรูปทรงหลายแบบซึ่งทั้งหมดนี้พอดีกับกระดาน ทุกทรงมีความต่อเนื่อง
แต่ละรูปร่างจะต้องวางครั้งเดียว (และเพียงครั้งเดียว) ในกระดาน เมื่อวางรูปร่างเซลล์แต่ละเซลล์ที่เป็นของรูปร่างจะมีค่าเพิ่มขึ้น 1 หากค่ากระดานในเซลล์ใด ๆ ถึง N เซลล์จะเปลี่ยนเป็น 0
เป้าหมายคือการหาตำแหน่งที่แต่ละรูปร่างต้องวางเพื่อให้บอร์ดสุดท้ายมีเซลล์ทั้งหมดที่มีค่า 0 มีวิธีแก้ปัญหาอย่างน้อยหนึ่งข้อเสมอ สมมติว่าปัญหาเกิดขึ้นโดยเริ่มจากกระดานสำเร็จรูปและใช้รูปทรงสุ่มในตำแหน่งสุ่ม
ขนาดกระดานจำนวนสถานะ N และจำนวนรูปร่างคือการตั้งค่าของเกมและเพิ่มขึ้นเรื่อย ๆ (ในอัตราที่แตกต่างกัน) สำหรับแต่ละระดับ
สิ่งที่ฉันกำลังทำอยู่
ฉันสามารถแก้ปัญหาได้ถึงขนาดหนึ่งโดยใช้กำลังดุร้าย ฉันมีการเพิ่มประสิทธิภาพบางอย่าง ฉันมาถึงจุดที่การแก้ปัญหาเป็นข้อห้ามดังนั้นฉันจึงต้องการปรับปรุงตรรกะของฉัน
สิ่งแรกที่ฉันทำคือจัดลำดับรูปร่างจากใหญ่ไปเล็กยิ่งเล็กจะถูกย้ายในการทำซ้ำภายใน ข้อสันนิษฐาน (ซึ่งฉันยังไม่ได้พิสูจน์ แต่ทดสอบแล้วว่าเร็วกว่า) คือควรขยับรูปร่างที่เล็กกว่าให้มากขึ้นเนื่องจากมีโอกาสสร้างโซลูชันได้สูง
ประการที่สองสำหรับรูปร่างที่ซ้ำ ๆ กันฉันหลีกเลี่ยงการตรวจสอบการเรียงสับเปลี่ยนทั้งหมดเนื่องจากให้ผลลัพธ์เหมือนกัน ฉันยังตรวจสอบตำแหน่งชุดเดียวเท่านั้นเมื่อคู่ของรูปทรงเดียวกันทับซ้อนกัน (เนื่องจากการทับซ้อนกันทั้งหมดให้ผลลัพธ์เหมือนกัน)
การเพิ่มประสิทธิภาพขั้นสุดท้ายอย่างหนึ่งที่ฉันคิดว่าจะช่วยได้มาก แต่ฉันยังคงใช้อยู่คือ: ในแต่ละรูปร่างในลำดับให้นับจำนวนเซลล์ทั้งหมดในรูปร่างที่ยังคงต้องย้าย จำนวนนี้ลบเซลล์ทั้งหมดที่จำเป็นเพื่อให้ได้บอร์ดที่เสร็จสมบูรณ์ต้องเป็นจำนวนนับของ N ถ้าไม่ใช่ก็ไม่มีจุดเดรัจฉานบังคับตำแหน่งรูปร่างที่เหลือและเราต้องวางตำแหน่งรูปร่างใหม่ในลูปภายนอก
รายละเอียดเพิ่มเติม
ฉันสนใจคำแนะนำอื่น ๆ เกี่ยวกับวิธีเพิ่มประสิทธิภาพนี้ อัลกอริทึมที่เป็นที่รู้จักแม้กระทั่งการตั้งชื่อที่ดีสำหรับชุดปัญหานี้ซึ่งฉันสามารถใช้ในการค้นคว้าเพิ่มเติมก็จะดีมาก
คำตอบ
การเขียนโปรแกรมเชิงเส้นจำนวนเต็ม
ปัญหาของคุณสามารถกำหนดได้ด้วยวิธีต่อไปนี้: เราได้รับเวกเตอร์ $v_{i,j} \in (\mathbb{Z}/N\mathbb{Z})^d$ที่คณะกรรมการมี $d$ เซลล์และเป้าหมายคือเวกเตอร์ $c \in (\mathbb{Z}/N\mathbb{Z})^d$ค้นหาฟังก์ชัน $f$ ดังนั้น $\sum_i v_{i,f(j)}=c$. จากนั้นปัญหานี้สามารถแก้ไขได้โดยการโปรแกรมเชิงเส้นจำนวนเต็ม สิ่งนี้เกี่ยวข้องกับไฟล์$d$- ปัญหาผลรวมชุดย่อยดังนั้นคุณอาจสามารถค้นหาอัลกอริทึมอื่น ๆ สำหรับผลรวมย่อยหลายมิติและทดลองใช้เช่นกัน
เราจะกำหนดมันอย่างไร? ถ้าตารางมี$d$ เซลล์เราสามารถคิดรูปร่างเป็น $d$- เวกเตอร์ของ 0 และ 1 โดยมี 1 อยู่ในเซลล์ที่ปกคลุมด้วยรูปร่าง แต่ละรูปร่างสามารถวางในตำแหน่งที่แตกต่างกันได้จำนวนเวกเตอร์ที่แตกต่างกัน$v_{i,j}$ สอดคล้องกับ $j$สถานที่ที่มีรูปร่าง $i$ สามารถวางได้ $c$ สอดคล้องกับตัวเลขเดิมในตาราง (การปฏิเสธของตัวเลขเหล่านั้นโมดูโล $N$). เลขคณิตทั้งหมดทำโมดูโล$N$.
กำลังเดรัจฉานที่ฉลาดกว่าเล็กน้อย
หรืออีกวิธีหนึ่งนี่คือวิธีปรับปรุงพลังเดรัจฉานเล็กน้อยโดยการซื้อขายหน่วยความจำเป็นเวลา สมมติว่าคุณมี$k$รูปร่าง เริ่มต้นด้วยการแจกแจงทุกวิธีในการวางอันดับแรก$k/2$รูปร่างลงบนกระดานว่างของศูนย์ทั้งหมดและจัดเก็บตำแหน่งผลลัพธ์ทั้งหมดในรายการแฮชแท็กหรือเรียงลำดับ จากนั้นแจกแจงทุกวิธีในการวางลำดับสุดท้าย$k/2$รูปร่างบนตำแหน่งเริ่มต้นและค้นหาแต่ละตำแหน่งที่เป็นผลลัพธ์ในรายการแฮชแท็กหรือเรียงลำดับ หากคุณพบรายการที่ตรงกันแสดงว่าจะให้คำตอบ วิธีนี้จะช่วยให้คุณสามารถผลักดันเดรัจฉานได้ไกลขึ้นอีกเล็กน้อยซึ่งอาจเป็นได้ถึงสองเท่าของรูปทรงหากคุณมีหน่วยความจำไม่ จำกัด จำนวน มีรายละเอียดมากมายที่เกี่ยวข้องในการเพิ่มประสิทธิภาพให้สูงสุด แต่เป็นความคิดที่คุณสามารถพิจารณาได้หากคุณกำลังดุร้ายทำให้คุณเข้าใกล้ แต่สั้นไปหน่อย ยังคงเป็นอัลกอริธึมเวลาเอกซ์โพเนนเชียลดังนั้นจึงยังคงถึงขีด จำกัด