7

(ID1, ID2, timestamp)他のIDの前にどのIDをソートするかを決定するタプルの配列である「ソートマップ」に基づいてIDのリストをソートしようとしています。ルールは次のとおりです。

  • ID1の前にソートする必要がありますID2。
  • タイムスタンプを使用して、古いタイムスタンプを上回る新しいタイムスタンプとの関係を断ち切ることができます。たとえば、指定された並べ替えキーは(C, A, 1/1/1900), (C, B, 1/1/2000)、Bの前に並べ替えられますA。
  • サイクルが存在する可能性があります(A, B, 1/1/1950), (B, C, 1/1/1980), (C, A, 1/1/1900)。タイムスタンプを使用してサイクルを中断できます。サイクル内のタイムスタンプが古いレコードは、サイクルがなくなるまでソートマップから削除されます。
  • IDが並べ替えマップに存在しない場合、並べ替えマップに存在するIDの後に並べ替えられます

例：並べ替えマップ(C, A, 1/1/1900), (C, B, 1/1/2000)と並べ替えるリスト(A, B, C, D)を指定すると、並べ替えられた出力はになります(C, B, A, D)。

これらのルールをアルゴリズムに変えることに困惑しています。これが私がこれまでに持っているものです：

  1. データベースから最新のソートマップを取得します。IDの一意のペアごとに最大で1つのレコードを取得します。

  2. ソートマップからサイクルを削除します。どのように？または、ステップ4の一部としてサイクルを単に無視する方が簡単ですか？

  3. 最適なパフォーマンスを得るために、メモリ内の並べ替えマップを変換します。たとえば、特定のIDを含むすべての並べ替えマップの行をすばやく見つけることができるように、並べ替えマップ内の一意のIDをキーとするハッシュテーブルを作成します。

  4. ID1任意の2つのIDとID2パラメーターを受け入れるカスタム比較関数を使用して、汎用のバイナリソートライブラリを使用してIDの配列をソートします。比較関数：

    a。手順3のハッシュテーブルを含むID1または使用しているすべての並べ替えマップエントリを検索します。ID2

    b。ID1との両方を含むレコードがすでにID2ソートマップにある場合は、停止します。どちらが最初であるかがわかります。

    c。ソートマップにID1もID2も見つからない場合、それは同点です。決定論的に任意の結果を返します（たとえば、IDが低い方が勝ちます）。

    d。一方のIDがソートマップに含まれているが、もう一方が含まれていない場合は、停止します。見つかったものを最初にソートする必要があります。

    e。ここに到達すると、両方のIDが並べ替えマップにありますが、並べ替えマップで直接比較できるものはありません。それで？

並べ替えマップの最大サイズは2万行未満であり、並べ替えられるIDの最大数は30未満であるため、パフォーマンスは大きな問題ではありません。

アイデアがありますか？

FWIWでは、.NETを使用List<T>.Sort(Comparison<T>)してC＃で並べ替えを行いますが、基盤となるアルゴリズムは明らかに言語やプラットフォームに依存しません。

興味がある場合は、このアルゴリズムの実際の必要性を次に示します。

当社は、担当する合計100〜150の場所の領域から毎日約20の場所を訪れる配達ドライバー向けのモバイルアプリを構築しています。毎日の場所のリストは、各場所の在庫に基づいて動的に割り当てられます。在庫が少ない場所では新しい在庫が配信されますが、在庫がまだ十分ある場所にはアクセスされません。

ドライバーは任意の順序で場所を自由に訪問できますが、通常は毎日同様のルートを使用します（たとえば、朝の交通量が少ない場合は町の南部の場所を訪問し、交通量が多い場合は町の北部の場所を訪問します）。南）。

最も効率的な運転ルートを自動的に決定するサードパーティのルーティングソフトウェアを使用しないことを選択しました。代わりに、ルーティングソフトウェアは「建物の積み込みドックは通常、午前7時までしか無料ではない」、「配達領収書に署名する必要がある人は早めに出発する」などの制約があるため、ドライバーにルートを選択させる方がよいことがわかりました。配達スケジュールに大きな影響を与える「金曜日」。

とにかく、ドライバーの過去の選択を使用して、ドライバーが前回同じ場所を訪れたのと同じ順序で毎日の旅程を並べ替えたいと思います。これにより、ドライバーは、異常な場合を除いて、スケジュールを手動で再調整することなく、自分の好みに合わせて毎日うまく整理された旅程を得ることができます。これにより、ドライバーは1日1〜2分節約でき、時間の経過とともに合計されます。

