解决条件填充难题的排列/算法
我一直在四处挖掘，看看以前是否做过类似的事情，但没有看到任何具有镜像条件的东西。为了让这个问题更容易理解，我将把它应用到填充棒球队名单的背景下。
给定的名单结构组织如下：C，1B，2B，3B，SS，2B/SS（两者之一），1B/3B，OF，OF，OF，OF，UT（可以是任何位置）
每个球员都有至少有一个非替补位置（允许多个位置的位置），其中他们有资格，并且在许多情况下不止一个（即可以玩 1B 和 OF 等的玩家）。假设您是一支球队的经理，该球队已经有一些球员，并且您想查看您的任何位置是否有特定球员的空间，或者您是否可以移动一名或多名球员以打开一个位置，其中他有资格。
我最初的尝试是使用条件排列并在列表中收集每个玩家所有可能的独特“阵容”，在移动到下一个玩家之前更新空位。这还要求（因为玩家移动的顺序会影响下一个玩家可用的位置）正在循环的列表被重新排序，然后再次循环。我仍然认为这是可行的方法，但有许多陷阱阻碍了该功能。
您假设给出的启动循环的数据是： 1. 被评估球员可以上场的位置列表（被检查是否适合的位置） 2.当前名单上的球员列表以及每个球员有资格获得的位置（我当前正在存储列表列表并使用列表索引作为球员的唯一标识符） 3. 目前名单中空缺职位的列表 事实
证明，这比我最初预期的更令人头疼。一位同事甚至向我建议，我所遇到的情况（在更大范围内涉及每个对象的条件分配）是 NP 完全的。我确信事实并非如此，因为一旦一名球员在正在测试的特定阵容中重新定位，一旦另一名球员移动，整个名单就不需要再次迭代。这就是它的长处和短处，我最终决定将其开放给论坛。
感谢任何人可以提供的帮助。由于限制，我无法发布部分代码（其中一些是遗留代码）。然而，它正在被翻译成.NET（目前是C#）。如果需要其他信息，我将尝试重写该函数的一些简短片段以供发布。
Joseph G.
已编辑 07/24/2010 非常感谢您的回复。我实际上确实考虑过使用遗传算法，但最终放弃了它，因为确定序数结果的工作量是多余的。测试的最终目的是确定是否确实存在返回正值的场景。无需确定每个工作解决方案的相对优势。
我感谢您对我提出问题的背景可能不熟悉的反馈。实际的模型是跨多个特定于平台的构建服务器分发构建命令。它是可以访问的，但我不想深入了解为什么某些构建任务只能在某些系统上执行以及为什么某些系统只能执行某些类型的构建命令。
看来您已经掌握了我所介绍内容的要点，但这里有一个不太具体的不同模型。在有序列表数组中有一组离散位置（我将这些称为“位置”）：
((2), (2), (3), (4), (5), ( 6), (4, 6), (3, 5), (7), (7), (7), (7), (7), (2, 3, 4, 5, 6, 7))
另外，有一个无序列表数组（我将其称为“员工”），如果其数组具有与其要分配到的有序列表相同的成员，则该数组只能占用其中一个槽。完成初始分配后，如果有额外的员工出现，我需要确定他是否可以填补其中一个空缺职位，如果不能，是否可以重新安排现有员工以允许该员工可以填补的职位之一可供使用。
我想避免使用蛮力，因为这大约是 40 - 50 个对象（并且很快就会增加），在运行时计算单独的确定将非常昂贵。
I've been digging around to see if something similar has been done previously, but have not seen anything with the mirrored conditions. To make swallowing the problem a little easier to understand, I'm going to apply it in the context of filling a baseball team roster.
The given roster structure is organized as such: C, 1B, 2B, 3B, SS, 2B/SS (either or), 1B/3B, OF, OF, OF, OF, UT (can be any position)
Every player has at least one of the non-backup positions (positions that allow more than one position) where they're eligible and in many cases more than one (i.e. a player that can play 1B and OF, etc.). Say that you are manager of a team, which already has some players on it and you want to see if you have room for a particular player at any of your slots or if you can move one or more players around to open up a slot where he is eligible.
My initial attempts were to use a conditional permutation and collect in a list all the possible unique "lineups" for each player, updating the open slots before moving to the next player. This also required (since the order that the player was moved would affect what positions were available for the next player) that the list being looped through was reordered and then looped through again. I still think that this is the way to go, but there are a number of pitfalls that have snagged the function.
The data to start the loop that you assume is given is:
1. List of positions the player being evaluated can player (the one being checked if he can fit)
2. List of players currently on the roster and the positions each of those is eligible at (I'm currently storing a list of lists and using the list index as the unique identifier of the player)
3. A list of the positions open as the roster currently is
It's proven a bigger headache than I originally anticipated. It was even suggested to me by a colleague that the situation I have (which involves, on a much larger scale, conditional assignments for each object) was NP-complete. I am certain that it is not, since once a player has been repositioned in a particular lineup being tested, the entire roster should not need to be iterated over again once another player has moved. That's the long and short of it and I finally decided to open it up to the forums.
Thanks for any help anyone can provide. Due to restrictions, I can't post portions of code (some of it is legacy). It is, however, being translated in .NET (C# at the moment). If there's additional information necessary, I'll try and rewrite some of the short pieces of the function for post.
Joseph G.
EDITED 07/24/2010
Thank you very much for the responses. I actually did look into using a genetic algorithm, but ultimately abandoned it because of the amount of work that would go into the determination of ordinal results was superfluous. The ultimate aim of the test is to determine if there is, in fact, a scenario that returns a positive. There's no need to determine the relative benefit of each working solution.
I appreciate the feedback on the likely lack of familiarity with the context I presented the problem. The actual model is in the distribution of build commands across multiple platform-specific build servers. It's accessible, but I'd rather not get into why certain build tasks can only be executed on certain systems and why certain systems can only execute certain types of build commands.
It appears that you have gotten the gist of what I was presenting, but here's a different model that's a little less specific. There are a set of discrete positions in an ordered array of lists as such (I'll refer to these as "positions"):
((2), (2), (3), (4), (5), (6), (4, 6), (3, 5), (7), (7), (7), (7), (7), (2, 3, 4, 5, 6, 7))
Additionally, there is a an unordered array of lists (I'll refer to as "employees") that can only occupy one of the slots if its array has a member in common with the ordered list to which it would be assigned. After the initial assignments have been made, if an additional employee comes along, I need to determine if he can fill one of the open positions, and if not, if the current employees can be rearranged to allow one of the positions the employee CAN fill to be made available.
Brute force is something I'd like to avoid, because with this being on the order of 40 - 50 objects (and soon to be increasing), individual determinations will be very expensive to calculate at runtime.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我根本不懂棒球，如果我走错了路，很抱歉。虽然我确实喜欢圆角手，但圆角手只有两个位置可以打，击球手或其他人。
您是否考虑过使用遗传算法来解决这个问题？它们非常擅长解决 NP 难题，并且在处理轮班和时间表类型问题上也表现得非常好。
您拥有一个可以轻松评分和操作的解决方案模型，这对于遗传算法来说是一个良好的开端。
对于总排列太大而无法计算的更复杂的问题，遗传算法应该在相当短的时间内找到接近最优或优秀的解决方案（以及大量其他有效解决方案）。尽管如果你希望每次都能找到最佳解决方案，那么你很可能不得不暴力破解它（我只是浏览了这个问题，所以情况可能并非如此，但听起来可能是这样）。
在您的示例中，您将有一个解决方案类，这代表一个解决方案，即棒球队的阵容。您随机生成 20 个解决方案，无论它们是否有效，然后您就有一个对解决方案进行评级的评级算法。在你的情况下，阵容中更好的球员会比更差的球员得分更多，并且任何无效的阵容（无论出于何种原因）都会强制得分为 0。
任何 0 得分的解决方案都会被取消，并替换为新的随机的，其余的解决方案聚集在一起形成新的解决方案。从理论上讲，经过足够的时间后，解决方案池应该会有所改善。
这样做的好处是不仅可以找到大量有效的独特阵容，还可以对它们进行评级。您没有在问题中指定需要对解决方案进行评分，但它提供了很多好处（例如，如果一名球员受伤，他可以暂时被评为 -10 或其他）。所有其他玩家根据他们的可量化统计数据得分。
它具有可扩展性并且性能良好。
I don't understand baseball at all so sorry if I'm on the wrong track. I do like rounders though, but there are only 2 positions to play in rounders, a batter or everyone else.
Have you considered using Genetic Algorithms to solve this problem? They are very good at solving NP hard problems and work surprisingly well for rota and time schedule type problems as well.
You have a solution model which can easily be scored and easily manipulated which is a great start for a genetic algorithm.
For more complex problems where the total permutations are too large to calculate a genetic algorithm should find a near optimum or excellent solution (along with lots and lots of other valid solutions) in a fairly short amount of time. Although if you wish the find the optimum solution every time, you are going to have to brute force it in all likelihood (I have only skimmed the problem so this may not be the case but it sounds like it probably is).
In your example, you would have a solution class, this represents a solution, IE a line-up for the baseball team. You randomly generate say 20 solutions, regardless if they are valid or not, then you have a rating algorithm that rates the solution. In your case, a better player in the line-up would score more than a worse player, and any invalid line-ups (for whatever reason) would force a score of 0.
Any 0 scoring solutions are killed off, and replaced with new random ones, and the rest of the solutions breed together to form new solutions. Theoretically and after enough time the pool of solutions should improve.
This has the benefit of not only finding lots of valid unique line-ups, but also rating them. You didn't specify in your problem the need to rate the solutions, but it offers plenty of benefits (for example if a player is injured, he can be temporarily rated as a -10 or whatever). All other players score based on their quantifiable stats.
It's scalable and performs well.
听起来好像你有一个二分匹配问题。一个分区对于名单上的每个球员都有一个顶点。另一个有每个名册位置的顶点。当且仅当玩家可以玩该位置时，玩家顶点和位置顶点之间存在边。您对匹配感兴趣：没有重复端点的边集合。
给定球员的位置分配（匹配）和要容纳的新球员，有一个简单的算法来确定是否可以完成。将当前匹配中的每一条边从该位置指向玩家；将其他人从玩家那里引导到该位置。现在，使用广度优先搜索，寻找从新玩家到未分配位置的路径。如果你找到了，它会告诉你一系列可能的重新分配。如果不这样做，就无法与所有玩家进行匹配。
例如，假设玩家 A 可以打 1 或 2 位置，
我们临时将 A 分配给 2。现在 B 出现，只能打 2。直接画图：
我们找到一条路径
B->2->A- >1，表示“将 B 分配给 2，将 A 替换为 1”。有很多漂亮的理论来处理假设的匹配。遗传算法不需要应用。
编辑：我应该补充一点，由于使用了 BFS，它计算出破坏性最小的重新分配序列。
It sounds as though you have a bipartite matching problem. One partition has a vertex for each player on the roster. The other has a vertex for each roster position. There is an edge between a player vertex and a position vertex if and only if the player can play that position. You are interested in matchings: collections of edges such that no endpoint is repeated.
Given an assignment of players to positions (a matching) and a new player to be accommodated, there is a simple algorithm to determine if it can be done. Direct each edge in the current matching from the position to the player; direct the others from the player to the position. Now, using breadth-first search, look for a path from the new player to an unassigned position. If you find one, it tells you one possible series of reassignments. If you don't, there's no matching with all of the players.
For example, suppose player A can play positions 1 or 2
We provisionally assign A to 2. Now B shows up and can only play 2. Direct the graph:
We find a path
B->2->A->1, which means "assign B to 2, displacing A to 1".There is lots of pretty theory for dealing with hypothetical matchings. Genetic algorithms need not apply.
EDIT: I should add that because of the use of BFS, it computes the least disruptive sequence of reassignments.