每实例算法选择问题

英文

per-instance algorithm selection problem

英文释义

given a computational problem, a set of algorithms for solving this problem, and a specific instance that needs to be solved, determine which of the algorithms can be expected to perform best on that instance

中文释义

给定一个计算问题、一组用于解决该问题的算法和一个需要解决的特定实例，确定哪种算法在该实例上的性能最好

问题建模

给定问题P的一组实例集合I，P的算法集合A={A1, A2,..., An} 以及矩阵 m：A × I ->R 。其中，m用来度量A中的每个的算法在I中实例上的表现。构建一个选择器(selector)S, 将I中的每个实例i映射为A中的算法S(i)，使得S在I上的性能最优（根据度量矩阵m）。

来源

Automated Algorithm Selection: : Survey and Perspective p4, 第二段； p6, Section2, 第一段