各履歴旅程は実際にはこのようなリスト（ID1、ID2、ID3、...、IDN、タイムスタンプ）ですが、過去の何百ものスケジュールを保存する代わりに、各Nマシンの履歴旅程を分解する方が簡単だと思いました。マシンのペアに。これは、新しい順序では常に古いものが並べ替えマップから追い出されるため、最大でN*N-1タプルを格納する必要があることを意味します。これが悪い単純化である場合は、私に知らせてください。;-)

4

2 に答える 2

3

あなたが探しているものは、トポロジカルソートと呼ばれます。その検索語を使用すると、おそらく非常に優れたリソースを見つけることができます。

あなたの特定のドメインには、1 つの合併症があります: サイクル (ドライバーが時間の経過とともに一貫性のない動作をしたため)。そうしないとトポロジカルソートが失敗するため、依存関係のサイクルを断ち切る必要があるという事実は正しいです。

また、長さが 2 より大きいすべてのサイクルを分割する必要があります。

ID マップをグラフとして扱いましょう。ID (場所) はノードです。マップ内のエントリはエッジです (場所 ID1 から場所 ID2 へ)。これを行う簡単な方法は次のとおりです。

while true
 allCycles = getListOfAllCycles();
 if (allCycles.length == 0) break;
 breakNode = chooseBreakNode(allCycles); //defined later
 deleteBreakNodeFrom(allCycles);

chooseBreakNode:
 chose the node which has been driven to the least //node is not important
 if ambiguous: chose the node in the dependency graph which is present in the highest number of cycles //breaks multiple cycles at once
 if ambiguous: chose the node which is in the longest cycle
 if ambiguous: pick an arbitrary node

chooseBreakNodeおそらく、私は完全に正しく理解していませんでした。これは、ニーズに合わせて調整できるヒューリスティックです。

于 2012-09-01T09:43:22.370 に答える
0

別のアプローチを提案しますが、ビジネス ニーズを誤解している場合はお知らせください。

各ドライバーの場所の相対的な優先順位を格納する (DriverId, LocationId, Priority) のようなテーブルを用意します。

完了した旅程を処理する必要がある場合はいつでも、リストの一番下 (最後に訪れた場所) から開始し、リストを上に向かって各場所に対して次のアルゴリズムを実行します。

  • 場所の優先度がまだその下の場所の優先度よりも大きくない場合、 newPriority = priorityBelow + 1. (下に何もない場合、priorityBelow = 0)

リストの処理が完了したら、優先度ポイントを 1、2、3... として再正規化します (最も低い優先度 = 1、2 番目に低い = 2 など)。

次に、新しい旅程を注文する必要がある場合は、そのドライバーの相対的な優先順位の値で場所を注文するだけです。

このアプローチを検討しましたか？

編集:以下のコメントごとにサンプル コードを追加します。

ABCD (最新)、ACBE、CBDF、CBDFA (最も古い) の 4 つの歴史的な旅程がある場合、新しい旅程 ABCDEF をどのように並べ替えますか?

static Dictionary<string, int> Priorities = new Dictionary<string, int>();

static void Main(string[] args)
{
    var itineraries = new string[][]{   
        new string[] { "C", "B", "D", "F", "A" },
        new string[] { "C", "B", "D", "F" },
        new string[] { "A", "C", "B", "E" },
        new string[] { "A", "B", "C", "D" } };

    //process past itineraries
    foreach (var itinerary in itineraries)
        ProcessItinerary(itinerary);

    //sort new itinerary
    string[] newItinerary = { "A", "B", "C", "D", "E", "F" };
    string[] sortedItinerary = newItinerary.OrderByDescending(
        x => Priorities.ContainsKey(x) ? Priorities[x] : 1).ToArray();

    Console.WriteLine(String.Concat(sortedItinerary));
    Console.ReadKey();
}

static void ProcessItinerary(string[] itinerary)
{
    itinerary.Reverse().Aggregate((below, above) =>
    {
        int priBelow = Priorities.ContainsKey(below) ?
            Priorities[below] : Priorities[below] = 1;

        if (!(Priorities.ContainsKey(above) &&
            Priorities[above] > priBelow))
            Priorities[above] = priBelow + 1;

        return above;
    });

    //normalize priorities
    // (note: running in reverse so that if priorities tie, 
    //  the older location has higher priority)
    int i = Priorities.Count;
    foreach (var pair in Priorities.OrderByDescending(x => x.Value))
        Priorities[pair.Key] = i--;
}

これは次のように出力されます。ABCDFE

于 2012-08-31T06:55:38.370 に答える