2

これは、優先順位をどのように表現するかについてのやや補足的な質問
です。答えは、Priority Queue ADT.

私の問題は、この問題をモデルPQ化する方法を理解できないことです（ a の仕組みを理解しています）。
したがって、私の元の（些細な例）を使用して、さまざまな料理などを好む...（クラスとして表される）を持っていると仮定PersonA PersonBしPersonYます 。最初の質問スレッドの回答の友人としても提案されています）。 これをどのようにモデル化すればよいかわかりません。私が最初に考えたのは、料理ごとに ( など) を作成し、各キューにすべてのPizzas Spaggeti Steak
Preference
PriorityQueuePizzaPQSpaggetiPQPersons各キューからトップを削除し始め（その料理の最大の好みを持つものとして）Person、他のキューからそれを削除します。このプロセスは、すべてのキューを順番に処理します。
概念的には正しいように見えますが（ただし、プロセス自体が原因で矛盾が生じることを念頭に置いているため、最善のアプローチではありません）、正しい軌道に乗っているとは思いません。

  1. 他のキューからの削除は線形操作であり (すでにサービスが提供されており、他のキューにあるべきではない remove(Object)場所について話している)、キューの数がどこにあるかがコストになります (そして、これは私にはかなりの量を追加するようです)そもそもプライオリティキューの使用法に）ObjectPizzaO(N*k)k
  2. プライオリティ キューの「プール」で動作するには抽象化が必要なように思えますが、実際にそのようなデータ構造が存在するかどうかはわかりません。

この問題は、ジョブの割り当て方法や複数のキューの操作方法として一般化できると思います (おそらく?)
。このような問題には、標準的な設計アプローチが必要です。
どんな入力でも大歓迎です

@Thomas
の回答後に更新: 問題はもう少し複雑です。
好みに加えて、（人の）他の属性が適所にある可能性があります。
たとえばPersonA、PersonBどちらも他の料理よりもステーキを好みます。しかしPersonA、コレステロールが高くPersonB、アスリートです。どういうわけかこれらの属性を考慮にPersonB入れると、ステーキが得られるはずです。そして、おそらくPersonA最終的には何か別のものになる可能性があります。これが私がもともと料理
について考えた理由ですPQs

4

3 に答える 3

1

このアプリケーションをマルチスレッド環境で実行することは可能ですか? もしそうなら、私は助けることができるいくつかのアイデアを持っています.

  1. Person オブジェクトを取得して PQ に割り当てるジョブを持つディスパッチャ スレッドを作成します。Person が 1 つの PQ にのみ存在する必要があると仮定すると、これは上記の他の PQ から Person を削除する際の問題を解決するのに役立ちます。これにより、コードの PQ 実行部分から Person を配置するロジック (および CPU 処理時間) が移動し、PQ がよりまとまりのあるものになり、Person との結合が低下します。Person が複数の PQ にいる可能性がある場合、またはある PQ から別の PQ に移動したい場合などは、ディスパッチャー コードで実行する必要があります。

  2. 使用可能なスレッドよりも多くの PQ がある場合は、PQ 用のスレッド プールを作成します。それ以外の場合は、単に PQ ごとにスレッドを作成します。このようにして、PQ を反復処理する方法と PQ 枯渇の可能性について心配する必要がなくなります。PQ オブジェクトと Person オブジェクトを処理するコードは、各スレッドで同じです。

マルチスレッド モデルを使用しない場合でも、PQ が認識している PQitem オブジェクトから Person オブジェクトを継承することを検討します。これにより、PQ は Person オブジェクトについて何も知る必要がなくなります。 C ++、しかし私はあなたがアイデアを得ると思います）

class PQitem
{
public:
    virtual void execute() = 0;
    virtual void getPriority() = 0;
private:
    // PQ specific stuff here
};

class Person : public PQitem
{
public:
    void execute() { /* logic executed when taken off the PQ */ }
    void getPriority() { /* logic used to determine where to place this Person */ }
};
于 2012-05-03T09:04:17.900 に答える
0

ロジックを反転させるとどうなりますか？

  • すべての料理を地図に入れる
  • すべての人をループする
    • その人の料理の優先キューをループする
    • 料理がまだマップにあるかどうかを確認する
    • 皿が地図上にある場合は、それを削除してループを終了します

このようにして、料理のマップと優先キューを持つ人物のリスト (またはマップの人物 -> キュー) が得られます。

反復は、 がO(n * m)人数nであり、mがその人の料理優先キューの長さです。

後で料理マップにカウンターを追加する場合、たとえば 5 つのピザが利用可能である場合、変更する必要があるのは、カウンターが 0 に達したときにマップから料理を削除することだけです (料理を提供するときにカウンターをインクリメントします)。コース ：） ）。

次のことを処理する必要があります。

  • サービスを受け始めるのは誰？
  • 人の優先キューにある料理がマップにもうない場合はどうなりますか?

これらの質問に対するアプローチの 1 つは、優先順位が最も短い人から始めることです。これでも問題全体が解決するわけではありません (2 人がピザだけを欲しがっていて、周りにピザが 1 枚しかない場合はどうなるでしょうか?)。

于 2012-05-02T16:58:06.137 に答える
0

Java の優先キューへのリンクは次のとおりです: http://docs.oracle.com/javase/7/docs/api/

優先度を定義するための鍵は、さまざまな料理を比較する Comparator を定義することです。コンパレーターが 1 つしかないか、好みを定義するコンパレーターが各人に 1 つしかない可能性があります。

于 2012-05-02T16:59:41.627 に答える