# Logikaufgabe: Beste Verteilung



## mysticado (2. Mrz 2014)

Hi Leute,
bevor mir sofort die Forenregeln um die Ohren geschmissen werden - NEIN, das ist keine Hausaufgabe, sondern ein klitzekleines Projekt, welches ich für mich selbst schreiben wollte. Es geht nämlich um Folgendes: 
Ich spiele auf Facebook das Spiel "Monster Legends" in welchem man Monster züchten und weiterentwickeln kann. Jedes Monster muss dafür in einem für ihn passenden Lebensraum leben.
Lebensräume haben eine Elementeigenschaft, während Monster mind. eine und max. zwei Elementeigenschaften besitzen. 
Nehmen wir als Beispiel ein Feuer/Natur Monster. Dieses kann im Lebensraum Feuer, sowie im Lebensraum Natur leben. Es gibt aber wie gesagt auch Monster mit nur einer Eigenschaft, wie z.B. Feuer. Dieses kann dementsprechend nur im Lebensraum Feuer leben.

Mein Ziel ist es nun all' meine Lebensräume und all' meine Monster einzulesen und dann eine Methode schreiben welche mir quasi die beste Verteilung der Monster in meinen Lebensräumen rausgibt. Sprich, ich möchte errechnet bekommen wie ich mir am meisten freien Platz in den Lebensräumen schaffen kann, indem ich alle meine Monster so gut verteile, dass die anderen Lebensräume vollgepackt sind.

Ein paar Klassen habe ich dafür auch schon geschrieben, mit welchen in zumindest die Daten eingelesen bekomme. Jetzt fehlt mir eben nur noch die Logik, und da hoffte ich auf einen kleinen Denkanstoß eurerseits. Hier schonmal der Code den ich bisher geschrieben habe und übrigens, falls ihr dazu auch ein paar Verbesserungstipps hättet - immer her damit!


```
public class Monster {

	int element1;
	int element2;
	
	public Monster(int e1, int e2){
		this.element1 = e1;
		this.element2 = e2;
	}
	
	public int getElement1(){
		return element1;
	}
	public int getElement2(){
		return element2;
	}
}
```


```
public class Habitat {
	
	int element;
	int size;
	
	public Habitat(int e, int s){ 
		this.element = e;
		this.size = s;
	}
	
	public int getElement() {
		return this.element;
	}
	
	public int getSize(){
		return this.size;
	}
		
}
```


```
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.Vector;

public class DataReader {

	public Vector<Habitat> habitat = new Vector<Habitat>();
	public Vector<Monster> monster = new Vector<Monster>();

	public DataReader(String file) throws FileNotFoundException, IOException {

		try (BufferedReader br = new BufferedReader(new FileReader(file))) {
			String line;
			while ((line = br.readLine()) != null) {
				line = line.replaceAll(" ", "");
				if (line.startsWith("Habitat")) {
					String hab = line.split(";")[0];
					String siz = line.split(";")[1];
					habitat.add(new Habitat(nameToInt(hab.split("=")[1]), Integer.parseInt(siz.split("=")[1])));
				} else if (line.startsWith("Monsters")) {
					String first = line.split("=")[1].trim();
					String[] second = first.split(",");
					try{	
					monster.add(new Monster(nameToInt(second[0]), nameToInt(second[1])));
					}catch(ArrayIndexOutOfBoundsException e){
						monster.add(new Monster(nameToInt(second[0]), 0));
					}
				} else if (line.startsWith("")) {
					continue;
				} else {
					System.err.println("Invalid line.");
				}
			}
		}
	}

	public Vector<Habitat> readHabitat() {
		return habitat;
	}

	public Vector<Monster> readMonster() {
		return monster;
	}
	
	public int nameToInt(String s){
		switch (s){
		case "Fire"		: return 1;
		case "Nature"	: return 2;
		case "Earth"	: return 3;
		case "Thunder"	: return 4;
		case "Water"	: return 5;
		case "Dark"		: return 6;
		case "Magic"	: return 7;
		case "Light"	: return 8;
		case "Legendary": return 9;
		case "default"	: return 0;
		}
		return -1;
	}
}
```


