taramath: Das Median-Kreis-Problem

Beschreibung

Gegeben seien existierende Standorte in der Ebene. Das Median-Kreis-Problem besteht darin, einen Kreis derart zu platzieren, dass die Summe der Abstände zwischen den existierenden Standorten sowie dem Kreisbogen minimiert wird. Dieses Problem kann dank einfacher DC-Zerlegung mit dem geometrischen Branch-and-Bound Verfahren effizient gelöst werden. Eine detaillierte Beschreibung kann dem folgenden Dokument entnommen werden.

mediancircle.pdf

Beispiel

Im folgenden Beispiel lösen wir das Median-Kreis-Problem mit einer zufälligen Anzahl an existierenden Standorten, welche zufällig in der Ebene verteilt werden. Anschließend wird das Ergebnis graphisch dargestellt.

<!DOCTYPE html>
<html>

<head>
  <script src="taramath.js"></script>
</head>

<body>

<div id="plot"></div>

<script>


// -- Zufaellige Eingabedaten erzeugen --

var n = 5+Math.round(Math.random()*50);
var A = new Array(n);
for (var k = 0; k < n; k++) A[k] = [10*Math.random(), 10*Math.random()];



// -- Zielfunktion sowie DC-Zerlegung und Subgradient --

function distance (a1, a2, b1, b2) {
  return Math.sqrt( (a1-b1)*(a1-b1) + (a2-b2)*(a2-b2) );
};

function f (x) {
  var r = 0;
  for (var k = 0; k < A.length; k++) r += Math.abs( distance(A[k][0],A[k][1],x[0],x[1])-x[2] );
  return r;
};

function g (x) {
  var r = 0;
  for (var k = 0; k < A.length; k++) r += Math.max(2*(distance(A[k][0],A[k][1],x[0],x[1])-x[2]), 0);
  return r;
};

function h (x) {
  var r = 0;
  for (var k = 0; k < A.length; k++) r += distance(A[k][0],A[k][1],x[0],x[1])-x[2];
  return r;
};

function d (x) {
  var r = [0,0,0];
  for (var k = 0; k < A.length; k++) {
    var z = distance(A[k][0],A[k][1],x[0],x[1]);
    if (z > x[2]) {
      r[0] += 2*(x[0]-A[k][0])/z;
      r[1] += 2*(x[1]-A[k][1])/z;
      r[2] += -2;
    };
  };
  return r;
};



// -- Initiale Box und Verfahren anwenden --

var X = [[0,10],[0,10],[0,20]];
var S = Gbb.dc(f, g, h, d, X);



// -- Ergebnis darstellen --

if (typeof(S) != "string") {
  Svg.init("plot", 320, 320);
  Svg.resize(-1, 11, -1, 11);
  Svg.clear("#f0f0f0");
  Svg.circle(S[0][0], S[0][1], S[0][2], "none", "#666666");
  for (var k = 0; k < A.length; k++) Svg.disc(A[k][0], A[k][1], 0.12, "#0000ff");
  Svg.draw();
};


</script>

</body>
</html>

Vorschau aktualisieren

Das Median-Kreis-Problem

als Beispiel der Standortplanung