Definition · Begriff 12 von 25
NP-schwer
Eine Klasse von Problemen, für die kein bekannter Algorithmus ein Optimum mit Lücke null in polynomieller Zeit findet. Der Aufwand kann exponentiell mit der Größe wachsen.
RechenbeispielEin Halt mehr, viel mehr TourenEine Folge von 10 Halten hat etwa 3,6 Millionen Reihenfolgen. Bei 15 Halten sind es etwa 1,3 Billionen. So schnell kann der Aufwand wachsen, deshalb zählt eine ausgewiesene Optimalitätslücke.
In einfachen Worten
Tourenplanung, Ablaufplanung und Bin Packing sind NP-schwer. Das heißt nicht, dass sie unlösbar sind. Es heißt, dass keine Abkürzung bekannt ist, die für jede Instanz funktioniert. In der Praxis lösen exakte Verfahren mit starkem Beschneiden viele echte Instanzen bis zu einer Lücke von null. Für den Rest melden sie, wie nah der beste gefundene Plan ist.
NP-schwer, auf Ihre eigene Entscheidung angewandt.
Bringen Sie eine wiederkehrende Entscheidung ein. Ihre Planer sehen die Begriffe dieses Glossars, angewandt auf ihre eigenen Regeln und Daten.
- Glossar
- alle 25 Begriffe, A bis Z
- Problemtypen
- die Entscheidungen, die kint löst
- Vergleiche
- kint im Vergleich mit anderen Ansätzen
- Kontakt
- hello@kint.pro