www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Wettbewerbe" - Makro für Problem
Makro für Problem < Wettbewerbe < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Wettbewerbe"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Makro für Problem: 16 Zahlen
Status: (Frage) beantwortet Status 
Datum: 17:59 Di 09.03.2010
Autor: Ferma

Hallo Programmierer,
gesucht 16 Zahlen von 1 bis 100. Mit je 2 von diesen sollen mittels Addition alle Zahlen von 1 bis 100 gebildet werden können. Ich denke an ein Array mit 17 Zahlen(die 0 ist auch dabei) Dieses Array soll verändert werden, bis die richtigen Zahlen gefunden sind. Initialisiert wird das Array mit plausibeln Werten. Die ersten beiden Zahlen sind sicher:0 und 1; a(2)= 2 bis3,; a(3)=3 bis 5; a(4)=4 bis......a(16)=45 bis 80; a(17)=50 bis90. Das nächste Element ist stets größer. Ich habe es mit brute force versucht, leider...Vielleicht hat jemand Spaß daran...
Gruß, Ferma


        
Bezug
Makro für Problem: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 23:22 Di 09.03.2010
Autor: Karl_Pech

Hallo Ferma,


Ich denke nicht, daß es möglich ist, jede Zahl von 1 bis 100 alleine durch die Addition von jew. zwei aus insg. 16 Zahlen darzustellen. Betrachte z.B. folgendes Python-Programm:


1: from math import floor
2:
3: f = open('out.txt','w')
4:
5: bfoundsmallestsolution = False
6:
7: for g in range(8):
8:  bfoundsmallestsolution = False
9:  for a in range(floor(g/2),g+1):
10:   if not bfoundsmallestsolution:
11:    for b in range(floor(g/2)+1):
12:     if a+b==g:
13:      #bfoundsmallestsolution = True
14:      print(g,a,b,file=f)
15:      break
16:   else:
17:       break
18:  print('\n',file=f)
19:
20: f.close()



Kommentiert man 'bfoundsmallestsolution = True' aus, so daß das Programm alle Lösungstupel für eine Zahl ausgibt, erhält man:


0 0 0


1 1 0


2 1 1
2 2 0


3 2 1
3 3 0


4 2 2
4 3 1
4 4 0


5 3 2
5 4 1
5 5 0


6 3 3
6 4 2
6 5 1
6 6 0


7 4 3
7 5 2
7 6 1
7 7 0


8 4 4
8 5 3
8 6 2
8 7 1
8 8 0


Jetzt sieht man, daß man weniger Summanden braucht, wenn man kleinere Summanden nimmt. Z.B. könnte man 0 = 0+0, 1=1+0 und 2=2+0 schreiben und erhält eine Liste mit 3 Summanden {0,1,2}. Besser ist es jedoch 2=1+1 zu schreiben, so daß die Liste ein Element weniger enthält. Und man sieht, daß sich das für die anderen Zahlen fortsetzt. Läßt man das Programm deshalb nur nach den kleinsten Summanden suchen, indem man 'bfoundsmallestsolution = True' wieder in den Code einfügt, erhält man Folgendes:


0 0 0

1 1 0

2 1 1

3 2 1

4 2 2

5 3 2

6 3 3

7 4 3

8 4 4


Für die Zahlen 0 bis 8 braucht man also die Summanden 0 bis 4. Weniger geht nicht, denke ich. Für die Zahlen 1 bis 100 sind es dann min. 50 Summanden, wenn ich das Programm damit laufen lasse. Nur allgemein beweisen, daß man bei [mm]n\![/mm] Zahlen mindestens [mm]\approx\tfrac{n}{2}[/mm] Summanden zur Darstellung braucht, konnte ich nicht. Dabei müßte das doch eigentlich sehr einfach zu beweisen sein... [kopfschuettel]



Viele Grüße
Karl




Bezug
                
Bezug
Makro für Problem: Korrektur
Status: (Frage) beantwortet Status 
Datum: 08:15 Mi 10.03.2010
Autor: Ferma

Hallo Karl,
tatsächlich soll es heißen "mit maximal 2 Zahlen". Beispiel: 1=1; 2=1+1; 3=3; 4=2+2; 5=5;
Sieh Dir bitte das an: Eine harte Nuß zum Wochenende +Spotlight (in google eingeben)
Gruß, Ferma

Bezug
                        
