การคำนวณระยะทางกริดที่สั้นที่สุด

อัลกอริทึมนั้นง่ายมากหากอินพุตเป็นจำนวนเต็ม เพียงค้นหาค่าสัมบูรณ์ระหว่างพิกัด x และ y แล้วบวกเข้าด้วยกัน ซึ่งเรียกว่าระยะทางแมนฮัตตัน

int distance = Math.abs(x1 - x2) + Math.abs(y1 - y2);

เมื่อใช้คู่ก็เกือบจะเหมือนกันทุกประการ ยกเว้นในสถานการณ์เดียว นี่คือความเป็นไปได้บางประการ:

1. ทั้งสองจุดมีพิกัดจำนวนเต็ม
2. จุดหนึ่งมีพิกัดจำนวนเต็ม และอีกจุดมีพิกัดจำนวนเต็มเพียงจุดเดียวเท่านั้น
3. ทั้งสองจุดมีพิกัดจำนวนเต็มเพียงจุดเดียว แต่อยู่บนแกนต่างกัน
4. จุดทั้งสองมีพิกัดจำนวนเต็มเพียงจุดเดียวและอยู่บนแกนเดียวกัน

ความเป็นไปได้ที่ 1-3 ทั้งหมดทำงานได้ดีโดยใช้อัลกอริธึมเดียวกันกับการค้นหาระยะทางด้วยจำนวนเต็ม ยกเว้น #4 มีความเป็นไปได้ที่แกนร่วมจะอยู่บนบล็อกเดียวกัน

ตัวอย่างเช่น หากอินพุตเป็น: {x: 0.5, y: 2} และ {x: 0.5, y: 3} คุณจะต้องเดินทางในแนวนอน แนวตั้ง และถอยหลังในแนวนอนอีกครั้งเพื่อไปยังจุดหมายปลายทาง สิ่งนี้แตกต่างจากอินพุต {x: 0.5, y: 2} และ {x: 1.5, y: 3} เนื่องจากไม่จำเป็นต้องเคลื่อนที่ถอยหลังบนแกนเดียวกัน

ดังนั้น คุณสามารถใช้อัลกอริธึมปกติได้ในทุกกรณี ยกเว้น ในกรณีที่ Xs หรือ Y ทั้งคู่มีค่าจุดลอยตัวและมีค่า floor-ed เท่ากัน

รหัสของคุณควรมีลักษณะเช่นนี้

import static java.lang.Math.*;

public static double perfectCity(double x1, double y1, double x2, double y2) {
    double xDist = abs(x1 - x2);
    double yDist = abs(y1 - y2);
    if (floor(x1) != x1 && floor(x2) != x2 &&        // both Xs are doubles
        floor(x1) == floor(x2) &&                    // on the same block
        y1 != y2) {                                  // not on the same street
        xDist = min(abs(x1 - floor(x1) + x2 - floor(x2)),
                    abs(x1 - ceil(x1)  + x2 - ceil(x2)));
    } else if (floor(y1) != y1 && floor(y2) != y2 && // both Ys are doubles
               floor(y1) == floor(y2) &&             // on the same block
               x1 != x2) {                           // not on the same street
        yDist = min(abs(y1 - floor(y1) + y2 - floor(y2)),
                    abs(y1 - ceil(y1)  + y2 - ceil(y2)));
    }
    return xDist + yDist;
}

ซึ่งสามารถทำให้ง่ายขึ้นได้อีกมากโดยใช้ฟังก์ชันตัวช่วยในการคำนวณแต่ละแกนแยกกัน

public static double perfectCity(double x1, double y1, double x2, double y2) {
    return travelOnAxis(x1, x2, y1 == y2) + travelOnAxis(y1, y2, x1 == x2);
}

private static double travelOnAxis(double from, double to, boolean travelIsStraight) {
    if (Math.floor(from) == Math.floor(to) && !travelIsStraight) {
        double dist = Math.abs((from % 1) + (to % 1));
        return Math.min(dist, 2 - dist);
    } else {
        return Math.abs(from - to);
    }
}

ฉันใช้เคล็ดลับกับ 2 - dist ที่นี่เพราะมันเหมือนกับการคำนวณ

Math.abs((1 - (from % 1)) + (1 - (to % 1)))

ซึ่งก็เหมือนกับ

Math.abs(from - Math.ceil(from) + to - Math.ceil(to))

หากเป็นตารางสี่เหลี่ยม คุณสามารถพิจารณาพิกัด x และ y แยกกัน ระยะทางต่ำสุดคือผลรวมของระยะทางขั้นต่ำในสองทิศทาง

ในทิศทาง p (อาจเป็น x หรือ y) คุณต้องย้ายจาก p1 ไปยัง p2 จาก p1 คุณสามารถย้ายไปที่ floor(p1) หรือ ceil(p1) เพื่อไปยังถนน (ซึ่งอาจมีค่าเท่ากัน หาก p1 เป็นจำนวนเต็ม) จากที่นั่น คุณสามารถย้ายไปที่ floor(p2) หรือ ceil(p2) ซึ่งเป็นถนนที่ p2 ตั้งอยู่ จากนั้น คุณสามารถย้ายไปที่ p2

