Algorithm development and research typically focus on algorithm design and implementation. For example, many algorithms have tackled the Traveling Salesman Problem (TSP) in order to increase the efficiency of a single method to apply to many sample graphs. Other types of research break down special cases of a problem, such as the Dynamic Traveling Salesman Problem or the Asymmetric TSP. We will suggest a different tactic and develop a rudimentary system to test it.;We propose a new "metaprocessor" algorithm which clusters graphs based on various similarity measures. For each cluster, this new algorithm finds the appropriate algorithm(s) for solving problems in that cluster: data clustering leads to algorithm clustering. The consequence is that instead of the traditional approach of solving problems using Occam's razor-where only one "best" of several candidate problem-solving methods survives-we propose an Epicurean problem-solving approach where all methods can perform better together than any single algorithm could on its own. Our system is designed to statistically analyze a graph and compare it along several dimensions to a database of solved and analyzed graphs. We believe that graphs will cluster along certain dimensions and that known algorithms and heuristics can perform differentially across these different clusters. For instance, a small graph, i.e., a small number of nodes, is a fine candidate for a simple brute force method. On current hardware, however, that method is not an option for graphs of tens of thousands of nodes or larger. On graphs that are larger or denser, then ant colony systems, river formation dynamics, or optimization heuristics may be a better alternative.
展开▼