Bezug
Makro für Problem: allgemeineres Problem
Status: (Frage) beantwortet Status 
Datum: 10:28 Mi 10.03.2010
Autor: Karl_Pech

Man könnte die Aufgabe ja auch allgemeiner formulieren... :-)


Aufgabe
Gegeben: [mm]\mathcal{B}\subset\mathbb{N}_0[/mm] mit [mm]2\leqslant\left|\mathcal{B}\right|<\infty,\ 0\in\mathcal{B}[/mm] und [mm]\forall\gamma\in\mathcal{B}\setminus\{0\}\exists\delta\in\mathcal{B}:\gamma=\delta+1[/mm].

Gesucht: Ein Algorithmus, der so schnell wie möglich (zumindest besser als Brute-Force) ein [mm]A\subseteq\mathcal{B}[/mm] bestimmen kann, für das Bedingung [mm]\alpha[/mm] erfüllt ist: [mm]\forall x\in\mathcal{B}\,\exists a,b\in A:a+b=x[/mm].
Dabei soll es kein [mm]\widetilde{A}\subseteq\mathcal{B}[/mm] geben mit [mm]\left|\widetilde{A}\right|<\left|A\right|[/mm] für das Bedingung [mm]\alpha[/mm] gilt.


Ich denke, ich verschiebe diese Diskussion nun ins Forum Informatik -> Wettbewerbe, da ich jetzt selber gespannt bin, wer diese Frage beantworten kann. Ich kann's jedenfalls ( (noch (?) ) nicht.

Bezug
                                
Bezug
Makro für Problem: Antwort
Status: (Antwort) fertig Status 
Datum: 04:02 Di 15.06.2010
Autor: felixf

Moin!

> Man könnte die Aufgabe ja auch allgemeiner formulieren...
> :-)
>  
>
> Gegeben: [mm]\mathcal{B}\subset\mathbb{N}_0[/mm] mit
> [mm]2\leqslant\left|\mathcal{B}\right|<\infty,\ 0\in\mathcal{B}[/mm]
> und
> [mm]\forall\gamma\in\mathcal{B}\setminus\{0\}\exists\delta\in\mathcal{B}:\gamma=\delta+1[/mm].

Sprich: [mm] $\mathcal{B} [/mm] = [mm] \{ 0, 1, \dots, n \}$ [/mm] fuer $n [mm] \ge [/mm] 1$.

> Gesucht: Ein Algorithmus, der so schnell wie möglich
> (zumindest besser als Brute-Force) ein

Die Frage ist, was genau du unter Brute Force verstehst. Brute Force mit Pruning ist wesentlich schneller als "normales" Brute Force, aber immer noch "langsam" (superexponentiell in $n$).

Hier ein paar Beobachtungen, die beim prunen helfen. Sei [mm] $(a_1, \dots, a_m)$ [/mm] eine Loesung mit [mm] $a_1 [/mm] < [mm] \dots [/mm] < [mm] a_m$. [/mm]

* Es gilt [mm] $a_0 [/mm] = 0$ und [mm] $a_1 [/mm] = 1$.

* Ist die Loesung minimal (also $m$ minimal), so gilt [mm] $a_i \le [/mm] n - (m - i)$.

* Wenn man sich [mm] $a_1, \dots, a_i$ [/mm] anschaut, und von diesen $k$ Zahlen aus [mm] $\{ 0, \dots, n \}$ [/mm] nicht abgedeckt werden, so muss $k [mm] \le \frac{m (m + 1)}{2} [/mm] - [mm] \frac{i (i + 1)}{2}$ [/mm] sein.

* Es muss [mm] $a_m [/mm] + [mm] a_m \ge [/mm] n$ sein, also [mm] $a_m \ge \bigl\lceil \frac{n}{2} \bigr\rceil$. [/mm]

* Es muss [mm] $a_m [/mm] + [mm] a_{m-1} \ge [/mm] n - 1$ sein, also [mm] $a_m \ge [/mm] n - 1 - [mm] a_{m-1}$. [/mm]

LG Felix


Bezug
                                
Bezug
Makro für Problem: Antwort
Status: (Antwort) fertig Status 
Datum: 22:01 So 27.06.2010
Autor: felixf

Moin!

