知识卡片

普通读书笔记卡 · 3713.a

抽象问题可表示为实例解关系

理解等级:初级

抽象问题是实例集合与解集合之间的关系,一例可以对应多个合法解;判定问题则把每个实例映射到0或1。

这样区分有助于把最短路等求解任务改写为可讨论复杂度类别的判定任务。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第34章 NP完全性 · 查看原书依据

      We define an abstract problem Q to be a binary relation on a set I of problem instances and a set S of problem solutions. For example, an instance for SHORTEST-PATH is a triple consisting of a graph and two vertices. A solution is a sequence of vertices in the graph, with perhaps the empty sequence denoting that no path exists. The problem SHORTEST-PATH itself is the relation that associates each instance of a graph and two vertices with a shortest path in the graph that connects the two vertices. Since shortest paths are not necessarily unique, a given problem instance may have more than one solution. This formulation of an abstract problem is more general than necessary for our purposes. As we saw above, the theory of NP-completeness restricts attention to decision problems: those having a yes/no solution. In this case, we can view an abstract decision problem as a function that

    参考来源

    - 位置:《算法导论(第4版)》第34章《NP完全性》(OEBPS/chapter034.xhtml,文本字符[15000,20000))。 - 结论依据:原文复杂度类别、判定问题、归约或编码定义;不把P与NP的未解关系写成已证明结论。 - 原始内容:We define an abstract problem Q to be a binary relation on a set I of problem instances and a set S of problem solutions . For example, an instance for SHORTEST-PATH is a triple consisting of a graph and two vertices. A solution is a sequence of vertices in the graph, with perhaps the empty sequence denoting that no path exists. The problem SHORTEST-PATH itself is the relation that associates each instance of a graph and two vertices with a shortest path in the graph that connects the two vertices. Since shortest paths are not necessarily unique, a given problem instance may have more than one solution. This formulation of an abstract problem is more general than necessary for our purposes. As we saw above, the theory of NP-completeness restricts attention to decision problems : those having a yes/no solution. In this case, we can view an abstract decision problem as a function that