----------



## Gucky (2. Mrz 2014)

Du verteilst erst alle eindeutigen Monster und danach guckst du, welcher Lebensraum am wenigsten Monster hat und da tust du so viele rein, bis der Mittelwert der restlichen Lebensräume erreicht ist. So machst du weiter, bis keine Monster mehr da sind. Wenn eine Gleichverteilung vorhanden ist, verteilst du einfach gleichmäßig.

Zum Stil: der Vector ist eigentlich veraltet und durch die ArrayList ersetzt worden.
Dann hast du einen Getter read... genannt, obwohl er nichts ließt und eine öffentliche Variable zurückgibt. Das entspricht nicht den OOP Konventionen. Attribute immer private und durch Getter zugänglich machen.


----------



## Lodoss (2. Mrz 2014)

Generell: es gibt da mehrere Ansätze wie man das ganze lösen kann
die Grundlagen dazu findet man hier: Entscheidungstheorie ? Wikipedia

im Prinzip musst du dir folgendes überlegen:

1) wie definiere ich ein gutes ergebnis (z.B. alle monster sind in passendem habitat => volle punktzahl)
2) wie definiere ich ein schlechtes ergebnis (z.B. monster hat falsches habitat => punktabzug)

nun kannst du mit deinem programm ALLE kombinationsmöglichkeiten durchprobieren und dazu die "punkte" jeder variation ausrechnen

höchte punktzahl ist dein optimales ergebnis


Zum Sourcecode:
1) Gucky hat da schonmal gut vorgelegt
2) Wenn es eine feste anzahl von elementen gibt, kannst du diese als "enum" abbilden, damit sparst du dir das ganze key-handling und der code wird lesbar, sobald für bestimmte elemente ausnahmen hinzukommen
3) deine Klasse DataReader ist etwas "chaotisch" (faustregel: je Methode eine Aufgabe)
4) benutze exceptions nicht zum steuern von deinem programm. (am besten schauste dir auch nochmal Galileo Computing :: Java ist auch eine Insel – 6 Exceptions genauer an)


```
package monsterlegends;

import java.util.NoSuchElementException;

public enum Elementary
{
	Undefined   (0, "Undinfined"),
	FIRE 		(1, "Fire"),
	NATURE		(2, "Nature"),
	EARTH		(3, "Earth"),
	THUNDER 	(4, "Thunder"),
	WATER		(5, "Water"),
	DARK		(6, "Dark"),
	MAGIC		(7, "Magic"),
	LIGHT		(8, "Light"),
	LEGANDARY 	(9, "Legendary"),
	DEFAULT		(10, "Default");

	final int key;
	final String name;
	
	private Elementary(int key, String name)
	{
		this.key = key;
		this.name = name;
	}
	
	public int getKey()
	{
		return key;
	}
	
	public String getName()
	{
		return name;
	}
	
	public static Elementary getElementByKey(int key)
	{
		for (Elementary el : Elementary.values())
		{
			if (el.getKey() == key)
				return el;
		}
		throw new NoSuchElementException("No Elementary with key " + key + " found!");
	}
}
```

dadurch sieht deine klasse habitat so aus:

```
package monsterlegends;

public class Habitat
{
    Elementary element;
    int size;
    
    public Habitat(Elementary e, int s)
    { 
        this.element = e;
        this.size = s;
    }
    
    public Elementary getElement()
    {
        return this.element;
    }
    
    public int getSize()
    {
        return this.size;
    }
}
```

und deine Klasse monster

```
package monsterlegends;

public class Monster
{
    Elementary element1;
    Elementary element2;
    
    public Monster(Elementary e1, Elementary e2)
    {
        this.element1 = e1;
        this.element2 = e2;
    }
    
    public Elementary getFirstElement1()
    {
        return element1;
    }
    public Elementary getSecondElement()
    {
        return element2;
    }
}
```

und zuletzt der aufgeräumte DataReader

