Breadth First - Breitensuche in PHP
Ich habe heute eine Breitensuche in PHP implementiert. Dazu habe ich eine abstrakte Klasse mit der Breitensuche implementiert. Der Problemteil kann dann in der davon abgeleiteten Klasse implementiert werden.
In der Problemklasse kann einfach die Methode generateDescandants überschrieben werden. In diesem Fall erstellen wir eine Art Inhaltsverzeichnissbaum, der jedes Kapitel mit drei Unterkapitel versieht. Sicher nicht gerade die intelligenteste Anwendung, aber eine nette kleine Demonstration.
Hier geht es nun noch zum Suchcode weiter.
In der Problemklasse kann einfach die Methode generateDescandants überschrieben werden. In diesem Fall erstellen wir eine Art Inhaltsverzeichnissbaum, der jedes Kapitel mit drei Unterkapitel versieht. Sicher nicht gerade die intelligenteste Anwendung, aber eine nette kleine Demonstration.
class SimpleSearch extends AbstractBreadthFirst {
function generateDescendants($parent){
$ret = array();
$ret[] = $parent.".1";
$ret[] = $parent.".2";
$ret[] = $parent.".3";
return $ret;
}
}
Das ganze wird dann relativ einfach verwendet. Nämlich so:$s = new SimpleSearch();So wird zuerst ein Suchobjekt instanziert und dann die Suche gestartet. Übergeben wird der Startzustand, der Zielzustand und die maximale Suchtiefe. Wenn ein Status gefunden wird, wird true zurückgegeben. Mit getPath kann in diesem Fall ein Array mit dem Lösungspfad zurückgegeben werden. Mit getCount kann die Anzahl durchsuchter Knoten zurückgegeben werden.
if( $s->runBreadthWithDepth("1", "1.2.3.1.2.2.3",6) ){
print_r($s->getPath());
}
print("\nCount: ".$s->getCount()."\n\n");
Hier geht es nun noch zum Suchcode weiter.