В задаче коммивояжера (TSP) нам дан набор узлов, где один узел является начальным узлом. Задача состоит в том, чтобы найти кратчайший тур, начинающийся в начальном узле и посещающий каждый узел ровно один раз. Вариантом более общего TSP является евклидово TSP , где расстояние между двумя городами — это обычное евклидово расстояние. Также можно рассматривать разные метрики, например, метрику городского квартала .
Основываясь на экспериментальных данных в [1], авторы утверждают, что евклидовы экземпляры TSP просты для человека. Они также собрали данные о случае, когда используемой метрикой является метрика городских кварталов. Они отмечают, что «... люди почти оптимальны для этих проблем по обоим показателям».
[1] Уолвин, А.Л., и Наварро, Д.Дж. (2010). Минимальные пути в городском квартале: человеческая деятельность в евклидовых и неевклидовых задачах коммивояжера. Журнал решения проблем, 3 (1), 5.
Я просто быстро просмотрел это в Google Scholar и нашел следующую интересную ссылку:
В этой статье утверждается, что «сложность TSP зависит от количества неграничных точек, а не от общего количества точек». Они определяют неграничную точку как точку внутри выпуклой оболочки, которая охватывает все точки задачи. В этой статье также делаются некоторые интересные наблюдения о пространстве восприятия для людей в этой задаче, утверждая, что проблема, по-видимому, решается людьми в двухмерном проблемном пространстве, которое соответствует двумерному перцептивному пространству. Наконец, ссылки, цитируемые в этой статье, указывают на то, что по крайней мере некоторые исследования касались вопроса о возможностях человека в TSP еще в конце 1960-х годов.
Похоже, что вы также можете получить некоторые полезные подсказки, следуя графику цитирования из этой статьи вперед во времени: http://scholar.google.com/scholar?cites=9195299723226128892 .
Wuschelbeutel Kartoffelhuhn