Zunächst einmal werde ich sagen, ich weiß nicht viel über Theorie und so. Aber ich fragte mich, ob das ein NP oder NP-vollständiges Problem war. Es klingt spezifisch wie ein spezieller Fall des Subset-Summenproblems.Ist das ein NP-Problem?
Wie auch immer, da ist dieses Spiel, das ich kürzlich gespielt habe, Alchemy genannt, was diesen Gedanken ausgelöst hat. Grundsätzlich beginnen Sie mit 4 Grundelementen und kombinieren diese zu anderen Elementen.
So zum Beispiel ist dies ein kurzes „Rezept“, wenn Sie werden für Elemente machen
fire=basic element water=basic element air=basic element earth=basic element sand=earth+earth glass=sand+fire energy=fire+air lightbulb=energy+glass
ist so ein Computer sagt sie nur die vier Grundelemente schaffen könnte, aber es könnte mehrere Sätze von der erstellen Elemente. Sie schreiben also ein Programm, um ein beliebiges Element zu erstellen, indem Sie andere Elemente kombinieren. Wie würde dieses Programm die Liste bearbeiten, um eine Glühbirne zu erstellen?
Es ist eindeutig Feuer + Luft = Energie, Erde + Erde = Sand, Sand + Feuer = Glas, Energie + Glas = Glühbirne.
Aber ich kann mir keine Möglichkeit vorstellen, ein Programm zu schreiben, um eine Liste zu bearbeiten und das herauszufinden, ohne eine Brute-Force-Methode zu machen und jedes Element zu überprüfen und sein Rezept zu überprüfen.
Ist das ein NP-Problem? Oder kann ich das nicht herausfinden?
Kann nicht hilfreich sein, aber das sieht wie ein Job für Prolog aus. –
ist es in P und daher auch in NP. Es ist jedoch nicht NP-vollständig. – lijie
Sie können eine Überprüfung dafür ziemlich einfach schreiben, also ist es in NP mindestens. –