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.
Hier folgt nun noch der Suchcode. Das ganze wurde möglichst einfach gehalten, damit die Performance möglichst hoh bleibt. Desshalb wurde auch darauf verzichtet einen Knoten als Klasse zu implementieren oder den Vergleich verschiedener Knoten generischer zu lösen.
abstract class AbstractBreadthFirst{
const PARENT = 0;
const ME = 1;
const DEPTH = 2;
private $open = array();
private $close;
private $closed = array();
private $goal;
private $last;
private $count = 0;
private $maxDepth = -1;
public function runBreadth($start, $goal){
$this->open[] = array(NULL, $start,0);
$this->goal = $goal;
return $this->breadthFirst();
}
public function runBreadthWithDepth($start, $goal, $maxDepth){
$this->open[] = array(NULL, $start,0);
$this->goal = $goal;
$this->maxDepth = $maxDepth;
return $this->breadthFirst();
}
private function breadthFirst(){
$act = array_shift($this->open);
if($act == NULL) {
echo "\n***KEIN TREFFER***\n\n";
return false;
} else {
++$this->count;
if($act[self::ME] == $this->goal) {
echo "\n***TREFFER (".$act[self::ME].")***\n\n";
$this->last = $act;
return true;
} else {
$this->closed[] = $act;
$this->open =
array_merge($this->open, $this->_generateDescendants($act));
return $this->breadthFirst();
}
}
}
public function getPath(){
return $this->_getPath($this->last);
}
private function _getPath($node){
if($node[self::PARENT] == NULL){
return array( $node[self::ME] );
} else {
$ret = $this->_getPath($node[self::PARENT]);
$ret[] = $node[self::ME];
return $ret;
}
}
public function getCount(){
return $this->count;
}
private function _generateDescendants($parent){
$newNodes = array();
if( $this->maxDepth == -1 || $this->maxDepth > $parent[self::DEPTH] ){
$childs = $this->generateDescendants($parent[self::ME]);
foreach($childs as $child){
if( $this->isNew($child) ){
$newNodes[] = array(&$parent, $child, $parent[self::DEPTH]+1);
}
}
}
return $newNodes;
}
private function isNew($child){
foreach($this->open as $lnode){
if($child == $lnode[self::ME]){
return false;
}
}
foreach($this->closed as $lnode){
if($child == $lnode[self::ME]){
return false;
}
}
return true;
}
public abstract function generateDescendants($parent);
}
Verbesserungsvorschläge sind natürlich sehr Willkommen. Und für was ich das ganze brauchen werde, wird hoffentlich auch bald in diesem Blog stehen.comments
leo
@ 07.07.2007 11:08 CESTDer Apache stürzt ab? Das sollte eigentlich nicht passieren. Das Script braucht aber zweifelsohne für eine gewisse Tiefe sehr viel Speicher. Kannst du mal die Fehlermeldung posten?
Für dein Problem würde sich auch ein A* star search algorithm eignen. Der würde dann vermutlich ein wenig weniger Speicher brauchen.
add a comment
The Trackback URL to this comment is:
http://leo.freeflux.net/blog/plugin=trackback(1347).xml
This blog is gravatar enabled.
Your email adress will never be published.
Comment spam will be deleted!
Schade, habe das Script für einen sinvollen Zweck angepasst. Und zwar habe ich eine Liste voller Zahlen und möchte herausfinden welche dieser Zahlen ich addieren muss um ein vorgegebenes Ergebnis zu erreichen. Der Apache schmiert mir nur leider immer ab (wohl wegen einer Speicherüberlast.) Ist auch bei obigem Script so.
Wenn ich statt
$s->runBreadthWithDepth("1", "1.2.3.1.2.2.3",6)
ein
$s->runBreadthWithDepth("1", "1.2.3.1.2.2.3.1.2.3.1.2.2.1.2.3.1.2.2",17)
mache produziert mir mein Xampp-Apache einen lustigen Ausnahmefehler und stürzt ab. Und das bei 4GB Speicher :-(. Trotzdem danke für den Code! Flo