Hallo
Ich möchte mir ein C# Programm schreiben, welches mir Gesamtsumme aus
einer Matrix auslesen soll.
zum Beispiel
1
S1 S2 S3 S4 S5
2
Z1 1 _2_ 3 5 8
3
Z2 8 20 _23_ 29 40
4
Z3 7 11 15 18 _24_
5
Z4 _23_ 27 30 38 40
Die Gesamtsumme besteht aus je einem Wert pro Zeile. Wenn ich 72 eingebe
soll mir das Programm jede mögliche Wertekomination ausspucken, welche
72 ergeben.
Hier wäre es 72 = 2 + 23 + 24 + 23 (unterstrichene Werte)
oder 72 = 8 + 8 + 18 + 38
oder oder oder...
Alles klar was das Programm tun soll?
Mein Problem ist, dass diese Matrix sehr gross werden kann (ca 30X30
max). Mit einer verschachtelten for-Schlaufen ergibt das extrem viele
Durchläufe und somit lange Berechnungszeit (>10 Minuten!)
Wie kann diese Arbeit effizienter geschrieben werden?
Vielen Dank
Du musst alle Kombinationen durchprobieren, da du ja alle möglichen
ausgegeben haben willst.
Um das effizienter zu machen, könntest du die Matrix
jeweils vorher aufräumen, zB. alle
Werte > dem gesuchten auslassen (wenn alle Werte positiv sind),
oder Kombinationen ausschließen,
fragst du zB nach 72, kannst du bei 8/40 abbrechen, weil
(min(Z3)+min(Z4))>72-8-40
Wie du das in dein Programm umsetzt musst du wissen,
grübel nen bisschen, dann fällt dir auch was ein.
Erstmal sortieren und Duplikate rauswerfen. Dann eine Art Backtracking
Algorithmus? Weiß nicht ob du mit weniger als exponentieller Komplexität
rauskommen kannst. Ich schätze nicht, nachdem du ALLE Möglichkeiten
suchst, nicht nur EINE.
Also irgendwie so:
- Schreibe alle Einträge in eine sortierte Liste ohne Duplikate, merk
dir extra wie oft welche Zahl vorkommt und wo sie stehen
- ignoriere alle Zahlen, die größer als die gesuchte ist
- greife dir die größte Zahl
- addiere die nächst Kleinere, so oft, bis du >= der Gesuchten bist
- falls es die gesuchte ist, merke dir die Zahlen
- subtrahiere die letzte Zahl und addiere wieder eine Kleinere
- wiederhole so lange, bis du durch die Liste durch bist
Wenn du dazu noch die Duplikate berücksichtigst könnte das gehen.
ah8 schrieb:> Die Komplexität liegt bei i^j, also nicht gerade unproblematisch, aber> besser geht's wohl nicht.
Kurze Ergänzung. Falls ich um die Uhrzeit nichts übersehen habe, ist das
Problem NP-vollständig
http://mathworld.wolfram.com/SubsetSumProblem.html
falls also jemand einen schnelleren Algorithmus findet, gratuliere ich
schon mal.
Ups, war wohl doch schon etwas spät gestern: statt list< unsigned >
muss es richtig natürlich überall list< Value > heißen, sonst dürfte
es mit anderen Typen für die Matrix Probleme geben.
Ihr seid echt super! Vielen Dank für die Antworten
Es sind sehr interessante Anregungen dabei, leider habe ich immoment
keine Zeit mehr diese anzuschauen (Abschlussprüfungen :/ ).
Werde es versuchen in c# umzusetzten und hoffen dass es einwenig
schneller ist als 50 verschachtelte For-Schlaufen
In der aktuellen C't ist ein ganzer Artikel über Matrixmultiplikation.
Du willst zwar nicht multiplizieren, aber vielleicht kannst du dir da
einige Interessante Überlegungen raussuchen…
Und die machen das mit 1024x1024 Matrixen und das ist schon eine ganz
Menge mehr ;-)
Die beschäftigen sich aber vor allem auch damit, wie du das ganze mit
dem Compiler optimierst.
12V DC schrieb:> In der aktuellen C't ist ein ganzer Artikel über Matrixmultiplikation.
Damit hat das Problem eigentlich nix zu tun, eher schon mit
Partitionierungsproblemen:
http://de.wikipedia.org/wiki/PartitionierungsproblemArc Net schrieb:> ah8 schrieb:>> Die Komplexität liegt bei i^j, also nicht gerade unproblematisch, aber>> besser geht's wohl nicht.>> Kurze Ergänzung. Falls ich um die Uhrzeit nichts übersehen habe, ist das> Problem NP-vollständig> http://mathworld.wolfram.com/SubsetSumProblem.html> falls also jemand einen schnelleren Algorithmus findet, gratuliere ich> schon mal.
In der gegebenen Aufgabenstellung lassen sich i und j nach oben durch 30
abschätzen, gehen also nicht in die Komplexität ein, ditto für die
Anzahl der Lösungen, die sich ebenfalls durch eine Konstante abschätzen
lässt.
In der Komplexität verbleiben Rechnungen mit Werten, deren Größe sich
durch die vorgegebene Summe N abschätzen lässt. Damit verbleibt als
Komplexität
Und falls N etwa eine 32-Bit Zahl ist (oder 64 Bits groß) dann reduziert
sich die Komplexität weiter zu
mit zugegeben etwas unkomfortablen O-Konstanten.
*wegduck*
Ohne die verlinkten Artikel gelesen zu haben - falls die Wertebereiche
es sinnvoll erscheinen lassen würde ich es mit der Bildung von
Äquivalenzklassen versuchen: Man nehme sich jeweils zwei
aufeinanderfolgende Zeilen der Matrix, bilde alle Paare von Elementen,
und ordne diejenigen Paare, welche die gleiche Summe ergeben, der
gleichen Klasse zu. Die Bildung der Äquivalenzklassen lässt sich
rekursiv fortsetzen, bis man - naja, eben fertig ist und die eine Klasse
hat, die der Zielsumme entspricht.
Die Idee dabei ist halt, das eine solche Äquivalenzklasse repräsentativ
für beliebig viele Werte(-kombinationen) steht. Wenn die Klasse die
Bedingung erfüllt (Summe = x), dann tun das automatisch auch alle
Elemente der Klasse, ohne das man diese einzeln zu prüfen bräuchte. Das
sollte auch bei einer 30x30 Matrix hinreichend zügig gehen.
Michael H. schrieb:> Ohne die verlinkten Artikel gelesen zu haben - falls die Wertebereiche> es sinnvoll erscheinen lassen würde ich es mit der Bildung von> Äquivalenzklassen versuchen:
Wenn es einen mathematischen Beweis gibt, dass das Problem
NP-vollständig ist, würde ich meine Zeit nicht damit verschwenden, nach
einer besseren Lösung zu suchen. (Es sei denn, Du hast Ambitionen auf
den Nobelpreis. Zwar gibt es noch keinen Nobelpreis für Informatik, aber
es ist gut möglich, dass für die Lösung dieses Problems eigens einer
gestiftet wird :-)
Natürlich gibt es immer wieder spezielle Matrizen, für die eine
effizientere Lösung angegeben werden kann, in allgemeinen Fall aber
wirst Du nicht besser werden. Bei einer m*n Matrix musst Du immer n^m
Kombinationen probieren, wenn Du nur mit zwei Zeilen anfängst sind es
halt n^2 Möglichkeiten und auch potentiell n^2 mögliche
Äquivalenzklassen. Kann sein, dass es weniger werden, sicher ist das
aber keinesfalls.
Es gibt auch im obigen Code noch etliche Verbesserungsmöglichkeiten – er
ist nicht auf Effizienz getrimmt –, substantielle Fortschritte wird man
aber nur machen können, wenn man sich das Originalproblem anschaut. Die
Matrix muss ja irgendwo her kommen. Vielleicht finden sich dort weitere
Informationen, die sich für eine effizienter Lösung heranziehen lassen.
A. H. schrieb:> ...in allgemeinen Fall aber wirst Du nicht besser werden.
Das ist natürlich richtig. Aber wenn man halt nicht den allgemeinen Fall
sondern ein konkretes Problem mit konkreten Constraints hat, dann kann
es durchaus möglich sein im average case auf akzeptable Laufzeiten zu
kommen. Und damit ist man häufig ja auch zufrieden. Gleich das Handtuch
zu werfen nur weil irgendwo ein TSP oder sowas auftaucht gilt nicht. ;-)
Im Anhang ist ein proof of concept. Die Matrizen werden dabei mit
Zufallswerten (natürliche Zahlen) gefüllt. Bei den bisherigen Tests
funktionierte das ganz gut würde ich sagen:
> fast sum solver; matrix size: 30x30, target sum = 100> 98670 solutions found in 0.031 seconds
Zumindest gut genug um den Ansatz mal weiterzuverfolgen.
PS: ob die Anzahl von 98670 möglichen Summen stimmt habe ich nicht
überprüft. Ein Brute-Force-Solver liefert aber stets die gleiche Antwort
(getestet natürlich nur auf kleineren Matrizen), also stehen die Chancen
ganz gut. :)
Michael H. schrieb:> A. H. schrieb:>> ...in allgemeinen Fall aber wirst Du nicht besser werden.>> Das ist natürlich richtig. [...] Gleich das Handtuch> zu werfen nur weil irgendwo ein TSP oder sowas auftaucht> gilt nicht. ;-)
Genau. - Zumal manches Argument stark nach "Beweis durch
Reduktion auf das falsche Problem" aussieht.
Der Hinweis auf das Partitionierungsproblem ist einerseits
richtig, andererseits auch irreführend - im vorliegenden
Fall steht die Anzahl der Summanden ja schon fest; beim
Partitionierungsproblem ist das nicht der Fall.
> Im Anhang ist ein proof of concept. Die Matrizen werden> dabei mit Zufallswerten (natürliche Zahlen) gefüllt. Bei> den bisherigen Tests funktionierte das ganz gut würde> ich sagen: [...]
Der Trick der Methode besteht ja darin, dass die Anzahl
der zu betrachtenden Elemente-Kombinationen mit 30^N
wächst, während der Wertebereich für die Summe nur N * Max
ist.
Bei 3 Zeilen zu 30 Elementen und Werten von 1...1000 gibt
es 3000 verschiedene Summen, aber 27000 verschiedene
Elemente-Tripel. Es fallen also immer sehr viele Tripel
in dieselbe Äquivalenzklasse, einfach weil die Anzahl
bildbarer Summen nicht ausreicht...
Für die nächste Stufe der Rekursion müssen aber erstmal
nur die Äquivalenzklassen betrachtet werden; daraus
resultiert die Einsparung.
>> fast sum solver; matrix size: 30x30, target sum = 100>> 98670 solutions found in 0.031 seconds
Hmm. 0.3µs je Lösung... in der Tat erstaunlich.
A. H. schrieb:> [...] wenn Du nur mit zwei Zeilen anfängst sind es halt> n^2 Möglichkeiten und auch potentiell n^2 mögliche> Äquivalenzklassen.
Im vorliegenden Falle nicht. Wenn der Definitionsbereich
für alle Elemente 0..N_max ist, lassen sich aus zwei
Zeilen maximal 2 * N_max Äquivalenzklassen bilden, die
gegen n^2 Elementekombinationen stehen. Das liegt in der
Natur der Summe.
> Kann sein, dass es weniger werden, sicher ist das aber> keinesfalls.
Doch, im vorliegenden Falle schon. Es gibt nicht ausreichend
viele verschiedene Summen - zumindest dann nicht, wenn der
Bereich für die Matrixelemente "vernünftig" eingeschränkt
wird.
Possetitjel schrieb:> Hmm. 0.3µs je Lösung... in der Tat erstaunlich.
Es geht. Je nach Matrix kann es auch extremer werden:
> fast sum solver, matrix size: 30x30, target sum = 100> 25399595030595 solutions found in 0.046 seconds
Wirklich erstaunlich fänd ich es allerdings wenn tatsächlich jemand über
diese Lösungen iterieren wollen würde. :P
Oliver S. schrieb:>Das schon. Bleibt die im solchen Fäälen immer zu stellende Frage:> W A R U M ?
Keine Ahnung. Projekt Euler? Oder der TE hat ganz einfach einen
speziellen Anwendungsfall für den er diese Informationen benötigt. Mir
persönlich reicht es eigentlich wenn der TE weiss wozu er die Lösung
braucht... ;-)
Possetitjel schrieb:> Im vorliegenden Falle nicht. Wenn der Definitionsbereich> für alle Elemente 0..N_max ist, lassen sich aus zwei> Zeilen maximal 2 * N_max Äquivalenzklassen bilden, ...
Das stimmt schon, aber wo in der Aufgabe steht denn geschrieben, dass
die Elemente der Matrix derart eingeschränkt werden können? Mit
hinreichend vielen Einschränkungen kann ich das Problem natürlich
beliebig einfach machen. Wenn ich mich auf die Null-Matrix beschränke
muss ich gar nicht mehr rechnen. Aber passt die Lösung dann noch zum
Problem?
> Doch, im vorliegenden Falle schon. Es gibt nicht ausreichend> viele verschiedene Summen
Im Prinzip wieder die gleiche Frage: Wo steht, dass das so ist ...
> zumindest dann nicht, wenn der> Bereich für die Matrixelemente "vernünftig" eingeschränkt> wird.
bzw. dass ich die Matrixelement so einschränken kann?
A. H. schrieb:> Possetitjel schrieb:>> Im vorliegenden Falle nicht. Wenn der Definitionsbereich>> für alle Elemente 0..N_max ist, lassen sich aus zwei>> Zeilen maximal 2 * N_max Äquivalenzklassen bilden, ...>> Das stimmt schon, aber wo in der Aufgabe steht denn geschrieben, dass> die Elemente der Matrix derart eingeschränkt werden können?
Na, die Antwort kennst du doch selbst: Es steht genau da, wo auch steht
das es keinerlei Beschränkungen gibt. Nämlich nirgends.
Auch wenn man durch die Annahme von Einschränkungen lediglich Teilmengen
des allgemeinen Problems effizient lösen kann, so find ich solche
Annahmen keineswegs per se unzulässig.
Ich schätze mal das niemand hier Lust hat eine komplette Theorie
auszuarbeiten, aber als Anstoß möchte ich mal folgenden Gedankengang
äußern:
Nehmen wir an, das der worst case für den oben skizzierten
Äquivalenzklassenalgorithmus darin besteht, das jede Klasse nur ein
einziges Element enthält; jede Teilsumme also nur ein einziges mal
vorkommt. Dann hätten wir gegenüber Brute-Force tatsächlich nichts
gewonnen und müssten die ganzen 30^30 möglichen Summen durchorgeln. Aber
wie müsste die Matrix beschaffen sein, damit dieser Fall eintritt?
Erste Idee: Wir befüllen sie systematisch mit Zweierpotenzen (2^0, 2^1,
2^2, ..., 2^899). Jetzt könnte man tatsächlich keine zwei Teilsummen mit
dem gleichen Ergebnis finden; die Bildung von Klassen nutzt uns also
nichts. Damit dieser Fall auftreten kann müsste das System allerdings
mit 900 Bit breiten Zahlen arbeiten. Das ist nun auch nicht gerade eine
realistische Annahme.
Zweite Idee für eine Worst Case Matrix: Bis jetzt noch keine. Fällt
jemand anderem etwas ein?
Kurzum, wenn man mal davon ausgeht (Achtung, reine Spekulation!), das
die 30x30 Matrix derart beschaffen ist, das beim Rechnen mit 32 Bit
breiten Zahlen keine Bereichsüberschreitungen auftreten, dann ist die
Anzahl der Äquivalenzklassen auf 2^32 beschränkt. Das ist zwar nicht
wenig, ermöglicht es uns aber auch im WC immer noch mit sehr viel
weniger Summenbildungen auszukommen, als das bei Brute-Force u.a. der
Fall ist.
Edit: Gerade eingefallen: Offenbar kann man die Matrix für den WC auch
mit Fibonacci-Zahlen befüllen. Wobei Fib(900) aber trotzdem noch
jenseits von gut und böse ist...
A. H. schrieb:> Possetitjel schrieb:>> Im vorliegenden Falle nicht. Wenn der Definitionsbereich>> für alle Elemente 0..N_max ist, lassen sich aus zwei>> Zeilen maximal 2 * N_max Äquivalenzklassen bilden, ...>> Das stimmt schon, aber wo in der Aufgabe steht denn> geschrieben, dass die Elemente der Matrix derart> eingeschränkt werden können?
Jaja. Haarespalten ist doch etwas Großartiges, besonders wenn
das Mikroskop von Carl Zeiss ist...
Es ist natürlich richtig. Mein erster Satz darf nicht lauten
"Im vorliegenden Falle nicht.", er muss lauten: "Im vorliegenden
Falle möglicherweise nicht."
Wenn man sich bemüht, eine gewisse kommunikative Kompetenz
zu simulieren, dann fällt im Ursprungsartikel auf, dass die
Beispielmatrix 20 Elemente enthält, die alle
- ganzzahlig
- positiv
- kleiner/gleich 40 sind.
Unter der - aus der Luft gegriffenen, aber m.E. sinnvollen -
Annahme, dass das Beispiel einen typischen Fall wiedergibt,
habe ich vermutet, dass alle Matrizen des Fragestellers
aus
- ganzzahligen
- positiven
- nach oben "sinnvoll" beschränkten
Elementen bestehen.
Das ist aber eine Annahme. Insofern ist die Kritik berechtigt.
Michael H. schrieb:> Erste Idee: Wir befüllen sie systematisch mit Zweierpotenzen> (2^0, 2^1, 2^2, ..., 2^899). Jetzt könnte man tatsächlich> keine zwei Teilsummen mit dem gleichen Ergebnis finden;
Korrekt, aber... Übertreibung :-)
> Zweite Idee für eine Worst Case Matrix: Bis jetzt noch keine.> Fällt jemand anderem etwas ein?
Es genügt, die erste Zeile mit "1, 2, 3 ... 30" zu befüllen;
die zweite mit "31, 62, 93, 124, ...", die dritte entsprechend
mit "961, 1922, 2883, ..." usw.
Mit einer länglichen Argumentation, die ich jetzt nach der
Nachtschicht und zwei Bier nicht tippen möchte, kann man die
Wortlänge auf ungefähr 150bit nach oben abschätzen.
Possetitjel schrieb:> Unter der - aus der Luft gegriffenen, aber m.E. sinnvollen -> Annahme, dass das Beispiel einen typischen Fall wiedergibt,> habe ich vermutet, dass alle Matrizen des Fragestellers> aus> - ganzzahligen> - positiven> - nach oben "sinnvoll" beschränkten> Elementen bestehen.>> Das ist aber eine Annahme. Insofern ist die Kritik berechtigt.
Und deshalb wiederhole ich jetzt hier nochmals meine Frage
W A R U M?
Oder, mit etwas mehr kommunikativer Kompetenz:
Was ist die Aufgabe hinter der Aufgabe?
Oliver
Possetitjel schrieb:> Es genügt, die erste Zeile mit "1, 2, 3 ... 30" zu befüllen;> die zweite mit "31, 62, 93, 124, ...", die dritte entsprechend> mit "961, 1922, 2883, ..." usw.> Mit einer länglichen Argumentation, die ich jetzt nach der> Nachtschicht und zwei Bier nicht tippen möchte, kann man die> Wortlänge auf ungefähr 150bit nach oben abschätzen.
Also i = 1..30, j = 1..30, matrix[j, i] = 31^(j - 1) * i
damit wäre das letzte Element 31^29 * 30 ~ 2^148.6
@Possetitjel
@Michael H.
Das Programm, was ich oben geschrieben habe, sollte nicht mehr sein, als
eine kleine Fingerübung vor dem Schlafengehen, mit Ziel, dem TO einen
grundsätzlichen Lösungsansatz und etwas Futter zum Nachdenken
anzubieten. Es war nie meine Absicht, eine optimale Lösung zu liefern.
Angesichts der begrenzten Information, die die Aufgabenstellung liefert,
halte ich das auch gar nicht für möglich.
Was Ihr schreibt ist alles richtig und die Gedankengänge sind
ausgesprochen interessant, nur bleibt leider alles Schall und Rauch,
solange wir nicht wissen, wo die Zahlen her kommen und welche
Einschränkungen realistisch sind. Wir wissen ja noch nicht einmal, ob
wir uns auf ganze, positive Zahlen beschränken können oder auch mit
Brüchen und negativen Werten rechnen müssen (deshalb zum Beispiel ganz
bewusst Templates und auch kein Abbruch der Rekursion bei sum > target).
Ohne solches Wissen bleibt die ganze Diskussion rein akademisch. Das mag
zwar interessant sein, aber irgendwie fehlt mir dafür gerade die Zeit
und ein wenig wohl auch die Motivation.
A. H. schrieb:> @Possetitjel> @Michael H.>> Es war nie meine Absicht, eine optimale Lösung zu liefern.> Angesichts der begrenzten Information, die die Aufgabenstellung liefert,> halte ich das auch gar nicht für möglich.
Ja, das ist allen klar, denke ich mal. Persönlich kann ich deinen
Standpunkt auch völlig nachvollziehen; ich teile ihn jedoch nicht. Ich
denke nach wie vor, das wir gar keine "unrealistischen" Einschränkungen
vorauszusetzen brauchen um auf "vernünftige" Ergebnisse zu kommen - aber
das ist halt auch nur meine eigene, subjektive Bewertung der Lage.
Schätze falls der TE uns noch zuliest muß er ab hier halt selber sehen
was er macht. Und jetzt ab in den Biergarten. Prost! ;-)
Oliver S. schrieb:
>Das schon. Bleibt die im solchen Fäälen immer zu stellende Frage:> W A R U M ?
Die Antwort ist nicht wirklich spektakulär.
Ich spiele ein Browsergame (staemme.ch), bei dem man ein Dorf ausbauen
kann. Jedes Gebäude hat eine bestimmte Anzahl Ausbaustufen und alles was
ich möchte ist ein Rechner zu programmieren, bei dem man eine
Endpunktzahl eingeben kann und danach erscheinen alle Möglichkeiten um
das Dorf soweit auszubauen bis diese Punktzahl erreicht ist.
Die Daten der Matrix:
http://help.staemme.ch/wiki/Punktetabelle/Gesamt
Da ich in der Lehre als Elektroniker bin, beherrsche ich die
Programmierkunst (und Mathe ;P ) einwenig. Aber für diese Problem kenne
ich nur die Holzhammer Lösungsmethode. Und da ich lernwillig bin
verfolge ich diese Diskussion auch weiter
Possetitjel schrieb:> Unter der - aus der Luft gegriffenen, aber m.E. sinnvollen -> Annahme, dass das Beispiel einen typischen Fall wiedergibt,> habe ich vermutet, dass alle Matrizen des Fragestellers> aus> - ganzzahligen> - positiven> - nach oben "sinnvoll" beschränkten> Elementen bestehen.
Korrekt. In der Matrix sind nur ganzzahlige, positive (mit Null) Zahlen
bis maximal 2000.
A. H. schrieb:> Das Programm, was ich oben geschrieben habe, sollte nicht> mehr sein, als eine kleine Fingerübung vor dem Schlafengehen,> mit Ziel, dem TO einen grundsätzlichen Lösungsansatz und> etwas Futter zum Nachdenken anzubieten.
Meine erste Antwort ist grantiger geraten als angemessen. Ich
bitte um Entschuldigung. Ich wollte Deine Absichten nicht in
Zweifel ziehen.
> Es war nie meine Absicht, eine optimale Lösung zu liefern.> Angesichts der begrenzten Information, die die Aufgabenstellung> liefert, halte ich das auch gar nicht für möglich.
Das ist sicherlich richtig. - Vermutlich haben wir einfach einen
sehr unterschiedlichen Blick auf das Problem. Ich finde es extrem
faszinierend, welche Überlegungen man an recht simple Abzähl-
Argumente knüpfen kann:
Aus den bisher bekannten Angaben lässt sich die Anzahl der
Äquivalenzklassen mit 10^5 nach oben abschätzen. Die Anzahl der
verschiedenen Auswahlmöglichkeiten der Matrix-Elemente ist aber
30^30 ~= 10^44 (für eine 30x30-Matrix). Eine Äquivalenzklasse ist
also im Mittel mit 10^(44-5) ~= 10^39 Varianten besetzt.
Was - um Gottes Willen - will der junge Mann mit 10^39 Varianten,
sein Dorf auszubauen, anfangen?
> Wir wissen ja noch nicht einmal, ob wir uns auf ganze, positive> Zahlen beschränken können oder auch mit Brüchen und negativen> Werten rechnen müssen [...]
Das ist richtig - aber ich finde das nicht so wesentlich. Mit
z.B. 32Bit-Fließkommazahlen kann man GARANTIERT höchstens 2^32
verschiedene Maschinenzahlen darstellen. Mehr Information ist
in den Bits nicht drin - egal, wie man sie interpretiert.
Es gibt also MIT SICHERHEIT höchstens 4*10^9 Äquivalenzklassen.
> Ohne solches Wissen bleibt die ganze Diskussion rein akademisch.> Das mag zwar interessant sein, aber irgendwie fehlt mir dafür> gerade die Zeit und ein wenig wohl auch die Motivation.
Ach... das geht mir deutlich anders. Im ersten Moment sah es so
aus, als ob der Berechnungsaufwand für 30^30 Varianten nicht
sinnvoll zu leisten ist. Inzwischen stelle ich mir vor, wie nach
2h Rechenzeit die Ausschrift erscheint:
"19274801724803707134981248037032 Varianten gefunden. Alle auflisten?"
Michaels Testergebnisse deuten zumindest in diese Richtung :)
chrisHome schrieb:> alles was ich möchte ist ein Rechner zu programmieren,> bei dem man eine Endpunktzahl eingeben kann und danach> erscheinen alle Möglichkeiten um das Dorf soweit> auszubauen bis diese Punktzahl erreicht ist.
Hast Du Dir das wirklich gut überlegt?
"Sei vorsichtig mit Deinen Wünschen - sie könnten in
Erfüllung gehen" (angeblich asiatisch)
> Korrekt. In der Matrix sind nur ganzzahlige, positive> (mit Null) Zahlen bis maximal 2000.
Okay. - Folgendes: Wenn Du 30 (ganze, nichtnegative) Zahlen
zwischen 0 und 2000 addierst, liegt, je nach Auswahl der
Zahlen, die Summe immer zwischen 0 und 60'000.
Es gibt aber ungefähr 10^44 Möglichkeiten, die 30 Elemente aus
der 30x30-Matrix auszuwählen. Da auch bei JEDER BELIEBIGEN
Auswahl der Matrixelemente IRGEND eine Summe herauskommt,
müssen sich die 10^44 Möglichkeiten der Elemente-Auswahl
irgenwie auf die 60'000 Summen aufteilen. Sollte eine Summe
gar nicht vorkommen, müssen andere desto häufiger sein.
Wenn Dein Zielwert nicht vorkommt, weißt Du, dass es eben
nicht geht. Wenn für Deinen Zielwert 5 oder 50 Varianten
angegeben werden, kannst Du Dir diese auflisten lassen, das
ist kein Problem. Beides ist möglich, aber unwahrscheinlich.
Was machst Du in dem - äußerst wahrscheinlichen - Falle,
dass es 187263487 oder 91327491248370920 oder
91287491274870124739093479012 Varianten gibt?
Um das Ganze etwas zu konkretisieren: Wenn ich die oben verlinkte Matrix
richtig interpretiert habe, dann gibt es 7.244.353.958.776.958.976 (~
10^18) verschiedene Möglichkeiten die Bauwerke zu kombinieren. Das
angehängte Diagramm zeigt die Anzahl der Möglichkeiten für die
Zielsummen von 1-500 - und man ahnt schon, das man auf diese Weise auf
keinen grünen Zweig kommt.
Ich kenne das Spiel zwar nicht, aber irgendwie liegt es doch nahe
ersteinmal ein Maß für die Güte einer Lösung zu entwickeln (aus
Baukosten, Bauzeit, strategischem Wert etc), damit man nicht ständig
alle 10^x Einzellösungen betrachten muß. Und wenn man das hat, dann
ergeben sich möglicherweise auch bessere Lösungansätze - Branch and
Bound oder Lagrange Multiplikatoren oder weiss der Henker was...
Noch besser wäre es allerdings wenn du dir eine andere Möglichkeit
ausdenkst um an die Spitze der Highscore zu gelangen. ;-)
Michael H. schrieb:> Ich kenne das Spiel zwar nicht, aber irgendwie liegt es doch nahe> ersteinmal ein Maß für die Güte einer Lösung zu entwickeln (aus> Baukosten, Bauzeit, strategischem Wert etc),
Ja klar, das ist so. Unterdessen bin ich im oberen Drittel der Rangliste
:D
Es gibt halt verschiedene Anforderungen an die Dörfer. Einige sind
Offensiv und Deffensiv ausgelegt. Da der Gegner nicht erkennen soll wo
welche Dörfer sind sollen alle die gleiche Punktzahl haben.
Possetitjel schrieb:> "19274801724803707134981248037032 Varianten gefunden. Alle auflisten?"
Was natürlich möglich wäre, dass ich einige Gebäude vordefiniere oder
zumindest die Ausbaustufen eingrenze....
Thread beobachten
Seitenaufteilung abschalten