```
package monsterlegends;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.List;
import java.util.Vector;

public class DataReader {
	 
    public List<Habitat> habitats = new Vector<Habitat>();
    public List<Monster> monsters = new Vector<Monster>();
 
	public List<Habitat> getHabitats()
	{
        return habitats;
    }
 
    public List<Monster> getMonsters()
    {
        return monsters;
    }
    
    public DataReader(String file) throws FileNotFoundException, IOException
    {
    	BufferedReader br = null;
    	try
    	{
    		br = new BufferedReader(new FileReader(file));

    		String line;
	        while ((line = br.readLine()) != null)
	        {            	
	            line = line.replaceAll(" ", "");
	            if (line.startsWith("Habitat"))
	            {
	            	parseHabitat(line);
	            }
	            else if (line.startsWith("Monsters"))
	            {
	               parseMonster(line);
	            }
	            else if (line.startsWith(""))
	            {
	                continue; // skip empty lines
	            }
	            else
	            {
	                System.err.println("Invalid line.");
	            }
	        }
    	}
    	finally
    	{
    		// if the opening of the resource has been successful
    		// the resource must be given back to the system!
    		if (br != null)
    			br.close();
    	}
    }
 
    /** parse single line to a Monster with elements */
    private void parseMonster(String line)
    {
    	 String first = line.split("=")[1].trim();
         String[] second = first.split(",");
         
         Elementary monsterEl1 = Elementary.Undefined;
         Elementary monsterEl2 = Elementary.Undefined;
         switch(second.length)
         {
         	case 1:
         	{
             	monsterEl1 = Elementary.getElementByKey(Integer.parseInt(second[0]));
             	break;
         	}
         	case 2:
         	{
         		monsterEl1 = Elementary.getElementByKey(Integer.parseInt(second[0]));
             	monsterEl2 = Elementary.getElementByKey(Integer.parseInt(second[1]));
         		break;
         	}
         	default:
         	{
         		System.err.println("invalid monster found with element-size " + second.length);
         		break;
         	}
         }
         monsters.add(new Monster(monsterEl1, monsterEl2));
	}

    /** parse single line to a habitat */
	private void parseHabitat(String line)
    {
        String hab = line.split(";")[0];
        String siz = line.split(";")[1];
        
        Elementary elementary = Elementary.getElementByKey(Integer.parseInt(hab.split("=")[1]));
        int size = Integer.parseInt(siz.split("=")[1]);
        habitats.add(new Habitat(elementary, size));
	}
}
```


----------



## Gucky (2. Mrz 2014)

@Lodoss


			
				Lodoss hat gesagt.:
			
		

> nun kannst du mit deinem programm ALLE kombinationsmöglichkeiten durchprobieren und dazu die "punkte" jeder variation ausrechnen



Meinst du eine BruteForce Attack?
Die Herangehensweise an Probleme finde ich gut aber sollten BruteForce Attacks nicht besser vermieden werden?


----------



## Lodoss (2. Mrz 2014)

naja, es ist eigentlich schlimmer als bruteforce, dennd a hörste auf wenn du die "eine richtige möglichkeit" gefunden hast.... hier hast du ja gerade das problem, das du niemanden hast den du fragen kannnst "hey, ist das ergebnis richtig?" sondern nur "ist das ergebnis richtiger als...."

man kann natürlich auch nach finden einer "optimalen lösung" abbrechen (wenn also alle monster in den richten habitaten sind) aber villeicht sind auch aletrnativen interessant

Beispiel:
Lösung 1 ist optimal (alle verteilt), es bleiben 3 plätze in habitat B übrig
Lösung 2 ist optimal (alle verteilt), es bleiben 2 plätze in habitat A und 1 platz im Habitat B übrig

wenn du grade ein monster mit element A und Element B "hinzufügen" willst, ist Lösung 2 natürlich noch besser als 1 =)
wenn du aber grade ein monster nur mit element B hinzufügen willst, ist lösung 1 villeicht die bessere wahl


----------



## rme (2. Mrz 2014)

