Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » Greedy Algorithmus
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Greedy Algorithmus
derechteChickenWing
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 24.06.2020
Mitteilungen: 39
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-11-29






Meine Tabelle


So wie ich es verstehe sind die 120 Punkte das höchste was man erreichen kann oder ?



Wahlurne Für derechteChickenWing bei den Matheplanet-Awards stimmen
Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2605
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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 -



Wahlurne Für DerEinfaeltige bei den Matheplanet-Awards stimmen
Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
derechteChickenWing
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 24.06.2020
Mitteilungen: 39
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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



Wahlurne Für derechteChickenWing bei den Matheplanet-Awards stimmen
Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6644
Herkunft: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.



Wahlurne Für Kitaktus bei den Matheplanet-Awards stimmen
Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
derechteChickenWing hat die Antworten auf ihre/seine Frage gesehen.
derechteChickenWing hatte hier bereits selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
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]