ดังนั้น ระยะทางต่ำสุดในทิศทาง p คือ

min(abs(p1 - ceil(p1) ) + abs(ceil(p1)  - floor(p2)) + abs(floor(p2) - p2),  # (1)
    abs(p1 - floor(p1)) + abs(floor(p1) - ceil(p2) ) + abs(ceil(p2)  - p2),  # (2)
    abs(p1 - floor(p1)) + abs(floor(p1) - floor(p2)) + abs(floor(p2) - p2),  # (3)
    abs(p1 - ceil(p1) ) + abs(ceil(p1)  - ceil(p2) ) + abs(ceil(p2)  - p2))  # (4)

ดังนั้นคุณจึงสามารถคำนวณค่านี้แยกกันสำหรับทิศทาง x และ y แล้วบวกได้

เพื่ออธิบายสิ่งนี้ (ย่อ floor และ ceil เป็น f และ p ตามลำดับ):

f(p1) p1  c(p1)
  +---O>>>>+>>>>>>>>+
                    .
                    .
                    +>>>O----+
                  f(p2) p2  c(p2)

--------------------------------> p axis

เส้นทางที่สั้นที่สุดแสดงไว้ที่นี่ด้วย > .s อยู่บนเส้นทางที่สั้นที่สุด แต่เนื่องจากส่วนหนึ่งของเส้นทางนั้นตั้งฉากกับทิศทาง p จึง "ไม่นับ" ระยะทางต่ำสุดในทิศทางนั้น

เส้นทางขั้นต่ำที่แสดงที่นี่ p1 -> c(p1) -> f(p2) -> p2 คือกรณีที่ 1 ด้านบน

ไม่ควรยากที่จะเห็นภาพการสลับ p1 และ p2 ซึ่งในกรณีนี้เส้นทางขั้นต่ำคือไปจาก p1 ->f(p1) -> c(p2) -> p2 (กรณีที่ 2)

กรณีของ pN == f(pN) == c(pN) ไม่ได้แตกต่างกันมากนัก ดังนั้นส่วนของนิพจน์ abs(pN - f(pN)) หรือ abs(pN - c(pN)) จะเป็นศูนย์เท่านั้น

กรณีที่แตกต่างกันเล็กน้อยคือที่ f(p1) == f(p2):

f(p1) p1  c(p1)          f(p1) p1  c(p1)
  +---O>>>>+               +<<<O----+
           .               .
           .               .
  +-----O<<+               +>>>>>O--+
 f(p2) p2  c(p2)          f(p2) p2  c(p2)

--------------------------------> p axis

ในกรณีนี้ เส้นทางขั้นต่ำอาจเป็น p1 -> f(p1) -> f(p2) -> p2 หรือ p1 -> c(p1) -> c(p2) -> p2 (ซึ่งก็คือกรณีที่ 3 และ 4 ตามลำดับ)

ดังที่ 4castle กล่าวไว้ ปัญหานั้นไม่สำคัญหากพิจารณาเฉพาะจำนวนเต็มสำหรับอินพุต คุณจะไม่ต้อง "ถอยกลับ" หลังจากที่ "ก้าวไปข้างหน้า" ในกรณีนั้นแล้ว เนื่องจากคุณจะไปถึงจุดหมายปลายทางของคุณในคราวเดียว

แต่เนื่องจาก สูงสุด จำนวนจุดลอยตัวหนึ่งต้องได้รับการพิจารณาสำหรับแต่ละต้นทาง/ปลายทาง เราจึงต้องพิจารณา 3 กรณี (คำเตือน: คำอธิบายยาว) ด้านล่างนี้คือการใช้งาน python2 พร้อมคำอธิบาย

1. พิกัด x ของทั้งต้นทางและปลายทางเหมือนกันและเป็นไม่ใช่ตัวเลขทศนิยม ในกรณีนี้ ระยะทางที่สั้นที่สุดเป็นเพียงผลต่างสัมบูรณ์ระหว่างพิกัด y ตรรกะเดียวกันนี้ใช้ในทางกลับกัน

   import math
   class Location():
       def __init__(self, cord):
           self.x = cord[0]
           self.y = cord[1]
   
   def perfectCity(departure, destination):
       l1 = Location(departure)
       l2 = Location(destination)
   
       if l1.x == l2.x and float(l1.x).is_integer() and float(l2.x).is_integer():
           return abs(l1.y-l2.y)
       if l1.y == l2.y and float(l1.y).is_integer() and float(l2.y).is_integer():
           return abs(l1.x-l2.x)
   