Gucky: Es gibt Probleme, bei denen noch nicht geklärt ist, ob es einen besseren Ansatz als Brute Force gibt. Das sind die Probleme, die in der Problemklasse "nichtdeterministisch-polynomiell" liegen. Und dieses Problem klingt zumindest auf dem ersten Blick nach einem NP-harten Problem


----------



## Gucky (2. Mrz 2014)

Ok. Wieder was gelernt.  danke euch beiden.

Wie sieht das denn mit meiner oben geschilderten Möglichkeit aus? Wäre die eine Alternative zur BruteForce Attack?


----------



## mysticado (3. Mrz 2014)

Hi Leute,
erstmal danke für die tollen und konstruktiven Antworten. Ich hab nicht schlecht gestaunt, als ich vorhin von der Arbeit nach Hause kam und solch eine rege Diskussion vorfand.

Gestern habe ich schonmal die erste Methode ausprobiert und die Monster mit einem Element direkt in ihre Habitate gesetzt, während ich es bei den anderen so gemacht habe, dass ich geschaut habe welches der zu ihren Elementen entsprechenden Habitate mehr Platz frei hat.

Beispiel: Ich habe ein Feuer/Erde Monster. Also gucke ich mir die Gesamtanzahl der freien Plätze in Feuer- bzw. Erdhabitaten an und setze das Monster in das welches mehr Platz bietet.

Das Problem, das ich hierbei sehe ist aber, dass ich zum Zeitpunkt des Reinsetzens des Monsters ins Erdhabitat immer noch keine Ahnung von der Zukunft habe, sprich ich weiss nicht, ob noch viele Erdmonster kommen werden und ob es am Ende vielleicht da drauf hinausläuft, dass meine restlichen Erdmonster keinen Platz mehr haben werden. Aus dem Grund implementiere ich momentan eine Checkerfunktion, welche beim Zustand des fehlenden freien Platzes die Monster einfach tauschen würde und wiederum beim getauschten Monster guckt, ob es nicht wo anders untergebracht werden kann.

Die Methode mit der Suche nach dem besten Ergebnis hört sich auch sehr spannend an, doch ich bezweifle, dass ich das alleine logisch soweit hinbekomme. Wer also Lust und Spaß hat kann ja gerne mal den Versuch anstellen diese Methode selber zu coden  

Ansonsten wenn es weitere interessante Tipps gibt, immer her damit! 

Viele Grüße


----------



## Gucky (3. Mrz 2014)

Diese Checkerfunktion hört sich so an, als wenn sie sehr viel Performance kostet. Die solltest du so selten, wie möglich aufrufen. Zum Beispiel, wenn beide Habitate voll sind, in die du dein Monster tun willst und dann tauschst du z.B. zwei Monster raus. Dann musst du auch noch eine Sicherheit einbauen, dass der Checker sich nicht im Kreis dreht.


----------



## Lodoss (4. Mrz 2014)

Die Aufgabe hat mir keine Ruhe gelassen... ich hab da mal was geschraubt was im groben die Anforderungen erfüllt oder ggf. noch erweitert werden kann nach bedarf

Ich entschuldige vorweg die "mäßige" codequali, muss morgen früh raus und wollt das heute noch loswerden... war hart zu schreiben, also darf es auch mal hart zu lesen sein 

zum scoring:
monster ist in passendem habitat +1
monster ist in nicht passendem habitat -1
habitat hat mehr monster als platz -100

es fehlen noch Kleinigkeiten, z.B. müssen doppelte Ergebnisse rausgefiltert werden und eine sortierung nach punkten wäre auch nicht verkehrt, aber ich denke das bekommste hin

sollte was unklar sein (davon geh ich mal aus...) kann ich da morgen nochmal genauer drauf eingehen 

ich leg mich dann mal hin... glaube habe mir bei der rekursion ne hirnwindung gezerrt...

Gruß Lodi

DataReader...

