基于主观偏好的排序算法迭代次数优化方案问询

我需要实现一个基于用户主观偏好排序列表的交互算法，通过input()实现用户交互。核心目标是最大化结果确定性的同时，最小化用户需要回答的迭代次数。

当前我实现了一个简单算法：从列表中随机选取两项，询问用户偏好项，将未被选中项的部分分配系数转移至选中项，并调整双方系数。现咨询：如何在不降低算法确定性的前提下，减少该排序算法的迭代次数？

原实现代码（带中文注释） #

# 给每个元素分配初始值为1.0的系数
def ListToDict(list_of_items):
    food_dict = {}
    for item in list_of_items:
        food_dict[item] = 1.0
    return food_dict

# 询问用户在两个选项中做选择
def AskUser(item_name_one, item_name_two):
    print("\n [" + item_name_one + "]  or  [" + item_name_two + "] ?")
    user_choice = input("--> ")
    if user_choice == "1" or user_choice == "2":
        return int(user_choice)
    else:
        print("\n请输入1或2！")
        return AskUser(item_name_one, item_name_two)

# PerformSort函数更新每个项的系数
# 每一步都会让用户在两个项中做选择
# 如果用户选第一个项，
#   第一个项的系数增加第二个项系数的0.1倍，
#   第二个项的系数减少第一个项系数的0.1倍（原逻辑存在计算顺序问题）
# 用户选第二个项时则相反
# number_of_iterations参数越高，结果确定性越强，但用户需要回答更多问题
def PerformSort(my_dict, number_of_iterations):
    from random import randint
    length_of_dict = len(my_dict)
    
    for i in range(number_of_iterations):
        print("\n---- 第" + str(i + 1) + "轮迭代 ----")
        remaining_items = list(my_dict.keys())
        while len(remaining_items) > 1: 
            item_one = remaining_items[randint(0, len(remaining_items) - 1)]
            item_two = remaining_items[randint(0, len(remaining_items) - 1)]
            while item_one == item_two:
                item_two = remaining_items[randint(0, len(remaining_items) - 1)]
            user_choice = AskUser(item_one, item_two)
            if user_choice == 1:
                my_dict[item_one] += 0.1 * my_dict[item_two]
                my_dict[item_two] -= 0.1 * my_dict[item_one]
            elif user_choice == 2:
                my_dict[item_one] -= 0.1 * my_dict[item_two]
                my_dict[item_two] += 0.1 * my_dict[item_one]
            remaining_items.remove(item_one)
            remaining_items.remove(item_two)
    return my_dict

# 根据系数对列表进行降序排序
def OrderByCoeficient(food_dict):
    list_of_keys = list(food_dict.keys())
    list_of_keys.sort(key=lambda x: food_dict[x], reverse=True)
    return list_of_keys


if __name__ == "__main__":
    items_to_sort = [ "披萨", "芝士汉堡", "牛肉", "汤", "冰淇淋" ]
    my_dict = ListToDict(items_to_sort)
    my_dict = PerformSort(my_dict, 3)
    print("\n 以下是你的偏好排序（从高到低）：")
    print(OrderByCoeficient(my_dict))

优化方案 #

1. 优先对比系数最接近的项，而非随机配对 #

随机配对经常浪费用户时间在已有明确偏好的项上（比如系数差距大的两个），对提升结果确定性帮助极小。应该每次挑选当前系数最接近的一对让用户选择——这一对的排序是最不确定的，用户的选择能最大程度修正系数，快速缩小排序的不确定性。

2. 动态调整系数转移幅度，替代固定0.1 #

固定的0.1转移幅度在迭代后期效率很低：当两个项系数差距已经较大时，小幅度转移对排序结果几乎没有影响。可以根据两项的系数比例调整转移量：

• 当系数比例在0.8~1.2之间（接近相等），转移更大比例（比如0.2），快速明确排序关系；
• 当系数差距超过阈值（比如比例<0.5或>2），转移较小比例（比如0.05），避免过度修正。

3. 用“排序结果稳定”作为停止条件，替代固定迭代次数 #

固定迭代次数要么导致结果不够确定，要么做无用功。可以改成：当连续2~3次迭代后，排序结果的顺序完全没有变化，就停止迭代——既保证结果稳定，又不会让用户做多余回答。

