การเดินทางขั้นต่ำจากจุดหนึ่งไปยังอีกจุดหนึ่งโดยมีขั้นตอนที่เพิ่มขึ้น

Question

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

ตัวอย่างเช่นฉันต้องไปที่ (1,1) จุดและขั้นตอนคือ:

• ไปที่ (1,0) ขั้นตอน 1 หน่วย
• ไปที่ (1, -2) ขั้นละ 2 หน่วย
• สุดท้ายไปที่ (1,1) ขั้นตอน 3 หน่วย

และสำหรับตัวอย่างนี้คำตอบคือฉันต้องการ 3 ขั้นตอนโดยมีระยะทาง 6 หน่วย

เห็นได้ชัดว่ามีหลายวิธีในการไปยังจุดหนึ่งจากจุดศูนย์กลาง แต่ปัญหาต้องการน้อยที่สุด

มีสูตรหรืออัลกอริทึมในการค้นหาจำนวนก้าวขั้นต่ำและระยะทางของวิธีนี้หรือไม่?

ถ้าคุณพบหนึ่งในนั้น (จำนวนก้าวหรือระยะทาง) อีกอันหาได้ง่ายเพราะระยะทางคือผลรวมของ N (จำนวนก้าว) จำนวนธรรมชาติแรก

ขอขอบคุณที่อ่านสิ่งนี้และสำหรับคำตอบและข้อเสนอแนะของคุณ

Answer 1

คำถามที่น่าสนใจ เป็นที่น่าแปลกใจที่คำตอบขึ้นอยู่กับ$|x|+|y|$. ตัวอย่างเช่นต้องใช้จำนวนขั้นตอนเดียวกันในการเข้าถึง$(1,1)$ หรือ $(0,2)$.

---

ขั้นต่ำสุดคือจำนวนเต็มที่ไม่เป็นลบน้อยที่สุด $n$ ดังนั้น $n(n+1)/2-(|x|+|y|)$ มีค่าสม่ำเสมอและไม่เป็นค่าลบ

นี่คือไฟล์ $O(1)$อัลกอริทึม -time ที่ส่งคืนค่าที่อธิบายไว้ข้างต้นโดยที่least_nกล่าวคือ$\left\lceil\frac{-1+\sqrt{8(|x|+|y|)+1}}2\right\rceil$เป็นจำนวนเต็มที่ไม่เป็นค่าลบน้อยที่สุด $n$ ดังนั้น $n(n+1)/2-(|x|+|y|)\ge0$.

def minimum_steps(x,y):
    distance_to_origin := absolute_value(x) + absolute_value(y)
    least_n := ceiling((-1 + square_root(8 * distance_to_origin + 1)) / 2)
    gap := n * (n + 1) / 2 - distance_to_origin
    # 0 <= gap <= n - 1

    if gap is even:
        return least_n
    else if n is even:
        return least_n + 1
    else:
        return least_n + 2

ระบุจำนวนก้าว $s$ระยะทางที่เดินทางคือ $1+2+\cdots+s=s(s+1)/2$.

---

ความถูกต้องของสูตรและอัลกอริทึมข้างต้นมาจากการกำหนดลักษณะดังต่อไปนี้

โจทย์. จำนวนก้าวขั้นต่ำจาก$(0,0)$ ถึง $(x,y)$ เป็นจำนวนเต็มที่ไม่เป็นลบน้อยที่สุด $n$ ดังนั้น $n(n+1)/2-(|x|+|y|)$ ไม่เป็นค่าลบและแม้กระทั่ง

หลักฐาน . หากเราสามารถไปที่$(x,y)$ ใน $n$ ขั้นตอนผลรวมของตัวเลขระหว่าง 1 ถึง $n$ หรือการปฏิเสธของพวกเขาจะต้องเป็น $x$ และผลรวมของตัวเลขที่เหลือหรือการปฏิเสธจะต้องเป็น $y$กล่าวคือ $$\pm1\pm2\pm\cdots\pm n = |x| + |y|$$ สำหรับทางเลือกทั้งหมด $\pm$ของ นั่นหมายความว่า,$$1+2+\cdots+ n - (|x| + |y|)$$ ไม่เป็นค่าลบและแม้กระทั่ง

ตอนนี้ก็เพียงพอแล้วที่จะพิสูจน์ว่า $(x,y)$ สามารถเข้าถึงได้ใน $n$ ขั้นตอนถ้า $n(n+1)/2-(|x|+|y|)$ไม่เป็นค่าลบและแม้กระทั่ง ให้เราพิสูจน์โดยการเหนี่ยวนำ$n$.