```
package monsterlegends;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.List;
import java.util.Vector;

public class DataReader {
	 
    public List<Habitat> habitats = new Vector<Habitat>();
    public List<Monster> monsters = new Vector<Monster>();
 
	public List<Habitat> getHabitats()
	{
        return habitats;
    }
 
    public List<Monster> getMonsters()
    {
        return monsters;
    }
    
    public DataReader(String file) throws FileNotFoundException, IOException
    {
    	BufferedReader br = null;
    	try
    	{
    		br = new BufferedReader(new FileReader(file));

    		String line;
	        while ((line = br.readLine()) != null)
	        {            	
	            line = line.replaceAll(" ", "");
	            if (line.startsWith("Habitat"))
	            {
	            	parseHabitat(line);
	            }
	            else if (line.startsWith("Monsters"))
	            {
	               parseMonster(line);
	            }
	            else if (line.startsWith(""))
	            {
	                continue; // skip empty lines
	            }
	            else
	            {
	                System.err.println("Invalid line.");
	            }
	        }
    	}
    	finally
    	{
    		// if the opening of the resource has been successful
    		// the resource must be given back to the system!
    		if (br != null)
    			br.close();
    	}
    }
 
    /** parse single line to a Monster with elements */
    private void parseMonster(String line)
    {
    	 String first = line.split("=")[1].trim();
         String[] second = first.split(",");
         
         Elementary monsterEl1 = Elementary.Undefined;
         Elementary monsterEl2 = Elementary.Undefined;
         switch(second.length)
         {
         	case 1:
         	{
             	monsterEl1 = Elementary.getElementByKey(Integer.parseInt(second[0]));
             	break;
         	}
         	case 2:
         	{
         		monsterEl1 = Elementary.getElementByKey(Integer.parseInt(second[0]));
             	monsterEl2 = Elementary.getElementByKey(Integer.parseInt(second[1]));
         		break;
         	}
         	default:
         	{
         		System.err.println("invalid monster found with element-size " + second.length);
         		break;
         	}
         }
         monsters.add(new Monster(monsterEl1, monsterEl2));
	}

    /** parse single line to a habitat */
	private void parseHabitat(String line)
    {
        String hab = line.split("=")[1].split(";")[0];
        String siz = line.split(";")[1];
        
        Elementary elementary = Elementary.getElementByKey(Integer.parseInt(hab));
        int size = Integer.parseInt(siz);
        habitats.add(new Habitat(elementary, size));
	}
}
```

Die zu parsende File sieht so aus (only for test):


> Monsters=7,0
> Monsters=3,0
> Habitat=7;1
> Habitat=3;2
> Habitat=4;2



hier die Elementary-class

```
package monsterlegends;

import java.util.NoSuchElementException;

public enum Elementary
{
	Undefined   (0, "Undinfined"),
	FIRE 		(1, "Fire"),
	NATURE		(2, "Nature"),
	EARTH		(3, "Earth"),
	THUNDER 	(4, "Thunder"),
	WATER		(5, "Water"),
	DARK		(6, "Dark"),
	MAGIC		(7, "Magic"),
	LIGHT		(8, "Light"),
	LEGANDARY 	(9, "Legendary"),
	DEFAULT		(10, "Default");

	final int key;
	final String name;
	
	private Elementary(int key, String name)
	{
		this.key = key;
		this.name = name;
	}
	
	public int getKey()
	{
		return key;
	}
	
	public String getName()
	{
		return name;
	}
	
	public static Elementary getElementByKey(int key)
	{
		for (Elementary el : Elementary.values())
		{
			if (el.getKey() == key)
				return el;
		}
		throw new NoSuchElementException("No Elementary with key " + key + " found!");
	}
}
```

die Habitat-class

```
package monsterlegends;

public class Habitat
{
    Elementary element;
    int size;
    
    public Habitat(Elementary e, int s)
    { 
        this.element = e;
        this.size = s;
    }
    
    public Elementary getElement()
    {
        return this.element;
    }
    
    public int getSize()
    {
        return this.size;
    }
}
```

die Monster-class

```
package monsterlegends;

public class Monster
{
    Elementary element1 = Elementary.Undefined;
    Elementary element2 = Elementary.Undefined;
    
    public Monster(Elementary e1, Elementary e2)
    {
        this.element1 = e1;
        this.element2 = e2;
    }
    
    public Elementary getFirstElement1()
    {
        return element1;
    }
    public Elementary getSecondElement()
    {
        return element2;
    }
}
```