4. 避免重复对比同一对项 #

维护一个已对比过的项对集合（比如用frozenset({item1, item2})存储），每次配对时跳过已经对比过的组合，彻底消除冗余提问。

5. 修正系数更新公式的逻辑错误 #

原代码中更新系数时，会先用修改后的item_one系数去计算item_two的减少量，导致逻辑矛盾。正确的做法是先计算固定的转移量，再同时更新两个系数：

# 用户选择item_one时的正确更新逻辑
transfer = 0.1 * my_dict[item_two]
my_dict[item_one] += transfer
my_dict[item_two] -= transfer

这样能避免数值误差累积，逻辑更严谨。

优化后的示例代码 #

def ListToDict(list_of_items):
    food_dict = {}
    for item in list_of_items:
        food_dict[item] = 1.0
    return food_dict

def AskUser(item_name_one, item_name_two):
    print("\n [" + item_name_one + "]  or  [" + item_name_two + "] ?")
    user_choice = input("--> ")
    if user_choice == "1" or user_choice == "2":
        return int(user_choice)
    else:
        print("\n请输入1或2！")
        return AskUser(item_name_one, item_name_two)

def GetClosestPair(item_dict):
    items = list(item_dict.keys())
    min_diff = float('inf')
    closest_pair = None
    # 遍历所有可能的项对，找到系数差最小的一对
    for i in range(len(items)):
        for j in range(i+1, len(items)):
            diff = abs(item_dict[items[i]] - item_dict[items[j]])
            if diff < min_diff:
                min_diff = diff
                closest_pair = (items[i], items[j])
    return closest_pair

def GetTransferRatio(coef1, coef2):
    ratio = min(coef1, coef2) / max(coef1, coef2)
    if ratio >= 0.8:
        return 0.2  # 系数接近时，转移更大比例
    elif ratio >= 0.5:
        return 0.15
    else:
        return 0.05  # 系数差距大时，转移小比例

def PerformSortOptimized(my_dict, max_stable_iterations=2):
    compared_pairs = set()
    last_order = None
    stable_count = 0

    while stable_count < max_stable_iterations:
        current_order = OrderByCoeficient(my_dict)
        # 如果排序结果和上一次一致，稳定计数加1
        if current_order == last_order:
            stable_count += 1
        else:
            stable_count = 0
            last_order = current_order

        remaining_items = list(my_dict.keys())
        while len(remaining_items) > 1:
            # 获取系数最接近的未对比过的项对
            pair = GetClosestPair({k:v for k,v in my_dict.items() if k in remaining_items})
            if not pair:
                break
            pair_frozen = frozenset(pair)
            # 如果已经对比过，跳过并移除其中一个项（避免死循环）
            if pair_frozen in compared_pairs:
                remaining_items.remove(pair[0])
                continue
            compared_pairs.add(pair_frozen)
            
            item_one, item_two = pair
            user_choice = AskUser(item_one, item_two)
            
            # 计算动态转移比例
            transfer_ratio = GetTransferRatio(my_dict[item_one], my_dict[item_two])
            if user_choice == 1:
                transfer = transfer_ratio * my_dict[item_two]
                my_dict[item_one] += transfer
                my_dict[item_two] -= transfer
            else:
                transfer = transfer_ratio * my_dict[item_one]
                my_dict[item_two] += transfer
                my_dict[item_one] -= transfer
            
            remaining_items.remove(item_one)
            remaining_items.remove(item_two)
        print("\n---- 当前排序已稳定{}轮 ----".format(stable_count+1))
    return my_dict

def OrderByCoeficient(food_dict):
    list_of_keys = list(food_dict.keys())
    list_of_keys.sort(key=lambda x: food_dict[x], reverse=True)
    return list_of_keys

if __name__ == "__main__":
    items_to_sort = [ "披萨", "芝士汉堡", "牛肉", "汤", "冰淇淋" ]
    my_dict = ListToDict(items_to_sort)
    my_dict = PerformSortOptimized(my_dict)
    print("\n 以下是你的偏好排序（从高到低）：")
    print(OrderByCoeficient(my_dict))

内容的提问来源于stack exchange，提问作者Genaro.exe