Mastermindproblem ist NP-vollständig |
| 16.11.2010, 08:29 | Auf diesen Beitrag antworten » |
| Clodan | Mastermindproblem ist NP-vollständig Moin Leute! Also ich habe eine Frage bzgl. des Mastermindsproblems: Also Mastermind ist ja NP-vollständig, da es auf SAT zurückgeführt werden kann. Mein Professor meinte, dass es keinen Sinn macht, Mastermind auf NP-vollständig zu untersuchen, wenn man beispielsweise 5 Plätze hat (man kann also 5 Kugeln in einer Reihe platzieren) und man darf Farben in einer Reihe doppelt verwenden (d.h. in einer Reihe ist 2x rot oder 3x blau). Mit Reihe meine ich waagerechte Platzierung der Kugeln d.h. in der Matrixsprechweise eine Zeile. Wieso macht das keinen Sinn? Ist es denn, wenn in einer Reihe Farben doppelt auftreten können, nicht mehr NP-vollständig bzw. nicht mehr auf SAT zurpckführbar oder was versteckt sich hinter dieser Aussage? O.o? Wäre supi, wenn mir jemand bei dieser Frage helfen könnte, da ich dachte, dass die Problematik mit NP-vollständig und SAT verstand. 
Doch leider macht mir das Mastermind-Problem einen Strich durch die Rechnung, dass ich irgendwas noch nicht verstand. Deswegen wäre es wirklich schön, wenn mich diesbezüglich jemand aufklären könnte. 
MFG Clodan |
|
|
|
| 16.11.2010, 13:12 | Auf diesen Beitrag antworten » |
| ed209 | Am besten formulierst du das Mastermind-Problem erstmal für alle die es nicht kenne. Das Spiel kenne ich zwar, aber was genau das Mastermind-Problem ist, ist mir nicht bekannt
Gruß, ED PS: Wenn du Komplexität betrachtest, brauchst du immer Probleme mit variabler Eingabegröße, sonst kannst du nicht beurteilen "wie schnell es wächst". |
|
|
