Было замечено , что люди хорошо решают задачу коммивояжера при определенных ограничениях. Существуют ли другие NP-сложные или NP-полные проблемы, с которыми хорошо справляются люди? Проводились ли другие исследования (психологические, нейробиологические) по этому поводу?
Одно из направлений, которое я сейчас исследую, — это то, насколько хорошо люди играют в «Сапёра», несмотря на то, что это NP-Complete .
Что касается взаимосвязи между мозгом и теорией сложности, я думаю, важно помнить, что мозг почти никогда не находит точных решений проблем и, кажется, предпочитает индуктивные рассуждения дедукции. ( Как вызвать стратегию тральщика с помощью вычислений ) Кроме того, мы в основном придумываем приближения. В книге «Краткий обзор байесовской рациональности: вероятностный подход к человеческому мышлению» решение проблем обсуждается в неточных (вероятностных) терминах. Я считаю, что одна из последующих статей (Определение оптимального ответа не является необходимым шагом к объяснению функции, стр. 85) имеет отношение к вашему вопросу:
«Объяснение, требующее оптимальной функции отклика, должно также учитывать, что: (e) для задач индуктивного вывода оптимальный отклик часто трудно определить аналитически с помощью точных методов, и он не будет уникальным; (f) поведенческие отклики обычно приблизительно оптимальны. , обнаруживая тенденцию, а не соответствие»
Коллективные ответы могут быть объединены для объединения общих фрагментов решения в глобальное решение. Возможно, ключом к решению NP-сложно/полностью является наличие достаточного разнообразия, следовательно, работа в коллективном смысле. Ознакомьтесь с «Мудростью толпы в комбинаторных задачах» от Шэн Кунга, Майкла Йи, Марка Стейверса, Майкла Д. Ли, Мэтью Дж. Драйба.
пользователь6682
пользователь3503