# Denksport: Radialer Bestplatz-Algorithmus



## Mik3e (1. September 2005)

Hi zusammen,

Vorweg, dieser Post ist wahrscheinlich eher mathematisch als technisch ein Problem und sicher nicht sonderlich simpel zu lösen. Ich hab mir schon länger mit Kollegen mein Hirn zermattert, wir kommen aber zu keiner eleganten Lösung.

*Aufgabenstellung:*
Es gibt einen Sitzplan (in Form eines 2-dimensionalen Arrays). Davon sind gewisse Plätze verfügbar (auf der Beispielskizze grün), andere sind nicht buchbar (auf der Beispielskizze rot).

Der Kunde gibt dem System nur bekannt, welche Anzahl an Tickets er haben möchte, und das System soll ihm nach Möglichkeit zusammenhängede Plätze zurückliefern.

*Dabei müssen folgende Regeln beachtet werden:*

1. Der beste Platz ist links und oben (Skizze: Platz 1/1). Von dort soll die Berechnung beginnen.

2. Die zurückgelieferten Plätze müssen nach folgender Priorisierung zusammenhängend sein (wobei n die vom User gewünschte Platzanzahl repräsentiert):

a) Versuche n nebeneinanderliegende Plätze zu finden. Ist die Suche erfolglos,...

b) versuche n hintereinanderliegende Plätze oder eine Kombination aus nebeneinanderliegenden Plätzen und hinterinanderliegenden Plätzen zu finden. Ist auch diese Suche erfolglos...

c) versuche n diagonal verbundene Plätze zu finden. Ist auch das erfolglos

d) liefere n Plätze mit den geringsten Zwischenabständen zurück, die am besten positioniert sind.

*Lösungsansatz & Beispiele:*
Klingt recht kompliziert, ist es nach menschlichem "Hausverstand" aber eigentlich nicht.
Hier ein paar Beispiele, passend zu angefügter Skizze:
*WICHTIG:* Rot makierte Plätze auf der Skizze sind nicht verfügbar!

Beispiel 1: Der Kunde möchte 2 Plätze
Das System muss ihm Platz 1/1 und Platz 1/2 zurückliefern

Beispiel 2: Der Kunde möchte 3 Plätze
Das System muss ihm Platz 3/2, 3/3 und 3/4 zurückliefern. (da nebeneinander liegende Plätze höher priorisiert sind als diagonal oder vertikal verbundene).

Beispiel 3: Der Kunde möchte 4 Plätze
Das System muss ihm Platz 3/2, 3/3, 3/4 und 2/4 liefern (kombination aus horizontal und vertikal)

Beispiel 4: Der Kunde möchte 5 Plätze
Das System muss ihm Platz 2/4, 2/5, 3/2, 3/3 und 3/4 zurückliefern.

Beispiel 4: Der Kunde möchte 15 Plätze
Das System muss ihm FALSE zurückliefern (da nicht mehr 15 Plätze verfügbar sind).

Wie Ihr seht, ist es mit Hausverstand eigentlich eine recht simple sache, dass ganze aber in eine Array-Berechnung umzulegen, ist nicht einfach...

Vielleicht habt Ihr ein paar Ideen oder Denkanstöße, wäre toll.

Danke & LG
Mike


----------



## Pendergast (1. September 2005)

Einen Denkanstoß zur Lösung kann ich dir jetzt nicht liefern, da das nun auf die Schnelle etwas zu komplex ist (wobei ich sagen muss, dass ich sowas auch mal aus Spaß an der Freud machen wollte, es dafür in meinem Bereich aber keine Anwendung gibt (und "nur so" war es dann doch zu viel Arbeit)).

Aber einen Verbesserungsvorschlag für deine Denkweise hätte ich: Bei Beispiel 4 (also das erste Beispiel 4) würde ich 3/3, 3/4 und 2/4, 2/5 vergeben wollen. Einzelpersonen von Gruppen abspalten finde ich nicht so toll. Also ab 4 Personen bitte minimum 2er-Gruppen bilden wenn möglich.


----------



## Mik3e (1. September 2005)

Da hast Du recht... Aber genau das ist das Problem. Es soll die Software selbständig ermitteln können.

Ich denke schon darüber nach, für alle Kombinationsmöglichkeiten Prioritäten zu vergeben.
z.B.: 
- nebeneinander liegende Plätze = 10 Punkte
- hintereinander liegende Plätze = 8 Punkte
etc.

Und nachdem alle Möglichkeiten durchgespielt sind, wird jene mit der höchsten Summe ausgegeben.

Das macht die Geschichte aber nicht gerade einfacher.
Vor allem soll die Berechnung keinesfalls länger als 2-3 Sekunden dauern.

Ich weiß, komplizierte Sache, aber das muss doch lösbar sein... 

Danke & Ciao,
Mike


----------



## hpvw (1. September 2005)