> Man könnte die Aufgabe ja auch allgemeiner formulieren...
> :-)
>  
>
> Gegeben: [mm]\mathcal{B}\subset\mathbb{N}_0[/mm] mit
> [mm]2\leqslant\left|\mathcal{B}\right|<\infty,\ 0\in\mathcal{B}[/mm]
> und
> [mm]\forall\gamma\in\mathcal{B}\setminus\{0\}\exists\delta\in\mathcal{B}:\gamma=\delta+1[/mm].
>  
> Gesucht: Ein Algorithmus, der so schnell wie möglich
> (zumindest besser als Brute-Force) ein
> [mm]A\subseteq\mathcal{B}[/mm] bestimmen kann, für das Bedingung
> [mm]\alpha[/mm] erfüllt ist: [mm]\forall x\in\mathcal{B}\,\exists a,b\in A:a+b=x[/mm].
>  
> Dabei soll es kein [mm]\widetilde{A}\subseteq\mathcal{B}[/mm] geben
> mit [mm]\left|\widetilde{A}\right|<\left|A\right|[/mm] für das
> Bedingung [mm]\alpha[/mm] gilt.
>  
> Ich denke, ich verschiebe diese Diskussion nun ins Forum
> Informatik -> Wettbewerbe, da ich jetzt selber gespannt
> bin, wer diese Frage beantworten kann. Ich kann's
> jedenfalls ( (noch (?) ) nicht.

Ich bin mal etwas genauer auf Suche gegangen, und hab mit meinem Programm geschaut, ab welchem $n$ man [mm] $|\mathcal{B}|$ [/mm] um eins erhoehen muss. Dabei kam der Anfang der Sequenz []A001212 in Sloanes Integer Sequence Encyclopedia heraus.

Das []Postage Stamp Problem ist aehnlich zu unserem Problem mit $h = 2$, mit dem Unterschied dass 0 kein Element der Menge sein muss (darf), da man auch null oder einen Summanden verwenden kann.

Es wurde uebrigens []gezeigt, dass dieses Problem NP-hart ist, insofern wird es wohl keine Loesung mit sub-exponentieller oder gar polynomieller Laufzeitkomplexitaet geben. Damit ist diese Frage zumindest teilweise beantwortet.

LG Felix


Bezug
        
Bezug
Makro für Problem: Bruteforce methode
Status: (Antwort) fertig Status 
Datum: 21:45 So 21.03.2010
Autor: Event_Horizon

Hallo!

ich habe jetzt tatsächlich mal ein Bruteforce-programm geschrieben.
Es gibt ein Array von 16 Elementen, die allesamt mit 1 initialisiert werden.

Es wird getestet, ob sich die Zahlen 1-100 aus ein bis zwei Zahlen des Arrays bilden lassen.

Dann wird die erste Zahl im Array um 1 vergrößert. Ist die Zahl 101, wird die zweite Zahl vergrößert, und die erste auf den gleichen Wert wie die zweite gesetzt, usw. Es wird also der Reihe nach durchgezählt.

Das Problem ist nur die Rechenzeit. Mein Rechner rechnet nun schon seit 1,5 Stunden und ist erst bei

95   94   87   86   71   53    3    1    1    1    1    1    1    1    1    1

angekommen. Braucht also noch ein paar tausend Stunden Rechenzeit, wenn nicht irgendwem noch eine geniale Optimierung einfällt.

[a]Link zum 1. Dateianhang

Dateianhänge:
Anhang Nr. 1 (Typ: cpp) [nicht öffentlich]
Bezug
                
Bezug
Makro für Problem: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 21:10 Do 25.03.2010
Autor: Ferma

eine geniale Idee findest Du hier:" Eine harte Nuß zum Wochenende +Spotlight". So bei Google eingeben. Das Programm stammt von Marco und ist jn Java geschrieben. Wenn das jemand in VBA übersetzen könnte...Das funktioniert schneller. Ein paar Lösungen sind dort angegeben
Gruß, Ferma

Bezug
                        
Bezug
Makro für Problem: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 22:46 So 06.06.2010
Autor: felixf

Hallo!

> eine geniale Idee findest Du hier:" Eine harte Nuß zum
> Wochenende +Spotlight". So bei Google eingeben. Das
> Programm stammt von Marco und ist jn Java geschrieben. Wenn
> das jemand in VBA übersetzen könnte...Das funktioniert
> schneller.

Glaubst du ernsthaft, dass ein VBA-Programm schneller ist als ein entsprechendes Java-Programm?

LG Felix


Bezug
        
Bezug
Makro für Problem: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 04:02 Di 15.06.2010
Autor: felixf

Hallo!

>  gesucht 16 Zahlen von 1 bis 100. Mit je 2 von diesen
> sollen mittels Addition alle Zahlen von 1 bis 100 gebildet
> werden können. Ich denke an ein Array mit 17 Zahlen(die 0
> ist auch dabei) Dieses Array soll verändert werden, bis
> die richtigen Zahlen gefunden sind. Initialisiert wird das
> Array mit plausibeln Werten. Die ersten beiden Zahlen sind
> sicher:0 und 1; a(2)= 2 bis3,; a(3)=3 bis 5; a(4)=4
> bis......a(16)=45 bis 80; a(17)=50 bis90. Das nächste
> Element ist stets größer. Ich habe es mit brute force
> versucht, leider...Vielleicht hat jemand Spaß daran...

Ich hab da ein wenig rumprogrammiert, und mein aktuelles Programm braucht 8 Minuten 10 Sekunden, um festzustellen, dass es keine solchen 16 Zahlen gibt (mal angenommen das Programm ist korrekt).

Ich hab mir auch den []anderen Thread angeschaut; die dortigen Loesungen von Marco13 haben alle 17 Zahlen, nicht 16!

Mein Programm sucht nun nach Loesungen mit 17 Zahlen, nach etwas mehr als 7 Minuten hat es schon Fast-Loesungen gefunden, bei denen nur noch eine Zahl fehlt.

LG Felix



PS: Es handelt sich um eine Intel(R) Xeon(TM) CPU mit 2.80GHz.


Bezug
                
Bezug
Makro für Problem: Antwort
Status: (Antwort) fertig Status 
Datum: 05:54 Di 15.06.2010
Autor: felixf

Moin!

> >  gesucht 16 Zahlen von 1 bis 100. Mit je 2 von diesen

> > sollen mittels Addition alle Zahlen von 1 bis 100 gebildet
> > werden können. Ich denke an ein Array mit 17 Zahlen(die 0
> > ist auch dabei) Dieses Array soll verändert werden, bis
> > die richtigen Zahlen gefunden sind. Initialisiert wird das
> > Array mit plausibeln Werten. Die ersten beiden Zahlen sind
> > sicher:0 und 1; a(2)= 2 bis3,; a(3)=3 bis 5; a(4)=4
> > bis......a(16)=45 bis 80; a(17)=50 bis90. Das nächste
> > Element ist stets größer. Ich habe es mit brute force
> > versucht, leider...Vielleicht hat jemand Spaß daran...
>  
> Ich hab da ein wenig rumprogrammiert, und mein aktuelles
> Programm braucht 8 Minuten 10 Sekunden, um festzustellen,
> dass es keine solchen 16 Zahlen gibt (mal angenommen das
> Programm ist korrekt).

Ich hatte mich ein wenig vertan und etwas zu wenig geprunt. Jetzt benoetigt das Programm 14 Sekunden, um zu zeigen, dass es keine Loesung mit 16 Zahlen gibt.

Weiterhin findet es alle Loesungen mit 17 Zahlen innerhalb 25 Minuten; diese sind:

(0, 1, 2, 3, 7, 11, 15, 19, 23, 27, 28, 29, 30, 61, 64, 67, 70)
(0, 1, 3, 4, 5, 8, 14, 20, 26, 32, 38, 44, 45, 47, 48, 49, 52)
(0, 1, 3, 4, 5, 8, 14, 20, 26, 32, 38, 44, 46, 47, 48, 49, 51)
(0, 1, 3, 4, 5, 8, 14, 20, 26, 32, 38, 44, 46, 48, 49, 51, 53)
(0, 1, 3, 4, 5, 8, 14, 20, 26, 32, 38, 44, 47, 48, 49, 51, 52)
(0, 1, 3, 4, 7, 8, 9, 16, 17, 21, 24, 35, 46, 57, 68, 79, 90)
(0, 1, 3, 4, 9, 11, 16, 20, 25, 30, 34, 39, 41, 46, 47, 49, 50)

Dies umfasst alle Loesungen, die Marco13 gepostet hat.

Ich habe mein C++-Programm mal [a]angehaengt; es ist nicht wirklich gut dokumentiert. Es umfasst eine Bit-Vektor-Klasse, die das ganze etwas schneller machen sollte als std::vector<bool>. Der obere Wert $n$ fuer das Intervall ist im Programm einkodiert, dies macht es vermutlich auch noch einen Tacken schneller. Kompilieren laesst es sich mit g++ -O3 -o executable programm.cpp, momentan nur mit dem G++ da ein spezieller GCC-Befehl fuer's Bitzaehlen benutzt wird (das laesst sich wegoptimieren, aber dazu hab ich grad keine Lust).

LG Felix


Dateianhänge:
Anhang Nr. 1 (Typ: cpp) [nicht öffentlich]
Bezug
        
Bezug
Makro für Problem: Wohlklang-Suche
Status: (Antwort) fertig Status 
Datum: 12:56 So 29.08.2010
Autor: Karl_Pech

Hallo Zusammen,


Ich habe nun auch etwas Zeit gefunden mich mit diesem Problem zu beschäftigen. Da Felix das Problem bereits gelöst hat, habe ich zwei Näherungsverfahren ausprobiert, um festzustellen, ob es damit auch lösbar ist. Leider hat sich das Problem gegenüber den klassischen evolutionären Algorithmen als resistent herausgestellt. Ich habe dann ein wenig gesucht und bin auf die []Wohlklang-Suche gestoßen. Ich habe daraufhin eine Variante der []Version von 2001 von diesem Verfahren in Python [a]implementiert.

Das Python-Programm besteht aus zwei Modulen: pereignisgen und wks.

pereignisgen kann ein Ereignis mit einer vorgegebenen Wahrscheinlichkeit $p$ eintreten lassen. (Dann wird 'True' zurückgegeben. D.h. mit W'keit $1-p$ tritt das Ereignis nicht ein und es wird 'False' zurückgegeben.) Die Funktion ereignisgeschieht() schneidet ein vorgegebenes $p$ zunächst auf 5 Stellen nach dem Komma ab und wandelt dieses dann in einen gekürzten Bruch um (Spezialfälle wie $p=1$ und $p=0$ werden berücksichtigt. Alternativ kann $p$ auch als Paar (zaehler, nenner) an die Funktion übergeben werden, wenn man z.B. mit W'keiten wie 1/7 arbeiten möchte. Ich benutze im Übrigen auch Hashing an zwei Stellen, um die Funktion zu beschleunigen.)
Nachdem wir $p$ als ein Paar (zaehler, nenner) vorliegen haben, werden 'zaehler' viele Zufallszahlen ausgewählt. Dazu fangen wir mit einer Liste [1, nenner] an und fügen die erste Zufallszahl ein: [1, z0, nenner]. Danach kommt der nächste Durchlauf [1, z2, z0, z1, nenner] u.s.w. . Dabei wird jede neue Zahl zwischen zwei "Nachbar"zahlen der Liste ausgewählt, wenn zwischen den Nachbarzahlen "genug Platz" ist. Wurde z.B. eine W'keit wie 2/3 übergeben, geschieht folgendes: [1, 3] --> [1, 2, 3]. Jetzt ist kein Platz mehr, um noch eine Zahl einzufügen. Deshalb muß dieser Spezialfall (zaehler == 1) behandelt werden, indem zufällig entweder 1 oder nenner in der Liste belassen werden, also z.B. [2,3]. War jedoch zaehler == 0, werden 1 und nenner aus der Liste gelöscht: [2] (z.B. für [mm] $p=\tfrac{1}{3}$). [/mm]
Zum Schluss wird eine Zufallszahl zwischen 1 und nenner ausgewählt und es wird geprüft, ob diese Zahl in der zaehler-Zufallszahl-Liste vorhanden ist.

Kommen wir nun zu wks. Im 1ten Schritt des Verfahrens wird der sogenannte Wohlklang-Speicher WS initialisiert. Dabei wird entweder ein vorhandener Speicher von einem Speichermedium geladen. Oder aber es wird ein Speicher mit zufälliger Belegung erzeugt.
Der WS besteht aus WSG (WS-Größe) vielen Listen, die alle eine Länge [mm] $N+2\!$ [/mm] haben. In den ersten [mm] $N+1\!$ [/mm] Zellen, werden Zufallszahlen zwischen [mm] $0\!$ [/mm] und [mm] $\left\lfloor\tfrac{x}{2}\right\rfloor$ [/mm] gespeichert, [mm] $\forall x\in\left[0:N\right]$. [/mm] In der [mm] $N+1\texttt{-ten}$ [/mm] Zelle wird die Bewertung der aktuellen [mm] ($y\texttt{-ten}$) [/mm] Liste gespeichert. (Hierbei wird jede Liste im WS als Wohlklang bezeichnet und die Bewertung einer Liste ist demnach eine Hörprobe dieses Wohlklangs. Ein Element der Liste heißt "Note".)
Im 2ten Schritt wird mit der Wohlklang-Speicher-Betrachtungswahrscheinlichkeit (WSBW) ein neuer Wohlklang gänzlich aus den im WS vorhandenen Wohlklängen erzeugt. Dazu wird in der [mm] $x\texttt{-ten}$ [/mm] WS-Spalte zufällig eine Note eines entsprechenden Wohlklangs ausgewählt. Mit der W'keit 1-WSBW wird der neue Wohlklang ganz zufällig erzeugt. Im Nachhinein ist mir jedoch aufgefallen, daß ich diesen Teil des Verfahrens mißverstanden habe. Und zwar sollte eigentlich für jede Note eines neuen Wohlklangs individuell entschieden werden, ob diese mit W'keit WSBW aus dem WS oder ganz zufällig erzeugt wird. Allerdings hat dieses Mißverständnis in meinem Falle dazu geführt, daß das Verfahren sogar besser funktioniert hat. Denn wenn man sich umgekehrt die Frage stellt, wie ein individuelles WSBW gewählt sein sollte, damit alle Noten mit W'keit 0.95 aus dem WS gewählt werden, so müßte [mm] $\operatorname{WSBW}^{101}\stackrel{!}{=}0.95\Leftrightarrow \operatorname{WSBW} \approx [/mm] 0.99949$ gelten. Wenn man also folgenden Code:


1: if ereignisgeschieht(WSBW):
2: for x in range(N+1): 
3: neuerwohlklang.append(WS[randint(0, WSG-1)][x])
4: else:
5: for x in range(N+1):
6: neuerwohlklang.append(randint(0, x//2))


durch Diesen ersetzt:


1: for x in range(N+1):
2: if ereignisgeschieht(WSBW):
3: neuerwohlklang.append(WS[randint(0, WSG-1)][x])
4: else:
5: neuerwohlklang.append(randint(0, x//2))


Und WSBW von 0.95 auf 0.99949 setzt, müßten beide Schleifen die meiste Zeit ungefähr dasselbe leisten. Deshalb habe ich den Code auch nicht mehr verändert. Denn das Verfahren hat von der erhöhten "virtuellen" individuellen WSBW offenbar sehr stark profitiert. (Es scheint, daß für dieses Problem die Ausnutzung vom bereits vorhandenen Wissen ("Exploitation") wesentlich wichtiger ist, als die zufällige Erzeugung neuer Wohlklänge ("Exploration").)

Der 3te Schritt des Verfahrens besteht darin, den schlechtesten Wohlklang des WS durch den neuen Wohlklang zu ersetzen, sofern der neue Wohlklang besser ist. Das Programm prüft alle 20000 Iterationen, ob es sich beenden soll und schreibt gleichzeitig ständig den aktuellen Inhalt des WS auf ein Speichermedium, sowie eine kleine Statistik zur Verteilung der Wohlklänge.

Das Programm und zwei Testläufe dazu befinden sich, wie schon gesagt, im Anhang. Das beste Ergebnis war die Erzeugung von Summandenketten mit 22 Summanden, wie z.B. diese hier:


0 0 0 0 2 2 3 1 0 1 0 5 6 5 6 5 2 3 8 2 10 3 8 6 0 8 8 3 10 5 6 14 0 1 10 17 18 0 14 2 8 17 10 6 1 0 0 1 2 5 1 3 6 8 5 8 10 5 6 10 8 14 14 18 17 18 17 24 24 24 24 24 24 24 37 32 24 32 32 32 37 32 37 37 32 37 43 43 44 44 44 45 43 44 47 46 48 48 49 47 48 : 22


Es gilt also:


0 + 0 = 0, 0 + 1 = 1, 0 + 2 = 2, 0 + 3 = 3, 2 + 2 = 4, u.s.w.



Viele Grüße
Karl





Dateianhänge:
Anhang Nr. 1 (Typ: zip) [nicht öffentlich]
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Wettbewerbe"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de