P=np?

[Lorenzy]

Zitat von richy

Doch, das geht mit neronalen Netzwerken. Ein Kohonen Netztwerk loest das Problem des Handlungsreisenden innerhalb weniger Minuten.

Hi richy,

Mit diesem Trick kann auch "nur" eine Annährung des Problems des Handlungsreisenden erreicht werden. Es gibt aber nur eine Lösung - die kürzeste Strecke. Selbst wenn man mit solchen neuronalen Netzwerken den Weg durch 50 Städte berechnen würde, hätte man immer noch Millionen von möglichen Lösungen, welche aber alle (zufällig könnte sich natürlich auch der heilige Gral darunter befinden) nur Annährungen des Problems sind.
Das soll natürlich nicht die Leistung solcher neuronalen Netzwerke schmälern. Es ist schon erstaundlich was in so kurzer Zeit damit erreicht werden kann - Annährung hin oder her.

Die derzeit einzigen Kandidaten um NP-Probleme in zumutbarer Zeit zu lösen, sind Quantenrechner bzw. deren Algorithmen.