Yahoo Answers is shutting down on May 4th, 2021 (Eastern Time) and beginning April 20th, 2021 (Eastern Time) the Yahoo Answers website will be in read-only mode. There will be no changes to other Yahoo properties or services, or your Yahoo account. You can find more information about the Yahoo Answers shutdown and how to download your data on this help page.

Anonymous
Anonymous asked in 電腦與網際網路程式設計 · 1 decade ago

演算法問題-貪婪演算法

假設我們分配n項工作給n個人,設cij是當指派第j項工作給第i個人所需付出的成本。請用貪婪演算法寫下一個可以將分配n項工作給n個人時的總成本支出壓到最低的分派方式。分析你的演算法,並使用量級表示法來表示最後的結果。

請問怎麼做比較好呢??謝謝

2 Answers

Rating
  • Leslie
    Lv 7
    1 decade ago
    Favorite Answer

    方法:

    1. 把 n^2 個 "所需付出的成本" 排序成從小到大.

    2. 根據 1 的次序, 一個一個選出指派, 但是若和已經指派過的衝突,

    則跳過.

    複雜度: 要 O((n^2)logn)

    正確性:

    這 "指派問題" (assignment problem) 用貪婪演算法 (greedy method)

    是不能保證得到最佳結果的. 底下這例子 (n=2) 就是失敗的例子:

    C(1,1)=5, C(1,2)=2, C(2,1)=3, C(2,2)=1.

    為了得到正確解:

    最直接是要用天真的窮舉法 (exhaustive search)(高複雜度),

    或是用 branch-and-bound 或 backtracking 改善 (複雜度仍是高).

    有效率的方法是 Hungarian method: O(n^4) 或

    Kuhn-Munkres algorithm: O(n^3).

    參考:

    1. A. Levitin 的演算法的書 (你的題目是在 9.1 節的習題 4 中)

    2. http://en.wikipedia.org/wiki/Hungarian_method

  • 1 decade ago

    自己思考一下自己會怎樣分配,多分配幾次就會知道怎樣分配了!!~

Still have questions? Get your answers by asking now.