Und nun zur eigentlichen Main-Klasse, hier ist auch die rekursive "Ergebnis-brute" drin

```
package monsterlegends;

import java.io.IOException;
import java.util.ArrayList;
import java.util.List;

public class MainClass
{
	public static List<Monster> monsters = null;
	public static List<Habitat> habitats = null;
	
	public static void main(String[] args)
	{
		readData();
		
		// calc result
		List<Result> all = calcResults(monsters);
		
		// output result
		for (int i = 0; i < all.size(); i++)
		{
			Result res = all.get(i);
			res.calculateScore();
			System.out.println("Result [" + i + "] with score " + res.score);
			for (ResultLine rl : res.assignments)
			{
				System.out.println(" --- Monster " + rl.m.getFirstElement1().name + " --> Habitat " + rl.h.getElement().name);
			}
			
		}
	}
	
	public static void readData()
	{
		try
		{
			DataReader dr = new DataReader("src/monsterlegends/data.txt");
			
			monsters = new ArrayList<Monster>(dr.monsters);
			for (Monster m : monsters)
			{
				System.out.println("found monster " + m.getFirstElement1().getName() + " " + m.getSecondElement().getName());
			}

			habitats = new ArrayList<Habitat>(dr.habitats);
			for (Habitat h : habitats)
			{
				System.out.println("found habitat " + h.getElement().getName() + " with size " + h.getSize());
			}
		}
		catch (IOException e)
		{
			// TODO Auto-generated catch block
			e.printStackTrace();
		}		
	}
	
	/*
	Monster 1 → Habi 1			
		Monster 2 → Habi 1		
			Monster 3 → habi 1	
				==> mon1 hab 1; mon2 hab 1; mon 3 hab 1
				-> 0 left new Result()
			Monster 3 → habi 2
				==> mon1 hab 1; mon2 hab 1; mon 3 hab 2
				-> 0 left new Result()
		Monster 2 → Habi 2		
			Monster 3 → habi 1
				==> mon1 hab 1; mon2 hab 2; mon 3 hab 1
				-> 0 left new Result()
			Monster 3 → habi 2	
				==> mon1 hab 1; mon2 hab 2; mon 3 hab 2
				-> 0 left new Result()
			
	Monster 2 → habi 2	
		...
*/
	/** THIS IS WHERE THE MAGIC HAPPENS! */
	public static List<Result> calcResults(List<Monster> monstersleft)
	{
		if (monstersleft.size() == 0)
		{
			List<Result> results = new ArrayList<Result>();
			results.add(new Result());
			return results;
		}
		
		List<Result> currentResults = new ArrayList<Result>();
		for (Monster m : monstersleft)
		{
			for (Habitat h : habitats)
			{
				List<Monster> nextMonsterLeft = new ArrayList<Monster>(monstersleft);
				nextMonsterLeft.remove(m);
				List<Result> subResults = calcResults(nextMonsterLeft);
								
				for (Result subResult : subResults)
				{
					ResultLine resultline = new ResultLine();
					resultline.h = h;
					resultline.m = m;
					subResult.assignments.add(resultline);
				}
				currentResults.addAll(subResults);
			}
		}
		return currentResults;
	}		
}
```

und noch 2 hilfsklassen zum speichenr der ergebnisse

```
package monsterlegends;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class Result
{
	public List<ResultLine> assignments = new ArrayList<ResultLine>();
	int score = 0;
	
	public void calculateScore()
	{
		score = 0;
		for (ResultLine rl : assignments)
		{
			if (rl.isMatch()) { score++; } else { score--; }
		}
		calculateMonstersInHabitats();
	}

	private void calculateMonstersInHabitats()
	{
		HashMap<Habitat, Integer> count = new HashMap<Habitat, Integer>();
		
		for (ResultLine rl : assignments)
		{
			Habitat used = rl.h;
			if (count.containsKey(used))
			{
				count.put(used, count.get(used) + 1);
			}
			else
			{
				count.put(used, 1);
			}
		} 

		for (Habitat h : count.keySet())
		{
			if (h.size < count.get(h))
			{
				score = score - 100;
			}
		}
	}
}
```


