1

これがシナリオです。

私は100台の車のオブジェクトを持っています。各車には速度のプロパティと価格のプロパティがあります。最速で最も高価な車が右上に、最も遅くて安い車が左下に、他のすべての車がグリッド内の適切な場所に配置されるように、車の画像をグリッドに配置したいと考えています。

これにはどのような並べ替えアルゴリズムを使用する必要がありますか?ヒントはありますか?

編集: 結果は正確である必要はありません。実際には、はるかに大きなグリッドを扱っているため、車が適切な場所に大まかにクラスター化されていれば十分です。

4

8 に答える 8

7

Cantor 氏にインスパイアされた単なるアイデア:

  • max(speed) と max(price) を計算する
  • すべての速度と価格のデータを 0..1 の範囲に正規化します
  • 各車について、可能な最大値までの「距離」を計算します

a²+b²=c² に基づくと、距離は次のようになります。

sqrt( (speed(car[i])/maxspeed)^2 + (price(car[i])/maxprice)^2 )

(視覚的に) 必要に応じて重み付けを適用する

  • 車を距離順に並べる
  • 「最高の」車を「最高の」正方形に配置します（あなたの場合は右上）
  • グリッドをジグザグに歩き、ソートされたリストの次の車で埋めます

結果 (ミラーリング、左上が最適):

1 - 2   6 - 7
  /   /   /
3   5   8
| /
4
于 2010-01-08T12:35:05.557 に答える
5

これを2つの問題として扱います。

1：ソートされたリストを作成する2：ソートされたリストのメンバーをグリッドに配置する

並べ替えは、ルールをより正確に定義するだけの問題です。「最初に最速で最も高価」は機能しません。私の£100,000ロールスロイス、最高速度120、または私のスープ付きミニ、£50,000、最高速度180のどちらが最初に来るのですか？

あなたのリストを手に入れたら、どのようにそれを埋めますか？最初と最後は簡単ですが、2番目はどこに行きますか？上に沿ってまたは下に沿って？次に、行に沿って、列に沿って、ジグザグにどこに？あなたが決める必要があります。その後、コーディングは簡単になるはずです。

于 2010-01-08T11:51:35.443 に答える
2

あなたが望むのは、「同様の」特性を持つ車を近くに配置することであり、さらに、一般にコストが右方向に増加し、一般に速度が上方向に増加することだと思います。

私は次のアプローチを試みます。N 台の車があり、それらを X * Y グリッドに配置するとします。N == X * Y と仮定します。

  1. N 台すべての車をグリッドのランダムな位置に配置します。
  2. グリッド内の合計の並べ替えを計算するメトリックを定義します。たとえば、車のペア C1=(x,y) と C2=(x',y') の数を数えて、C1.speed > C2.speed であるが y < y' と車のペア C1=(x,y) となるようにします。 C1.price > C2.price であるが x < x' となるような C2=(x',y')。
  3. 次のアルゴリズムを実行します。
    1. 現在の並べ替えメトリック M を計算する
    2. グリッド内のすべての車のペアを列挙し、車を交換した場合に得られる順序付けの誤りのメトリック M' を計算します
    3. そのようなペアが見つかった場合、メトリックを最も減少させる車のペアを交換します
    4. 2 台の車を交換した場合は、手順 1 から繰り返します。
    5. 終了

これは、最適化問題に対する標準的な「ローカル検索」アプローチです。ここにあるのは、基本的に単純な組み合わせ最適化問題です。試みるべき別のアプローチは、マトリックス内の速度とコストの事前シード勾配を持つ自己組織化マップ (SOM) を使用することです。

于 2010-01-08T20:13:30.210 に答える
1

基本的に、速度または価格のいずれかをプライマリとして取得し、このプライマリと同じ値を持つ車を取得し、それらの値を昇順/降順で並べ替える必要があります。必要に応じて、プライマリも昇順/降順で取得されます。

例：

c1(20,1000) c2(30,5000) c3(20, 500) c4(10, 3000) c5(35, 1000)

上記のリストの尺度として車 (速度、価格) を想定し、主な尺度は速度です。

1 最低速度で車を手に入れる

2 次に、同じ速度値を持つすべての車を取得します

3 これらの値を車の価格が高い順に並べ替えます

4 次の最小速度値を持つ次の車を取得し、上記のプロセスを繰り返します

