menghitung jarak jaringan terpendek

Algoritmenya sangat sederhana jika inputnya berupa bilangan bulat, cukup cari nilai absolut antara koordinat x dan y lalu jumlahkan keduanya. Ini disebut jarak Manhattan.

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

Dengan ganda, hampir persis sama, kecuali satu situasi. Berikut beberapa kemungkinannya:

1. Kedua titik tersebut memiliki koordinat bilangan bulat
2. Satu titik memiliki koordinat bilangan bulat, dan titik lainnya hanya memiliki satu koordinat bilangan bulat
3. Kedua titik tersebut hanya mempunyai satu koordinat bilangan bulat, namun terletak pada sumbu yang berbeda.
4. Kedua titik tersebut hanya mempunyai satu koordinat bilangan bulat dan berada pada sumbu yang sama.

Kemungkinan 1-3 semuanya berfungsi dengan baik menggunakan algoritma yang sama seperti untuk mencari jarak dengan bilangan bulat, kecuali #4 memiliki kemungkinan sumbu yang sama berada pada blok yang sama.

Misalnya, jika inputnya adalah: {x: 0.5, y: 2} dan {x: 0.5, y: 3} Anda harus melakukan perjalanan secara horizontal, vertikal, dan kemudian mundur lagi secara horizontal untuk mencapai tujuan. Ini berbeda dengan input {x: 0.5, y: 2} dan {x: 1.5, y: 3} karena tidak perlu melakukan perjalanan mundur pada sumbu yang sama.

Jadi Anda dapat menggunakan algoritma normal dalam semua kasus kecuali ketika kedua X atau Y memiliki nilai floating-point dan memiliki nilai floor-ed yang sama.

Kode Anda akan terlihat seperti ini.

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;
}

Hal ini dapat disederhanakan lebih lanjut dengan menggunakan fungsi pembantu untuk menghitung setiap sumbu secara terpisah.

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);
    }
}

Saya menggunakan trik dengan 2 - dist disini karena sama saja dengan menghitung

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

yang sama dengan

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

Jika ini adalah kotak persegi, Anda dapat mempertimbangkan koordinat x dan y secara terpisah; jarak minimum adalah jumlah jarak minimum pada dua arah.

Di arah p (baik x atau y), Anda harus berpindah dari p1 ke p2. Dari p1, Anda dapat berpindah ke floor(p1) atau ceil(p1) untuk sampai ke jalan (yang mungkin sama, jika p1 adalah bilangan bulat); dari sana, Anda dapat berpindah ke floor(p2) atau ceil(p2), jalan di mana p2 berada; dari sana, Anda dapat pindah ke p2.

Jadi, jarak minimum pada arah p adalah

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)

Jadi Anda tinggal menghitungnya secara mandiri untuk arah x dan y, lalu menambahkannya.

Untuk mengilustrasikannya (menyingkat floor dan ceil masing-masing menjadi f dan p):

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

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

Rute terpendek ditunjukkan di sini dengan >. .s berada pada rute terpendek, tetapi karena bagian rute tersebut ortogonal terhadap arah p, maka "tidak dihitung" terhadap jarak minimum ke arah tersebut.

Rute minimum yang ditampilkan di sini, p1 -> c(p1) -> f(p2) -> p2, adalah Kasus 1 di atas.

Seharusnya tidak sulit untuk memvisualisasikan pertukaran p1 dan p2, dalam hal ini rute minimumnya adalah dari p1 ->f(p1) -> c(p2) -> p2 (Kasus 2).

Kasus pN == f(pN) == c(pN) tidak jauh berbeda; maka, bagian dari ekspresi abs(pN - f(pN)) atau abs(pN - c(pN)) hanyalah nol.

Kasus yang sedikit berbeda adalah ketika 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

Dalam hal ini, rute minimum dapat berupa p1 -> f(p1) -> f(p2) -> p2 atau p1 -> c(p1) -> c(p2) -> p2 (masing-masing merupakan Kasus 3 dan 4).

Seperti disebutkan oleh 4castle, masalahnya sepele jika hanya bilangan bulat yang dipertimbangkan sebagai input. Dalam hal ini, kamu tidak perlu "mundur" setelah "bergerak maju" karena kamu akan selalu mencapai tujuan dalam satu gerakan.

Namun karena, paling banyak satu nomor floating point perlu dipertimbangkan untuk setiap keberangkatan/tujuan, kita perlu mempertimbangkan 3 kasus, (peringatan: penjelasan panjang). Di bawah ini adalah implementasi python2 beserta penjelasannya.

1. koordinat x keberangkatan dan tujuan adalah sama dan bukan bilangan floating point. Dalam hal ini, jarak terpendek hanyalah selisih mutlak antara koordinat y. Logika yang sama berlaku sebaliknya.

   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. Jika salah satu koordinat keberangkatan adalah titik mengambang, maka:

   • If x co-ordinate is floating point, we can move backwards(round down) or move front(round up).
   • Jika koordinat y adalah titik mengambang, kita dapat bergerak ke bawah (membulatkan ke bawah) atau ke atas (membulatkan ke atas).
   • Logika di atas harus bekerja bahkan ketika tidak ada koordinat titik mengambang karena kita bergerak ke salah satu arah sebanyak nol satuan.
   • Setelah kita menghitungnya, kita tinggal memilih minimum di antara yang seperti di bawah ini,

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) untuk perhitungan di bawah ini.

3. Saat menghitung round_up kita perlu menghitung 3 jarak:

   • 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
   • perbedaan titik_mengambang: perbedaan antara koordinat titik keberangkatan bukan titik mengambang dan koordinat tujuan yang bersangkutan ( perhatikan bahwa ini mungkin titik mengambang atau bukan titik mengambang abs(3-1) = 2 in the above example
   • Selisih antara nilai floating point keberangkatan pada koordinat tujuan 0.9 in the above case dan nilai floating point keberangkatan yang baru setelah dibulatkan ke atas, 0.4 + 0.6(this is the round_up distance) = 1.0, yakni abs(0.9 - 1.0) = 0.1
   • Menambahkan ketiga hal di atas kita mendapatkan 0.6 + 2 + .1 = 2.7 yang merupakan jarak terpendek.

   • Perhitungan yang sesuai perlu dilakukan untuk pembulatan ke bawah. Dan kami memilih nilai minimum di antara keduanya. Kode untuk round_up dan round_down adalah seperti di bawah ini,

     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. Fungsi pembulatan ke atas dan ke bawah adalah seperti di bawah ini,

   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. Terakhir fungsi utama yang memanggil metode di atas,

   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))