Alle Möglichkeiten durchspielen, halte ich nicht für sinnvoll.
Du könntest Dir überlegen, die "Distanz" zwischen den freien Plätzen zu ermitteln.
Z.B. könntest Du nebeneinanderliegende freie Plätze mit einer Kante verbinden, die Du mit 1 bewertest. Hintereinander liegende Plätze erhalten 1.3, Diagonal verbundene 1.6. Nun suchst Du Dir von jedem freien Platz zu jedem anderen freien Platz die kürzeste "Entfernung", wobei Du keine "Wege" berücksichtigen mußt, die über freie Plätze führen.
Die gängigen Verfahren (TSP-Verfahren, Dykstra, etc.) aus der Routen- und Tourenplanung lassen sich dann ggf. auf Dein Problem anpassen.

Gruß hpvw


----------



## Tobias Menzel (1. September 2005)

Ich würds mal mit einem Floodfill-Algorithmus probieren, der zuerst nach rechts und danach erst nach oben und unten füllt (zuletzt diagonal) und bei der eingebenen Anzahl gefundener Felder abbricht. Dürfte in etwa das zurückgeben, was Du Dir vorstellst.

Der Ansatz mag kompletter Blödsinn sein, war aber das was mir spontan zuerst einfiel. ^^

Gruß
.


----------



## Mik3e (1. September 2005)

Hm.. mich würden diese Algorithmen zur Routenplanung interessieren.. Im Prinzip ist es ja nichts anderes, als die Verbindung von n-Orten (Plätzen) auf einem Plan (Sitzplan) mit der kürzestmöglichen Distanz...

Habt Ihr eine ahnung, wo man näheres über diese Algorithmen erfährt?

Danke & LG
Mike


----------



## hpvw (1. September 2005)

Datic hat gesagt.:
			
		

> Ich würds mal mit einem Floodfill-Algorithmus probieren, der zuerst nach rechts und danach erst nach oben und unten füllt (zuletzt diagonal) und bei der eingebenen Anzahl gefundener Felder abbricht. Dürfte in etwa das zurückgeben, was Du Dir vorstellst.
> 
> Der Ansatz mag kompletter Blödsinn sein, war aber das was mir spontan zuerst einfiel. ^^
> 
> ...


Die Idee ist gar nicht schlecht und ließe sich evtl. mit einer Bewertung der ermittelten Platzgruppen erweitern, um unter den gefundenen die beste zu finden.

Gruß hpvw


----------



## Mik3e (1. September 2005)

Die Idee von Datic klingt wesentlich unkomplizierter als die TSP-Geschichte....
Gibt es zu diesen Floodfill Algorithmen irgendwelche Tuts (Vor allem um die Performance hochzuhalten?)

LG
Mike


----------



## hpvw (1. September 2005)

Mik3e hat gesagt.:
			
		

> Hm.. mich würden diese Algorithmen zur Routenplanung interessieren.. Im Prinzip ist es ja nichts anderes, als die Verbindung von n-Orten (Plätzen) auf einem Plan (Sitzplan) mit der kürzestmöglichen Distanz...
> 
> Habt Ihr eine ahnung, wo man näheres über diese Algorithmen erfährt?
> 
> ...


Ausgangspunkt könnte die Übersichtsseite zur Graphentheorie bei Wikipedia sein.

Außerdem könntest Du Dich durch die Uniseiten kämpfen, am ehesten bei den Lehrstühlen für Informatik, Wirtschaftsinformatik oder auch Logistik.

Gruß hpvw


----------



## Irgendjemand_1 (1. September 2005)

Naja warum kommt es erst zu solchen Probs?
Wenn du systematisch die Plätze verzeilst, wird die Aufteilung nie so, wie im Beispiel sein.

D.h die ersten setzt du vorne hin, die nächsten dahinter etc.
Dann brauchst du nur immer abfragen, wo dir 1. n Plätze nebeneinander sind.

Also wenn ich das richtig sehe ...
Und wenn keine n Plätze mehr nebeneinander sind, dann eben so aufteilen, dass möglichst keiner alleine sitzt von denen, die du neu zuteilst.

Wenn's dir aber echt nur um das Problem geht, einfach so aus spaß, dann ist ok.
Aber so schwer ist das gar nicht, du kannst im Array ja ausrechnen, welche indizes nebeneinander sind.

Und das mit dem diagonal verteilen ... Das ergibt sowieso keinen sinn, oder?
entweder nebeneinander oder hintereinander, aber diagonal?


----------



## Tobias Menzel (1. September 2005)

Hi,

ich hab mal eben in Flash was zusammengestoppelt (siehe Anhang). Scheint halbwegs Deinen Anforderungen zu entsprechen, ist (was den Code anbelangt) aber weit davon entfernt, optimiert und gut lesbar zu sein. (  ) - Bei Interesse optimier ich's Dir aber gerne (im Moment fehlt mir die Zeit) und schicke es Dir als Pseudocode zu.

Gruß

P.S.: Anzahl in das Textfeld eingeben und "GO" drücken.
.


----------



## Mik3e (2. September 2005)

Vorweg: Sorry, musste gestern abend schon weg (daher keine Rückmeldung mehr) 

