AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Tutorials Gewichteter Zufall
Tutorial durchsuchen
Ansicht
Themen-Optionen

Gewichteter Zufall

Ein Tutorial von Luckie · begonnen am 6. Mär 2008 · letzter Beitrag vom 10. Mär 2008
Antwort Antwort
Seite 1 von 2  1 2      
Benutzerbild von Luckie
Luckie

Registriert seit: 29. Mai 2002
37.621 Beiträge
 
Delphi 2006 Professional
 
#1

Gewichteter Zufall

  Alt 6. Mär 2008, 11:04
Es gibt einen neuen Artikel auf meiner Homepage zum gewichteten Zufall: http://www.michael-puff.de/Artikel/2...eterzufall.php

Zitat:
Kleine Vorgeschichte oder die Problemstellung

Vor der Zwischenprüfung zum Fachinformatiker für anwendungsentwicklung, wollte unser Lehrer mit uns noch mal ein paar Prüfungsaufgaben durchgehen. Damit nicht immer die selben Schüler drankommen nämlich, jene die die Antwort wissen und sich melden bzw. damit nicht vom Lehrer willkürlich Schüler darngenommen werden, hatte unser Lehrer eine Idee. Und zwar sollten wir in der ersten halben Stunde des Unterrichts ein Programm entwicklen, welches es ihm ermöglichte zufällig einen Schüler auszuwählen, aber mit der Einschränkung, dass ein Schüler, der gerade dran gewesen ist, mit einer geringeren Wahrscheinlichkeit noch mal von dem programm ausgewählt wird, als ein Schüler, der noch keine Frage beantworten musste.

Zusammengefasst sollte also folgendes Programm entwickelt werden: Aus einer Liste von Namen solte zufällig ein Name gezogen werden. bei wiederholtem ziehen eines Namens, soll der zuvor ermittelte Name mit einer geringeren Wahrscheinlichkeit gezogen werden, als ein Name, der noch nicht gezogen wurde.
Angehängte Dateien
Dateityp: zip gewichteterzufall_135.zip (27,7 KB, 27x aufgerufen)
Dateityp: pdf gewichteterzufall_208.pdf (20,4 KB, 50x aufgerufen)
Michael
Ein Teil meines Codes würde euch verunsichern.
  Mit Zitat antworten Zitat
Benutzerbild von stahli
stahli

Registriert seit: 26. Nov 2003
Ort: Halle/Saale
4.352 Beiträge
 
Delphi 11 Alexandria
 
#2

Re: Gewichteter Zufall

  Alt 6. Mär 2008, 12:30
Hallo Luckie,

ich wäre es über mehrfaches Random angegangen:

- Liste mit 30 Schülern
- X := Anzahl Schüler;
- N := 2;
- for I := 1 to N do X := Random(X)
- Treffer := Schüler(X)
- Treffer an das Ende de Liste

Je höher N ist um so frühere Treffer sind zu erwarten.

stahli


PS. Mathe ist mir zu kompliziert
  Mit Zitat antworten Zitat
Benutzerbild von Nikolas
Nikolas

Registriert seit: 28. Jul 2003
1.528 Beiträge
 
Delphi 2005 Personal
 
#3

Re: Gewichteter Zufall

  Alt 6. Mär 2008, 13:34
Bei dieser Idee hängt aber das Ergebnis von der Initalisierung der Liste ab.
In der Aufgabenstellung wird aber verlangt, dass nur derjenige, der als letzter geantwortet hat, eine kleinere Wahrscheinlichkeit hat als alle anderen. Das ist somit nicht gegeben.
Auch ist es so, dass man nach einer Antwort für die nächsten paar Fragen immer noch eine geringere Wahrscheinlichkeit hat, da man erst wieder in den höheren Bereich der Liste geschoben werden muss.

Die Idee mit der Wurzel ist zwar nett, aber erfüllt nicht ganz die Aufgabenstellung.
Erwarte das Beste und bereite dich auf das Schlimmste vor.
  Mit Zitat antworten Zitat
Benutzerbild von Khabarakh
Khabarakh

Registriert seit: 18. Aug 2004
Ort: Brackenheim VS08 Pro
2.876 Beiträge
 
#4

Re: Gewichteter Zufall

  Alt 6. Mär 2008, 13:45