กรณีฐาน $n=0$ หรือ $1$ หมายถึง $(x,y)=(0,0), (0,1), (1,0)$. กรณีเหล่านี้เป็นกรณีที่ต้องตรวจสอบทันที

สมมติว่าเป็นสมมติฐานการเหนี่ยวนำมันถูกต้องสำหรับขนาดเล็กกว่า $n$ของ ตอนนี้พิจารณากรณีของ$n\ge2$ ด้วย $n(n+1)/2-(|x|+|y|)$ไม่เป็นลบและแม้กระทั่ง เราสามารถสันนิษฐานได้$x$ และ $y$ไม่เป็นลบ มิฉะนั้นตัวอย่างเช่นถ้า$x$ เป็นลบเราสามารถเปลี่ยนแปลงได้ $x$ เป็นค่าสัมบูรณ์และกลับทิศทางของขั้นตอนทั้งหมดที่ขนานกัน $X$-แกน.

มีสามกรณี

• $x \ge n$. ปล่อย$x'= x-n$. แล้ว$$(n-1)n/2-(|x'|+|y|)=n(n+1)/2-(|x|+|y|)$$ไม่เป็นค่าลบและแม้กระทั่ง โดยสมมติฐานการเหนี่ยวนำเราสามารถไปที่$(x',y)$ ใน $n-1$ขั้นตอน ในการเข้าถึง$(x,y)$ ใน $n$ ขั้นตอนเราดำเนินการต่อ $n$ หน่วยในทิศทาง X
• $y\ge n$. นี่คือสมมาตรกับกรณีด้านบน
• $0\le x\lt n$ และ $0\le y\lt n$. มีสองกรณีย่อย
  • $x\ge 2$ และ $y\ge 2$. ปล่อย$x'=(n-1)-x$ และ $y'=n-y$. แล้ว$|x'|\le n-3$ และ $|y'|\le n-2$. $$(n-2)(n-1)/2-(|x'|+|y'|)\ge(n-3)(n-4)/2\ge0.$$ ความเท่าเทียมกันของ $(n-1)(n-1)/2-(|x'|+|y'|)$ เหมือนกับ $n(n+1)/2-(|x|+|y|)$กล่าวคือแม้ โดยสมมติฐานการเหนี่ยวนำเราสามารถไปที่$(x',y')$ ใน $n-2$ขั้นตอน ย้อนกลับทุกขั้นตอนเราสามารถไปที่$(-x', -y')$ ใน $n-2$ขั้นตอนเช่นกัน ในการเข้าถึง$(x,y)$ ใน $n$ ขั้นตอนเราสามารถดำเนินการต่อได้อีกสองขั้นตอน $n$ หน่วยใน X-direction และ $n+1$ หน่วยในทิศทาง Y
  • หนึ่งใน $x$ และ $y$ คือ $0$ หรือ $1$. ปล่อย$g(k)=k(k+1)/2-(|x|+|y|)$. จำนวนเต็มไม่ติดลบที่เล็กที่สุดเช่นนั้น$g(k)\ge0$ คือ $m=\left\lceil\frac{-1+\sqrt{8(|x|+|y|)+1}}2\right\rceil$. เนื่องจากทั้งสอง$x$ และ $y$ คือ $\lt n$ และหนึ่งในนั้นคือ $0$ หรือ $1$, $$m\le \frac{1+\sqrt{8n+1}}2.$$ เมื่อไหร่ $g(m)$ เป็นคู่ $n=m$ตามความหมาย เมื่อไหร่$g$ เป็นเรื่องแปลกเนื่องจากอย่างใดอย่างหนึ่ง $g(m+1)=g(m)+(m+1)$ หรือ $g(m+2)=g(m)+(m+1)+(m+2)$ ต้องเป็นคู่อย่างใดอย่างหนึ่ง $m+1$ หรือ $m+2$ ต้องเป็น $n$. ดังนั้นไม่ว่า$g(m)$ เป็นคู่หรือคี่เรามี $$n\le m+2.$$ เรามีความไม่เท่าเทียมกันสองอย่างข้างต้น $$n\le \frac{5+\sqrt{8n+1}}2,$$ ซึ่งหมายความว่า $n\le 6$. เนื่องจากทิศทาง X และทิศทาง Y เป็นแบบสมมาตรให้เราสมมติ$y=0,1$. ตั้งแต่$x\lt n$, $x\lt 6$. ดังนั้นจึงเพียงพอที่จะตรวจสอบกรณีที่$(x,y)$ $\in $ $\{(0,0),(0,1),$ $(1,0),(1,1),$ $(2,0), (2,1),$ $(3,0), (3,1),$ $(4,0), (4,1),$ $(5,0), (5,1)\}.$ ง่ายต่อการตรวจสอบแต่ละรายการ

$\ \checkmark$