*@Irgendjemand_1:*
Nein, so leicht ist das leider nicht...
Klar werden die Plätze normalerweise links oben begonnen (ist auf dem Beispiel vielleicht etwas schlecht abgebildet.

Zu einzelnen Plätzen kommt es zum Beispiel bei folgender Situation:
Kunde 1 bestellt 3 Plätze -> Bekommt 1/1, 1/2 und 1/3
Kunde 2 bestellt ebenfalls 3 Plätze -> muss 2/1, 2/2, 2/3 bekommen (da in der ersten Reihe nur noch 2 nebeneinanderliegende Plätze verfügbar sind.

Und.. Tataa.. es sind in der ersten Reihe schon zwei "alleinstehende" Plätze vorhanden.
Und genau durch diesen Ablauf, kann es zu unterschiedlichsten Belegungen kommen.

*@Datic:*
Dein Flash werde ich mir gleich reinziehen.. Hab auch schom mit einem Test-Array in PHP begonnen 

*@Alle:*
Ich mach das nicht zum Spass, sonder weil ich es für eine Applikation brauche (Bestplatzreservierung) 

Ciao,
Mike


----------



## Pendergast (2. September 2005)

Aber bei welchem Einsatzgebiet bekommt man eigentlich als "bestmöglichen Platz" einen Sitz in der Ecke? Ich kann mir grad nichts vorstellen, wo nicht ein Platz in der Mitte höherwertiger ist als am Rand.


----------



## Irgendjemand_1 (2. September 2005)

Mhm du brauchst das also richtig.
Was war denn schon dein Ansatz? Du hast dann ja sicher schon was - wenigtens - versucht?
Ich stell mir das nicht allzu schwer vor. Ein paar Rehnungen, mehr sollte das auch nicht sein.


----------



## Mik3e (2. September 2005)

Eine "Teilung" der Plätze kann auch dann auftreten, wenn zb. in einer reihe gewisse Plätze gesperrt sind (nicht für den Verkauf freigegeben).

Das der Beste Platz links oben ist, habe ich nur hier für das Beispiel angenommen (um die Sache nicht zusätzlich zu verkomplizieren). In der richtigen Applikation kann der Systemadministrator dann festlegen, wo der Verkauf begonnen werden soll (insgesamt 8 Punkte -> An jeder ecke sowie auf den Verbindungsgeraden zwischen den Ecken).

Mein Ansatz wäre gewesen, die Abfrage in mehrere Funktionen zu gliedern:

1.Funktion -> Finde n nebeneinanderliegende Plätze
wenn 1. Funktion == false gehe zu Funktion 2
2. Funktion - Finde n hintereinanderliegende Plätze
usw..

Das Problem hierbei ist eigentlich, dass bereits bei Funktion 2 eine Kombination aus nebeneinander und hintereinanderliegenden Plätzen besser wäre (3 Plätze hintereinander und einer dahinter ist zu 99% besser als 4 hintereinanderliegende).

LG
Mike


----------



## Irgendjemand_1 (2. September 2005)

Du meintest 3 Plätze nebeneinander und 1 dahinter? 
Hast dich wohl verschrieben 

Sicher ist das besser.
Wenn die 1. Funktion false zurückgibt, dann kommt ja die 2., wenn ich das richtig verstehe.
Dann teilst du die Zahl so auf, dass es, wenn es 
a) eine ungerade Zahl ist: So aufteilst, dass die 2 Zahlen fast gleichgroß sind (z.B 7 = 3 und 4)
b) eine gerade Zahl ist: So aufteilst, dass beide gleichgroß sind.

Dann rufst du die 1. Funktion auf, ob beide (! Vielleicht solltest du einen optionalen Paremeter einbauen, der erlaubt 2 Zahlen zu "testen") Zahlen "reinpassen".
Wenn nicht kommst du wieder mit beiden Zahlen zu der 2. Funktion, allerdings kommt da schon das Problem, dass du jetzt mehrere optionale Parameter in Funktion 1 brauchst.
Naja aufjedenfall um es zu Ende zu führen: Wenn Funktion 2 eine der Zahlen nicht mehr teilen kann --> Summe ausrechnen und weiter in Funktion 3.

Also so vielleicht irgendwie 
Wenn ich nacher mal Lust+Zeit hab, versuch ich das vielleicht sogar mal.


----------



## Mik3e (2. September 2005)

Im Prinzip braucht man ja nicht n-Parameter sondern einen einzigen, an den man einen Array an gesuchten Plätzen übergibt.

Geht Funtkion 1 nicht auf wird der zweidimensionale Array auf zwei reihen gesplittet.
Geht es damit noch immer nicht, wird er auf drei Reihen aufgeteilt.

Also zu Beginn (wenn der Kunde 3 Plätze haben möchte):
$testarray[0]=reihe1
$testarray[1]=reihe1
$testarray[2]=reihe1

Findet er nicht 3 nebeneinanderliegende in einer einzigen Reihe, muss der Array wie folgt umgebaut werden:
$testarray[0]=reihe1
$testarray[1]=reihe1
$testarray[2]=reihe2

Aber auch das ist nicht wirklich schön.. vor allem ist das ein Performancefresser hoch 3...
Es wird doch Algorithmen geben (so wie der angesprochene Floodfill Algorithmus), der so ähnlich ist wie zb Bubble-Search...

