Das Coin-Weighing-Problem < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:59 Di 03.05.2005 | | Autor: | Aly |
Hallo zusammen!
Könnte jemand einen Ansatz zur Lösung des folgenden Problems geben?
Gegeben seien N Münzen und eine elektronische Waage.
Es ist nicht bekannt wieviele dieser Münzen unecht sind.
Man weiss aber, dass echte Münzen das Gewicht "A" haben und verfälschte Münzen das Gewicht "B", mit B<A.
Gefragt ist, ob es einen Algorithmus gibt, der ab ein bestimmtes N im "worst case" weniger als N Wiegeoperationen braucht, um die echten Münzen zu erkennen (Und somit auch die verfälschten), wobei man pro Wiegeoperation eine beliebige Anzahl(<= N) von Münzen nehmen kann.
--------------------------------------------------------------------
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
|
|
| |
|
Hi Aly,
![[willkommenvh]](/images/smileys/willkommenvh.png "[willkommenvh]")
Das Coin-Weighting Problem ist offensichtlich berühmt.
Ich habe ![[]](/images/popup.gif) hier etwas dazu gefunden, weiß aber nicht, ob es dir gänzlich weiterhilft.
Grüße
Karl
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:39 Do 12.05.2005 | | Autor: | michagm1 |
Hallo,
weißt Du zu Beginn des Lösungsweges wie viele München Du hast? Wenn ja, dann geht folgendes Verfahren
Man z.B. so vorgehen:Nimm die erste Hälte der Münzen und rechne wie folgt:
x=n/2 * Gewicht der Münzen
dann berechne
y =n/2 * Gewicht "A"
wenn x != y dann halbierst du die Menge und prüfst die neue Menge usw.
Dann prüfst du die zweite Hälfte ähnlich
Dieses Verfahren hat einen speziellen Namen. Der fällt mir im Moment nur nicht ein.
Viel Spaß beim probieren.
Gruß
Michae> Hallo zusammen!
>
> Könnte jemand einen Ansatz zur Lösung des folgenden
> Problems geben?
>
> Gegeben seien N Münzen und eine elektronische Waage.
> Es ist nicht bekannt wieviele dieser Münzen unecht sind.
> Man weiss aber, dass echte Münzen das Gewicht "A" haben
> und verfälschte Münzen das Gewicht "B", mit B<A.
> Gefragt ist, ob es einen Algorithmus gibt, der ab ein
> bestimmtes N im "worst case" weniger als N
> Wiegeoperationen braucht, um die echten Münzen zu erkennen
> (Und somit auch die verfälschten), wobei man pro
> Wiegeoperation eine beliebige Anzahl(<= N) von Münzen
> nehmen kann.
>
>
> --------------------------------------------------------------------
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:26 Do 12.05.2005 | | Autor: | Karl_Pech |
Hallo Michael,
> Dieses Verfahren hat einen speziellen Namen. Der fällt mir
> im Moment nur nicht ein.
Nennt sich das nicht "Divide And Conquer"-Verfahren?
Grüße
Karl
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:53 Fr 13.05.2005 | | Autor: | Aly |
Hallo :),
Danke für eure Antworten.
Also was die Halbierungsmethode betrifft ist nichts einzuwenden, ausser dass sie nicht garantiert, dass ab einer bestimmten Anzahl von Münzen im Worst-Case mit geringer als N wiegeoperationen auszukommen ist, weil es kann so passieren, dass in jeder gewählten Menge x!=y gilt.
Idee:
Das Problem kann schön vereinfacht dargestellt werden ohne seine Schärfe zu verlieren.
Nämlich man kann o.B.d.A annehmen, dass verfälschte Münzen das Gewicht 0 haben, wogegen die echten das Gewicht 1 bekommen.
Nun reduziert sich das Problem auf die Anzahl der Wiegevorgänge die nötig sind, um diese "Zeichenkette" von Nullen und Einssen zu bestimmen.
Es ist auch nützlich sich Gedanken darüber zu machen, was es bedeuten würde, wenn es tatsächlich einen Algorithmus gibt, die die gewünschte Eigenschaft hat. z.B würde das dann meiner Meinung nach bedeuten, dass man über beliebige Zeichenketten (ab einer bestimmten Länge) nicht alles wissen muss, um diese zu bestimmen.
Grüsse,
Ali
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:22 Fr 20.05.2005 | | Autor: | Zyllyn |
mit der elektronischen Waage sehe ich keine Lösung die worst case weniger als N Wiegeversuche braucht ... Dafür garantiert die Teilungsmethode, dass du maximal N Wiegeversuche brauchst.
Der worse case tritt ein, wenn Du gleiche Anzahl echte und unechte Münzen hast. Je größer die Differenz zwischen zwischen den Anzahlen von echten und unechten Münzen, desto weniger Wiegeversuche. --> also indirekt eine Aussage über N :)
NB: wenn du eine Balkenwaage nimmst, und vorraussetzt, das Du mindestens eine echte und mindesten eine unechte Münze hast, wieder ein Teilungsverfahren ansetzt, dann brauchst du auch im worst case nur N-1 Wiegeversuche (allerdings sollte N eine Zweipotenz sein :) )
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:51 Fr 03.06.2005 | | Autor: | Becci |
In N Versuchen ist das Problem trivial (wiege jede einzelne der N Münzen), aber ich glaube, in N-1 Wiegeversuchen ist es i.A. nicht möglich, das Gewicht jeder einzelnen Münze festzustellen (also ob es A oder B ist).
Begründung:
Wir können über das Gewicht einer bestimmten Münze nur dann etwas aussagen, wenn wir sie schon einmal
- entweder allein
- oder aber NUR mit anderen Münzen desselben Gewichts zusammen gewogen haben.
D.h., dass wir genau das für jede Münze einmal tun müssen, um am Ende über alle "Bescheid zu wissen".
Es bringt uns aber nichts, einzelne Münzen zu wiegen, denn: Dann haben wir N-1 Münzen übrig, deren Gewicht wir nicht kennen, und dürfen nur noch N-2mal wiegen => Dasselbe Problem immer noch.
Also muss ein Algorithmus, der das Problem in N-1 Versuchen löst, dabei mindestens einmal eine Menge M von [mm] |M| \geq 2 [/mm] Münzen gleichen Gewichts wiegen.
Gibt es einen Algorithmus, der garantiert auf solch eine Menge M stößt und dennoch nur N-1 mal wiegen muss?
Denken wir uns mal den worst-case, d.h. es haben [mm] \bruch{N}{2}[/mm] Gewicht A und der Rest hat Gewicht B (für N ungerade nehme die untere Gaußklammer, d.h. es gibt 1 weniger echte Münzen als falsche).
Wann immer der Algorithmus aus den N Münzen einige (einzelne Münzen bringen ihm ja nix, s.o.) auswählt, um sie zu wiegen, habe er nun "Pech", d.h. für diese Menge von Münzen gilt wieder dass die Hälfte echt ist und die Hälfte unecht.
Dann wird der Alg., egal welche Münzen er genommen hat, immer noch nichts über das Gewicht einer beliebigen Einzelmünze wissen.
Dieses Spielchen kann man jetzt fortführen und sieht, dass unter den worst-case-Voraussetzungen der Alg. jede Münze tatsächlich einzeln berachten muss: Solange eine zweite dabei ist, ist ja nach der Annahme, dass wir "Pech" haben, eine davon schwerer und eine leichter und niemand weiß welche jetzt welche ist...
Damit braucht er auch mindestens N Wiegevorgänge.
(Die erwartete Anzahl Wiegevorgänge für die schon vorgeschlagene Divide-and-Conquer-Methode ist zwar wohl <N, weil der worst case höchst unwahrscheinlich ist. Aber garantieren kann man eben (meiner Meinung nach) nichts besseres als N.)
Hoffe du kannst was damit anfangen
Gruß
Becci
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:49 Mo 06.06.2005 | | Autor: | Aly |
Hallo Becci,
Danke für deine ausführliche Vorführung .
Dein Beweis ist schön. Aber er enthält nur eine Schwachstelle oder zumindest scheint eine Schwachstelle zu enthalten.
Sei superA ein Algorithmus der das Coinweighingproblem positiv löst.
Deine Überlegungen stimmen sicher, wenn man annimmt dass der Algorithmus zur Lösung des Problems vorbestimmt und vordefiniert sein soll, aber es wäre denkbar, dass der Algorithmus sein Verhalten entscheidend verändert je nachdem was das Ergebnis
des Wiegens ist... z.B Wenn der Algorithmus merkt, dass die Hälfte der Münzen echt sind, kann er zu einer bestimmten Aufteilung der Menge aller Münzen in Teilmengen zugreifen, die die Eigenschaft hat, dass mindestens eine dieser Teilmengen weniger echte als verfälschte Münzen hat.
Es wäre sogar denkbar dass man durch eine geeignete Aufteilung mehrere solcher mengen erhält oder dass es ebenfalls durch geeignete Aufteilung einen deutlichen unterschied zwischen der Anzahl echter und verfälschter Münzen in einer Teilmenge entsteht. Wenn man das erreicht dann hat man gewiss weniger als n-Wiegeoperationen durchzuführen.
Es ist hier zu erwähnen dass man theoretisch mithilfe der Entropie der Informationstheorie beweisen kann, dass man nicht mit besser als n/log(n) Wiegeoperationen rechnen kann. Aber man weiss noch nicht, ob man diese untere Schranke tatsächlich erreichen kann.
Also ich denke dass deine Überlegungen reichen nicht, um die Existenz von superA zu verneinen sondern sie reichen um die Existenz aller vorbestimmten Algorithmen die das Problem positiv lösen zu verneinen.
D.h. wir wissen dass wenn es einen solchen Algorithmus gibt dann muss er klug sein.
Was meinst du dazu? und andere auch?
Gruß
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:35 Mi 15.06.2005 | | Autor: | Becci |
>> Sei superA ein Algorithmus der das Coinweighingproblem positiv löst.
>> Deine Überlegungen stimmen sicher, wenn man annimmt dass der Algorithmus zur Lösung des Problems vorbestimmt
>> und vordefiniert sein soll, aber es wäre denkbar, dass der Algorithmus sein Verhalten entscheidend verändert je nachdem was das Ergebnis
>> des Wiegens ist... z.B Wenn der Algorithmus merkt, dass die Hälfte der Münzen echt sind, kann er zu einer bestimmten Aufteilung der Menge aller
>> Münzen in Teilmengen zugreifen, die die Eigenschaft hat, dass mindestens eine dieser Teilmengen weniger echte als verfälschte Münzen hat.
Nun, ich denke eigentlich nicht dass das so ist.
Man könnte es meinen, ja. Aber als ich mir das überlegt habe, bin ich zu folgendem Ergebnis gekommen:
Also sei jetzt der Algorithmus abhängig vom Ergebnis des Wiegens, d.h.
er hat jetzt eine Menge A von Münzen gewogen und weiß: Aha, die Hälfte ist falsch.
(oder für ungerade Anzahl halt untere/obere Gaußklammer)
Er weiß nur leider NICHT: Welche Münzen sind die falschen und welche die richtigen?
Du sagst jetzt, er kann sich die Menge A so in Teilmengen aufteilen, dass er über die Teilmengen weiß:
Eine hat weniger echte als falsche Münzen.
Wie denn? Sagen wir mal, er macht aus A n Teilmengen.
Er kann die Elemente der Teilmengen nur zufällig aus A wählen, weil er keinen Schimmer hat, welche Münze in A wieviel wiegt.
Also holt er meinetwegen zuerst mal m Münzen in die Teilmenge M.
Egal was jetzt m ist, er kann Pech haben (worst case) und hat ausgerechnet wieder (untere Gaußklammer von) m/2 falsche Münzen.
Wenn er das Pech hatte, und das nehmen wir ja an (immer noch worst case),
dann hat er bei der Einteilung der nächsten Menge wieder exakt dasselbe Problem (weil A immer noch gleichverteilt) und so weiter für alle n Teilmengen die er bildet.
D.h., wenn A sicherstellen will, dass irgendwo ein Ungleichgewicht in einer Teilmenge herrscht, dann muss er eine Teilmenge ungerader Kardinalität nehmen -
und auch da ist das Ungleichgewicht wieder nur genau EINE Münze (im worst case), so dass wir eh nur wieder den in meinem Lösungsvorschlag behandelten Fall haben.
Oder?
Gruß
Becci
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:45 Mi 15.06.2005 | | Autor: | Zyllyn |
ich kann becci nur Zustimmen. Unabhängig davon interessiert mich der Beweis der untere Schranke [mm] \bruch{n}{log(n)}[/mm]
vielleicht versteckt sich ja im Beweis die Idee für unser Wiegeproblem
Zyllyn
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:33 Mi 20.07.2005 | | Autor: | Aly |
Hallo Becci,
Ich habe einen Algorithmus gefunden der in allen Fällen mit weniger als n-Wiegeoperationen auskommt.
Es stimmt nicht, dass die Wiegeoperationen uns bei der Bestimmung der einzelnen Münzen überhaupt
nicht helfen. Versuche es mit dem Fall über den du schnell geflogen bist. nämlich den Fall wo die Anzahl der Münzen ungerade ist. Da kann man ein Loch verursachen und es mit grösser werdenden n vergrössen. Ich werde meinen Algorithmus momentan nicht veröffentlichen. ich versuche ihn zu verbessern.
Aber danke für deine Denkanstösse, sie haben mich dazu geführt diesen Algorithmus zu finden.
Grüsse Aly.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 06:55 So 24.07.2005 | | Autor: | Aly |
Hallo Alle,
test
Grüsse Aly.
|
|
|
|
