Denksport: Radialer Bestplatz-Algorithmus

Mik3e · 8. September 2005

So, hab das Teil jetzt noch umgebaut und mit einer Grafischen Ausgbae versehen... Funktioniert ganz gut, nur müsste man die Priorisierung noch optimieren:
http://www.powerticket.net/TESTbestplatzcalc3.php

Quellcode komplett:

PHP:

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
"http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<title>Unbenanntes Dokument</title>
</head>
<body>
<?php 
// globale Variablen 

// in $places stehen die freien Plätze 
// Grundplan anlegen 
$places = array();
for ($i=0;$i<=10;$i++) {
	for($g=0;$g<=10;$g++) {
		if (rand(0,1)==0) {
			$places[$i][$g] = true;
		} else {
			$places[$i][$g] = false;
		}
	}
}

/*echo 'REIHEN:'.count($places);
echo 'PLÄTZE:'.count($places[0]);*/

function searchPlaces($amt) { 
    checkPlaces($amt); 
} 

// Gefundene Plätze löschen 
function clearResp() { 
    global $places, $response, $famt; 
    $response = array(); 
    for ($y=0; $y<count($places); $y++) { 
        $response[$y] = array(); 
        for ($x=0; $x<count($places[$y]); $x++) { 
            $response[$y][$x] = false; 
        } 
    } 
    $famt = 0; 
} 

// Gefundene Plätze zählen 
function countResp() { 
    global $places, $response; 
    $c = 0; 
    for ($y=0; $y<count($places); $y++) { 
        for ($x=0; $x<count($places[$y]); $x++) { 
            if ($response[$y][$x] == true) {
				$c++;
			} 
        } 
    } 
    return $c; 
} 

// Plätze suchen: 
function checkPlaces($amt) { 
    global $places, $response, $famt; 
	/********************************
	* $i = 3 Varianten:
	* - horizontal verbunden
	* - vertikal verbunden
	* - diagonal verbunden
	/********************************/
    for ($i=1; $i<=3; $i++) {
        for ($y=0; $y<count($places); $y++) { 
            for ($x=0; $x<count($places[0]); $x++) { 
                /*echo 'REIHE:'.$y.'<br>';
				echo 'PLATZ:'.$x.'<br>';*/
				clearResp(); 
                flood($i, $x, $y, $amt); 
                if (countResp() >= $amt) {
					return true;
				}
            } 
        } 
    } 
} 

// Weitersuchen 
function flood($fmode, $x, $y, $amt) { 
    global $places, $response, $famt; 
    if ($famt >= $amt) {
		return true; 
	}
    if ($places[$y][$x] == true && $response[$y][$x] != true) { 
        $response[$y][$x] = true; 
        $famt ++; 
        switch($fmode) { 
            case 1: 
                flood($fmode, ($x-1), $y, $amt); 
                flood($fmode, ($x+1), $y, $amt); 
                break; 
            case 2: 
                flood($fmode, ($x-1), $y, $amt); 
                flood($fmode, ($x+1), $y, $amt); 
                flood($fmode, $x, ($y-1), $amt); 
                flood($fmode, $x, ($y+1), $amt); 
                break; 
            case 3: 
                flood($fmode, ($x-1), $y, $amt); 
                flood($fmode, ($x+1), $y, $amt); 
                flood($fmode, $x, ($y-1), $amt); 
                flood($fmode, $x, ($y+1), $amt); 
                flood($fmode, ($x-1), ($y-1), $amt); 
                flood($fmode, ($x+1), ($y-1), $amt); 
                flood($fmode, ($x-1), ($y+1), $amt); 
                flood($fmode, ($x+1), ($y+1), $amt); 
                break; 
        } 
    } 
    return; 
} 

