Hi 
In AlgoDat 2 wird gleich am Anfang eine "Distanzmatrix" erwähnt. Ich suche aktuell den besten Weg, wie man so eine Distanzmatrix anlegen kann.
Warum ich das Thema nicht in AlgoDat 2 aufgemacht habe? Hatte ich. Aber dort bekam ich kein Feedback 
. Aber es gibt noch einen anderen Grund: es geht nämlich darum, wie man so etwas ganz grundsätzlich programmiert. Also darum, ob und wie man Informationen zurückgibt oder als Parameter übergibt. Ich hab damit leider ganz grundsätzlich noch Probleme. Ich weiß immer noch nicht, wo ich eine Zahl oder ein Objekt übergeben soll, wo ich etwas zurückgeben soll, oder nicht. Solange mir das Gespühr dafür fehlt, in welchem Stil man das programmiert, mache ich es vielleicht immer falsch.
Ich hätte jetzt zu diesem konkreten Beispiel 3 unterschiedliche Varianten anzubieten. Hier mal die erste Variante.
Ich hätte die Klassen BranchAndBoundNode und BranchAndBound. Also keine edge-Klasse.
Für BranchAndBound:
insert(key0, value0) // fügt einen Knoten hinzu
insert(key1, value1)
edgeDistances(key0, key1, distance01, distance10) // definiert die Distanzen zwischen 2 Knoten
0 entspricht "von" (erster Knoten), 1 entspricht "nach" (zweiter Knoten).
Bei jedem insert wird eine BranchAndBoundNode-Instanz angelegt.
So schaut das bei mir aktuell in PHP aus:
<?php
error_reporting(~0);
class BranchAndBoundNode
{
private $iKey;
private $value;
function __construct($key, $value)
{
$this->setKey($key);
$this->value = $value;
}
private function setKey($key)
{
if
(
!is_int($key) ||
$key < 0
)
throw new Exception('key');
$this->iKey = $key;
}
}
class BranchAndBound
{
private $aNode = []; // Alle Knoten.
private $aDistanceMatrix = []; // Für die Werte einer Distanz-Matrix.
/**
* Einen node hinzufügen.
* @param mixed $key
* @param mixed $value
*/
function insert($key, $value)
{
if(array_key_exists($key, $this->aNode))
throw new Exception('key');
$this->aNode[$key] = new BranchAndBoundNode($key, $value);
}
/**
* Definiert eine asymmetrische Distanz zwischen 2 Knoten.
* @param int $key0 key von node 0
* @param int $key1 key von node 1
* @param number $distance01 Distanz von node 0 auf node 1
* @param number $distance10 Distanz von node 1 auf node 0
*/
function edgeDistances($key0, $key1, $distance01, $distance10)
{
if(!array_key_exists($key0, $this->aNode))
throw new Exception('key0');
if(!array_key_exists($key1, $this->aNode))
throw new Exception('key1');
if($key0 == $key1)
throw new Exception('keys');
self::checkDistance($distance01);
self::checkDistance($distance10);
$this->aDistanceMatrix[$key1]/* nach .. x */[$key0]/* von .. y */ = $distance01; /* von 0 nach 1 */
$this->aDistanceMatrix[$key0][$key1] = $distance10;
}
/**
* Distanz prüfen.
* @param number $distance
* @throws Exception
* not typ number
*/
static private function checkDistance($distance)
{
if(!is_numeric($distance))
throw new Exception('distance');
}
/**
* Distanz-Matrix prüfen.
* @throws Exception
*/
private function checkDistanceMatrix()
{
$iCount = count($this->aNode);
for($iTo = 0; $iTo < $iCount; ++$iTo)
{
for($iFrom = 0; $iFrom < $iCount; ++$iFrom)
{
if($iFrom == $iTo)
{
$this->aDistanceMatrix[$iTo][$iFrom] = INF; // unendlich
}
elseif // Kontrolle, ob das Array-Element existiert:
(
!array_key_exists($iTo, $this->aDistanceMatrix) ||
!array_key_exists($iFrom, $this->aDistanceMatrix[$iTo])
)
throw new Exception('matrix value');
}
if(count($this->aDistanceMatrix[$iTo]) != $iCount)
throw new Exception('matrix count from');
}
if(count($this->aDistanceMatrix) != $iCount)
throw new Exception('matrix count to');
}
// nur zum Testen:
function getMatrix()
{
return $this->aDistanceMatrix;
}
function check()
{
$this->checkDistanceMatrix();
}
}
$oBAB = new BranchAndBound();
// nodes:
$oBAB->insert(0, 0);
$oBAB->insert(1, 1);
$oBAB->insert(2, 2);
$oBAB->insert(3, 3);
$oBAB->insert(4, 4);
$oBAB->insert(5, 5);
// Distanzen:
$oBAB->edgeDistances(1, 0, 6, 5);
$oBAB->edgeDistances(2, 0, 1, 1);
$oBAB->edgeDistances(3, 0, 4, 2);
$oBAB->edgeDistances(4, 0, 1, 1);
$oBAB->edgeDistances(5, 0, 6, 6);
$oBAB->edgeDistances(2, 1, 4, 6);
$oBAB->edgeDistances(3, 1, 3, 3);
$oBAB->edgeDistances(4, 1, 5, 7);
$oBAB->edgeDistances(5, 1, 2, 2);
$oBAB->edgeDistances(3, 2, 3, 1);
$oBAB->edgeDistances(4, 2, 1, 2);
$oBAB->edgeDistances(5, 2, 6, 5);
$oBAB->edgeDistances(4, 3, 2, 5);
$oBAB->edgeDistances(5, 3, 4, 4);
$oBAB->edgeDistances(5, 4, 5, 5);
// nur zum Testen:
var_dump($oBAB->getMatrix());
$oBAB->check();
?>