```
package monsterlegends;

public class ResultLine
{
	Monster m = null;
	Habitat h = null;
	
	public boolean isMatch()
	{
		if (m != null && h != null)
		{
			if (m.getFirstElement1() == h.getElement() || m.getSecondElement() == h.getElement())
			{
				return true;
			}
		}
		return false;
	}
}
```

Ergebnis::
found monster Magic Undinfined
found monster Earth Undinfined
found habitat Magic with size 1
found habitat Earth with size 2
found habitat Thunder with size 2
Result [0] with score -100
 --- Monster Earth --> Habitat Magic
 --- Monster Magic --> Habitat Magic
*Result [1] with score 2*
 --- Monster Earth --> Habitat Earth
 --- Monster Magic --> Habitat Magic
Result [2] with score 0
 --- Monster Earth --> Habitat Thunder
 --- Monster Magic --> Habitat Magic
Result [3] with score -2
 --- Monster Earth --> Habitat Magic
 --- Monster Magic --> Habitat Earth
Result [4] with score 0
 --- Monster Earth --> Habitat Earth
 --- Monster Magic --> Habitat Earth
Result [5] with score -2
 --- Monster Earth --> Habitat Thunder
 --- Monster Magic --> Habitat Earth
Result [6] with score -2
 --- Monster Earth --> Habitat Magic
 --- Monster Magic --> Habitat Thunder
Result [7] with score 0
 --- Monster Earth --> Habitat Earth
 --- Monster Magic --> Habitat Thunder
Result [8] with score -2
 --- Monster Earth --> Habitat Thunder
 --- Monster Magic --> Habitat Thunder
Result [9] with score -100
 --- Monster Magic --> Habitat Magic
 --- Monster Earth --> Habitat Magic
Result [10] with score -2
 --- Monster Magic --> Habitat Earth
 --- Monster Earth --> Habitat Magic
Result [11] with score -2
 --- Monster Magic --> Habitat Thunder
 --- Monster Earth --> Habitat Magic
*Result [12] with score 2*
 --- Monster Magic --> Habitat Magic
 --- Monster Earth --> Habitat Earth
Result [13] with score 0
 --- Monster Magic --> Habitat Earth
 --- Monster Earth --> Habitat Earth
Result [14] with score 0
 --- Monster Magic --> Habitat Thunder
 --- Monster Earth --> Habitat Earth
Result [15] with score 0
 --- Monster Magic --> Habitat Magic
 --- Monster Earth --> Habitat Thunder
Result [16] with score -2
 --- Monster Magic --> Habitat Earth
 --- Monster Earth --> Habitat Thunder
Result [17] with score -2
 --- Monster Magic --> Habitat Thunder
 --- Monster Earth --> Habitat Thunder


----------



## Alex Unkreativ (5. Mrz 2014)

mysticado hat gesagt.:


> Die Methode mit der Suche nach dem besten Ergebnis hört sich auch sehr spannend an, doch ich bezweifle, dass ich das alleine logisch soweit hinbekomme.
> 
> Ansonsten wenn es weitere interessante Tipps gibt, immer her damit!


Im Grunde ist es ein Optimierungsproblem. Dann brauchst du eine Bewertungsmethode und eine Änderungsmethode.
Die Bewertungsmethode liefert dir einen Wert, wie gut die aktuelle Verteilung der Monster ist. Die Änderungsmethode liefert eine andere Verteilung der Monster: Hier kannst du Vorwissen über das Spiel einbringen, also z. B. nur zulässige Verteilungen berechnen oder Verteilungen bevorzugen, von denen du weißt, dass sie gut sind. Du kannst es aber auch zufällig angehen: D. h. du wählst eine (korrekte) Verteilung randomisiert und probierst durch Iterieren eine optimale Lösung zu erhalten. Hast du viele Daten, dann lohnt ein Blick auf Gradientenabstiegs- und verwandte Methoden. Möchtest du es möglichst schnell implementiert haben, dann sind evolutionäre Algorithmen was für dich: Hier wird die Verteilung an wenigen Stellen geändert, anschließend geguckt, wie sie bewertet wird und wenn sie besser ist, als der bisherige Spitzenreiter, dann wird sie übernommen. Das wiederholt man, bis sich über eine längere Zeit keine Änderung mehr ergibt. Hier kann es sein, dass man ein Problem mit sog. lokalen Optima hat, in solchen Fällen startet man das Programm mit einer anderen Startverteilung neu und wählt am Ende, den besten von allen Läufen aus. Das wäre die Herangehensweise, die ich dir für diesen Zweck empfehlen würde.



