1

1 人または複数の人が、誰がタスクを実行するかを決定するために使用できる最も単純なアルゴリズムは何ですか? 1 回だけ実行する必要がある 1 つのタスクと、1 人以上の人がいます。人々は話すことができます。つまり、メッセージを互いに送信できます。コミュニケーションは最小限にする必要があり、すべての人がまったく同じアルゴリズムを使用します。

1 人が「やっています」と言うだけでは不十分です。2 人が同時に言う可能性があるからです。

私の頭に浮かぶ最も単純なことは、各人が数字を言って少し待つということです. 誰かがその時間内に応答すると、数字が小さい人が「勝ち」、タスクを実行します。誰も応答しない場合、その人は自分がやっていると言い、それを実行します。彼女がやると言うと、他のみんなは引き下がります。2 人が同時にタスクを実行するのを避けるにはこれで十分ですが (待機/握手期間があるため)、両方の人が同じ数を言う場合は「2 回目のラウンド」が必要になる場合があります。

もっと簡単なものはありますか?

好奇心旺盛な人のために、SecondLife LSL スクリプトの複数のコピーを同期して、一度だけ何かを実行しようとしています。

4

9 に答える 9

1

ラッフル。

誰もが番号を取得します。それは座席番号かもしれませんし、チケットの半券番号かもしれません。

帽子に数字を入れて、1つ引き出して立ててもらいます。

これはまた、膨大な数にまで拡張でき、より高速です。弱点は、番号割り当ての前段階が必要なことです。

于 2009-06-14T16:03:08.530 に答える
1

答えは、ブロードキャスト メッセージを送信できるかどうかによって異なります。

ブロードキャストを送信できる場合は、ランダムな短い時間 (10ms) 待ってからブロードキャストを送信し、ネットワークの遅延を考慮して妥当な時間待機し、最初にメッセージを送信した人にブロードキャストを送信してもらいます。タスク。

ネットワークがそのネイバーのみを認識している場合は、同じことを行いますが、ラウンドで行います。各ラウンドで、別のシンを実行するいくつかのノードを排除します。

実際には、「最小数」ではなく「最も早い時間」を使用することをお勧めします。これは、最初になることが、より高速なマシンである/ネットワーク接続が良好である/アイドル状態であることと相関するという些細な理由からです。タスクを実行するために選択されたマシンのように。

于 2009-06-28T07:09:51.080 に答える
1

わかりました、これはロングショットです。たぶん、それは何らかの方法を定式化するのに役立ちます。

仮定。

  • マシン (LSL インスタンス) 間で通信する方法がある
  • タスクをすべてのインスタンスで実行するタスクとして発行できるタスク生成のポイントがある

選挙。

  • すべてのインスタンスで利用できるある種のリストを作成できる場合
  • タスク ジェネレーターは、リスト インスタンスを作成できます (または、リストに要件エントリを入力します)。
  • 他のインスタンスがリスト (またはその中の新しいエントリ) を検出します。
  • 要求を受け取りたいインスタンスが応答しなければならないタイムアウトがあります。
  • インスタンスは、ID をリストに追加して、タスクの完了に関心があることを示すことができます
  • タイムアウト後、最後に回答したものが選択されたものになります (または、ダイナミクスに応じて、リストの最初のものを選択できます)。この時点で、ジェネレーターが theat インスタンスの受け入れを投稿すると仮定しています
  • すべてのインスタンスがリストを見ることができれば、選挙がいつ完了したかを正しく知ることができます

個々のインスタンスの反応時間とそれらの可用性があなたの仕事をするはずです

于 2009-06-14T02:40:40.223 に答える
0

OK、これらは部屋にいる実在の人物なので、答えは簡単になり、それは一般的な解決策です。

最初はグー、じゃんけん。

全員がペアになってRPSをプレイします。簡単にするために、グループごとに2人と3人のプレーヤーを許可します(これによりオッズが完全に均等になるわけではありませんが)。すべてのラウンドの後、勝者は勝者とペアになり、勝者が1人になるまで繰り返します。

これは実際にはまともなスケーリングです!私はかつて間抜けなチームビルディングの砕氷船にいましたが、これは5分以内に500人以上が参加する大きな会議室で機能しました。

于 2009-06-14T16:00:48.520 に答える
0

結局、私はかなりうまく機能する解決策を思いついた。私は考え始めました-誰がタスクを実行するかを交渉するのではなく、衝突を最小限に抑えてみませんか(つまり、ボランティアを1人だけにしてみてください)。

主な原則は次のとおりです。

  • ボランティアが唯一のボランティアである場合、それを行うのは彼です
  • 2人(またはそれ以上)の人が同時にタスクを実行したい場合は、衝突を最小限に抑えるために、両方をランダムな期間待機させます

