假设你有25个对象，一台机器可以根据一些你甚至不知道的标准对其中的5个对象进行排序。使用这台机器的成本非常昂贵（一次发射需要1美元），那么对所有物品进行分类的最低成本是多少？
我目前的解决方案非常简单（类似于merge sort）：
随机分成5组，每组5个对象
对每一个进行排序（+5次发布）
现在，对这五个组的最小元素进行排序（+1次启动）
现在我们得到了整个集合的最小元素。将其从所属的组中移除，然后重复步骤3，直到只剩下5个未排序的对象（启动时间为+19）
对其余5个对象进行排序（+1次启动）
所以，一般来说，我们必须支付26美元（26次发射）。
问：有什么方法可以使它更便宜（以最少的发射次数分类）？
最佳答案
下面是一个贪婪的算法，用于在每次迭代时选择要排序的对象：
排序25个对象ai与完全填充表m25x25相同，其中mi，如果ai>a j，j=1，否则-1。在您使用机器执行一次排序迭代后，您将获得刚刚排序的元素之间的直接关系（最多可立即填充5个单元格），但之后您可以使用交换性（即，如果a>b，则您知道bb和b>c，则您知道a>c）。
若要选择5个元素进行下一次排序，请选择元素，在与这些元素相对应的行和列的交叉点中有大多数空单元格。因此，你可以比较所有可能的组合。有25个选择5＝53130个可能的变体，复杂性实际上是指数型的，但是在这个问题上不需要任何“钱”。
当表被完全填充时，您可以使用Topological sort构建排序序列，或者只需根据相应表行中的值之和对元素进行排序：总和越高，元素就越大。
这并不理想，但相当有效。我已经在随机排列上测试了这个方法，结果平均约为16.8美元。以下是python中的代码示例：
import random
import itertools
class SortingMachine:
def __init__(self):
self.coins = 0
def sort(self, elements):
assert(len(elements) == 5)
self.coins += 1
return list(sorted(elements))
def test_sorting(seq):
N = len(seq)
machine = SortingMachine()
table = [[0 if i == j else None for j in range(N)] for i in range(N)]
# Fill empty table cells using transitivity with Floyd-Warshall algorithm
def fill_transitive():
for k in range(N):
for i in range(N):
for j in range(N):
if table[i][j] is None and table[i][k] == table[k][j]:
table[i][j] = table[i][k]
# Register in the table the information that seq[i] > seq[j]
def set_greater(i, j):
table[i][j] = 1
table[j][i] = -1
# Register in the table information from 5 sorted elements
def register_sorted(sub):
for (el1, i1), (el2, i2) in zip(sub, sub[1:]):
set_greater(i2, i1)
# Select 5 elements to send to the machine
def choose_elements():
# Count empty cells in the cells corresponding to 5 comb elements
def empty_cells(comb):
return sum(table[i][j] is None
for i, el1 in comb for j, el2 in comb)
comb = max((empty_cells(comb), comb)
for comb in itertools.combinations(enumerate(seq), 5))[1]
return [(el, ind) for ind, el in comb]
# Return True if the table is completely filled
def is_complete():
return all(all(el is not None for el in row) for row in table)
while not is_complete():
chosen = choose_elements()
sorted_chosen = machine.sort(chosen)
register_sorted(sorted_chosen)
fill_transitive()
# Checking that the sorting is correct
sorted_seq = list(sorted(seq))
assert(all(sorted_seq.index(seq[ind]) == (sum(row) + N - 1) // 2
for ind, row in enumerate(table)))
return machine.coins
def random_sequence():
l = list(range(25))
random.shuffle(l)
return l
贪心启发式在这种方法中，最大限度地只获得从排序获得的即时信息，而不考虑传递性。现在，理论上，一个更好的启发式是最大化预期信息，对所选择的5个元素进行排序，包括通过传递性获得的所有信息。也就是说，选择5个元素，具有最大平均值（超过所有可能的排序结果）后的填充细胞数考虑及物性。但实现这种算法需要更长的计算时间。
关于algorithm - 给定一台可以分类5个对象的机器。我们可以对其中的25种进行分类的速度有多快？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/30265140/