时间戳

首页 > 解决方案 > Java - 使用 bellman-held-karp 算法的基于规则的排序

java - Java - 使用 bellman-held-karp 算法的基于规则的排序

问题描述

我在 CS SE 上问了以下问题，但不知道如何在 java 中实现答案（更不用说弄清楚它实际上在说什么）：

我想在花园里种一排。某些植物对某些植物有益而对其他植物有害，我正在尝试找到植物的最佳顺序：最相邻的朋友，没有相邻的敌人，如下表所定义（我各有一个）：

Num Vegetable     Friends      Foes
1   Watermelon    7,4,3        8,6
2   Tomatoes      9,8,6,5,1    7
3   Sunflowers    7,6,11  
4   Zucchini      9,7,3   
5   Eggplant      9,6,2        7,10
6   Cucumbers     9,7,3        8,1
7   Corn          8,6,4,3,1    5,2
8   Cantaloup     7,4,3        6,1
9   Bell peppers  6,5,11,10,2 
10  Swiss chard   2            5
11  Rhubarb       9,3

如何找到安排？

“Jakube”回答：

您可以通过简单地遍历所有 n! 不同的排列，并检查每个排列是否允许以及它有多好。这具有复杂性 O(n⋅n!)。

Bellman-Held-Karp 算法的变体将更快（但仍然是指数复杂度）。计算每一对 (V,v)，其中 V 是所有蔬菜的子集，并且 v∈V，如果有可能以一种方式排列蔬菜 V，使得 v 是最后一个并且它的最佳值是什么。您可以为此函数定义一个递归公式，并应用动态编程，就像在 BHK 算法中一样。这应该在 O(n 2 ⋅2n) 内运行。”

我最初问这个问题是因为我每个人都有一个，但现在意识到我需要一个可以偶尔重复的答案。我不确定他给出的答案是否适用于我拥有多个给定植物的情况。

标签： javaalgorithm

解决方案

我知道你标记了这个 Java，但这里有一些 Python 实现了那个动态程序。

import collections

Plant = collections.namedtuple("Plant", ("id", "name", "friends", "foes"))


def extend(first_plant, result):
    objective, other_plants = result
    return (
        (first_plant.id in other_plants[0].friends)
        + (other_plants[0].id in first_plant.friends)
        + objective,
        [first_plant] + other_plants,
    )


def best_order_recursive(first_plant, other_plants, cache):
    if not other_plants:
        return 0, [first_plant]
    cache_key = (first_plant.id, frozenset(plant.id for plant in other_plants))
    if cache is None:
        cache = {}
    else:
        cache_value = cache.get(cache_key)
        if cache_value is not None:
            return cache_value
    value = max(
        (
            extend(
                first_plant,
                best_order_recursive(
                    next_plant, other_plants[:i] + other_plants[i + 1 :], cache
                ),
            )
            for (i, next_plant) in enumerate(other_plants)
            if first_plant.id not in next_plant.foes
            and next_plant.id not in first_plant.foes
        ),
        default=(float("-inf"), [first_plant]),
    )
    cache[cache_key] = value
    return value


def best_order(plants):
    cache = {}
    return max(
        best_order_recursive(first_plant, plants[:i] + plants[i + 1 :], cache)
        for (i, first_plant) in enumerate(plants)
    )


def main():
    objective, plants = best_order(
        [
            Plant(1, "Watermelon", {7, 4, 3}, {8, 6}),
            Plant(2, "Tomatoes", {9, 8, 6, 5, 1}, {7}),
            Plant(3, "Sunflowers", {7, 6, 11}, set()),
            Plant(4, "Zucchini", {9, 7, 3}, set()),
            Plant(5, "Eggplant", {9, 6, 2}, {7, 10}),
            Plant(6, "Cucumbers", {9, 7, 3}, {8, 1}),
            Plant(7, "Corn", {8, 6, 4, 3, 1}, {5, 2}),
            Plant(8, "Cantaloupe", {7, 4, 3}, {6, 1}),
            Plant(9, "Bell peppers", {6, 5, 11, 10, 2}, set()),
            Plant(10, "Swiss chard", {2}, {5}),
            Plant(11, "Rhubarb", {9, 3}, set()),
        ]
    )
    print(objective)
    print(*(plant.name for plant in plants), sep=", ")


if __name__ == "__main__":
    main()

推荐阅读