Comparing Problem Solving Strategies for NP-hard Optimization Problems

• Autorzy: Hidalgo-Herrero M. , Rabanal P. , Rodríguez I. , Rubio F.
• Języki publikacji: EN

Abstrakty

EN

NP-complete problems are particularly hard to solve. Unless P=NP, any algorithm solving an NP-complete problem takes exponential time in the worst case. The intrinsic difficulty of NP-complete problems when we try to optimally solve them with computers seems to apply to humans too. Intuitively, solving NP-complete problems requires taking a series of choices where each choice we take disables many subsequent choices, but the scope of dependencies between these mutually exclusive choices cannot be bound. Thus, the problem cannot be split into smaller subproblems in such a way that their solutions can be computed independently and easily combined for constructing the global solution (as it happens in divide and conquer algorithms). Moreover, for each choice, the space of subsequent subproblems to be considered for all possible choice elections does not collapse into a polynomial size set (as it happens in dynamic programming algorithms). Thus, intuitively, in NP-complete problems any choice may unboundedly affect any other, and this difficulty seems to puzzle humans as much as computers. In this paper we conduct an experiment to systematically analyze the performance of humans when solving NP-complete problems. For each problem, in order to measure partial fulfillment of the decision problem goal, we consider its NP-hard optimization version. We analyze the human capability to compute good suboptimal solutions to these problems, we try to identify the kind of problem instances which make humans compute the best and worst solutions (including the dependance of their performance on the size of problem instances), and we compare their performance with computational heuristics typically used to approximately solve these problems. We also interview experiment participants in order to infer the most typical strategies used by them in experiments, as well as how these strategies depend on the form and size of problem instances.

Słowa kluczowe

EN

heuristic methods; human reasoning; human-computer comparison; learning strategies; metaheuristics; NP-hard problems; problem solving; testing

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 124, nr 1/2
• Strony: 1--25
• Opis fizyczny: Bibliogr. 25 poz., wykr.

Twórcy

autor

Hidalgo-Herrero M.

• Facultad de Educación, Universidad Complutense de Madrid, E-28040 Madrid, Spain

autor

Rabanal P.

• Facultad de Informática, Universidad Complutense de Madrid, E-28040 Madrid, Spain

autor

Rodríguez I.

• Facultad de Informática, Universidad Complutense de Madrid, E-28040 Madrid, Spain

autor

Rubio F.

• Facultad de Informática, Universidad Complutense de Madrid, E-28040 Madrid, Spain

Bibliografia

• [1] Arora, S.: Polynomial time approximation schemes for Euclidean TSP and other geometric problems, Proceedings of the 37th IEEE Symposium on Foundations of Computer Science (FOCS’96), 1996.
• [2] Artigue, M.: Didactics of Mathematics as a Scientific Discipline, chapter Didactical Engineering as a framework for the conception of teaching products, Kluwer Academic Publishers, Dordrecht, 1994, 27-39.
• [3] Brousseau, G., Balacheff, N.: Theory of Didactical Situations in Mathematics: Didactique Des Mathematiques, 1970-1990, Mathematics Education Library, Kluwer Academic Publishers, 1997.
• [4] Brusco, M.: Measuring Human Performance on Clustering Problems: Some Potential Objective Criteria and Experimental Research Opportunities, The Journal of Problem Solving, 1(2), 2007.
• [5] Burns, N., Lee, M., Vickers, D.: Are Individual Differences in Performance on Perceptual and Cognitive Optimization Problems Determined by General Intelligence, The Journal of Problem Solving, 1(1), 2006.
• [6] Chevallard, Y.: Familiere et problematique, la figure du professeur, Recherches en Didactique des Mathematiques, 17(3), 1997, 17-54.
• [7] Cook, S.: The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, STOC ’71, ACM, 1971.
• [8] Cook, S.: The P versus NP Problem, 2000, Manuscript prepared for the Clay Mathematics Institute for the Millennium Prize Problems.
• [9] Davis, L., Mitchell, M.: Handbook of Genetic Algorithms, Van Nostrand Reinhold, 1991.
• [10] Dorigo, M.: Ant Colony Optimization, MIT Press, 2004.
• [11] Dry, M., Lee, M., Vickers, D., Hughes, P.: Human Performance on Visually Presented Traveling Salesperson Problems with Varying Numbers of Nodes, The Journal of Problem Solving, 1(1), 2006.
• [12] Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, USA, 1979.
• [13] Goldberg, D.: Genetic Algorithms in Search, Optimisation and Machine Learning, Addison-Wesley, 1989.
• [14] Graham, S., Joshi, A., Pizlo, Z.: The travelling salesman problem: A hierarchical model, Memory and Cognition, 28, 2000, 1191-1204.
• [15] Halperin, E.: Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs, Proc. 11th Ann. ACM-SIAM Symp. on Discrete Algorithms, ACM-SIAM, 2000.
• [16] Ibarra, O., Kim, C.: Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems, J. ACM, 22(4), 1975,463-468.
• [17] Kirkpatrick, S., Gelatt, C. D., Vecchi, M. P.: Optimization by simulated annealing, Science, 220, 1983, 671-680.
• [18] Lester, F.: Theories of Mathematics Education. Seeking New Frontiers, chapter On the Theoretical Conceptual and Philosophical Foundations for Conceptual Research in Mathematics Education, Springer, Berlin, 2010, 67-85.
• [19] MacGregor, J., Ormerod, T.: Human performance on the travelling salesman problem, Perception and Psychophysics, 58, 1996, 527-539.
• [20] Papadimitriou, C.: Computational complexity, Addison-Wesley, 1994.
• [21] Papadimitriou, C., Steiglitz, K.: Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., 1982.
• [22] Pizlo, Z., Li, Z.: Solving combinatorial problems: 15-puzzle, Memory and Cognition, 33(6), 2005, 10691084.
• [23] Rabanal, P., Rodriguez, I., Rubio, F.: Applying River Formation Dynamics to Solve NP-Complete Problems, in: Nature-Inspired Algorithms for Optimisation (R. Chiong, Ed.), vol. 193 of Studies in Computational Intelligence, Springer, 2009, 333-368.
• [24] Rabanal, P., Rodriguez, I., Rubio, F.: Appendix: NP-Completeness and NP-Complete problems under consideration, http://antares.sip.ucm.es/prabanal/research/fi12appendix.pdf, 2012.
• [25] van Rooij, I., Schactman, A., Kadlec, H., Stege, U.: Perceptual or Analytical Processing? Evidence from Children’s and Adult’s Performance on the Euclidean Traveling Salesperson Problem, The Journal of Problem Solving, 1(1), 2006