Es wurde festgestellt , dass Menschen unter bestimmten Bedingungen gut darin sind, das Problem des Handlungsreisenden zu lösen. Gibt es andere NP-schwere oder NP-vollständige Probleme, die Menschen gut lösen können? Gibt es dazu andere (psychologische, neurobiologische) Untersuchungen?
Eine Spur, der ich derzeit nachgehe, ist, wie gut Menschen Minesweeper spielen können, obwohl es NP-Complete ist .
Im Hinblick auf die Beziehung zwischen Gehirn und Komplexitätstheorie ist es meines Erachtens wichtig, sich daran zu erinnern, dass das Gehirn kaum jemals zu exakten Problemlösungen kommt und das induktive Denken dem Deduktion vorzuziehen scheint. ( Wie man eine Minesweeper-Strategie rechnerisch herbeiführt ) Außerdem beschwören wir meistens Näherungen herauf. Précis of Bayesian Rationality: The Probabilistic Approach to Human Reasoning diskutiert die Problemlösung in ungenauen (probabilistischen) Begriffen. Ich glaube, dass einer der Folgeartikel (Identifizieren der optimalen Reaktion ist kein notwendiger Schritt zur Erklärung der Funktion, Seite 85) für Ihre Frage relevant ist:
„Eine Erklärung, die eine optimale Antwortfunktion erfordert, muss auch berücksichtigen, dass: (e) für Probleme der induktiven Inferenz die optimale Antwort oft analytisch schwer zu bestimmen ist mit exakten Methoden und nicht eindeutig sein wird; (f) Verhaltensantworten sind typischerweise annähernd optimal , die eher eine Tendenz als eine Entsprechung offenbart"
Sammelantworten können aggregiert werden, um gemeinsame Lösungsfragmente zu einer globalen Lösung zu kombinieren. Vielleicht ist ein Schlüssel zur Lösung von NP-hard/complete, genug Diversität zu haben und daher im kollektiven Sinne zu arbeiten. Lesen Sie The Wisdom of the Crowd in Combinatorial Problems von Sheng Kung Michael Yi, Mark Steyvers, Michael D. Lee, Matthew J. Dryb
Benutzer6682
Benutzer3503