Welche Formen des Handlungsreisenden-Problems sind für Menschen schwer lösbar?

Beim Problem des Handlungsreisenden ( Traveling Salesman Problem, TSP) ist uns eine Menge von Knoten gegeben, wobei ein Knoten der Startknoten ist. Die Aufgabe besteht darin, die kürzeste Tour zu finden, die am Startknoten beginnt und jeden Knoten genau einmal besucht. Eine Variante des allgemeineren TSP ist das euklidische TSP , bei dem die Entfernung zwischen zwei Städten die übliche euklidische Entfernung ist. Es können auch andere Metriken berücksichtigt werden, wie z. B. die City-Block-Metrik .

Basierend auf experimentellen Daten in [1] behaupten die Autoren, dass euklidische TSP-Instanzen für Menschen einfach sind. Sie sammelten auch Daten zu Fällen, in denen die verwendete Metrik die City-Block-Metrik ist. Sie stellen fest, dass "... Menschen in beiden Metriken nahezu optimal für diese Probleme sind."

  • Welche Varianten des Handlungsreisenden-Problems sind für Menschen schwierig?
  • Wurden diesbezüglich Untersuchungen durchgeführt?

[1] Walwyn, AL, & Navarro, DJ (2010). Minimale Pfade im Stadtblock: Menschliche Leistung bei euklidischen und nicht-euklidischen Problemen mit reisenden Verkäufern. The Journal of Problem Solving, 3(1), 5.

Meine Vermutung ist, dass immer dann, wenn für ein bestimmtes Problem die Optimalitätslücke für die Greedy-Heuristik klein ist, es für Menschen einfach ist, es so zu lösen.

Antworten (1)

Ich habe das gerade schnell bei Google Scholar nachgeschlagen und folgende interessante Referenz gefunden:

  • JN Macgregor, T. Ormerod. "Menschliche Leistung zum Problem des Handlungsreisenden." Perception & Psychophysics Band 58, Ausgabe 4, S. 527-539 (Juni 1996)

In diesem Papier wird behauptet, dass "die Komplexität von TSPs eine Funktion der Anzahl der nicht begrenzten Punkte ist, nicht der Gesamtzahl der Punkte". Sie definieren einen Nichtbegrenzungspunkt als einen Punkt innerhalb der konvexen Hülle, der alle Punkte des Problems umfasst. Dieses Papier macht auch einige interessante Beobachtungen über den Wahrnehmungsraum für Menschen bei dieser Aufgabe und behauptet, dass das Problem scheinbar von Menschen in einem 2D-Problemraum gelöst wird, der mit dem 2D-Wahrnehmungsraum übereinstimmt. Schließlich weisen die in diesem Papier zitierten Referenzen darauf hin, dass sich zumindest einige Forschungen bereits in den späten 1960er Jahren mit der Frage der menschlichen Leistung auf dem TSP befasst haben.

Es sieht so aus, als könnten Sie auch einige nützliche Hinweise erhalten, wenn Sie dem Zitierdiagramm aus diesem Papier zeitlich vorwärts folgen: http://scholar.google.com/scholar?cites=9195299723226128892

Wenn Sie "Zitatdiagramm" sagen, beziehen Sie sich auf dieses Tool ?
Welche Formen des Handlungsreisenden-Problems sind für Menschen schwer lösbar?
AntwortenHierDatenschutz-Bestimmungen1y, 0v