Największy skarb na płaszczyźnie euklidesowej

 | 
Mapa kartograficzna z przypinanymi do niej czerwonymi pinezkami. Photo by GeoJango Maps on Unsplash.

Czy kiedykolwiek zastanawialiście się, jak za pomocą jednego algorytmu można odnaleźć najcenniejsze punkty w dwuwymiarowej przestrzeni? W dzisiejszym wpisie zgłębimy to zagadnienie mające zastosowanie w dziedzinach, takich jak analiza danych, grafika komputerowa czy algorytmy optymalizacyjne.

Problem

Dany jest zbiór PP zawierający punkty na płaszczyźnie euklidesowej. Celem jest znalezienie kk-elementowego podzbioru QQ o maksymalnej sumie odległości między punktami.

Zdefiniowany problem możemy zapisać za pomocą wzoru:

Q=argmaxQP,Q=k{u,v}Qd(u,v)Q^* = \underset{Q \subseteq P, |Q| = k}{\arg\max} \sum_{\lbrace u,v \rbrace \subseteq Q} d(u, v)

gdzie d(u,v)d(u, v) to odległość między punktami uu i vv.

Rozwiązanie

Opisany powyżej problem zostanie rozwiązany za pomocą programu napisanego w języku JavaScript.

Odległość między dwoma punktami

Pierwszym elementem składowym jest funkcja obliczająca odległość między dwoma punktami na płaszczyźnie euklidesowej. Łatwiej można to zrozumieć, wyobrażając sobie długość odcinka pomiędzy tymi punktami. Formalnie, odległość między punktem P1(x1,y1)P_1(x_1, y_1), a punktem P2(x2,y2)P_2(x_2, y_2) możemy wyrazić wzorem:

d(P1,P2)=(x1x2)2+(y1y2)2d(P_1, P_2) = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}

Funkcja calculateDistance to implementacja powyższego wzoru w języku JavaScript. Przyjmując punkty P1P_1 o współrzędnych (x1,y1)(x_1, y_1) i P2P_2 o współrzędnych (x2,y2)(x_2, y_2), odległość euklidesowa między punktami to pierwiastek kwadratowy z sumy kwadratów różnic współrzędnych.

function calculateDistance(point1, point2) {
  return Math.sqrt((point1[0] - point2[0]) ** 2 + (point1[1] - point2[1]) ** 2);
}

W powyższym kodzie:

  • (point1[0] - point2[0]) - oblicza różnicę współrzędnych xx między punktami.
  • (point1[1] - point2[1]) - oblicza różnicę współrzędnych yy między punktami.
  • ** 2 - podnosi każdy wynik do kwadratu.
  • Math.sqrt(...) - oblicza pierwiastek kwadratowy z sumy kwadratów, co daje nam ostateczną odległość euklidesową między punktami point1 i point2.

Największy podzbiór

Drugą składową będzie funkcja findLargestDistanceSubset. Ma ona na celu znalezienie kk-elementowego podzbioru QQ z danego zbioru punktów PP. Suma odległości między każdą parą punktów ma być jak największa.

function findLargestDistanceSubset(points, k) {
  const n = points.length;
  const Q = [];
  const distances = new Array(n);

  // Obliczanie sum odległości...

  return { distanceSum, selectedIndexes: Q };
}

W powyższym kodzie:

  • n - liczba punktów w zbiorze PP.
  • Q - początkowo pusty zbiór, który będzie przechowywał wybrane punkty.
  • distances - tablica, w której distances[i] jest sumą odległości punktu ii od pozostałych punktów.

Algorytm zwraca obiekt zawierający sumę odległości (distanceSum) oraz indeksy wybranych punktów (Q).

Obliczanie sum odległości

Dla każdego punktu ii w zbiorze PP, obliczamy sumę odległości od wszystkich innych punktów. Wartość ta zostaje zapisana w tablicy distances[i].

distances[i]=j=0n1d(points[i],points[j])\text{distances}[i] = \sum_{j=0}^{n-1} d(\text{points}[i], \text{points}[j])

gdzie d(P1,P2)d(P_1, P_2) to odległość euklidesowa między punktami P1P_1 i P2P_2, co jest obliczane za pomocą funkcji calculateDistance.

for (let i = 0; i < n; i++) {
  let distanceSum = 0;
  for (let j = 0; j < n; j++) {
    distanceSum += calculateDistance(points[i], points[j]);
  }
  distances[i] = distanceSum;
}

Wybieranie punktów do QQ

Algorytm iteracyjnie dodaje do zbioru QQ punkt, który maksymalizuje wzrost sumy odległości w QQ.

while (Q.length < k) {
  let maxIncrease = -1;
  let bestPoint = null;

  // Wzrost sumy odległości...

  if (bestPoint !== null) {
    Q.push(bestPoint);
  } else {
    break;
  }
}

W powyższym kodzie:

  • maxIncrease - zmienna przechowująca dotychczasowy maksymalny wzrost sumy odległości.
  • bestPoint - indeks punktu, który jest najlepszym kandydatem do dodania do QQ.
Wzrost sumy odległości

Dla każdego punktu ii spoza QQ, obliczamy wzrost sumy odległości, jaki byłby uzyskany po dodaniu punktu ii do QQ.

