Denksport: Radialer Bestplatz-Algorithmus

Mik3e · 2. September 2005

Genial, werd das gleich testen.. break passt schon, nur kannst Du keine Ausstiegsebene angeben (wie zb in Java)... Werd mir das jetzt ansehen, geb Dir dann bescheid

Ciao,
Mike

Mik3e · 2. September 2005

Sodale.. anbei mal dein Code ohne Syntaxfehler

PHP:

<?php 
// globale Variablen 

// in $places stehen die freien Plätze 
$places = array(); 
$places[0] = array(true, true, false, false, false); 
$places[1] = array(false, false, false, true, true); 
$places[2] = array(false, true, true, true, false); 
$places[3] = array(true, true, false, false, false); 

// In $response werden die gefundenen Plätze geschrieben 
$response = Array(); 
$famt = 0; 

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

// 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; 
    for ($i=1; $i<=3; $i++) { 
        for ($y=0; $y<count($places); $y++) { 
            for ($x=0; $x<count($places[0]); $x++) { 
                clearResp(); 
                flood($i, $x, $y, $amt); 
                if (countResp() >= $amt) return; 
            } 
        } 
    } 
} 

// Weitersuchen 
function flood($fmode, $x, $y, $amt) { 
    global $places, $response, $famt; 
    if ($famt >= $amt) return; 
    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; 
} 

?>

Mik3e · 2. September 2005

Hm.... hab jetzt die funktion "searchPlaces(3);" aufgerufen (3 für die gesuchte Platzanzahl)... Irgendwo bleibt das Teil aber in ner Endlosschleife hängen...

Hast Du zufällig Skype Wär einfacher

Ciao,
Mike

hpvw · 2. September 2005

Ich habe mal ein bisschen gegoogelt und bin in Zusammenhang mit Sitzplatzvergabe desöfteren auf das "Intervallgraphfärbeproblem" gestossen. Offen gestanden habe ich keine Ahnung, was das ist

Aber vielleicht ist es ja ein Anhaltspunkt, mit dem Du Dich näher beschäftigen kannst.
Die meisten Probleme, die ich dabei gefunden habe, waren Bahn- und Flugreiseprobleme, die sich meist nur auf einzeln buchende Passagiere bezogen. Dafür wurden dort mehrere Streckenabschnitte behandelt.
Das erhöht jedoch meine Hoffnung, dass auch die Sitzplatzvergabe für Kino- und Theaterkassen bereits theoretisch behandelt wurde.
Vielleicht findest Du ja mehr.

Gruß hpvw

Tobias Menzel · 2. September 2005

hmm... so sieht der aktuelle Code in Flash aus:

Code:

function showPlaces() {
	for (var y=0; y<resp.length; y++) {
		for (var x=0; x<resp[y].length; x++) {
			var clp = this.attachMovie("pad", "p" + c, c);
			clp._x = x * clp._width;
			clp._y = y * clp._height + 100;
			var cl = new Color(clp);
			var d = (resp[y][x])? 0x00FF00 : 0xFF0000;
			cl.setRGB(d);
			c ++;
		}
	}
}


function clearResp() {
	resp = new Array();
	for (var y=0; y<places.length; y++) {
		resp[y] = new Array(places[y].length);
		for (var x=0; x<places[y].length; x++) {
			resp[y][x] = false;
		}
	}
	famt = 0;
}

function countResp() {
	var c = 0;
	for (var y=0; y<places.length; y++) {
		for (var x=0; x<places[y].length; x++) {
			if (resp[y][x] == true) c ++;
		}
	}
	return c;
}

function checkPlaces(amt) {
	for (var i=1; i<=3; i++) {
		for (var y=0; y<places.length; y++) {
			for (var x=0; x<places[0].length; x++) {
				clearResp();
				flood(i, x, y, amt);
				if (countResp() >= amt) return true;
			}
		}
	}
}

function flood(fmode, x, y, amt) {
	if (famt >= amt) return;
	if (places[y][x] == true && resp[y][x] != true) {
		resp[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;
		}
	}
}

, der sich nicht aufhängt. So gut bin ich nicht in PHP, dass ich ohne Tests lauffähigen Code aus AS generiere (und ich hab grade keine Zeit, ne Ausgabe zu schreiben und es zu testen). - Vielleicht fällt Dir beim Vergleich etwas auf?

(War da nicht mal so was, dass die Aktionen in einzeiligen if-Bedingungen auch in geschweifte Klammern müssen?)

Gruß

P.S.: Skype hab ich zwar, aber hier weder ein Mikro noch Boxen - via ICQ könntest Du es probieren: 265-943-707
.

Mik3e · 2. September 2005

@hpvw:
Danke.. aber die Lösung von Datic ist eigentlich genial..
Leider hat das Teil noch einen Fehler (sieht nach ner Endlosschleife aus) und ich find den einfach nicht... Vielleicht hast Du eine Idee, wo sich der verstecken könne (möglicherweise bin ich auch schon ein wenig blind

):