mysticado hat gesagt.:


> Das Problem, das ich hierbei sehe ist aber, dass ich zum Zeitpunkt des Reinsetzens des Monsters ins Erdhabitat immer noch keine Ahnung von der Zukunft habe, sprich ich weiss nicht, ob noch viele Erdmonster kommen werden und ob es am Ende vielleicht da drauf hinausläuft, dass meine restlichen Erdmonster keinen Platz mehr haben werden. Aus dem Grund implementiere ich momentan eine Checkerfunktion, welche beim Zustand des fehlenden freien Platzes die Monster einfach tauschen würde und wiederum beim getauschten Monster guckt, ob es nicht wo anders untergebracht werden kann.


Ich habe dein Spiel nicht so richtig verstanden: Wenn du alle Daten beisammen hast und dann das Programm rechnen lassen kannst, dann kannst du es so angehen, wie ich es beschrieben habe. 
Gibt dir hingegen die Facebook-Seite ständig neue Monster und du kannst immer nur einen optimalen Ist-Zustand berechnen, weil du nicht weißt, was FB dir in Zukunft für Monster gibt, dann haben wir es mit einem Online-Algorithmus zu tun: Hier musst du versuchen, eine Wahrscheinlichkeitsverteilung für die kommenden Monster zu erstellen. Grob gesagt, wenn die Feuermonster extrem selten sind, dann kannst du auch das zugehörige Habitat mehr füllen, als wenn es die häufigsten Monster sind.
Diese ermittelten Wahrscheinlichkeiten fließen dann in deine Berwertungsfunktion ein. Am Programm wie oben beschrieben musst du nichts sonst ändern, nur dass du immer nur die optimale Ist-Verteilung berechnest.


----------



## dcc (11. Mrz 2014)

Riecht nach dem "Rucksack" Problem. Was dort gemacht wird ist einfach alle möglichen Kombinationen (rekursiv) auszuprobieren und das Beste daraus zu nehmen. Dafür werden alle Pfade eines Baumes durchlaufen und einzeln betrachtet. Das findet 100% die beste Verteilung. 

Ansonsten gibt es da noch die ganzen GREEDY Alogrithmen die schneller sind, aber nicht immer die optimale Lösung liefern. Z.b. man hat 1,2,4,5 er Münzen und will 10 Cent Rückgeld ausgeben, was ist die beste Kombo?

Wurzel -> (Feuer oder Natur) -> (Größe / Schaden etc.), der Baum wird nach unten immer größer.

Dazu kannst dir den binary tree Kram im anderen Thread anschauen den ich gepostet habe. Wenn man dann unten am Blatt angekommen ist, also es nicht tiefer geht, dann schaust wie die Verteilung in der Zwischenvariable ist, ist die neue besser einfach überschreiben. Das Resultat ist das mögliche Optimum.

Falls dir Rekursion nicht liegt, könntest dir auch eine Tabelle vorstellen wo du auch alle Kombinationen durchgehst. Das wäre dann sowas wie eine multidimensionales Array.

array[] => Wie eine Perlenkette 
array[][] => Wie eine Tabelle in Excell
array[][][x] => Tabelle auf einer Karteikarte in einer Box, mit x Karteikarten hintereinander
array[][][][] => Eher landen Aliens bevor das einer nutzt und nach dem Chef noch lebt


----------