Was imo aus dem Artikel nicht ganz klar wird: deine Lösung benachteiligt ja nicht die Schüler, die sich oft gemeldet haben, sondern die, die sich vor kurzem gemeldet haben.
Ich denke einmal, dass es so auch gedacht war; um jedenfalls Ersteres zu erreichen, müsste jedem Schüler nur eine Auswahl-Wahrscheinlichkeit p zugeordnet werden, die bei n Schülern anfangs 1 / n beträgt. Wenn er dann nach einer Meldung z.B. nur noch halb so oft aufgerufen werden soll, muss natürlich erst einmal seine eigene Wahrscheinlichkeit p1 um 50% gesenkt und zusätzlich die Wahrscheinlichkeiten aller anderen Schüler um .5 * p1 / (n - 1) erhöht werden. Die Auswahlfunktion könnte dann so aussehen:
Delphi-Quellcode:
// Rückgabewert: Index des gewählten Eintrags
// Summe der Wahrscheinlichkeiten sollte 1 betragen
function RandomItem(aProbabilities: array of Real): Integer;
var
  r: Real;
begin
  r := Random;
  Result := 0;
  while Result < Length(aProbabilities) do
  begin
    r := r - aProbabilities[Result];
    if r < 0 then
    begin
      Dec(Result);
      Exit;
    end;
    Inc(Result);
  end;
  Dec(Result); // im Zweifelsfall der letzte Eintrag
end;
[add]
Zitat von Nikolas:
In der Aufgabenstellung wird aber verlangt, dass nur derjenige, der als letzter geantwortet hat, eine kleinere Wahrscheinlichkeit hat als alle anderen. Das ist somit nicht gegeben.
Könnte man so verstehen, aber die Aufgabenstellung ist unklar:
Zitat:
dass ein Schüler, der gerade dran gewesen ist, mit einer geringeren Wahrscheinlichkeit noch mal von dem programm ausgewählt wird, als ein Schüler, der noch keine Frage beantworten musste.
Es wird nichts über die Schüler ausgesagt, die schon einmal früher dran waren. Deshalb würde ich die Aufgabenstellung auch nicht zu wörtlich nehmen, es bleibt also ein ziemlicher Spielraum für Deutungen.
[/add]
Sebastian
Moderator in der EE
  Mit Zitat antworten Zitat
Medium

Registriert seit: 23. Jan 2008
3.687 Beiträge
 
Delphi 2007 Enterprise
 
#5

Re: Gewichteter Zufall

  Alt 6. Mär 2008, 13:52
Bei gewichtetem Zufall habe ich spontan an eine Zuordnungsliste gedacht. Alle Personen bekommen einen je gleich großen Zahlenbereich zwischen 0 und 1 zugewiesen. Mit einer Zufallszahl geht man dann in diese Liste, und schaut in wessen Bereich sie liegt. Anschließend wird die Liste neu Aufgebaut, wobei der Bereich der zuletzt gezogenen Person um einen Faktor verkleinert wird, während die Bereiche der anderen prozentual gleichmäßig vergrößert werden, so dass alle Bereich in Summe wieder 1 ergeben.
Das System ist allerdings dann gesprengt, wenn jemand so oft hintereinander gezogen wird, dass sein Bereich 0 wird (dank Ungenauigkeiten von Floats). Die Wahrscheinlichkeit dafür dürfte aber sehr gering sein, und ließe sich durch Einführen eines Minimums leicht beheben.
Dies ließe sich sogar finetunen, da man über den Faktor bestimmen kann, wie stark ein gezogener "bestraft" werden soll, und sogar ob dies linear, prozentual, oder nach welchem Gesetz auch immer statt finden soll. Ebenso ist die Verteilung des frei gewordenen Bereichs anpassbar, so dass z.B. jemand mit großem Bereich stärker profitieren würde als jemand im Mittelfeld.

Was ein solches Verfahren generell bewirkt ist, dass die Gleichverteilung auf alle Zufallszahlen eines Seeds bereits für eine kleinere Untermenge wählbar schnell forciert wird.
"When one person suffers from a delusion, it is called insanity. When a million people suffer from a delusion, it is called religion." (Richard Dawkins)
  Mit Zitat antworten Zitat
Benutzerbild von sirius
sirius