Hier der gesamte Quellcode (eigentlich recht schlank für die Funktionalität):

PHP:

$places = array();

// Reihe 1
$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; 

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

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

// In $response werden die gefundenen Plätze geschrieben 
$response = Array(); 
$famt = 0; 

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

// 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; 
    for ($i=1; $i<=3; $i++) {
        for ($y=0; $y<count($places); $y++) { 
            for ($x=0; $x<count($places[0]); $x++) { 
                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 3 PLÄTZE
searchPlaces(3);

Wär toll, wenn du über den Fehler stolperst,
LG
Mike

Tobias Menzel · 2. September 2005

Hi,

PHP:

$response = Array();

müsste "array" nicht kleingeschrieben werden?

PHP:

for ($y=0; y<count($places); $y++) {

(In Funktion countResp) fehlt ein $ vor dem zweiten y

Die Funktion showPlaces() ist natürlich noch nicht definiert (Ausgabe), was zu einer Fehlermeldung führen dürfte

Wäre interessant, wenn Du es hinbekommst, dass das Ding von einem beliebigen Startpunkt aus anfängt zu suchen. Ich habe damit eben mal ein wenig rumgefummelt, bin aber noch zu keinem eleganten Ergebnis gekommen.

Gruß
.

Pendergast · 2. September 2005

Also von mir gibt es hier anscheinend nur Kommentare nebenbei: Wäre das alles hier nicht ein geeignetes Thema für oben angesprochenen PHP-Contest?

Irgendjemand_1 · 2. September 2005

Pendergast hat gesagt.:
Also von mir gibt es hier anscheinend nur Kommentare nebenbei: Wäre das alles hier nicht ein geeignetes Thema für oben angesprochenen PHP-Contest?

Stimmt, dann würde ich auch mitmachen und als erster fertig sein

Aber leider ist es jetzt fast schon zu spät, wenn die die Lösung fast schon haben ...

btw: array() muss nicht kleingeschrieben werden. PHP macht da keinen Unterschied.

hpvw · 2. September 2005

Ich habe mich aus Langeweile gerade mal dran gesetzt und für das Problem einen genetischen Algorithmus geschrieben. Für das konkrete Beispiel erzeugt er recht passable Lösungen. Allerdings wäre es sicher ratsam bei Selektion, Rekombination und Mutation noch Verbesserungen zu implementieren, um die Laufzeit (über Generationen und Population) zu verkürzen.

PHP:

<?
/*******************/
/* Konfiguration   */
/*******************/

//Anzahl gesuchte Plätze
$f = 2;

//Platzmatrix frei 1, besetzt 0
$pl = array(
        array(1,1,0,0,0),
        array(0,0,0,1,1),
        array(0,1,1,1,0),
        array(1,1,0,0,0)
    );

//Distanzmatrix (horizontal, vertikal, diagonal,
//  Faktor für Entfernung vom Nullpunkt)
$di = array(1,1.3,1.5,0.1);

//Bester Platz
$bp = array();
$bp['x'] = 0;
$bp['y'] = 0;

/*******************/
/* Distanzmethoden */
/*******************/

//Berechnung der Distanz zwischen 2 Sitzplätzen
function calcDistanceBetweenPlaces($x1,$y1,$x2,$y2,$dis) {
    $d = min(abs($x1 - $x2), abs($y1 - $y2)) * $dis[2]
        + max(0, abs($x1 - $x2) - abs($y1 - $y2)) * $dis[0]
        + max(0, abs($y1 - $y2) - abs($x1 - $x2)) * $dis[1];
    return $d;
}

//Berechnung der Distanz zwischen einer Gruppe und dem idealen Platz
function calcDistanceFromBestplace($xz,$yz,$pl,$dis) {
    $x = 0;
    $y = 0;
    foreach($pl as $p) {
        $x += $p['x'];
        $y += $p['y'];
    }
    $x /= count($pl);
    $y /= count($pl);
    $d = calcDistanceBetweenPlaces($xz,$yz,$x,$y,$dis) * $dis[3];
    return $d;
}

//Berechnung der Distanz innerhalb einer Gruppe und zum idealen Platz
function calcDistance($pl,$bp,$dis) {
    $d = 0;
    $tmp = $pl;
    $start = array_shift($tmp);
    foreach($tmp as $p) {
        $d += calcDistanceBetweenPlaces(
                $start['x'],
                $start['y'],
                $p['x'],
                $p['y'],
                $dis);
        $start = $p;
    }
    $d += calcDistanceFromBestplace($bp['x'],$bp['y'],$pl,$dis);
    return $d;
}

/*******************/
/* Vorbereitung    */
/*******************/

//Liste der freien Plätze ermitteln
$fp = array();
for ($y = 0; $y < count($pl); $y++) {
    for ($x = 0; $x < count($pl[$y]); $x++) {
        if ($pl[$y][$x]==1) {
            $p = array();
            $p['x'] = $x;
            $p['y'] = $y;
            $fp[] = $p;
        }
    }
}

//Überprüfung, ob genügend Plätze zur Verfügung stehen
if (count($fp) < $f) {
    die("Zu wenig freie Plätze.");
}

/*******************/
/* Genetischer     */
/* Algorithmus     */
/* -Parameter      */
/*******************/

//Anzahl Individuen in Population
$popCount = 1000;

//Anzahl der Generationen
$gen = 20;

/*******************/
/* Genetischer     */
/* Algorithmus     */
/* -Vorbereitung   */
/*******************/

//Individuen in der Generation
$pe = array();

//Anfangspopulation ermitteln (zufällig)
for ($i = 0; $i < $popCount; $i++) {
    $tmp = $fp;
    shuffle($tmp);
    $in['places'] = array_slice($tmp,0,$f);
    $in['dist'] = calcDistance($in['places'],$bp,$di);
    $pe[] = $in;
}

//Vergleichsfunktion, um Individuen zu ordnen
function cmp($a,$b) {
   if ($a['dist'] == $b['dist']) return 0;
   return ($a['dist'] < $b['dist']) ? -1 : 1;
}

/*******************/
/* Genetischer     */
/* Algorithmus     */
/* -Ausführung     */
/*******************/

//Generationen bilden
for ($i = 0; $i < $gen; $i++) {
    //aktive Generation ordnen
    usort($pe,'cmp');
    
    //die bessere Hälfte finden
    $bestHalf = array_slice($pe,0,$popCount/2);
    
    //die bessere Hälfte mischen
    $bestHalfRand = $bestHalf;
    shuffle($bestHalfRand);
    
    //Array für die Kinder ermitteln,
    //die bessere Hälfte bleibt erhalten und zeugt Kinder
    //Verbesserung evtl. dass die bessere Hälfte nur 1/4
    //der neuen Generation zeugt und 1/4 neue zufällige
    //Individuen "zuwandert"
    $new = array();
    for ($k = 0; $k < count($bestHalf); $k++) {
        $dad = $bestHalf[$k]['places'];
        $mom = $bestHalfRand[$k]['places'];
        //gentischen Code der Eltern ermitteln
        //zufällig vier verschiedene Genteile (=Plätze)
        //im Kind aufnehmen
        $code = array_merge($dad,$mom);
        shuffle($code);
        $l = 0;
        $kid = array();
        $kid['places'] = array();
        while (count($kid['places']) < $f) {
            if (!in_array($code[$l],$kid['places'])) {
                $kid['places'][] = $code[$l];
            }
            $l++;
        }
        $kid['dist'] = calcDistance($kid['places'],$bp,$di);
        //das entstandene Kind hinzufügen
        $new[] = $kid;
    }
    //neue Population aus besserer Hälfte und Kindern erzeugen
    $pe = array_merge($bestHalf,$new);
}

//ein letztes mal die genaration sortieren
usort($pe,'cmp');

//den besten der letzten Generation aussuchen
$best=array_shift($pe);

/*******************/
/* Ausgabe         */
/*******************/

echo "Distanz: ".$best['dist'];
echo "<table>";
for ($y = 0; $y < count($pl); $y++) {
    echo "<tr>";
    for ($x = 0; $x < count($pl[$y]); $x++) {
        $p = array();
        $p['x'] = $x;
        $p['y'] = $y;
        $col = "000";
        if ($x == $bp['x'] && $y == $bp['y']) {
            $col = "fff";
        }
        if (in_array($p,$best['places'])) {
            echo "<td style=\"background-color:#cc3; color:#"
                .$col.";\">&nbsp; $x - $y &nbsp;</td>";
        } else if(in_array($p,$fp)) {
            echo "<td style=\"background-color:#0f0; color:#"
                .$col.";\">&nbsp; $x - $y &nbsp;</td>";
        } else {
            echo "<td style=\"background-color:#f00; color:#"
                .$col.";\">&nbsp; $x - $y &nbsp;</td>";
        }
    }
    echo "</tr>";
}
echo "</table>";

?>

Gruß hpvw

Denksport: Radialer Bestplatz-Algorithmus

Mik3e

Erfahrenes Mitglied

Mik3e

Erfahrenes Mitglied

Mik3e

Erfahrenes Mitglied

hpvw

Erfahrenes Mitglied

Tobias Menzel

Erfahrenes Mitglied

Mik3e

Erfahrenes Mitglied

Tobias Menzel

Erfahrenes Mitglied

Pendergast

Erfahrenes Mitglied

Irgendjemand_1

Erfahrenes Mitglied

hpvw

Erfahrenes Mitglied

Neue Beiträge