ความซับซ้อนของเวลาของอัลกอริทึมการค้นหาแบบหมดจด

ฉันมีชุด $S_1=\{2,10,20,6\}$ และ $S_2=\{25,26,20\}$ และฉันต้องการหาว่าตัวเลขใดรวมกันได้ 32 การตรวจสอบทำได้ง่ายมาก 6 และ 26 ดูเหมือนจะคล้ายกับปัญหาเป้ แต่ฉันไม่ใช่ผู้เชี่ยวชาญ

อย่างไรก็ตาม สมมติว่าฉันมี 1,000 ชุด โดยแต่ละชุดมีองค์ประกอบ 500 รายการ ซึ่งการบวกหนึ่งพจน์จากแต่ละชุดจะให้ค่าที่ไม่ซ้ำกันเสมอ สิ่งนี้ตรวจสอบและแก้ไขได้ยากกว่ามาก โดยเฉพาะอย่างยิ่งหากเซ็ตต่างๆ เป็นไปตามโครงสร้างที่ดูเหมือนสุ่ม (พวกมันจะถูกสร้างจากเซ็ตที่มีโครงสร้างที่ยุ่งเหยิง และแทบจะเป็นไปไม่ได้เลยที่จะคาดเดาการผสมและย้อนกลับของเซ็ต)

ดังนั้นวิธีเดียวจึงต้องเป็นอัลกอริทึมการค้นหาแบบหมดจด เนื่องจากหมายเลขของฉันคือ 52,485,332 จึงมี $1000^{500}$ ตัวเลือกที่เป็นไปได้ในการดู แน่นอนว่าจะมีวิธีในการทำให้การค้นหานี้สั้นลง (เช่น เมื่อชุดมีตัวเลขมากกว่าค่าเป้าหมายของคุณ คุณสามารถเพิกเฉยต่อตัวเลขเหล่านั้นได้) แต่อย่างอื่นคุณอาจจะยังดูอยู่ $750^{500}$ ทางเลือกที่เป็นไปได้

ดังนั้นความซับซ้อนของเวลาของอัลกอริทึมการค้นหาดังกล่าวคืออะไร? $O(n^{k})$, กับ $n$ จำนวนชุดและ $k$ จำนวนองค์ประกอบในชุดเหล่านั้น? พวกเขาต้องตรวจสอบการรวมกันของคำศัพท์ที่เป็นไปได้ "ทั้งหมด" จนกว่าจะตรงกับค่าที่กำหนด

คำถามหลักดูเหมือนจะเป็น "มีกี่ชุด" และ "ชุดใหญ่แค่ไหน". แท้จริงแล้วชุดสามารถมีขนาดต่างๆ ได้ทั้งหมด ไม่ใช่แค่ชุดเดียว

ฉันไม่ใช่คนเข้ารหัส การวิจัยของฉันเพียงแค่เจ้าชู้กับความคิดที่อยู่ในมือ ความช่วยเหลือใด ๆ ที่จะได้รับการชื่นชม

ดังนั้นวิธีเดียวจึงต้องเป็นอัลกอริทึมการค้นหาแบบหมดจด

ดังที่ฉันได้กล่าวไว้ในความคิดเห็นของฉัน มีวิธีปฏิบัติสำหรับมูลค่าที่ไม่มากของ $m$ (และ $m=52485332$ ไม่ใหญ่โตนัก) ต่อไปนี้เป็นโครงร่างของวิธีการดังกล่าว (ซึ่งถือว่าชุดทั้งหมดประกอบด้วยจำนวนเต็มที่ไม่เป็นลบ):

• เรามีอาร์เรย์ $A_{n, ม+1}$; แต่ละองค์ประกอบของอาร์เรย์ $A_{a, ข}$ จะสังเกตว่าเราสามารถสร้างผลรวมได้อย่างไร $ข$ จากครั้งแรก $a$ ชุด (หรือ $\perp$ ถ้ายังหาช่องทางนั้นไม่เจอ)

• เริ่มต้นองค์ประกอบทั้งหมด $A$ ถึง $\perp$

