次佳解、最重要元及再生演算法

Abstract

在本篇論文中，我們將定義組合問題中的再生問題。假如我們可以解決組 合問題中的再生問題。則我們就可以找到次佳解及最重要元。找到最重要 元的最直接的方法是重覆地解原始問題。為了避免重覆執行原來的演算法 ，我們萃取及再利用已經求得的資訊。這種再利用方式的演算法，我們稱 之為再生演算法。在本篇論文中，我們將敘述兩個再生演算法。然後，瀏 覽一些再生演算法，並且討論它們的再生策略。雖然，我們無法有一致的 方法來作再生策略，但我們主張利用有效率的再生演算法來解決一些問題 。 In this paper, we formulate the concept of recycling problems for combinatorial problems. If we solve the recycling problem of a combinatorial problem, we can find the second optimal solution(s) and the critical element(s). A naive method of finding the critical element, for example, is to repeatedly solve the original problem several times. To avoid repeated execution of an algorithm, we extract and reuse information from what we have solved. We call algorithms that reuse information in this way recycling algorithms. Two recycling algorithms are presented in this paper. Furthermore, we survey several recycling algorithms and discuss their recycling strategies which are problem-dependent. Though we cannot provide a unifying approach to recycling strategies, we advocate the use of efficient recycling algorithms for a variety of problems.