排序问题Fm‖Cmax的几种启发式算法在最坏情况下性能比上界的可达性研究 |
| |
作者姓名: | 杨汉兴 |
| |
摘 要: | Gonzalez和Sahni已证明:当m≥3时,排序问题FmCmax是NP困难问题,没有好算法。因此,很多学者提出了多种简单易行的启发式方法求这类问题的次优解,且对其中的GS算法和RS算法证明了在最坏情况下性能比C*max(A)/C*max的上界不超过{m/2}*。本文用同一例子证明,对这两种算法,这一上界是可达的。
|
关 键 词: | 性能比;启发式算法;NP-完全问题;“好”算法 |
本文献已被 CNKI 等数据库收录! |
|