兩個組合最優化的問題

Abstract

本篇論文分為二個部分：一為偽幣問題，另一為最優分割問題。 偽幣問題大都以有序演算法來討論：如何利用天秤，找出偽幣？假使共測試t次， 每次至多測k個硬幣的情形下，本篇論文第一部份利用無序演算法的測試方式，在某些 t和k值下，對可測試的最大硬幣個數，給出最優解。並提供了測試矩陣的建構方式。 在最優分割上有一個很重要的性質------超模性（Supermodular）。本篇論文第二部份 找到了不管是編號或不編號限制類型分割均不是超模函數的反例。

There are two main parts in this thesis, one is the counterfeit coin's problem, the other is the optimal partition problem. The first problem is to find the counterfeit coin using a scale through a nonadaptive algorithm. We give the optimal solution of the maximum number of tested coins in t given tests for some t and k. We also provide the construction of testing matrices. Supermodularity is one of the important properties in optimal partion. In the second part of the thesis, we give two counterexample to show that both labeled and unlabeled constrained-shape-partitions are not supermodular.