2. เมื่อพิกัดตัวใดตัวหนึ่งใน ขาออก เป็นจุดลอยตัว ดังนั้น:

   • If x co-ordinate is floating point, we can move backwards(round down) or move front(round up).
   • หากพิกัด y เป็นจุดลอยตัว เราสามารถเลื่อนลง (ปัดลง) หรือเลื่อนขึ้น (ปัดขึ้น)
   • ตรรกะข้างต้นควรใช้งานได้แม้ว่าจะไม่มีพิกัดจุดลอยตัว เนื่องจากเราเคลื่อนที่ไปในทิศทางใดทิศทางหนึ่งด้วยหน่วย ศูนย์
   • เมื่อเราคำนวณสิ่งเหล่านี้แล้ว เราก็เลือกค่าขั้นต่ำจากค่าด้านล่าง

return min(calc_round_up_dist(l1, l2), cal_round_down_dist(l1, l2))

Lets take an example of (0.4, 1) and (0.9, 3) สำหรับการคำนวณด้านล่าง

3. ขณะคำนวณ Round_up เราจำเป็นต้องคำนวณ 3 ระยะทาง:

   • round_up_distance: difference between the rounded up value of the floating point co-ordinate and the original floating point co-ordinate. We return zero if there is no floating point co-ordinate. 1 - 0.4 = 0.6 in the above example
   • ความแตกต่าง non_floating_point: ความแตกต่างระหว่างพิกัดจุดออกเดินทางที่ไม่ใช่จุดลอยตัวและพิกัดที่สอดคล้องกันของปลายทาง ( โปรดทราบว่านี่อาจเป็นจุดลอยตัวหรือไม่ใช่จุดลอยตัว abs(3-1) = 2 in the above example
   • ความแตกต่างระหว่างจุดลอยตัวของการออกเดินทางในพิกัดปลายทาง 0.9 in the above case และค่าใหม่ของจุดลอยตัวของการออกเดินทางหลังปัดเศษขึ้น 0.4 + 0.6(this is the round_up distance) = 1.0 เช่น abs(0.9 - 1.0) = 0.1
   • เมื่อบวกทั้ง 3 รายการข้างต้น เราจะได้ 0.6 + 2 + .1 = 2.7 ซึ่งเป็นระยะทางที่สั้นที่สุด

   • จำเป็นต้องคำนวณที่สอดคล้องกันเพื่อปัดเศษลง และเราเลือกค่าต่ำสุดจากทั้งสองค่า รหัสสำหรับ Round_up และ Round_down มีดังต่อไปนี้

     import math
     class Location():
         def __init__(self, cord):
             self.x = cord[0]
             self.y = cord[1]
     
         def floating_point_round_up(self):
             if not float(self.x).is_integer():
                 return math.ceil(self.x) - self.x
             if not float(self.y).is_integer():
                 return math.ceil(self.y) - self.y
             return 0
     
         def floating_point_round_down(self):
             if not float(self.x).is_integer():
                 return self.x - math.floor(self.x)
             if not float(self.y).is_integer():
                 return self.y - math.floor(self.y)
             return 0
     
         def non_floating_point_diff(self, obj):
             if not float(self.x).is_integer():
                 return abs(self.y - obj.y)
             if not float(self.y).is_integer():
                 return abs(self.x - obj.x)
             return abs(self.y - obj.y)
     
         def floating_point_counterpart(self, obj):
             if not float(self.x).is_integer():
                 return obj.x
             if not float(self.y).is_integer():
                 return obj.y
             return obj.x
     
         def floating_point(self):
             if not float(self.x).is_integer():
                 return self.x
             if not float(self.y).is_integer():
                 return self.y
             return self.x
     

4. ฟังก์ชั่นการปัดเศษขึ้นและลงมีดังนี้

   def calc_round_up_dist(l1, l2):
       dist = l1.floating_point_round_up()
       diff = l1.non_floating_point_diff(l2)
       floating_point_counterpart = l1.floating_point_counterpart(l2)
       new_val = dist + l1.floating_point()
       return dist + diff + abs(new_val - floating_point_counterpart)
   
   def cal_round_down_dist(l1, l2):
       dist = l1.floating_point_round_down()
       diff = l1.non_floating_point_diff(l2)
       floating_point_counterpart = l1.floating_point_counterpart(l2)
       new_val = l1.floating_point() - dist
       return dist + diff + abs(floating_point_counterpart - new_val)
   

5. ในที่สุดฟังก์ชันหลักที่เรียกใช้เมธอดข้างต้น

   def perfectCity(departure, destination):
       l1 = Location(departure)
       l2 = Location(destination)
   
       if l1.x == l2.x and float(l1.x).is_integer() and float(l2.x).is_integer():
           return abs(l1.y-l2.y)
       if l1.y == l2.y and float(l1.y).is_integer() and float(l2.y).is_integer():
           return abs(l1.x-l2.x)
   
       return min(calc_round_up_dist(l1, l2), cal_round_down_dist(l1, l2))