アルゴリズムは次のとおりです。

  1. 「Finished!」と聞こえたら いつでも、待っている間でも、再起動してください
  2. ランダムな時間(30mから1時間30mの間)待つ
  3. 事前定義された一定の時間(1サイクル、24時間)待機します
  4. やるべきことがあるなら
    1. 「私は生きている!」と言います
    2. 5秒待ちます(タスクが常に5秒未満で完了すると仮定します!)
    3. 「私は生きている!」と聞いたら その間
      1. 「私は生きている!」を繰り返します。
      2. 後藤2
    4. それ以外の場合(何も聞こえない場合)
      1. タスクを実行します
      2. 「終了しました!」と言います
  5. 再起動

これは基本的に、2つの可能な信号/メッセージ(「私は生きています!」と「終了しました!」)の文法があることを意味します。

nはクライアント/人の数です。理想的な条件では、これは、どのnに対しても衝突がない場合、サイクルごとに2つのメッセージを意味します。衝突がある場合、これは衝突ごとにサイクルごとに+2メッセージを意味します。可能性は低いですが、最悪の場合、メッセージがn個あり、このサイクルでタスクが完了しません。タスクが実行される最悪のシナリオでは、n+1個のメッセージがあります。

可能な簡略化

サイクルをスキップする余裕はありますが(このサイクルではタスクは完了しません)、次のサイクルの前に別のタスクを実行する余裕がないため、最初は全員に1サイクル待機させます。「サイクルごとに1つのタスク」の要件がない場合は、ステップ3をスキップできます。タスクが1サイクルで実行される保証はありませんが、ステップ2の値が大きく、ステップ4.2の値が小さく、少数のクライアント/人々にはかなりのチャンスがあります。

アルゴリズムは、1つの信号/メッセージでも機能します。手順1をスキップして、「私は生きています」と言うことができます。4.4.2でも同様ですが、4.4.1でステップ4のチェックがすぐに失敗する場合に限ります。

于 2009-06-16T22:42:13.950 に答える
0

これは LSL プロトタイプの実装です (パブリック ドメインですが、使用するためにはおそらく変更する必要があります):

// user configuration parameters
integer CHANNEL = -635;

// ------------------------------------------------

// scripter configuration parameters (in seconds)
float POLL_PERIOD = 60.0;               // 1 minute
// minimum length of suspend period
float CORE_SUSPEND_PERIOD = 15.0;       // 15 seconds 
// maximum length added to core suspend period (minimum is 0)
float MAX_RANDOM_SUSPEND_PERIOD = 30.0; // 30 seconds
float LOCK_PERIOD = 5.0;                // 5 seconds

// variables
integer lock = FALSE;


// mock poll method, assumes there are always tasks
integer poll()
{
    llSay(0, "Polling for tasks...");
    return TRUE;
}

// mock work method
work()
{
    llSay(0, "*** Executing task... ***");
}

default
{
    state_entry()
    {
        llSay(0, "Entering default state.");
        lock = FALSE;
        llListen(CHANNEL, "", NULL_KEY, "");
        llSetTimerEvent(POLL_PERIOD);
    }

    timer()
    {
        if (lock)
        {
            // step 4 - do some work
            work();
            // step 5 - make everybody go into suspend state
            // to make sure run times are randomized AND not sooner
            // than POLL_PERIOD
            llRegionSay(CHANNEL, "suspend");
            lock = FALSE;
            state suspended;
        }
        else
        {
            if (poll())
            {
                // step 1 - acquire lock
                llRegionSay(CHANNEL, "lock");
                lock = TRUE;
                // step 2 - wait and listen for others
                llSetTimerEvent(LOCK_PERIOD);
            }
        }
    }

    listen(integer channel, string name, key id, string message) 
    {
        // step 3 - did someone reply?
        if (message == "lock" && lock)
        {
            // other script woke up at the same time - signal
            // that you're here and suspend until next round,
            // where there will hopefully be a winner
            llSay(0, "Collision!");
            llRegionSay(CHANNEL, "lock");
            state suspended;
        }
        else if (message == "suspend")
            state suspended;
    }
}

state suspended
{
    state_entry()
    {
        // this gives random number between 0 and MAX_RANDOM_SUSPEND_PERIOD
        float random = llFrand(MAX_RANDOM_SUSPEND_PERIOD);
        float total = CORE_SUSPEND_PERIOD + random;
        llSetTimerEvent(total);
        llSay(0, "Entering suspended state for " + (string) ((integer) total)
            + " seconds.");
    }

    timer()
    {
        state default;
    }
}
于 2009-06-21T17:09:30.860 に答える