Künstliche Intelligenz (KI) als Hobby / Artificial Intelligence (AI) as a Hobby

Facebook Group: Künstliche Intelligenz (KI) als Hobby

Berechnung des Manhattan-Abstandes in einer Tabelle mit PHP

Der Manhattan-Abstand in einer Tabelle oder z.B. einem Schachbrett ist die Anzahl der Felder, die man von einem Start-Feld zu einem Ziel-Feld gehen muss, wenn man nicht diagonal, sondern nur "hoch/runter" und "rechts/links" von Feld zu Feld gehen kann.

Lineare Regression Skizze

Schritt 1: Tabelle erzeugen (Zwei-dimensionales Array in PHP)

Jedes Schlüssel-Paar in dem Array stellt eine Koordinate dar. Dabei ist der erste Schlüssel im Array die Y-Koordinate. Die darauf folgenden Schlüssel der zweiten Stufe sind die X-Koordinaten (0-4). Der Wert wird mit 0 = normales Feld, 1 = blockiertes Feld gefüllt.

$map = array();
$map = array(
            array(0, 0, 0, 0, 0),
            array(0, 0, 0, 0, 0),
            array(0, 0, 0, 0, 0),
            array(0, 0, 0, 0, 0),
            array(0, 0, 0, 0, 0)
        );

Das Array kann schnell als übersichtliche Tabelle dargestellt werden, wobei Y von oben nach unten dargestellt wird, sodass X von links nach rechts aber Y von oben nach unten ansteigt:

Koordinate: Y0 / X0Koordinate: Y0 / X1Koordinate: Y0 / X2Koordinate: Y0 / X3Koordinate: Y0 / X4
Koordinate: Y1 / X0Koordinate: Y1 / X1Koordinate: Y1 / X2Koordinate: Y1 / X3Koordinate: Y1 / X4
Koordinate: Y2 / X0Koordinate: Y2 / X1Koordinate: Y2 / X2Koordinate: Y2 / X3Koordinate: Y2 / X4
Koordinate: Y3 / X0Koordinate: Y3 / X1Koordinate: Y3 / X2Koordinate: Y3 / X3Koordinate: Y3 / X4
Koordinate: Y4 / X0Koordinate: Y4 / X1Koordinate: Y4 / X2Koordinate: Y4 / X3Koordinate: Y4 / X4

Schritt 2: Ziel-Feld definieren

Ziel-Feld = Y2/X3

$ZielX = 3;
$ZielY = 2;

Schritt 3: Manhattan-Abstand jedes Feldes zum Ziel-Feld berechnen

Die Anzahl der Felder vom Feld zum Ziel wird mit der Manhattan-Formel berechnet: Manhattan-Abstand = BETRAG (FeldY-ZielX) + BETRAG (FeldX-ZielY).

$manhattan = array();
for($i = 0, $ni = count($map); $i < $ni; $i++){
	for($i2 = 0, $ni = count($map); $i2 < $ni; $i2++){
		$manhattan[$i][$i2] = (abs($i-$ZielX) + abs($i2-$ZielY) );
	};
};

Manhattan-Abstand als Tabelle:

Koordinate: Y0 / X0
Abstand zum Ziel: 5
Koordinate: Y0 / X1
Abstand zum Ziel: 4
Koordinate: Y0 / X2
Abstand zum Ziel: 3
Koordinate: Y0 / X3
Abstand zum Ziel: 4
Koordinate: Y0 / X4
Abstand zum Ziel: 5
Koordinate: Y1 / X0
Abstand zum Ziel: 4
Koordinate: Y1 / X1
Abstand zum Ziel: 3
Koordinate: Y1 / X2
Abstand zum Ziel: 2
Koordinate: Y1 / X3
Abstand zum Ziel: 3
Koordinate: Y1 / X4
Abstand zum Ziel: 4
Koordinate: Y2 / X0
Abstand zum Ziel: 3
Koordinate: Y2 / X1
Abstand zum Ziel: 2
Koordinate: Y2 / X2
Abstand zum Ziel: 1
Koordinate: Y2 / X3
Abstand zum Ziel: 2
Koordinate: Y2 / X4
Abstand zum Ziel: 3
Koordinate: Y3 / X0
Abstand zum Ziel: 2
Koordinate: Y3 / X1
Abstand zum Ziel: 1
Koordinate: Y3 / X2
Abstand zum Ziel: 0
Koordinate: Y3 / X3
Abstand zum Ziel: 1
Koordinate: Y3 / X4
Abstand zum Ziel: 2
Koordinate: Y4 / X0
Abstand zum Ziel: 3
Koordinate: Y4 / X1
Abstand zum Ziel: 2
Koordinate: Y4 / X2
Abstand zum Ziel: 1
Koordinate: Y4 / X3
Abstand zum Ziel: 2
Koordinate: Y4 / X4
Abstand zum Ziel: 3