c4(10, 3000)
c3(20, 500)
c1(20, 1000)
c2(30, 5000)
c5(35, 1000)

使用している言語を投稿すると、一部の言語構造によって実装が容易になるため、役に立ちます。たとえば、LINQ を使用すると、この状況での作業が非常に簡単になります。

cars.OrderBy(x => x.Speed).ThenBy(p => p.Price);

編集：

これで、この車のアイテムをグリッドに配置することによるリストが得られました。これらの値を持つ事前に決められた車の数がこれだけ多くなることがわかっていない限り、固定のグリッド サイズを使用することは期待できません。今。

1 つのオプションは、不均一なグリッドを使用することです。必要に応じて、各行に特定の速度の車のアイテムを配置しますが、これは、同じ速度値を持つ車がかなりの数存在することがわかっている場合にのみ適用できます。

したがって、各行には同じ速度の車がグリッドに表示されます。

ありがとう

于 2010-01-08T11:43:22.847 に答える
1

10x10 の制約は必要ですか? そうである場合、10 の速度と 10 の価格が必要です。たとえば、最速の車が最も高価でない場合はどうなるでしょうか。

グリッドサイズを次のようにすることをお勧めします

  (number of distinct speeds) x (number of distinct prices),

その場合、2 つの軸による順序付けの (かなり) 単純なケースになります。

于 2010-01-08T11:58:21.467 に答える
0

うーん...バブルソートのようなものは、ここでは単純なアルゴリズムかもしれません。

  1. ランダムな 10x10 配列を作成します。
  2. 「間違った順序」にある 2 つの隣接 (水平または垂直) を見つけて、それらを交換します。
  3. そのような近隣が見つからなくなるまで (2) を繰り返します。

2 つの隣接する要素は、次の場合に「間違った順序」になります: a) それらが水平の隣接要素であり、左の要素が右の要素よりも遅い場合、b) それらが垂直の要素であり、上部の要素が下部の要素よりも安価です。

しかし、このアルゴリズムがすべてのデータで停止するかどうかは実際にはわかりません。私はそれが非常に遅いと確信しています:-)。実装は簡単で、有限回の反復の後、部分的な結果が目的に十分な場合があります。ここに記載されている他の方法のいずれかを使用して配列を生成することから始めることもできます。また、配列形状の状態を維持します。

編集：ここで何かを証明するには遅すぎますが、Pythonでいくつかの実験を行いました。100x100 のランダムな配列をこの方法で数秒でソートできるように見え、私は常に完全な 2 次元順序を取得することができました (つまり、最後に間違った順序の隣人が得られました)。OP がこの配列を事前に計算できると仮定すると、合理的な数の車を配列に入れ、適切な結果を得ることができます。実験的なコード: http://pastebin.com/f2bae9a79 (matplotlib が必要です。ipython もお勧めします)。iterchangeそこでのソート方法です。

于 2010-01-09T01:34:35.747 に答える
0

データがデータベースに由来する場合は、データベースからフェッチするときに順序付けする必要があります。ORDER BY speed, priceこれは、クエリの最後近くに追加することを意味する必要がありますが、そのLIMIT部分の前に追加する必要があります (「速度」と「価格」は適切なフィールドの名前です)。

他の人が言っているように、「最速で最も高価」というのは難しいことです。ただし、このアルゴリズムを使用して近似を行うことは可能です。

  1. 最高の価格と最速の速度を見つけます。
  2. すべての価格と速度を、たとえば 1 分の 1 に正規化します。これは、価格をステップ 1 で見つけた最高価格で割ることによって行います。
  3. 正規化された価格と速度を掛け合わせて、1 つの「価格と速度」の数値を作成します。
  4. この番号で並べ替えます。

これにより、車 A が車 B よりも高速で高価であることが保証され、リストの上位に置かれます。一方の値が高く、他方の値が低い車は、大まかにソートされます。これらの値をデータベースに保存し、選択したとおりに並べ替えることをお勧めします。

それらを 10x10 のグリッドに配置するのは簡単です。アイテムの出力を開始し、10 の倍数になったら、新しい行を開始します。

于 2010-01-08T12:10:56.310 に答える
0

もう 1 つのオプションは、0 .. 200%各車にスコアを適用し、そのスコアで並べ替えることです。

例： 

score_i = speed_percent(min_speed, max_speed, speed_i) + price_percent(min_price, max_price, price_i)
于 2010-01-08T12:11:02.643 に答える