// PLATZSUCHE STARTEN FÜR 4 PLÄTZE
// In $response werden die gefundenen Plätze geschrieben 
$response = Array(); 
$famt = 0; 
searchPlaces(20);
?>
<a href="javascript:window.location.reload();"><strong>Saalplan neu generieren</strong><br>
<br>
</a><?PHP
echo '<table width="100%"  border="1" cellspacing="2" cellpadding="0">';
for ($y=0; $y<count($response); $y++) {
	echo '<tr>';
	for ($x=0; $x<count($response[0]); $x++) { 
    	if ($places[$y][$x]) {
			$bgcolor='#006600';
		} else {
			$bgcolor='#FF0000';
		}
		if ($response[$y][$x]==1) {
			echo '<td bgcolor="'.$bgcolor.'"><FONT COLOR="#FFFFFF"><STRONG>X</STRONG></FONT></td>';
		} else {
			echo '<td bgcolor="'.$bgcolor.'">&nbsp;</td>';
		}
	}
  	echo '</tr>';
}
echo '</table>';
?>
</body>
</html>

hpvw · 8. September 2005

Mik3e hat gesagt.:
nur müsste man die Priorisierung noch optimieren

Dann solltest Du auch schreiben, wie die Priorisierung geändert werden sollte. Ob das dann möglich ist, müßte Datic vielleicht sagen. Für mich sieht es so aus, als ob man daran nur etwas ändern könnte, indem man die Verschachtelung der Schleifen ändert. Das würde aber vermutlich nicht zu einem besseren Ergebnis führen. So ganz verstehe ich den Code allerdings nicht, um das mit Gewissheit zu sagen.

Gruß hpvw

Mik3e · 8. September 2005

Hab den Code jetzt etwas optimiert.. läuft eigentlich prima (immer eine schöne Gruppenbildung)...
Kannst Du hier testen:
http://www.powerticket.net/TESTbestplatzcalc3.php

Und flott ist es auch..
Ich steh jetzt nur schon vor dem nächsten Problem:
Es kann auch sein, dass die Plätze über mehrere Sektoren (Pläne) gesucht werden sollen.
Und jeder Sektor kann eine andere Anzahl an Plätzen und Reihen haben...

Alle Plätze einfach in einen Array packen geht auch nicht...
Verstehst Du was ich meine

LG
Mike

Mik3e · 8. September 2005

So.. jetzt hab ich aber ein anderes Problem (ich glaub ich steh auf der Leitung).
Bau mir gerade eine bequeme Klasse für die Berechnung der besten Plätze. An die entsprechende Methode wird dann nur noch der Saalplan-Array (mit true/false) und die Anzahl der gesuchten Plätze übergeben.

Jedoch hab ich ein kleines Phänomen: Meine Literale gehen irgendwo verloren. Genaugenommen geht es um die Variable $places, die in der checkPlaces() Funktion als Global definiert wird. Prüfe ich diese in der Funktion, ist sie leer...!?

Vielleicht siehst du etwas, das ich nicht sehe:

PHP:

class bestplatzcalculation
{
function searchPlaces($places,$amt) {
		echo 'GESUCHT: '.$amt.'<br>'; // GIBT 2 AUS
		echo 'PLATZ 2/0: '.$places[2][0].'<br>'; // GIBT 1 AUS
    	$response = Array();
		$this->checkPlaces($amt);
	}

function checkPlaces($amt) { 
    	global $places;
		global $response;
		global $famt; 

		echo 'GESUCHT:'.$amt.'<br>'; // GIBT 2 AUS
		echo 'PLATZ 2/0: '.$places[2][0].'<br>'; //GIBT NULL AUS
    }
}

Aber auch wenn ich $places als Parameter übergebe, habe ist diese Variable = Null in der Funktion ckeckPlaces(). Davor ist genau in diesem array-feld aber der Wert TRUE.
Nun bin ich am grübeln, wo der Wert verloren gegangen sein kann!?

Ich glaub ich bin überarbeitet

Bitte um Hilfe,
Ciao & Danke,
Mike

Mik3e · 9. September 2005

@Datic:

Hi!

Danke vorweg vielmals für die Idee zur Sitzplatzberechnung.. Habe das jetzt komplett in eine PHP Klasse implementiert und ein wenig optimiert.

Ich stehe jetzt nur vor einem Problem:
Es funktioniert sehr gut, solange die Plätze irgendwie verbunden sind (horizontal, vertikal oder diagonal).

