给定一台可以对5个物体进行分类的机器.我们能以多快的速度排序其中的25个？

Question

假设您有25个对象,并且可以按照您甚至不知道的某些条件对其中的5个进行排序.使用这台机器的成本非常昂贵(一次发射需要1美元),那么分类所有物品的最低成本是多少？

我目前的解决方案非常简单(类似于合并排序的想法):

1. 随机将它们分成5组,每组5个
2. 对它们进行排序(+5次发布)
3. 现在,对这五个组中的最小元素进行排序(+1启动)
4. 现在我们拥有整套的最小元素.将其从它所属的组中删除,并重复步骤3,直到一般只留下5个未分类的对象(+19启动)
5. 对其余5个对象进行排序(+1启动)

因此,一般来说,我们必须支付26美元(26次发射).

问题:有没有办法让它更便宜(以最少的发布次数排序)？

Answer 1

这是一个贪心算法,用于选择在每次迭代时对哪些对象进行排序:

对25个对象进行排序a _i与完全填充表M _25x25相同,其中如果_i > a _j则M _i,j = 1 ,否则为-1.在您使用机器执行单次迭代排序后,您可以立即获得刚排序的元素之间的关系(最多可立即填充5个单元格),但之后您可以使用交换性填充更多单元格(即,如果a> b,则你知道b <a)和传递性(即,如果a> b和b> c,那么你知道a> c).

要为下一个排序选择5个元素,请选择元素,对应于这些元素的行和列之间的交叉点中有大多数空单元格.为此,您可以比较所有可能的组合.有25种选择5 = 53130种可能的变体,复杂性实际上是指数级的,但在这个问题上并没有花费任何"金钱".

当表格完全填充时,您可以使用拓扑排序构建排序序列,或者只是通过相应表格行中值的总和对元素进行排序:总和越大,元素越大.

这不是理想的,但非常有效.我已经在随机排列上测试了这种方法,结果平均约为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个元素,在考虑传递性之后,使用最大平均值(在它们的所有可能的排序结果上)填充单元格的数量.但是实现这个的天真算法需要更长的时间来计算.