0

あるプレイヤー X がプレイヤー Y にボールをパスしたいゲームがありますが、彼は複数のプレイヤーとプレイでき、他のプレイヤーは Y にボールをパスできます。

ボールが X から Y に移動できるパスは何通りあるか知りたいです。

たとえば、彼が 3 人のプレーヤーでプレーしている場合は 5 つの異なるパスがあり、4 人のプレーヤーでプレーしている場合は 16 のパスがあり、20 人のプレーヤーでプレーしている場合は 330665665962404000 のパスがあり、40 人のプレーヤーで 55447192200369381342665835466328897344361743780 のパスがあります。数最大。一緒に遊べる選手は500人。

カタロニア数字を使用することを考えていましたか? これを解決するための正しいアプローチだと思いますか？ヒントを教えてください。

4

5 に答える 5

4

一見すると、考えられるパスの数は次のように計算できると思います (「パス」とは、複数回出現するプレーヤーがいない一連のプレーヤーであると想定しています)。

n+2プレーヤー、つまりプレーヤー X、プレーヤー Y、およびnパスで発生する可能性のある他のプレーヤーと一緒にプレイする場合。

0次に、パスには、、、、、、、1または2プレイヤー3X n-1(n開始) とプレイヤー Y (終了) の間の「中間」プレイヤーを含めることができます。

プレイヤー全体からk( 1 <= k <= n) 人のプレイヤーを選択した場合、これをいくつかの方法で行うことができます。n(n choose k)

この中間プレーヤーのサブセットごとに、k!可能なプレーヤーの配置があります。

したがって、これにより が得られsum(i=0 to n: (n choose i) * i!)ます。

「より良い」読書のために：

---- n     / n \           ---- n      n!            ---- n      1
\          |   |           \        --------         \         ------
/          |   | * i!   =  /         (n-i)!   =  n!  /           i!
---- i=0   \ i /           ---- i=0                  ---- i=0

しかし、これらはカタロニアの数字ではないと思います。

于 2010-05-28T13:28:35.190 に答える
1

これは実際には組み合わせ論の問題であり、アルゴリズムの問​​題ではありません。

プレーヤー X からプレーヤー Y への異なるパスの数を F(n) とマークします。ここで、n は Y を含み、X を含まないプレーヤーの数です。プレーヤー X はボールを Y に直接パスするか (オプション 1)、他のプレーヤーの 1 人にパスする (オプション n-1) ことができます。X が別のプレイヤーにパスした場合、フィールドに n-1 人のプレイヤーがいる場合、そのプレイヤーが新しい X であると見なすことができます (「古い」X はもはやゲームに存在しないため)。そのため、F(n) = 1 + (n-1)F(n-1) および F(1) = 1

この回答から phimuemue の回答に到達できると確信しています。問題は、再帰的なソリューションを好むか、合計を使用するソリューションを好むかです。

于 2010-05-28T13:37:11.177 に答える
0

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を削除します。これらは、上記のすべてに共通しており、質問に変換されます。0からnまでのkのk順列の合計は何ですか。ここで、nは数値です。 Pの。

これは次のように与えることができます

f(n):=sum(n!/(n-i)!,i,0,n);

19と39（表記では20と40）の結果を確認できます。

f（499）の場合

6633351524650661171514504385285373341733228850724648887634920376333901210587244906195903313708894273811624288449277006968181762616943058027258258920058014768423359811679381900054568501151839849768338994244697593758840394106353734267539926205845992860165295957099385939316593862710470512043836452624452665801937754479602741031832540175306674471495745716725509714798824661807396000105338256698426305553340786519843729411660457896089840381658295930455362209587765698327585913037665131195504013431486823990271059962837959407778393078276213331859189770016153265512805722812864376997337140529242894215031131618375899072989922780132488077015246576266246551484603286735418485007674249207286921801779414240854077425752351919182464902664206622037834736215298295580945851569079682952183639701057397376328170754187008425429164206646365285647875545882646729176997107332605851460212415526607757545366695048460341802079614840254694664267117469603856584752270653889630424848913719533359942725361985274851471687885265903663806182184272555073708882789845441094009797907518245726494471433964169680271980763830020431957658400573531564215436064984091520

wxMaximaで得られた結果

于 2010-05-28T14:21:55.847 に答える
0

私はこの種の検索には多少慣れていませんが、数字をざっと見てみると、トリミング、切り取り、フィルター処理を行うほど、より高速に実行できることがわかります。あなたが引用する数字はBIGです。

最初に頭に浮かぶのは、「検索の深さを制限することは実際的ですか?」ということです。検索の深さを 4 (任意の数) に制限できる場合、最悪の場合の可能性の数は ...

499 * 498 * 497 * 496  = 61,258,725,024  (assuming no one gets the ball twice)

これはまだ大きいですが、徹底的な検索は、元の数値セットよりもはるかに高速です (ただし、ゲームには遅すぎます)。

この分野でより多くの経験を持つ他の人がより良い提案をしてくれると確信しています。それでも、これがお役に立てば幸いです。

于 2010-05-28T13:36:47.967 に答える
-1

編集：質問のコメントからさらに明確にした後、私の答えは絶対に役に立たない:)彼は間違いなく可能なルートの数を望んでおり、最良のルートではありません！

私の最初の考えは、なぜこれらの数字を知りたいのですか？500人が利用できるすべてのパスを繰り返すことは決してありません（時間がかかりすぎるでしょう）。また、UIに意味のある方法で表示するには大きすぎます。

ボールがとることができる最適なルートを見つけようとしていると思います。その場合、ルート内のノードの数を気にしないアルゴリズムを検討することを検討します。

Aスターアルゴリズムとダイクストラのアルゴリズムを見てみます。

于 2010-05-28T13:23:00.380 に答える