• สำหรับ $i := 1$ ถึง $n$ ค้นหาองค์ประกอบ $A_{i-1}$ สำหรับผู้ที่ไม่ใช่$\perp$ องค์ประกอบ (และสำหรับ $i=1$องค์ประกอบที่ 0 จะถือว่าเป็นองค์ประกอบเดียวที่ไม่ใช่$\perp$ ธาตุ. สำหรับแต่ละองค์ประกอบดังกล่าว $A_{i-1, x}$, ชุด $A_{i, x + S_{i,j}}$ ถึง $เจ$ (สำหรับแต่ละองค์ประกอบ $S_{i,j}$ ของชุด $S_i$) ถ้า $x + S_{i,j} > ม$ไม่สนใจมัน

• สุดท้ายถ้า $A_{n,m} = \perp$ไม่มีเซตย่อยที่นำไปสู่ผลรวม $m$. หากเป็นอย่างอื่น เราสามารถกู้คืนเงื่อนไขได้โดยย้อนรอยผ่านอาร์เรย์ $A$.

นี่ควรเป็นอัลกอริทึมที่ใช้งานได้จริงสำหรับการกู้คืนเงื่อนไขตามพารามิเตอร์ที่คุณระบุไว้

นี่เป็นคำตอบเพิ่มเติมว่าเหตุใดผลรวมที่ไม่ซ้ำใครจึงส่งผลต่อขนาดอย่างมาก $52485332$ กลายเป็นเรื่องเล็กน้อย (เป็นวิธีที่จะใช้เวลานานสำหรับความคิดเห็น)

เมื่อผลรวมทั้งหมดต้องไม่ซ้ำกัน ผลรวมทั้งหมดจึงต้องเป็นจำนวนเต็มที่แตกต่างกัน เพราะมี $500^{1000}$ ผลรวมที่เป็นไปได้นอกจากนี้ยังมี $500^{1000}$ ผลลัพธ์จำนวนเต็มที่แตกต่างกันสำหรับสิ่งนั้น กรณีต่ำสุดจะเป็นจำนวนเต็มทั้งหมดจาก $0$ ถึง $500^{1000}-1$.

ตัวอย่างเช่น,

$S_1 = \{0, 1, 2, ..., 499\}$

$S_2 = \{0, 500, 1,000, ..., 249500\}$

$S_3 = \{0, 250000, 500000, ..., 124750000\}$

...

$S_{1000} = \{0, 500^{999}, 2*500^{999}, ..., 499*500^{999}\}$

จะเป็นวิธีที่รับประกันความเป็นเอกลักษณ์ของผลลัพธ์ อย่างที่คุณเห็น ตัวเลขเพิ่มขึ้นเร็วมากจริงๆ

ในตัวอย่างนี้ ง่ายต่อการค้นหาผลลัพธ์ (เพียงเลือกจำนวนที่มากที่สุดที่พอดีจากชุดสุดท้ายถึงชุดแรกเสมอ) แม้แต่ตัวเลขส่วนใหญ่ก็คือ $S_3$ มีค่ามากกว่า $52485332$ ดังนั้นจึงสามารถละเว้นได้

คุณอาจต้องการค่าที่ค่อนข้างสุ่มในชุดของคุณ ในกรณีนี้ ช่วงของค่าต้องมากกว่าเล็กน้อยเป็นอย่างน้อย

อย่างไรก็ตาม ไม่น่าเป็นไปได้อย่างยิ่งที่ค่าใดๆ จะต่ำกว่าหรือเท่ากับ $52485332$ (เมื่อคุณเลือกแบบเดียวกัน $500000$ ค่าออกจาก $500^{1000}$)

การเขียนโปรแกรมแบบไดนามิกตามที่ @poncho แนะนำนั้นใช้งานได้กับจำนวนน้อยเท่านั้น และประสิทธิภาพของมันก็ไม่ได้ดีไปกว่าการค้นหาแบบละเอียดถี่ถ้วน (ความแตกต่างเชิงเส้นในจำนวนชุด) เนื่องจากผลรวมย่อยที่สามารถนำมาใช้ซ้ำได้นั้นไม่ซ้ำกัน ข้อได้เปรียบ การไม่ดูความเป็นไปได้อย่างอื่นก็ไม่มี รันไทม์ควรเป็นลำดับเดียวกับการค้นหาแบบละเอียด การปรับปรุงเพียงอย่างเดียวคือต้องดำเนินการเมื่อค่ามีขนาดใหญ่หรือเล็กเพื่อบรรลุเป้าหมาย แต่สำหรับเป้าหมายที่สมเหตุสมผลนั้นไม่มีข้อได้เปรียบมากนัก

On สามารถลดปัญหาผลรวมย่อยหรือปัญหาเป้ได้อย่างง่ายดายเพียงแค่ใช้ชุดเดียวกันหลาย ๆ ครั้งตามจำนวนที่คุณต้องการรวมปัญหาของสิ่งนี้คือนี่ไม่ใช่มดลดเวลาพหุนาม ดังนั้นจึงไม่เพียงพอที่จะพิสูจน์ว่าปัญหาคือ NP ยากหรือไม่