Registriert seit: 3. Jan 2007
Ort: Dresden
3.443 Beiträge
 
Delphi 7 Enterprise
 
#6

Re: Gewichteter Zufall

  Alt 6. Mär 2008, 14:20
Durch die Wurzel hast du einfach eine quadratische Verteilungsfunktion abgebildet.

Edit (wurde grad rausgerissen):
Ich wollte noch ergänzen, dass dies eine lineare Dichtefunktion ergibt. Also anstatt der Glockenkurve bei der Normalverteilung, hast du eine lineare Funktion.
Dieser Beitrag ist für Jugendliche unter 18 Jahren nicht geeignet.
  Mit Zitat antworten Zitat
Benutzerbild von Luckie
Luckie

Registriert seit: 29. Mai 2002
37.621 Beiträge
 
Delphi 2006 Professional
 
#7

Re: Gewichteter Zufall

  Alt 9. Mär 2008, 13:09
Zitat von sirius:
Durch die Wurzel hast du einfach eine quadratische Verteilungsfunktion abgebildet.
Bist du da sicher? Es müsste eine nach rechts verschobene Normalverteilung sein, bei der die Werte auf der linken Seite sanft ansteigen und dann auf der rechten Seite steil abfallen.

Zitat:
Ich wollte noch ergänzen, dass dies eine lineare Dichtefunktion ergibt. Also anstatt der Glockenkurve bei der Normalverteilung, hast du eine lineare Funktion.
Hast du mal Grafiken dafür parat?
Michael
Ein Teil meines Codes würde euch verunsichern.
  Mit Zitat antworten Zitat
Benutzerbild von sirius
sirius

Registriert seit: 3. Jan 2007
Ort: Dresden
3.443 Beiträge
 
Delphi 7 Enterprise
 
#8

Re: Gewichteter Zufall

  Alt 10. Mär 2008, 09:46
Grafiken? Schwer.

Wenn du dir die beiden Bilder auf Seite 1 ansiehst. Dann hast du links die dichtefunktion und rechts die Verteilungsfunktion. Von links nach rechts kommst du über Integration (was auch in der Formel untendrunter steht) und von rechts nach links über Differentation.
Wenn du für eine bestimmte Verteilung einen zufälligen Wert haben möchtest, dann nimmst du dir die Verteilungsfunktion (rechts) und einen gleichverteilten Zufallswert (random von 0 bis 1). Mit diesem Wert gehst du in die y-Achse der Verteilungsfunktion und liest den x-Wert ab. Fertig.

Das bedeutet, du bildest mathematisch die Umkehrfunktion der Verteilungsfunktion. Wenn du jetzt als Umkehrfunktion der Verteilung eine Wurzelfunktion hast, ist die Verteilungsfunktion selbst eine quadratische. Und damit ist die Dichtefunktion (Ableitung der quadratischen Funktion) linear.
Dieser Beitrag ist für Jugendliche unter 18 Jahren nicht geeignet.
  Mit Zitat antworten Zitat
Benutzerbild von Luckie
Luckie

Registriert seit: 29. Mai 2002
37.621 Beiträge
 
Delphi 2006 Professional
 
#9

Re: Gewichteter Zufall

  Alt 10. Mär 2008, 09:50
Ah, ok, dann habe ich jetzt zumindest eine Erklärung. Mit dem Verstehen hapert es noch ein wenig, aber das ist Licht am Horizont.
Michael
Ein Teil meines Codes würde euch verunsichern.
  Mit Zitat antworten Zitat
Benutzerbild von Jelly
Jelly

Registriert seit: 11. Apr 2003
Ort: Moestroff (Luxemburg)
3.741 Beiträge
 
Delphi 2007 Professional
 
#10

Re: Gewichteter Zufall

  Alt 10. Mär 2008, 10:35
Jetzt bewegen wir uns bereits ganz nah am elementaren Standbein der Monte Carlo Simulation. Auch dort wird mit Verteilerfunktionen gearbeitet. Da das mal Thema meiner Diplomarbeit war, hätte ich dazu auch einiges an Dokumentation. Wenns denn interessiert, so kann ich dazu heut abend was hier ins Forum schreiben.
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 2  1 2      


Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 04:39 Uhr.
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024-2025 by Thomas Breitkreuz