| |
| Autor |
 Greedy Algorithmus |
|
derechteChickenWing
Aktiv 
Dabei seit: 24.06.2020
Mitteilungen: 39
 |
Meine Tabelle
So wie ich es verstehe sind die 120 Punkte das höchste was man erreichen kann oder ?
|
 Notiz  Profil
 Quote
 Link |
DerEinfaeltige
Senior 
Dabei seit: 11.02.2015
Mitteilungen: 2622
 |      Beitrag No.1, eingetragen 2020-11-29
|
Ja, 120 ist im Beispiel das beste Ergebnis.
Hier könnte man ja sogar per Bruteforce alle möglichen Strategien durchspielen.
Du sollst jetzt einen Greedy-Algorithmus angeben, der die optimale Strategie für ein beliebiges Problem berechnet.
-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -
|
Notiz Profil
Quote
Link |
derechteChickenWing
Aktiv
Dabei seit: 24.06.2020
Mitteilungen: 39
| Beitrag No.2, vom Themenstarter, eingetragen 2020-11-30
|
Reicht das als Algorithmus ?
Wenn der Computer die größte Karte aus seinem Stapel (in diesem Fall 100) einsetzt, setze ich die kleinste Zahl in meinem Fall die 1.
Wenn der Computer die Karte 5 einsetzt setze die gleiche Karte
Am Ende addiere die gewonnenen Punkte
|
Notiz Profil
Quote
Link |
Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 6652
Herkunft: Niedersachsen
| Beitrag No.3, eingetragen 2020-11-30
|
Nein, das reicht nicht als Algorithmus, da das vorgehen im Allgemeinen nicht optimal ist.
Ein sehr einfacher (aber nicht optmaler) Algorithmus wäre:
a) Wenn Du den Gegner nicht schlagen kannst, dann lege die kleinste Karte, die Du hast (das ist optimal).
b) Wenn Du den Gegner schlagen kannst, dann schlage ihn mit der kleinstmöglichen Karte.
Für diesen Algorithmus müsste man nichtmal die Karten des Gegners kennen. Er ist aber nicht optimal, was am Teil b) liegt.
Hat man selbst die 2 und die 100, während der Gegner 1 und 101 hat, dann ist es nicht optimal, die 1 mit der 2 zu nehmen. Man sollte dafür die 100 wählen, weil die mehr Punkte bringt.
Daraus kann man jetzt einen tatsächlich optimalen Greedy-Algorithmus konstruieren. Er beruht darauf, dass man für die eigenen wertvollen Karten Gegner findet, gegen die sie gewinnen. Damit man sich nicht wie im obigen Beispiel mit einer kleinen Karte den möglichen Gegner für eine große Karte selbst wegschnappt, beginnt man bei der Zuordnung mit der eigenen höchsten Karte und geht dann im Kartenwert abwärts.
Kannst Du daraus den Greedy-Algorithmus konstruieren?
PS: Die Einhaltung von Regel a) ergibt relativ automatisch.
|
Notiz Profil
Quote
Link |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
