算法找到在一定的约束项的最佳组合 [英] Algorithm to find the best combination of items under certain constraints

问题描述

我会尽力解释，在数学语言的问题。
假设我有一组项目 X = {X_1，X_2，...，x_n} 。对中的每一项X 属于集中的一个 S_1，S_2，...，S_5 。我认为 X 所有由5个项目的子集： {x_i1，x_i2，...，xi5} 让 x_i1 属于 S_1 ，...， x_i5 $ belogns到 S_5 。
部分子集被认为是正确的，一些被认为是不正确的。子集被认为是正确的，如果它不包含冲突项目。我有一个函数f1至determing如果对项目发生冲突或没有。
我也有一个函数f2它可以比较这种正确的子集，并说这集是更好的（他们可能是等于为好）。
我需要找到最好不冲突的子集（S）。

I'll try to explain the problem in the math language.
Assume I have a set of items X = {x_1, x_2, ..., x_n}. Each item of X belongs to one of the sets S_1, S_2, ..., S_5. I consider all the subsets of X consisting of 5 items: {x_i1, x_i2, ..., xi5} so x_i1 belongs to S_1, ..., x_i5 belogns to S_5.
Some subsets are considered to be correct and some are considered to be not correct. Subset is considered to be correct if it does not contain conflicting items. I have a function f1 to determing if a pair of items conflict or not.
I also have a function f2 which can compare such correct subsets and say which subset is better (they might be equal as well).
I need to find the best not-conflicting subset(s).

算法中我使用：
我建所有的子集，丢弃未正确的子集。然后我整理使用F2作为排序功能正确的子集，并把第一个（我用的快速排序算法）最好的子集（S）。至于有一个巨大的亚群的数量这一过程花的时间不够。

Algo I used:
I built all the subsets, discarded not-correct subsets. Then I sorted correct subsets using f2 as a sorting function and took first best subset(s) (I used quick-sort algorithm). As far as there were a huge number of subsets this procedure took insufficient amount of time.

有时间消费方面有更好的方法？

Is there a better approach in terms of time-consumption?

更新时间：
让我们考虑x_i的，如果是区间的整数端点。 F1返回true，如果2区间不相交，否则为假。 F2比较区间的长度总和在子集。

UPDATED
Let's think of x_i as if it's interval with integer endpoints. f1 returns true if 2 intervals do not intersect and false otherwise. f2 compares sum lengths of intervals in subsets.

推荐答案

这个问题是最大的加权区间调度算法的变化。该DP算法具有多项式复杂 O（N *日志（N））与为O（N）空间幼稚的问题，而 O（2 ^ G * N * LOGN（N））与 0的复杂性（2 ^ G * N）这种变化问题，其中， N 重present群体的总量不/空间子集（这里5）及间隔分别。

This problem is a variation of maximum weighted interval scheduling algorithm. The DP algorithm has polynomial complexity of O(N*log(N)) with O(N) space for the naive problem, and O(2^G * N * logn(N)) complexity with O(2^G * N) space for this variation problem, where G, N represent the total no of groups/subsets(5 here) & intervals respectively.

如果x_i不重新present间隔，那么问题是NP，这是其它解决方案已被证明。

If x_i doesn't represent intervals, then the problem is in NP, which other solutions have proved.

首先让我解释的最大加权区间调度的动态规划的解决方案，进而解决问题的变化。

First let me explain the dynamic programming solution for maximum weighted interval scheduling, and then solve the variation problem.

• 我们给出的起始和放大器;结束的时间间隔的点。让启动（我），结束（我），重（一）首发，结束点，该区间的区间长度我分别。
• 在排序的基础上递增的顺序开始点的区间。
• 让间隔的排序顺序是 1，2，...，N 。
• 让下一个（我）重present不与间隔重叠的下一个时间间隔我
• 允许定义一个子问题 S（I）为最大权重区间只考虑工作 I，I + 1，...，N 。
• S（1）是解决方案，即考虑所有作业 1,2，...，N 并返回最大权重区间。
• 现在，让定义 S（I）递归。