increase=j=0k1(distances[i]d(points[i],points[Q[j]]))\text{increase} = \sum_{j=0}^{k-1} \left( \text{distances}[i] - d(\text{points}[i], \text{points}[Q[j]]) \right)

Jeśli increase jest większe od maxIncrease, wtedy aktualizujemy maxIncrease i bestPoint.

for (let i = 0; i < n; i++) {
  if (!Q.includes(i)) {
    let increase = 0;

    for (let j = 0; j < Q.length; j++) {
      increase += distances[i] - calculateDistance(points[i], points[Q[j]]);
    }

    if (increase > maxIncrease) {
      maxIncrease = increase;
      bestPoint = i;
    }
  }
}

Obliczanie sumy odległości w QQ

Po wybraniu kk punktów, obliczamy sumę odległości między każdą parą punktów w QQ.

distanceSum=i=0k1j=i+1k1d(points[Q[i]],points[Q[j]])\text{distanceSum} = \sum*{i=0}^{k-1} \sum*{j=i+1}^{k-1} d(\text{points}[Q[i]], \text{points}[Q[j]])
let distanceSum = 0;
for (let i = 0; i < Q.length; i++) {
  for (let j = i + 1; j < Q.length; j++) {
    distanceSum += calculateDistance(points[Q[i]], points[Q[j]]);
  }
}

Cała funkcja

function findLargestDistanceSubset(points, k) {
  const n = points.length;
  const Q = [];
  const distances = new Array(n);

  for (let i = 0; i < n; i++) {
    let distanceSum = 0;
    for (let j = 0; j < n; j++) {
      distanceSum += calculateDistance(points[i], points[j]);
    }
    distances[i] = distanceSum;
  }

  while (Q.length < k) {
    let maxIncrease = -1;
    let bestPoint = null;

    for (let i = 0; i < n; i++) {
      if (!Q.includes(i)) {
        let increase = 0;
        for (let j = 0; j < Q.length; j++) {
          increase += distances[i] - calculateDistance(points[i], points[Q[j]]);
        }

        if (increase > maxIncrease) {
          maxIncrease = increase;
          bestPoint = i;
        }
      }
    }

    if (bestPoint !== null) {
      Q.push(bestPoint);
    } else {
      break;
    }
  }

  let distanceSum = 0;
  for (let i = 0; i < Q.length; i++) {
    for (let j = i + 1; j < Q.length; j++) {
      distanceSum += calculateDistance(points[Q[i]], points[Q[j]]);
    }
  }

  return { distanceSum, selectedIndexes: Q };
}

Uruchomienie

Do uruchomienia potrzebujemy funkcji main, która pełni rolę wejścia do programu.

function main() {
  const args = process.argv.slice(2);
  let options = {};

  for (let i = 0; i < args.length; i++) {
    if (args[i] === '-f' && i + 1 < args.length) {
      options.file = args[i + 1];
      i++;
    } else if (args[i] === '-k' && i + 1 < args.length) {
      options.k = parseInt(args[i + 1]);
      i++;
    }
  }

  if (!options.file || !options.k) {
    console.log('Usage: node prog.js -f <file> -k <k>');
    return;
  }

  const data = fs.readFileSync(options.file, 'utf-8');
  const points = data
    .trim()
    .split('\n')
    .map(line => {
      const [x, y] = line.split(',').map(Number);
      return [x, y];
    });

  if (points.length < options.k) {
    console.log('The value of k is larger than the number of points.');
    return;
  }

  const result = findLargestDistanceSubset(points, options.k);

  console.log(result.distanceSum.toFixed(2));
  console.log(result.selectedIndexes.join(', '));
}

Jest odpowiedzialna za:

  • pobranie argumentów z linii komend,
  • przetworzenie argumentów i ustawienie opcji,
  • obsługę błędów,
  • odczytanie danych z pliku,
  • przetworzenie danych,
  • wywołanie algorytmu,
  • wyświetlanie wyników.

Cały program można znaleźć tu, a przykładowe punkty znajdują się tu.

Aby skorzystać z programu, należy go uruchomić z odpowiednimi parametrami, na przykład:

node prog.js -f points.txt -k 4
  • node prog.js - uruchamia program napisany w języku JavaScript. Wymagany NodeJS.
  • -f points.txt - określa plik, w którym znajdują się dane z punktami.
  • -k 4 - określa rozmiar poszukiwanego podzbioru punktów.

Wynik

Program wypisuje sumę odległości między punktami w wybranym podzbiorze oraz indeksy tych punktów. Przykład dla danych testowych z points.txt:

59.82
0, 91, 9, 99

Oznacza to, że punkty QQ o współrzędnych (0,0)(0, 0), (9,1)(9, 1), (0,9)(0, 9), i (9,9)(9, 9) tworzą podzbiór, dla którego suma odległości między punktami jest największa spośród wszystkich możliwych 4-elementowych podzbiorów. Wartość tej sumy wynosi 59.8259.82.

Złożoność czasowa algorytmu wynosi O(n2+kn)O(n^2 + k \cdot n), gdzie nn to liczba punktów w zbiorze PP. Algorytm iteracyjnie dodaje punkty do zbioru, wybierając te, które maksymalizują sumę odległości.


Profile picture

Dawid Ryłko
Digital Persona | GitHub | Twitter | Linkedin

Copyright © 2024 Dawid Ryłko