Eine bestimmte Anzahl an verbunden Elementen in einem Array finden ist ja vermutlich doch nicht eine sooo ausgefallene Anforderung


----------



## Mik3e (2. September 2005)

@Datic:
Echt genial! Ich hab mir zwar den Source noch nicht angesehen (weil ich Flash nicht installiert habe , aber das SWF funktioniert toll..

Kannst Du mir vielleicht mal die Funktionen (Methoden) posten
Damit wäre mir sehr geholfen..

Danke & Ciao,
Mike


----------



## Irgendjemand_1 (2. September 2005)

Hm Arrays sind schonmal ein guter Ansatz.
Dann hat man kein Parameter-Problem. Ich würd's aber so machen wie ich vorgeschlagen habe, nur auf Arrays umgebaut. Damit man dann anstatt 2 Parameter einfach 2 Elemente hat (beim aufteilen der Zahlen)


----------



## Mik3e (2. September 2005)

Sieh dir mal das SWF von Datic an..
Das kann genau das, was ich brauche (Vorausgesetzt es ist kein Fake-Code dahinter 

Nur ein paar Feinheiten müssten dann noch gemacht werden, aber sonst sieht das sehr brauchbar aus...

Ich hoffe er ist bald wieder mal online und kann mir den Source posten )


----------



## Irgendjemand_1 (2. September 2005)

Mik3e hat gesagt.:
			
		

> Sieh dir mal das SWF von Datic an..
> Das kann genau das, was ich brauche (Vorausgesetzt es ist kein Fake-Code dahinter
> 
> Nur ein paar Feinheiten müssten dann noch gemacht werden, aber sonst sieht das sehr brauchbar aus...
> ...



Sorry, an dem PC geht das leider nicht.
Falls er nicht mehr online kommen sollte, oder das ein fake-code ist, kannst du dir ja nocheinmal meine Idee anschaun.
Ich vermute nämlich fast, dass das klappen könnte.


----------



## Mik3e (2. September 2005)

Das komplexe ist ja eigentlich das anordnen der Plätze hintereinander und nebeneinander... Zusammenhängende in einer Reihe oder eine Spalte finden ist ja easy.. 
Ich saug mir grad die Flash Trial und werd mir dann den source mal ansehen  Bin schon sehr gespannt..


----------



## Irgendjemand_1 (2. September 2005)

Hehe  So geht's auch.

Ähm meine 2 Funktionen, die ich beschrieben habe würden ja noch weitergehen.
Dann sucht er sich so viele es geht nebeneinander (und der Rest muss größer als 1 sein, sonst sitzt einer Alleine)  und den Rest dahinter. Er sucht sich eben eine Stelle, wo das möglich ist 
Das lässt sich ja alles ausrechnen, welcher Platz wo ist, um dann abzufragen ob die Plätze frei sind.


----------



## Mik3e (2. September 2005)

Ja, aber genau dieses permanente "Abfragen" müsste man verhindern, da das immens Laufzeit kostet.. Ich les mir gerade die Graphentheorie im Wikipedia durch.. Das klingt recht spannend.. Solltest Du auch mal ansehen. Damit bekommt man eine ganz andere Sichtweise 
http://de.wikipedia.org/wiki/Kategorie:Graphentheorie


----------



## Irgendjemand_1 (2. September 2005)

ALLES, was da steht?
Also wo (Graphentheorie) dahinter steht?


----------



## Mik3e (2. September 2005)

Naja.. ist etwas viel .. ich les mir das durch, was brauchbar klingt.
Aber ich hab nun den Quellcode von Datic.. Mein Problem: Meine Actionskript-Zeit ist schon etwas in die Jahre gekommen. Aber ich werde das schon irgendwie entschlüsseln:


```
var places = new Array();
places[0] = new Array(true, true, false, false, false);
places[1] = new Array(false, false, false, true, true);
places[2] = new Array(false, true, true, true, false);
places[3] = new Array(true, true, false, false, false);

var resp = new Array();
var famt = 0;
var c = 0;

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

button.onPress = function() {
	doCheck(parseInt(etext.text, 10));
}

function doCheck(a) {
	checkPlaces(a);
	showPlaces();
}

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;
			//trace(resp[y][x]);
		}
	}
	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();
				resp = flood(places, i, x, y, resp, amt);
				if (countResp() >= amt) return true;
			}
		}
	}
}

function flood(matrix, fmode, x, y, rmtx, amt) {
	if (famt >= amt) return rmtx;
	if (matrix[y][x] == true && rmtx[y][x] != true) {
		rmtx[y][x] = true;
		famt ++;
		switch(fmode) {
			case 1:
				rmtx = flood(matrix, fmode, x - 1, y, rmtx, amt);
				rmtx = flood(matrix, fmode, x + 1, y, rmtx, amt);
				break;
			case 2: 
				rmtx = flood(matrix, fmode, x - 1, y, rmtx, amt);
				rmtx = flood(matrix, fmode, x + 1, y, rmtx, amt);
				rmtx = flood(matrix, fmode, x, y - 1, rmtx, amt);
				rmtx = flood(matrix, fmode, x, y + 1, rmtx, amt);
				break;
			case 3:
				rmtx = flood(matrix, fmode, x - 1, y, rmtx, amt);
				rmtx = flood(matrix, fmode, x + 1, y, rmtx, amt);
				rmtx = flood(matrix, fmode, x, y - 1, rmtx, amt);
				rmtx = flood(matrix, fmode, x, y + 1, rmtx, amt);
				rmtx = flood(matrix, fmode, x - 1, y - 1, rmtx, amt);
				rmtx = flood(matrix, fmode, x + 1, y - 1, rmtx, amt);
				rmtx = flood(matrix, fmode, x - 1, y + 1, rmtx, amt);
				rmtx = flood(matrix, fmode, x + 1, y + 1, rmtx, amt);
				break;
		}
	}
	return rmtx;
}
```

Der Anfang ist klar: ein zweidimensioanles Array "Places" (4 Reihen, 5 Spalten). In den Spalten ist dann jeweils der boolsche Wert für "verfügbar" und "nicht verfügbar" gespeichert.

Dann durchläuft er alle Plätze mit den beiden for-Schleifen (in PHP foreach) um den Grundplan auszugeben (können wir also vernachlässigen).

Die "button.OnPress" Funktion können wir auch vernachlässigen. Wichtig ist für uns nur der Aufruf der "doCheck()" Funktion.

Diese Funktion ruft zuerst die "CheckPlaces()" Funktion auf. Als Parameter wird die Anzahl der gesuchten Plätze übergeben.

Dort wird dann die "flood()" Funktion ausgeführt und an diesem Punkt ist es bei mir aus.. Dann durchblick ich die Variablenbezeichnungen nicht mehr 

..................


----------



## Irgendjemand_1 (2. September 2005)

Hm naja mit Actionscript kenn ich mich jetzt nicht aus ...
Auch wenn ich es wahrscheinlich verstehen würde, wenn ichs mir genauer anschaun würde, lassen wir das mal die Leute machen, die es können 

Zur Nor musst du das dann doch nocht selbst machen ...


----------



## Tobias Menzel (2. September 2005)

OMG - der Quellcode ist noch so grauslig, der sollte hier nicht gepostet werden. ^^

Jedenfalls: Mit Deinem Beispiel funktioniert er - wenn ein "Startplatz" manuell ausgewählt werden soll, muss aber einiges geändert werden (im Moment geht das Ding die Matrix einfach von links oben nach rechts unten durch; das müsste dann wohl eher "Ringförmig" geschehen.

Ich werd mal schauen, ob ich die Zeit finde, diese verbotene Mischung aus lokalen und globalen Arrays zu vereinfachen und das ganze in PHP umzusetzen.

Gruß

P.S.: Das, wo man dann nicht mehr durchblickt, ist vermutlich der Punkt, wo in "flood" das globale Array "rmtx" als Parameter übergeben, verändert und zurückgegeben wird (Zur Entschuldigung: Ich hab den Code in einer Mittagspause schnell runtergetippt).
.


----------



## Mik3e (2. September 2005)

Hi..
Kein Problem, war ja nur ein Testcode 
Ja, du hast recht.. bei der Flood Rekursion bin ich dann ausgestiegen ) (zu viele Variablennamen die nicht sonderlich viel aussagen)..

Ich versuch das gerade in PHP nachzubauen.. Bin aber noch nicht weit gekommen..
Kannst Du Dir hier ansehen:
http://www.powerticket.net/TESTbestplatzcalc.php

Im Moment hab ich noch ein kleines Array Problem 
Wenn Du mir das irgendwie für PHP klar machen könntest, wäre ich dir echt dankbar...

Ciao,
Mike


----------



## Tobias Menzel (2. September 2005)

Hi,

ich habe mir Deine Version noch nicht angesehen (mach ich gleich), aber ich habe mal versucht, das ganze in PHP umzuschreiben:
	
	
	



```
<?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 (var $y=0; y<count($places); $y++) {
		$response[$y] = array();
		for (var $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 (var $y=0; y<count($places); $y++) {
		for (var $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;
}

?>
```
Kann gut sein, dass sich da noch Fehler verbergen, denn ich habe es nicht getestet (kann es sein, dass es statt "break" in PHP "exit" heisst?).

Gruß
.


----------



## 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 
// 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:
	
	
	



```
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):

```
$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,





```
$response = Array();
```
 müsste "array" nicht kleingeschrieben werden?






```
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.

```
<?
/*******************/
/* 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


----------



## Pendergast (2. September 2005)

Irgendjemand_1 hat gesagt.:
			
		

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


Naja, das ist dann _eine_ mögliche Lösung, die bestimmt nicht mal perfekt ist (bezweifle auch, dass es _die_ perfekte Lösung gibt). Dazu kommen dann noch Konfigurationsmöglichkeiten (Raumplanung etc.), Darstellung der Informationen, Performancetuning etc. - da gäb es genug zu tun!


----------



## Irgendjemand_1 (2. September 2005)

Pendergast hat gesagt.:
			
		

> Naja, das ist dann _eine_ mögliche Lösung, die bestimmt nicht mal perfekt ist (bezweifle auch, dass es _die_ perfekte Lösung gibt). Dazu kommen dann noch Konfigurationsmöglichkeiten (Raumplanung etc.), Darstellung der Informationen, Performancetuning etc. - da gäb es genug zu tun!



Schon, aber das Thema wurde jetzt ja schon ausreichend besprochen und verschiedene Lösungssätze geliefert.

Naja ok das ist vielleicht sogar ganz gut  Aber die - ich hab sie mir nciht angeschaut - fast funktionierenden Funktionen etc. sind ja schon fertig.


----------



## Mik3e (2. September 2005)

So.. das ganze artet ja schon in ein wissenschaftliches Experiment aus 
Werde mir mal den Code von hpvw zu Gemüte führen.
(Danke vorweg an dieser Stelle).

Zum Thema Contest:
Solche Problemstellungen sind sicher spannend. Und das ganze nach bester Performance bewerten (hab sowas ähnliches schon für Primzahlen im Contest Forum vorgeschlagen).

Und ich denke das diese Thematik so komplex ist, dass die beste Lösung sicher noch lange nicht gefunden ist


----------



## Mik3e (2. September 2005)

So.. hab den Code von hpvw nun genommen und noch ein wenig "interaktion" eingefügt...
Damit kann man das ganze besser testen:
*URL: http://www.powerticket.net/TESTbestplatzcalc3.php*

*Dabei stehen wir nun vor zwei Problemen:*
1. Die Berechnung passt nicht immer (mit 3 Plätzen werden die weiter hinten gereihten gewählt).
2. Die Berechnung ist ein ziemlicher Performancefresser... Möglicherweise kann man das noch verbessern!?

Ciao,
Mike


----------



## Mik3e (2. September 2005)

Noch was:
Bei hpvw`s Code setzt er die Priorität "links" höher als die Priorität "oben"....
Und mit den Parametern "bester Platz" konnte ich das Verhalten leider nicht ändern... 
(sofern Du y=reihen und x=plätze angenommen hast)...


----------



## hpvw (2. September 2005)

Ich habe den Code eben mal erweitert. Und zwar habe ich eine zufällige Ausgangsmatrix eingeführt, um auch anhand anderer Fälle zu testen:
	
	
	



```
//statt $pl=..
$pl=array();
$mx = 11;
$my = 8;
$full = 20;
for ($x=0;$x<$mx;$x++) {
    for ($y=0;$y<$my;$y++) {
        $pl[$y][$x]=(rand(0,100)>$full)?1:0;
    }
}
```
Dabei ist mir aufgefallen, dass die Zuordnung schlechter wird, je mehr freie Plätze es gibt. Das liegt offensichtlich daran, dass man mit den Plätzen in der Ausgangspopulation leben muss, da keine neuen hinzugefügt werden (im Code-Kommentar angesprochene Zuwanderung). 
Problematisch ist sicherlich auch, dass bei der Ausgangspopulation in keiner Weise berücksichtigt wird, dass möglichst viele Plätze im genetischen Code auftauchen. Ist der Raum relativ leer, ist die Chance sehr groß, dass einige Plätze gar nicht erst berücksichtigt werden können. An diesen Punkten könnte man weiterarbeiten, um den Algorithmus zu verbessern.
Auch an der Bewertung könnte man noch verbessern, da dort nicht der ideale Wert einer Gruppe ermittelt wird, sondern die Distanz der Gruppe in der zufälligen Reihenfolge, wie sie im Gencode auftaucht berechnet wird.
Bei der Rekombination könnte man sich bemühen, dass man Pärchen nicht nur zufällig bildet, sondern auch Gruppen als mom und dad zusammenführt, die verhältnismäßig dicht beieinander sitzen.

Gruß hpvw

EDIT: Verdammt seit ihr schnell


----------



## Irgendjemand_1 (2. September 2005)

Verbesserungswürdig. Gebt mal 5 ein. Da s  1 - 10, 	  2 - 10,  	  3 - 10,     3 - 9,  	   4 - 9  
wären besser.
Naja soll nicht beleidigend sein, aber ist halt so  
Ich find das an sich ganz gut gelungen - Für eine alpha-version allemale


----------



## Mik3e (2. September 2005)

Das klingt hier ja wie bei der Einwanderungsbehörde (Mutter, Vater, kinder, zeugung.. 
Vor allem den Codekommentar finde ich gut:

//die bessere Hälfte bleibt erhalten und zeugt Kinder
lol..

Spass beiseite.. Die aktuelle Version mit den Zufalls-Array ist wieder online:
http://www.powerticket.net/TESTbestplatzcalc3.php

Leider versteh ich von dem genetischen Code im Moment überhaupt nichts 

Ciao,
Mike


----------



## hpvw (2. September 2005)

Ein genetischer Algorithmus ist ja auch kein Optimierungsverfahren, sondern eine Heuristik.
Dieses Beispiel sollte auch nur eine Idee sein, nicht mal eine Alpha-Version.
Wenn man die Mutationskriterien geschickt programmiert und die Berechnung der Fitness (im Beispiel die Distanz) besser der Problemstellung anpasst, führen genetische Algorithmen i.d.R. in verhältnismäßig kurzer Zeit zu Ergebnissen, die nahe am Optimum sind.
Durch die deutliche Trennung der Bewertung von der Ermittlung und weiteren Parametern gibt es eine Menge Schrauben, an denen man drehen kann.
Höchstwahrscheinlich muss man insbesondere die Größe der Population und die Anzahl der Generationen von der Anzahl freier Plätze abhängig machen und ggf. sogar bei fast leerem Saal auf andere Algorithmen zurückgreifen.
Auf jeden Fall sind die oben bereits angesprochen Schwachstellen noch auszubessern und (sollte man bei dieser Art der Fitnessberechnung bleiben) die Distanzparameter anzupassen.

Gruß hpvw


----------



## Mik3e (2. September 2005)

So...
Was ich nicht ganz durchblicke sind die Angaben der Distanzmatrix:

//Distanzmatrix (horizontal, vertikal, diagonal, 
//  Faktor für Entfernung vom Nullpunkt) 
$di = array(1,1.3,1.5,0.1);
Ist ein Wert mit 4 Werten.. aber was gibt der vierte an

Folgendes Problem ist noch aufgetreten (wie schon erwähnt): Er bevorzugt links vor oben.. (d.h. er beginnt seine Berechnung an der linken seite und nicht oben)...

LG
Mike


----------



## hpvw (2. September 2005)

Mik3e hat gesagt.:
			
		

> Das klingt hier ja wie bei der Einwanderungsbehörde (Mutter, Vater, kinder, zeugung..
> Vor allem den Codekommentar finde ich gut:
> 
> //die bessere Hälfte bleibt erhalten und zeugt Kinder
> ...


Genau so kannst Du Dir einen genetischen Algorithmus vorstellen.
Es gibt eine Population. Im Sinne von "Survival of the Fittest" mischen die besten ihren genetischen Code und erzeugen Nachkommen daraus. Damit entsteht eine neue Population, die selbst wieder Nachkommen erzeugt, usw.
Die Population besteht aus Individuen.
Jedes Individuum enthält einen genetischen Code (eine Gruppe von Plätzen) und eine Fitness (Bewertung der Gruppe von Plätzen).
Nun sucht man sich nach bestimmten Kriterien zwei Individuen aus und mischt ihren genetischen Code. Man nimmt also ein Paar Plätze aus dem einen Individuum und ein Paar aus dem anderen. Daraus entsteht ein neues Individuum, welches in die Population der nächsten Generation übernommen wird.

Gruß hpvw


----------



## hpvw (2. September 2005)

Mik3e hat gesagt.:
			
		

> Ist ein Wert mit 4 Werten.. aber was gibt der vierte an


Den vierten Wert verwende ich für den Abstand der Plätze-Gruppe zum idealen Platz. Damit die Entfernung der Gruppe zum idealen Platz weniger stark gewichtet wird, als die Entfernung der Plätze in der Gruppe untereinander, aber zwei gleichwertige Gruppen, mit unterschiedlicher Entfernung zum idealen Platz geordnet werden können.
Dazu wird der Mittelpunkt der Gruppe gebildet, von diesem die Entfernung zum idealen Platz und das Ergebnis dann mit dem Faktor (4.Wert im Array) multipliziert.

Wie gesagt, ist die Bewertung einer Platzgruppe ein Punkt, an dem sicherlich noch verbessert werden kann.

Gruß hpvw


----------



## Mik3e (2. September 2005)

Wie gesagt scheitere ich schon bei den Distanzparametern.. 
Ich vermute $di ist die Bewertung der Distanz zwischen zwei Objekten...
d.h: 
Horizontal = 1.0
Vertikal = 1.3
Diagonal = 1.5
? = 0.1 <= Welche Anordnung stellt dieser Wert dar?

Und jenes Individum, die in Summe die geringste Distanz hat, ist das Beste...

Habe ich diese erste Überlegung mal richtig verstanden


----------



## Mik3e (2. September 2005)

Ich würde den genetischen Algorithmus mal gerne so weit durchblicken, dass ich es selbst schaffe, die Priorisierung zu ändern (d.h. OBEN geht vor LINKS). In beigefügtem Beispiel für 2 gewählte Plätze würde das heißen, dass er mir die Plätze 2-0 und 3-0 zurückliefert, und nicht wie derzeit die Plätze 0-1 und 1-1...


----------



## hpvw (2. September 2005)

Es wird zur Zeit nur die Distanz, egal in welche Richtung, vom idealen Platz ermittelt.
Eine leichte Priorisierung entsteht durch den ersten und den zweiten Faktor. Womit dieselbe Reihe bereits leicht bevorzugt wird.
Da die Bedingungen zunehmend binär, bzw. unstetig werden, muss wohl eine neue Funktion zur Bewertung her, die mehr mit Bedingungen, als mit Rechnungen arbeitet.
Ich schau mal, ob mir noch was einfällt.

Gruß hpvw


----------



## Mik3e (2. September 2005)

Hilfe.. mir wird das langsam zu komplex 
Es muss doch auch eine simplere und einfachere Lösung geben.
Hast Du Dir den Ansatz von Datic schon angesehen Das funktioniert eigentlich perfekt.

Den variablen Startpunkt kannst Du ruhig außen vor lassen (ist nicht wichtig im Moment)... Damit wird die Sache sicher wesentlich simpler...


----------



## Irgendjemand_1 (2. September 2005)

Ich hab keine interesse das zu machen, keine Lust zurzeit.
Vielleicht werde ich das mal in ein paar Wochen, wenn ich Lust habe auch machen.

Aber ich hätte noch eine Idee:
Das von der 2d Ebene auf 3d zu übertragen: $places[0][0][0] 
Also der erste index bestimmt dann das Stockwerk oder so. Bei nem Doppeldecker-Bus zum Beispiel^^
Noch eine Aufgabe: Das alles so so Flexibel sein, dass man angeben kann, wie viele Reihen, Stockwerke und Sitze es gibt.
Also Sitze = Sitze pro Reihe
Reihen = Reihe pro Stockwerk.

Man gibt also sozusagen alles an 

Das könnte man als contest-Thema nehmen 

edit: oder vierdimensional. Dann gibt man noch an, dass das selbe nocheinmal daneben gestellt wird. ^^


----------



## hpvw (2. September 2005)

Mik3e hat gesagt.:
			
		

> Hilfe.. mir wird das langsam zu komplex


Das ist auch kein triviales Problem.



			
				Mik3e hat gesagt.:
			
		

> Es muss doch auch eine simplere und einfachere Lösung geben.


Möglich, aber mir fällt als einfache Lösung nur die eigenständige Wahl durch den Anwender ein.



			
				Mik3e hat gesagt.:
			
		

> Hast Du Dir den Ansatz von Datic schon angesehen Das funktioniert eigentlich perfekt.


Den Code habe ich mir angesehen. Im unglücklichsten Fall führt das (zumindest fast) zur vollstängiden Enumeration. Bist Du Dir sicher, dass er in einer Endlosschleife steckt oder kann es sein, dass er nur sehr lange braucht? Oder war das jetzt Blödsinn und ich habe die Lösung überlesen?



			
				Mik3e hat gesagt.:
			
		

> Den variablen Startpunkt kannst Du ruhig außen vor lassen (ist nicht wichtig im Moment)... Damit wird die Sache sicher wesentlich simpler...


Bei Datics Code macht das sicher einen Unterschied, da die dreifach verschachtelte Schleife etwas anders aussehen müßte, bei den Bewertungsfunktionen des genetischen Algorithmus ist das relativ egal.

@Irgendjemand_1:
Das ganze in 2d mit vernünftigen Ergebnissen und akzeptablem Laufzeitverhalten hinzukriegen ist schon Arbeit genug. Wenn das jedoch anständig läuft, dürfte es ein geringfügiges Problem sein, das auf eine weitere Dimension zu portieren.

Das war jetzt bis Sonntag erstmal mein letzter Post, jetzt geht es ins Wochenende.
Ich wünsche Euch noch viel Spaß und vor allem Erfolg.

Gruß hpvw


----------



## hpvw (8. September 2005)

Mik3e hat gesagt.:
			
		

> @hpvw:
> Ich gehe das Problem nun anders (simpler) an...
> Ich versuche immr nebeneinanderliegende Plätze zu finden....
> 
> ...


Die Idee ist ganz gut. Ich hätte evtl. einen Vorschlag, wie man das Beschleunigen und ggf. auch verbessern könnte (Bei 8: 8; 4/4; 5/3; 6/2; 4/2/2; 3/3/2; 2/2/2/2).

Wie wäre es, wenn Du das Array nur einmal durchläufst und jeweils in einer Zeile nebeneinanderliegende Plätze gruppierst. Dann hättest Du ein wesentlich kleineres Array, was Du so oft durchlaufen kannst, wie Du willst.

Die oben angesprochene andere Verteilung müßte man evtl. für gängige Gruppengrößen von Hand machen, aber ich versuche gleich mal eine Funktion zu schreiben.

Gruß hpvw


----------



## Mik3e (8. September 2005)

Warte - Stop - Halt 

Ich hab mir den Code von Datic nochmal zu gemüte geführt..
Ich muss sagen, die Lösung ist überhaupt genial und schnell..

Habe es jetzt noch für PHP umgesetzt (abgesehen von den noch hässlichen global-Definitionen)...
Sieh es dir mal an.. Bei der Flood-Funktion hab ich noch nicht ganz den Durchblick:


```
// In $places steht die gesamte Platzmatrix 
$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;

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; 
} 

// In $response werden die gefundenen Plätze geschrieben 
$response = Array(); 
$famt = 0; 
// Platzsuche für $amt=4 Plätze starten
searchPlaces(4);
print_r($response);
```

LG
mike

EDIT: War noch ein Fehler im Source-Code.. ist jetzt korrigiert...


----------



## 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:

```
<!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:

```
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
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 
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
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>
```


----------