• We are given starting & ending points of the intervals. Let start(i), end(i), weight(i) be starting, ending point, interval length of the interval i respectively.
• Sort the intervals based on increasing order of start point.
• Let the sorted order of intervals be 1, 2, ... N.
• Let next(i) represent the next interval that doesn't overlap with interval i.
• Lets define a subproblem S(i) to be the maximum weighted interval only considering jobs i, i+1, ... N.
• S(1) is the solution, that considers all jobs from 1,2,... N and returns the maximum weighted interval.
• Now lets define S(i) recursively.

S(i)  = weight(i)                             if(i==N) // last job
      = max(weight(i)+S(next(i)), S(i+1)

该解决方案的复杂性是 O（N *日志（N）+ N）。 N *日志（N）查找下一个（我）所有作业，而ñ 解决的子问题。空间是 O（N）保存子问题的解决方案。

Complexity of this solution is O(N*log(N) + N). N*log(N) for finding next(i) for all jobs, and N for solving the subproblems. Space is O(N) for saving subproblem solutions.

现在，让我们解决这个问题的变化。

Now, lets solve variation of this problem.

• 让我们共同看看所有的间隔十，每个区间所属的集S_1，... S_5之一。
• 让启动（我），结束（我），重（一） ，子集（I）首发，结束点，区间长度，间隔子集我分别。
• 在排序的基础上递增的顺序开始点的区间。
• 让间隔的排序顺序是 1，2，...，N 。
• 让下一个（我）重present不与间隔重叠的下一个时间间隔我
• 允许定义一个子问题 S（I，待定）为最大权重区间只考虑工作 I，I + 1，... ñ和挂起是亚群，我们必须选择每一个间隔的列表。
• S（1，{S_1，... S_5}）是解决方案，即考虑所有作业 1，...，N ，选择一个时间间隔，每个 S_1，... S_5 并返回最大权重区间。
• 现在，让定义 S（I）递归如下：

• Lets collectively look at all the intervals in X. Each interval belongs to one of the sets S_1,... S_5.
• Let start(i), end(i), weight(i), subset(i) be starting, ending point, interval length, subset of the interval i respectively.
• Sort the intervals based on increasing order of start point.
• Let the sorted order of intervals be 1, 2, ... N.
• Let next(i) represent the next interval that doesn't overlap with interval i.
• Lets define a subproblem S(i, pending) to be the maximum weighted interval only considering jobs i, i+1, ... N and pending is a list of subsets from which we have to choose one interval each.
• S(1, {S_1,...S_5}) is the solution, that considers all jobs 1,...N , chooses one interval for each of S_1,...S_5 and returns the maximum weighted interval.
• Now lets define S(i) recursively as follows.

S(i, pending)  = 0                          if(pending==empty_set) // possible combination
               = -inf                       if(i==N && pending!={group(i)}) // incorrect combination
               = S(i+1, pending)            if(group(i) not element of pending)
               = max(weight(i)+S(next(i), pending-group(i)),
                     S(i+1, pending)

请注意，我可能已经错过了一些基本情况。

Note that I may have missed some base cases.

该算法中的复杂性是 O（2 ^ G * N * LOGN（N））与 O（2 ^ G * N）的空间。 2 ^ G *ñ重presents子问题大小。

Complexity of this algo is O(2^G * N * logn(N)) with O(2^G * N) space. 2^G * N represents the subproblem size.

作为估计，为 G＆LT小值= 10 和的高值N＆GT; = 100000 ，这种算法中快速运行pretty的。对于 G＆GT中值= 20 ， N'LT = 10000 应较低，以及该算法中收敛。而对于高值 G＆GT;。= 40 ，该算法中不收敛

As an estimate, for small values of G<=10 and high values of N>=100000, this algo runs pretty quickly. For medium values of G>=20, N<=10000 should be low as well for this algo to converge. And for high values of G>=40, the algo doesn't converge.

这篇关于算法找到在一定的约束项的最佳组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！