查找不同路径的数量
我有一个游戏，一名球员 X 想要将球传给球员 Y，但他可以与多名球员一起玩，其他球员可以将球传给 Y。
我想知道球可以走多少种不同的路径从 X 到 Y？
例如，如果他与 3 名球员一起比赛，则有 5 条不同的路径，4 名球员则有 16 条路径，如果他与 20 名球员比赛，则有 330665665962404000 条路径，而 40 名球员则有 55447192200369381342665835466328897344361743780 条路径。 最大数量他可以玩的玩家数量是 500。
我在考虑使用加泰罗尼亚数字？您认为解决这个问题的正确方法是什么？ 你能给我一些建议吗？
I have a game that one player X wants to pass a ball to player Y, but he can be playing with more than one player and the others players can pass the ball to Y.
I want to know how many different paths can the ball take from X to Y?
for example if he is playing with 3 players there are 5 different paths, 4 players 16 paths, if he is playing with 20 players there are 330665665962404000 paths, and 40 players 55447192200369381342665835466328897344361743780 that the ball can take.
the number max. of players that he can play with is 500.
I was thinking in using Catalan Numbers? do you think is a correct approach to solve this?
Can you give me some tips.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
乍一看，我想说，可能的路径数量可以通过以下方式计算（我假设“路径”是玩家的序列，没有玩家出现超过一次）。
如果您与
n+2个玩家一起玩，即玩家 X、玩家 Y 和路径中可能出现的n个其他玩家。那么路径可以包含
0,1,2,3, ... ,n-玩家 X（开始）和玩家 Y（结束）之间有 1或n个“中间”玩家。如果您从总共
n名玩家中选择k(1 <= k <= n) 名玩家，您可以在中执行此操作>(n 选择 k)方式。对于中间玩家的每个子集，都有
k!种可能的玩家安排。所以这会产生
sum(i=0 to n: (n select i) * i!)。为了“更好”的阅读：
但我认为这些不是加泰罗尼亚数字。
At first sight, I would say, that tht number of possible paths can be calculated the following way (I assume a "path" is a sequence of players with no player occuring more than once).
If you play with
n+2players, i.e. player X, player Y andnother players that could occur in the path.Then the path can contain
0,1,2,3, ... ,n-1orn"intermediate" players between player X (beginning) and player Y (end).If you choose
k(1 <= k <= n) players fromnplayers in total, you can do this in(n choose k)ways.For each of this subsets of intermediate players, there are
k!possible arrangements of players.So this yields
sum(i=0 to n: (n choose i) * i!).For "better" reading:
But I think that these are not the catalan numbers.
这实际上是组合学的问题，而不是算法的问题。
将从玩家 X 到玩家 Y 的不同路径的数量标记为 F(n)，其中 n 是包括 Y 但不包括 X 的玩家数量。
现在，有多少条不同的路径？球员 X 可以将球直接传给 Y（1 个选项），也可以将球传给其他球员之一（n-1 个选项）。如果 X 传球给另一个玩家，我们可以假装该玩家是新的 X，其中场上有 n-1 名玩家（因为“旧”X 不再在游戏中）。这就是为什么
F(n) = 1 + (n-1)F(n-1)
和
F(1) = 1
我很确定你可以从这个得到 phimuemue 的答案。问题是您更喜欢递归解决方案还是求和解决方案。
This is really a question in combinatorics, not algorithms.
Mark the number of different paths from player X to player Y as F(n), where n is the number of players including Y but not X.
Now, how many different paths are there? Player X can either pass the ball straight to Y (1 option), or pass it to one of the other players (n-1 options). If X passes to another player, we can pretend that player is the new X, where there are n-1 players in the field (since the 'old' X is no longer in the game). That's why
F(n) = 1 + (n-1)F(n-1)
and
F(1) = 1
I'm pretty sure you can reach phimuemue's answer from this one. The question is if you prefer a recursive solution or one with summation.
我对这种搜索有点菜鸟，但快速浏览一下这些数字表明，你可以修剪、剪掉、过滤掉的东西越多，你就能做得越快。你引用的数字很大。
首先想到的是“限制搜索深度是否实用？”如果您可以将搜索深度限制为 4（任意数字），则最坏情况下的可能性数量为...
这仍然很大，但详尽的搜索会快得多（尽管对于游戏来说仍然太慢）比你原来的一组数字。
我相信在这方面有更多经验的其他人会提出更好的建议。不过，我希望这会有所帮助。
I'm somewhat of a noob at this kind of searching, but a quick run through the numbers demonstrates the more you can trim, cut out, filter out, the faster you can do it. The numbers you cite are BIG.
First thing that comes to mind is "Is it practical to limit your search depth?" If you can limit your search depth to say 4 (an arbitrary number), your worst case number of possibilities comes out to ...
This is still large, but an exhaustive search would be far faster (though still too slow for a game) than your original set of numbers.
I'm sure others with more experience in this area would have better suggestions. Still, I hope this helps.
如果 X 需要传球给 Y，并且中间可能有 P1、P2、...、Pn 球员，并且您关心传球顺序，那么确实
对于 2 个额外球员，您有路径：XY、X-P1-Y， X-P2-Y、X-P1-P2-Y、X-P2-P1-Y
这总共给出了 5 条不同的路径，同样，对于 3 个额外的玩家，你有 16 条不同的路径
首先尝试将问题简化为已知的问题，为此，我将消除 XY，它们对于上述所有问题都是通用的，转化为问题：k 从 0 到 n 的 k 排列之和是多少，其中 n 是 P 的数量。
这可以给出为
和 I可以确认您对 19 和 39 的发现（您的符号中的 20 和 40）。
对于 f(499) 我得到
使用 wxMaxima 获得的结果
If X needs to pass to Y, and there could be P1, P2, ..., Pn players in between and you care about the order of passing then indeed
For 2 extra players you have paths: X-Y, X-P1-Y, X-P2-Y, X-P1-P2-Y, X-P2-P1-Y
Which gives a total of 5 different paths, similarly for 3 extra players you have 16 different paths
First try to reduce the problem to something known, and for this I would eliminate X-Y, they are common to all of the above translates to question: what is the sum of k-permutations for k from 0 to n, where n is the number of P.
This can be given as
and I can confirm your findings for 19 and 39 (20 and 40 in your notation).
For f(499) I get
Results obtained with wxMaxima
编辑：在对问题的评论进行更多澄清之后，我的回答绝对没有用:)他肯定想要可能的路线数量，而不是最好的路线！
我的第一个想法是你为什么想知道这些数字？您当然永远不会迭代 500 人可用的所有路径（这会花费太长时间），而且它太大，无法以任何有意义的方式在 ui 上显示。
我假设您将尝试找到球可以采取的最佳路线，在这种情况下，我会考虑研究不关心路线中节点数量的算法。
我会尝试查看 A 星算法 和 Dijkstra 算法。
EDIT: After more clarification from the comments of the question, my answer is absolutely useless :) he definitely wants the number of possible routes, not the best one!
My first thought is why do you want to know these numbers? You're certainly never going to iterate through all the paths available to 500 people (would take far too long) and it's too big to display on a ui in any meaningful way.
I'm assuming that you're going to try to find the best route that the ball can take in which case I would consider looking into algorithms that don't care about the number of nodes in a route.
I'd try looking at the A star algorithm and Dijkstra's algorithm.