Als vierte Instanz (in der Schleife) möchte ich nun, dass er auch "alleinstehende" Plätze mit einbezieht.. Angenommen es sind auf einem Plan noch 4 Plätze frei, aber nur drei miteinander verbunden, dann soll er trotzdem den 4ten (alleinstehenden) Platz auch dazu nehmen...

Ich weiß, dass es etwas mit der Schleife in der Funktion checkPlaces() und der zugehörigen Case-Verzweigung zu tun hat. Nur leider bin ich einfach zu dämlich um eine 4. Bedingung einzubauen...

Vielleicht kannst Du mir noch ein letztes mal helfen
Hier zur Sicherheit nochmals die Klasse (ist ein wenig erweitert, lass dich davon aber nicht irritieren):

PHP:

<?PHP
class bestplatzcalculation
{
	var $places;
	var $amt;
	var $response;
	var $famt;
	
	function searchPlaces($places,$amt) { 
		$this->places = $places;
		$this->amt = $amt;
		$this->checkPlaces($this->amt);
		$this->show_result();
	}
	
	// Gefundene Plätze löschen 
	function clearResp() { 
	    $this->response = array(); 
    	for ($y=0; $y<count($this->places); $y++) { 
	        $this->response[$y] = array(); 
    	    for ($x=0; $x<count($this->places[$y]); $x++) { 
	            $this->response[$y][$x]['ist_platz'] = false; 
    	    } 
	    } 
    	$this->famt = 0; 
	} 

	// Gefundene Plätze zählen 
	function countResp() { 
	    $c = 0; 
    	for ($y=0; $y<count($this->places); $y++) { 
	        for ($x=0; $x<count($this->places[$y]); $x++) { 
    	        if ($this->response[$y][$x]['ist_platz'] == true) {
					$c++;
				} 
	        } 
    	} 
	    return $c; 
	} 

	// Plätze suchen: 
	function checkPlaces($amt) { 
		/********************************
		* $i = 3 Varianten:
		* - horizontal verbunden
		* - vertikal verbunden
		* - diagonal verbunden
		/********************************/
	    for ($i=1; $i<=3; $i++) {
    	    for ($y=0; $y<count($this->places); $y++) { 
        	    for ($x=0; $x<count($this->places[0]); $x++) { 
					$this->clearResp(); 
	                $this->flood($i, $x, $y, $this->amt); 
    	            if ($this->countResp() >= $this->amt) {
						return true;
					}
	            } 
    	    } 
	    } 
	} 

	// Weitersuchen 
	function flood($fmode, $x, $y, $amt) { 
    	//global $places, $response, $famt; 
	    if ($this->famt >= $this->amt) {
			return true; 
		}
    	if ($this->places[$y][$x]['ist_platz'] == true && $this->response[$y][$x]['ist_platz'] != true) { 
	        $this->response[$y][$x]['ist_platz'] = true;
			$this->response[$y][$x]['saalplan_platzID'] = $this->places[$y][$x]['saalplan_platzID'];
			$this->response[$y][$x]['xbez'] = $this->places[$y][$x]['xbez'];
			$this->response[$y][$x]['ybez'] = $this->places[$y][$x]['ybez'];
    	    $this->famt ++; 
	        switch($fmode) { 
    	        case 1: 
        	        $this->flood($fmode, ($x-1), $y, $this->amt); 
            	    $this->flood($fmode, ($x+1), $y, $this->amt); 
                	break; 
	            case 2: 
    	            $this->flood($fmode, ($x-1), $y, $this->amt); 
        	        $this->flood($fmode, ($x+1), $y, $this->amt); 
            	    $this->flood($fmode, $x, ($y-1), $this->amt); 
                	$this->flood($fmode, $x, ($y+1), $this->amt); 
	                break; 
    	        case 3: 
        	        $this->flood($fmode, ($x-1), $y, $this->amt); 
            	    $this->flood($fmode, ($x+1), $y, $this->amt); 
                	$this->flood($fmode, $x, ($y-1), $this->amt); 
	                $this->flood($fmode, $x, ($y+1), $this->amt); 
    	            $this->flood($fmode, ($x-1), ($y-1), $this->amt); 
        	        $this->flood($fmode, ($x+1), ($y-1), $this->amt); 
            	    $this->flood($fmode, ($x-1), ($y+1), $this->amt); 
	                $this->flood($fmode, ($x+1), ($y+1), $this->amt); 
    	            break; 
	        } 
	    } 
    	return; 
	} 
	
