ปัญหาเกี่ยวกับผมรวมของเวกเตอร์

[armpakorn]

สมมุติว่าเรามีเซตของเวกเตอร์เซตหนึ่ง ให้เป็น A จะมีสูตรคำนวนหรือเปล่าครับว่า จะต้องใช้เวกเตอร์ในเซตดังกล่าวน้อยที่สุดกี่ตัว ที่ผลรวมของมันเท่ากับ (x,y)

ตัวอย่างเช่นเรามี A = {(1,2),(2,1),(-1,2),(-2,1),(1,-2),(2,-1),(-1,-2),(-2,-1)} ต้องการทราบว่า ต้องใช้เวกเตอร์ในเซตนี้น้อยที่สุดกี่ตัว ที่ผลรวมของมันเท่ากับ (1,4) [ทราบว่าต้องใช้ 3 ตัว คือ (2,1)+(-2,1)+(1,2)]

ไม่งงนะครับ

[lnพwsะบุ๑sสุ๑xล่o]

ลองหา 2 ตัวดูครับ ปรากฎว่า ไม่มี แสดงว่าต้องใช้อย่างน้อย 3 แบบที่คุณยกมาให้ครับ

ขออภัยครับ อ่านไม่ครบ ให้หาสูตร -__-

คิดว่าคงไม่มีสูตรครับ เพราะเงื่อนไขหรือข้อกำหนดจากโจทย์ยังน้อยเกินไป

[nooonuii]

ถ้าให้เอามาบวกกันอย่างเดียวคงไม่มีสูตร และบางครั้งก็ทำไม่ได้ด้วย

แต่ถ้าอนุญาตให้ใช้ผลรวมเชิงเส้นของเวกเตอร์พวกนี้ด้วย สองตัวก็พอครับ

[armpakorn]

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

นอกจากนี้ผมยังสนใจปัญหาอื่นอีกคือ จำนวนตาที่มากที่สุดที่จะเดินไปยังช่องช่องหนึ่งบนกระดาน ไม่ต้องถึงกับม้า แค่ขุน(อย่างง่ายที่สุดคือเดินตรง 4 ทิศรอบตัว ไม่ต้องเดินเฉียง) ยังหาสูตรทั่วไปไม่พบเลยครับ ท่านใดใจดีช่วยขบคิดปัญหานี้ต่อด้วยครับ

[lnพwsะบุ๑sสุ๑xล่o]

ถ้าหาจำนวนตาที่เดินมากสุด ก็เป็นอนันต์ครับ เดินกลับไปมา ผมเข้าใจถูกมั้ยครับ

[armpakorn]

นั่นคือในกรณีที่กระดานกว้างอนันต์ ยาวอนันต์ (ไม่จำกัดช่อง) ครับ แต่ที่เป็นปัญหาคือในกรณี กว้าง 8 ยาว 8 ช่องครับ

**เพิ่มเติม** ลืมระบุเงื่อนไข ต้องเดินไม่ซ้ำช่องเดิมด้วยนะครับ

ปล. กลับมาโพสอีกทีหลังจากหายไปหลายเดือน เห็นสมาชิกแอคทีฟขึ้นเยอะเลยนะครับ

[armpakorn]

ถ้าพิจารณาต่อไปนี้ (กำหนดให้กระดานกว้าง 1 ยาว N ให้ขุนอยู่ที่ (1,1) และเดินตรงได้อย่างเดียว ห้ามเดินเฉียง)


ถ้าช่องที่จะเดินไปคือ (1,2) จะพบว่า เดินได้มากสุด 1 ตา

ถ้าช่องที่จะเดินไปคือ (1,3) จะพบว่า เดินได้มากสุด 2 ตา
...
ถ้าช่องที่จะเดินไปคือ (1,N) จะพบว่า เดินได้มากสุด N-1 ตา

แต่ถ้าเพิ่มความกว้างเป็น 2 ล่ะ...

[Free Style01]

พอดีเข้ามาอ่าน เเล้วลองคิดดูนะครับ ไม่รู้ช้าไม่หรือปล่าว

ถ้าเกิด set A เป็นอย่างที่ยกตัวอย่างก็พอจะคิดได้ครับ คือ


หลักการ ผมอุปนัยมาจาก ถ้าอยากได้ค่า y เป็นเลข 5 ก้าวที่สั้นที่สุดก็ควรเป็น (y/2 เศษปัดขึ้น)
คือ 2,2 และ 1 รวม 3 ก้าว ตามลำดับ

เลข 2 ที่มีค่าเป็น 1 ก้าว สามารถเปลี่ยนเป็นเลข 1 กับ 1 รวม 2 ก้าวได้
เลข 1 ที่มีค่าเป็น 1 ก้าว สามารถเปลี่ยนเป็นเลข 2 กับ -1 รวม 2 ก้าวได้
เลข -1 ที่มีค่าเป็น 1 ก้าว สามารถเปลี่ยนเป็นเลข 2 กับ -1 รวม 2 ก้าวได้
เลข -2 ที่มีค่าเป็น 1 ก้าว สามารถเปลี่ยนเป็นเลข -1 กับ -1 รวม 2 ก้าวได้

ดังนั้นถ้าเรามี x ก้าว เราก็สามารถเปลี่ยนเป็น x+1 , x+2 , x+3,... ได้
หรือถ้าเรามี y ก้าว เราก็สามารถเปลี่ยนเป็น y+1 , y+2 , y+3,... ได้เช่นกัน

สิ่งที่เราต้องทำคือ การจับคู่ x กับ y ให้จำนวนก้าวเท่ากันก็พอ ซึ่งหาได้จาก max(x/2 , y/2) เศษปัดขึ้นก็พอครับ

ปล. ผมมือใหม่ครับ ถ้าผิดพลาดประการใดก็ขออภัยด้วยนะครับ

[Free Style01]

ข้อขุน ยากพอสมควรครับ เพราะรูปแบบการเดินขุนไปทั่วๆกระดานนั้นมีหลากหลายมาก แต่ผมพอจะตั้งสมมติฐานได้ว่า
ถ้าสมมติให้ขุนอยู่ตำแหน่ง (a,b) จะเดินไปในตำแหน่ง (c,d) แล้วถ้าหากว่า (a-c+b-d) เป็นเลขคี่
จะเดินขุนได้มากที่สุด 63 ตาเดิน แต่ถ้าได้เลขคู๋จะได้ 62 ตาเดินครับ
(นับตำเเหน่งจุดที่ขุน start เป็น 0 ตาเดินและนับตำแหน่งที่ขุนก้าวเดินไป 1 ครั้งเป็น 1 ครับ)
ยังไงก็ลองๆหาตัวอย่างค้านเพื่อพิสูจน์ว่าเท็จดูนะครับ..

[armpakorn]

ขอบคุณครับที่ช่วยคิดต่อ จะลองเอาไปต่อยอดดูนะครับ

[kongp]

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

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

ดาวเทียม ทีวี เครื่องใช้ไฟฟ้าต่างๆ ก็ไม่ต่างจากหุ่นยนต์ที่เมื่อคนนำไปใช้ในทางที่ผิด ก็ให้ผลร้ายในทางใดก็ทางหนึ่ง

อนาคตฝรั่งจะปกครองคนไทย ก็เป็นเรื่องที่ช่วยไม่ได้ เพราะตอนนี้ก็เป็นแบบนั้นกลายๆ เนื่องจากเราอ้างเหตุผลไม่สู้ฝรั่ง ในที่สุดละนะ