Solving the Large-Scale TSP Problem in 1 h: Santa Claus Challenge 2020.
Ontology highlight
ABSTRACT:
SUBMITTER: Mariescu-Istodor R
PROVIDER: S-EPMC8520904 | biostudies-literature | 2021
REPOSITORIES: biostudies-literature
Publications
Solving the Large-Scale TSP Problem in 1 h: Santa Claus Challenge 2020.
Mariescu-Istodor Radu R Fränti Pasi P
Frontiers in robotics and AI 20211004
The scalability of traveling salesperson problem (TSP) algorithms for handling large-scale problem instances has been an open problem for a long time. We arranged a so-called Santa Claus challenge and invited people to submit their algorithms to solve a TSP problem instance that is larger than 1 M nodes given only 1 h of computing time. In this article, we analyze the results and show which design choices are decisive in providing the best solution to the problem with the given constraints. Ther ...[more]
Similar Datasets
Project description:IntroductionThis study investigates the process data from scientific inquiry tasks of fair tests [requiring test-takers to manipulate a target variable while keeping other(s) constant] and exhaustive tests (requiring test-takers to construct all combinations of given variables) in the National Assessment of Educational Progress program.MethodsWe identify significant associations between item scores and temporal features of preparation time, execution time, and mean execution time.ResultsReflecting, respectively, durations of action planning and execution, and execution efficiency, these process features quantitatively differentiate the high- and low-performing students: in the fair tests, high-performing students tended to exhibit shorter execution time than low-performing ones, but in the exhaustive tests, they showed longer execution time; and in both types of tests, high-performing students had shorter mean execution time than low-performing ones.DiscussionThis study enriches process features reflecting scientific problem-solving process and competence and sheds important light on how to improve performance in large-scale, online delivered scientific inquiry tasks.
| S-EPMC10151488 | biostudies-literature
Project description:The paper aims to introduce the conceptual framework of problem solving through values. The framework consists of problem analysis, selection of value(s) as a background for the solution, the search for alternative ways of the solution, and the rationale for the solution. This framework reveals when, how, and why is important to think about values when solving problems. A consistent process fosters cohesive and creative value-based thinking during problem solving rather than teaching specific values. Therefore, the framework discloses the possibility for enabling the development of value-grounded problem solving capability.The application of this framework highlights the importance of responsibility for the chosen values that are the basis for the alternatives which determine actions. The 4W framework is meaningful for the people's lives and their professional work. It is particularly important in the process of future professionals' education. Critical issues concerning the development of problem solving through values are discussed when considering and examining options for the implementation of the 4W framework in educational institutions.
| S-EPMC7382331 | biostudies-literature
Project description:BackgroundsThe field of Artificial Intelligence (AI) has seen a major shift in recent years due to the development of new Machine Learning (ML) models such as Generative Pre-trained Transformer (GPT). GPT has achieved previously unheard-of levels of accuracy in most computerized language processing tasks and their chat-based variations.AimThe aim of this study was to investigate the problem-solving abilities of ChatGPT using two sets of verbal insight problems, with a known performance level established by a sample of human participants.Materials and methodsA total of 30 problems labeled as "practice problems" and "transfer problems" were administered to ChatGPT. ChatGPT's answers received a score of "0" for each incorrectly answered problem and a score of "1" for each correct response. The highest possible score for both the practice and transfer problems was 15 out of 15. The solution rate for each problem (based on a sample of 20 subjects) was used to assess and compare the performance of ChatGPT with that of human subjects.ResultsThe study highlighted that ChatGPT can be trained in out-of-the-box thinking and demonstrated potential in solving verbal insight problems. The global performance of ChatGPT equalled the most probable outcome for the human sample in both practice problems and transfer problems as well as upon their combination. Additionally, ChatGPT answer combinations were among the 5% of most probable outcomes for the human sample both when considering practice problems and pooled problem sets. These findings demonstrate that ChatGPT performance on both set of problems was in line with the mean rate of success of human subjects, indicating that it performed reasonably well.ConclusionsThe use of transformer architecture and self-attention in ChatGPT may have helped to prioritize inputs while predicting, contributing to its potential in verbal insight problem-solving. ChatGPT has shown potential in solving insight problems, thus highlighting the importance of incorporating AI into psychological research. However, it is acknowledged that there are still open challenges. Indeed, further research is required to fully understand AI's capabilities and limitations in verbal problem-solving.
| S-EPMC10244637 | biostudies-literature
Project description:Diet induces parallel changes to the gut microbiota and problem solving performance in a wild bird
| PRJEB40949 | ENA
Project description:In this paper we argue that a synthesis of findings across the various sub-areas of research in complex problem solving and consequently progress in theory building is hampered by an insufficient differentiation of complexity and difficulty. In the proposed framework of person, task, and situation (PTS), complexity is conceptualized as a quality that is determined by the cognitive demands that the characteristics of the task and the situation impose. Difficulty represents the quantifiable level of a person's success in dealing with such demands. We use the well-documented "semantic effect" as an exemplar for testing some of the conceptual assumptions derived from the PTS framework. We demonstrate how a differentiation between complexity and difficulty can help take beyond a potentially too narrowly defined psychometric perspective and subsequently gain a better understanding of the cognitive mechanisms behind this effect. In an empirical study a total of 240 university students were randomly allocated to one of four conditions. The four conditions resulted from contrasting the semanticity level of the variable labels used in the CPS system (high vs. low) and two instruction conditions for how to explore the CPS system's causal structure (starting with the assumption that all relationships between variables existed vs. starting with the assumption that none of the relationships existed). The variation in the instruction aimed at inducing knowledge acquisition processes of either (1) systematic elimination of presumptions, or (2) systematic compilation of a mental representation of the causal structure underpinning the system. Results indicate that (a) it is more complex to adopt a "blank slate" perspective under high semanticity as it requires processes of inhibiting prior assumptions, and (b) it seems more difficult to employ a systematic heuristic when testing against presumptions. In combination, situational characteristics, such as the semanticity of variable labels, have the potential to trigger qualitatively different tasks. Failing to differentiate between 'task' and 'situation' as independent sources of complexity and treating complexity and difficulty synonymously threaten the validity of performance scores obtained in CPS research.
| S-EPMC5641385 | biostudies-other
Project description:According to the restructuring hypothesis, insight problem solving typically progresses through consecutive stages of search, impasse, insight, and search again for someone, who solves the task. The order of these stages was determined through self-reports of problem solvers and has never been verified behaviorally. We asked whether individual analysis of problem solving attempts of participants revealed the same order of problem solving stages as defined by the theory and whether their subjective feelings corresponded to the problem solving stages they were in. Our participants tried to solve the Five-Square problem in an online task, while we recorded the time and trajectory of their stick movements. After the task they were asked about their feelings related to insight and some of them also had the possibility of reporting impasse while working on the task. We found that the majority of participants did not follow the classic four-stage model of insight, but had more complex sequences of problem solving stages, with search and impasse recurring several times. This means that the classic four-stage model is not sufficient to describe variability on the individual level. We revised the classic model and we provide a new model that can generate all sequences found. Solvers reported insight more often than non-solvers and non-solvers reported impasse more often than solvers, as expected; but participants did not report impasse more often during behaviorally defined impasse stages than during other stages. This shows that impasse reports might be unreliable indicators of impasse. Our study highlights the importance of individual analysis of problem solving behavior to verify insight theory.
| S-EPMC4523725 | biostudies-literature
Project description:When confronted with novel problems, problem-solvers must decide whether to copy a modeled solution or to explore their own unique solutions. While past work has established that infants can learn to solve problems both through their own exploration and through imitation, little work has explored the factors that influence which of these approaches infants select to solve a given problem. Moreover, past work has treated imitation and exploration as qualitatively distinct, although these two possibilities may exist along a continuum. Here, we apply a program novel to developmental psychology (DeepLabCut) to archival data (Lucca et al., 2020) to investigate the influence of the effort and success of an adult's modeled solution, and infants' firsthand experience with failure, on infants' imitative versus exploratory problem-solving approaches. Our results reveal that tendencies toward exploration are relatively immune to the information from the adult model, but that exploration generally increased in response to firsthand experience with failure. In addition, we found that increases in maximum force and decreases in trying time were associated with greater exploration, and that exploration subsequently predicted problem-solving success on a new iteration of the task. Thus, our results demonstrate that infants increase exploration in response to failure and that exploration may operate in a larger motivational framework with force, trying time, and expectations of task success.
| S-EPMC8606407 | biostudies-literature
Project description:Behavioural innovations with tool-like objects in non-habitually tool-using species are thought to require complex physical understanding, but the underlying cognitive processes remain poorly understood. A few parrot species are capable of innovating tool-use and borderline tool-use behaviours. We tested this capacity in two species of macaw (Ara ambiguus, n = 9; Ara glaucogularis, n = 8) to investigate if they could solve a problem-solving task through manufacture of a multi-stone construction. Specifically, after having functional experience with a pre-inserted stick tool to push a reward out of a horizontal tube, the subjects were required to insert five stones consecutively from one side to perform the same function as the stick tool with the resulting multi-component construction. One Ara glaucogularis solved the task and innovated the stone construction after the experience with the stick tool. Two more subjects (one of each species) did so after having further functional experience of a single stone pushing a reward out of a shortened tube. These subjects were able to consistently solve the task, but often made errors, for example counter-productive stone insertions from the opposing end, even in some of the successful trials. Conversely, multiple trials without errors also suggested a strong goal direction. Their performance in the follow-up tasks was inconclusive since they sometimes inserted stones into un-baited or blocked 'dummy tubes', but this could have been an attention-deficit behaviour as subjects had not encountered these 'dummy tubes' before. Overall, the successful subjects' performance was so erratic that it proved difficult to conclude whether they had functional understanding of their multi-stone constructions.
| S-EPMC7979646 | biostudies-literature
Project description:Cognitive flexibility allows individuals to adapt to novel situations. However, this ability appears to develop slowly over the first few years of life, mediated by task complexity and opacity. We used a physically simple novel task, previously tested with nonhuman primates, to explore the development of flexible problem solving in 2-, 3-, and 4-year-old children from a developmental and comparative perspective. The task goal was to remove barriers (straws) from a clear tube to release a ball. The location of the ball, and therefore the number of straws necessary to retrieve it, varied across two test phases (four of five straws and two of five straws, respectively). In Test Phase 1, all children retrieved the ball in Trial 1 and 83.61% used the most efficient method (removing only straws below the ball). Across Phase 1 trials, 4-year-olds were significantly more efficient than 2-year-olds, and solve latency decreased for all age groups. Test Phase 2 altered the location of the ball, allowing us to explore whether children could flexibly adopt a more efficient solution when their original (now inefficient) solution remained available. In Phase 2, significantly more 4-year-olds than 2-year-olds were efficient; the older children showed greater competency with the task and were more flexible to changing task demands than the younger children. Interestingly, no age group was as flexible in Phase 2 as previously tested nonhuman primates, potentially related to their relatively reduced task exploration in Phase 1. Therefore, this causally clear task revealed changes in cognitive flexibility across both early childhood and species.
| S-EPMC7449664 | biostudies-literature
Project description:Accumulating neuroscience evidence indicates that human intelligence is supported by a distributed network of frontal and parietal regions that enable complex, goal-directed behaviour. However, the contributions of this network to social aspects of intellectual function remain to be well characterized. Here, we report a human lesion study (n = 144) that investigates the neural bases of social problem solving (measured by the Everyday Problem Solving Inventory) and examine the degree to which individual differences in performance are predicted by a broad spectrum of psychological variables, including psychometric intelligence (measured by the Wechsler Adult Intelligence Scale), emotional intelligence (measured by the Mayer, Salovey, Caruso Emotional Intelligence Test), and personality traits (measured by the Neuroticism-Extraversion-Openness Personality Inventory). Scores for each variable were obtained, followed by voxel-based lesion-symptom mapping. Stepwise regression analyses revealed that working memory, processing speed, and emotional intelligence predict individual differences in everyday problem solving. A targeted analysis of specific everyday problem solving domains (involving friends, home management, consumerism, work, information management, and family) revealed psychological variables that selectively contribute to each. Lesion mapping results indicated that social problem solving, psychometric intelligence, and emotional intelligence are supported by a shared network of frontal, temporal, and parietal regions, including white matter association tracts that bind these areas into a coordinated system. The results support an integrative framework for understanding social intelligence and make specific recommendations for the application of the Everyday Problem Solving Inventory to the study of social problem solving in health and disease.
| S-EPMC4163035 | biostudies-literature