匈牙利法命名的由來
美國著名作業研究學者庫恩(Harold Kuhn)在2005年2月出版的Naval Research Logistics 學刊上發表一篇Statement for Naval Research Logistics(Naval Research Logistics, Volume 52, Issue 1, Date: February 2005, Pages: 6)的文章,述說他於1955 年自己在該學刊所發表的奠基性論文「The Hungarian method for the assignment problem」,將解決指派問題的方法命名為匈牙利法(Hungarian method)的經過。
庫恩教授在該文中回憶說,1953年的夏天,他在數值分析學會(Institute for Numerical Analysis)工作,這學會位於UCLA的校園內。學會內有一架由馮紐曼所設計的SWAC(Standards Western Automatic Computer)電腦,由256 Williamson(陰極)管組成。庫恩想要解決一個10x10的指派問題,這問題的原始敘述含100個變數,其對偶敘述含100個限制式,對於SWAC電腦而言,問題實在太大。當時在國家標準局(National Bureau of Standards)內的SEAC(Standards Eastern Automatic Computer)電腦也只能計算25個變數和25個限制式的線性規劃問題。
那年的夏天,庫恩偶然的機會讀到布達佩斯科技大學教授科尼格(Dénes Kőnig)關於圖論(graph theory)的書,他由書中所述的某定理聯想到指派問題的特例。科尼格教授在該定理有一個註腳(footnote),提到依格華里(Jenő Egerváry)以匈牙利文所寫的論文中有解決更一般性的做法。庫恩竟然只靠著一本匈牙利文字典和文法書,花費兩個星期的時間,研讀依格華里的論文,理解其推理邏輯,指派問題的解法因而誕生,他將該方法命名為匈牙利法。
2005年10月31日,匈牙利科學院(Hungarian Academy of Sciences)在布達佩斯該院的大樓舉辦「匈牙利法50週年慶祝大會」*,會中發表作業研究學術論文。
* A celebration day of the 50th anniversary of the Hungarian Method, www.cs.elte.hu/HungarianMethod50/
美國著名作業研究學者庫恩(Harold Kuhn)在2005年2月出版的Naval Research Logistics 學刊上發表一篇Statement for Naval Research Logistics(Naval Research Logistics, Volume 52, Issue 1, Date: February 2005, Pages: 6)的文章,述說他於1955 年自己在該學刊所發表的奠基性論文「The Hungarian method for the assignment problem」,將解決指派問題的方法命名為匈牙利法(Hungarian method)的經過。
庫恩教授在該文中回憶說,1953年的夏天,他在數值分析學會(Institute for Numerical Analysis)工作,這學會位於UCLA的校園內。學會內有一架由馮紐曼所設計的SWAC(Standards Western Automatic Computer)電腦,由256 Williamson(陰極)管組成。庫恩想要解決一個10x10的指派問題,這問題的原始敘述含100個變數,其對偶敘述含100個限制式,對於SWAC電腦而言,問題實在太大。當時在國家標準局(National Bureau of Standards)內的SEAC(Standards Eastern Automatic Computer)電腦也只能計算25個變數和25個限制式的線性規劃問題。
那年的夏天,庫恩偶然的機會讀到布達佩斯科技大學教授科尼格(Dénes Kőnig)關於圖論(graph theory)的書,他由書中所述的某定理聯想到指派問題的特例。科尼格教授在該定理有一個註腳(footnote),提到依格華里(Jenő Egerváry)以匈牙利文所寫的論文中有解決更一般性的做法。庫恩竟然只靠著一本匈牙利文字典和文法書,花費兩個星期的時間,研讀依格華里的論文,理解其推理邏輯,指派問題的解法因而誕生,他將該方法命名為匈牙利法。
2005年10月31日,匈牙利科學院(Hungarian Academy of Sciences)在布達佩斯該院的大樓舉辦「匈牙利法50週年慶祝大會」*,會中發表作業研究學術論文。
* A celebration day of the 50th anniversary of the Hungarian Method, www.cs.elte.hu/HungarianMethod50/
留言