	function show_result() {
		echo '<table width="100%"  border="1" cellspacing="2" cellpadding="0">';
		for ($y=0; $y<count($this->places); $y++) {
			echo '<tr>';
			for ($x=0; $x<count($this->places[0]); $x++) { 
	    		if ($this->places[$y][$x]['ist_platz']==true) {
					$bgcolor='#006600';
				} else {
					$bgcolor='#FF0000';
				}
				if ($this->response[$y][$x]['ist_platz']==true) {
					echo '<td style="background-color:'.$bgcolor.';"><FONT COLOR="#FFFFFF"><STRONG>CHOOSEN!<br>PlatzID: '.$this->places[$y][$x]['saalplan_platzID'].'<br>Platz: '.$this->places[$y][$x]['ybez'].'/'.$this->places[$y][$x]['xbez'].'</STRONG></FONT></td>';
				} else {
					echo '<td style="background-color:'.$bgcolor.'"><FONT COLOR="#FFFFFF">PlatzID: '.$this->places[$y][$x]['saalplan_platzID'].'<br>Platz: '.$this->places[$y][$x]['ybez'].'/'.$this->places[$y][$x]['xbez'].'</FONT></td>';
				}
			}
  			echo '</tr>';
		}
		echo '</table>';
	}
}
?>

Du würdest mir damit wirklich sehr weiterhelfen, wenn ich irgendwas für Dich tun kann, gib mir bescheid..

Danke & Ciao,
Mike

Mik3e · 12. September 2005

@Datic:
Hier der Code (Klasse und Objekterstellung sind getrennt). Im Zweiten Bereich auf der Output (leider nicht so wie ich mir das vorstelle

...

Benenne die Files am Besten so wie angeführt, dann kannst Du das Teil direkt starten...

Klasse (TESTbestplatzcalc6.php):

PHP:

<?php 
class CalcPlaces {
	
	var $_input=array();
	var $_output=array();
	var $_probed=array();
	var $_rem=array();
	
	var $_damt=0;
	var $_famt=0;
	
	var $_sx=0;
	var $_sy=0;
	
	function test() {
		echo 'TESTFUNKTION';
	}
	
	function clearOutput($probe, $rem) {
		$c = 0;
		for ($y=0; $y<count($_output); $y++) {
			for ($x=0; $x<count($_output[$y]); $x++) {
				if ($rem==true) {
					$_output[$y][$x] = $_rem[$y][$x];
					$c += ($_rem[$y][$x])? 1 : 0;
				} else {
					$_output[$y][$x] = false;
				}
				if ($probe==true) {
					$_probed[$y][$x] = false;
				}
			}
		}
		if ($rem) {
			$_famt = $c;
		} else {
			$_famt = 0;
		}
	}
	
	function findPlaces($a, $amt, $sx, $sy) {
		/*****************************************************************
		* $a = Array des Grundplans
		* $amt = Anzahl der gesuchten Plätze
		* $sx = Startpunkt, von dem die Berechnung beginnen soll (x-koord)
		* $sy = Startpunkt, von dem die Berechnung beginnen soll (y-koord)
		/*****************************************************************
		/*$_input = new array(count($a));
		$_output = new Array(a.length);
		$_probed = new Array(a.length);*/
		$_input = array();
		$_output = array();
		$_probed = array();
		for ($y=0; $y<count($a); $y++) {
			$_input[$y] = array(count($a[$y]));
			$_output[$y] = array(count($a[$y]));
			$_probed[$y] = array(count($a[$y]));
			for ($x=0; $x<count($a[$y]); $x++) {
				$_input[$y][$x] = $a[$y][$x];
				$_output[$y][$x] = false;
				$_probed[$y][$x] = false;
			}
		}
		$_rem = $_output;
		$_damt = $amt;
		$_famt = 0;
		if (!isset($sx)) {
			$sx = 0;
		}
		if (!isset($sy)) {
			$sy = 0;
		}
		$_sx = $sx;
		$_sy = $sy;
		for ($h=0; $h<5; $h++) {
			if ($h > 0) {
				$_rem = $_output;
			}
			for ($i=0; $i<3; $i++) {
				if ($_famt < $_damt) {
					$this->clearOutput(true, ($h > 0));
					$this->doProbe($i, $_sx, $_sy, ($h > 0));
				}
			}
		}
			
		if ($_famt < $_damt) {
			$this->clearOutput(true, false);
		}
		return $_output;
	}
	
	function doProbe($fmode, $dx, $dy, $rem) {
		if ($_probed[$dy][$dx] == true) {
			return;
		}
		if ($dx < 0 || $dy < 0) {
			return;
		}
		if ($dx >= count($_input[0]) || $dy >= count($_input)) {
			return;
		}
		$_probed[$dy][$dx] = true;
		$this->clearOutput(false, $rem);
		$this->doFlood($fmode, $dx, $dy);
		if ($_famt < $_damt) $this->doProbe($fmode, $dx + 1, $dy, $rem);
		if ($_famt < $_damt) $this->doProbe($fmode, $dx - 1, $dy, $rem);
		if ($_famt < $_damt) $this->doProbe($fmode, $dx, $dy + 1, $rem);
		if ($_famt < $_damt) $this->doProbe($fmode, $dx, $dy - 1, $rem);
	}
	
	function doFlood($fmode, $x, $y) {
		if ($_famt >= $_damt) return;
		if ($_input[$y][$x] == true) {
			if ($_output[$y][$x] != true) {
				$_famt ++;
				$_output[$y][$x] = true;
				switch($fmode) {
					case 2:
						$this->doFlood($fmode, $x + 1, $y + 1);
						$this->doFlood($fmode, $x + 1, $y - 1);
						$this->doFlood($fmode, $x - 1, $y + 1);
						$this->doFlood($fmode, $x - 1, $y - 1);
					case 1:
						$this->doFlood($fmode, $x, $y - 1);
						$this->doFlood($fmode, $x, $y + 1);
					case 0:
						$this->doFlood($fmode, $x + 1, $y);
						$this->doFlood($fmode, $x - 1, $y);
				}
			}
		}
	}
}
?>

Instanzierung und Ausgabe (STARTbestplatzcalc6.php):

PHP:

<?PHP
include("TESTbestplatzcalc6.php");
$CalcPlaces=&new CalcPlaces();

// Reihe 1
$places=array();
$response=array();
$places[0][0] = true; 
$places[0][1] = true; 
$places[0][2] = false; 
$places[0][3] = false; 
$places[0][4] = false; 

// Reihe 2
$places[1][0] = false; 
$places[1][1] = false; 
$places[1][2] = false; 
$places[1][3] = true; 
$places[1][4] = true;

$response=$CalcPlaces->findPlaces($places, 3, 0, 0);
?>
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
"http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<title>Unbenanntes Dokument</title>
</head>
<body>
<?PHP
echo '<table width="100%"  border="1" cellspacing="0" cellpadding="0">';
for ($y=0; $y<count($response); $y++) {
	echo '<tr>';
	for ($x=0; $x<count($response[0]); $x++) { 
		if ($places[$y][$x]) {
			$bgcolor='#006600';
		} else {
			$bgcolor='#FF0000';
		}
		if ($response[$y][$x]==true) {
			echo '<td bgcolor="'.$bgcolor.'">XXXX</td>';
		} else {
			echo '<td bgcolor="'.$bgcolor.'">&nbsp;</td>';
		}
	}
  	echo '</tr>';
}
echo '</table>';
?>
</body>
</html>

Denksport: Radialer Bestplatz-Algorithmus

Mik3e

Erfahrenes Mitglied

hpvw

Erfahrenes Mitglied

Mik3e

Erfahrenes Mitglied

Mik3e

Erfahrenes Mitglied

Mik3e

Erfahrenes Mitglied

Mik3e

Erfahrenes Mitglied

Neue Beiträge