xkh3121@sina.com；1090841758@qq.com
許康華老師聯(lián)系方式：
微信（xkh3121）；QQ（1090841758）
“和老婆討論數(shù)學(xué)題”系列之3
也和老婆討論數(shù)學(xué)問題
李晶 廣東省深圳市寶安中學(xué)
陳學(xué)輝(執(zhí)筆)
公眾號(hào)日前發(fā)布了金磊老師跟他老婆討論下面這道小學(xué)奧數(shù)的文章:
他們將題目轉(zhuǎn)化成求如下賦權(quán)無向圖從A到K的“最短路徑”的問題.
我將文章轉(zhuǎn)發(fā)給我老婆(她是深圳某中學(xué)數(shù)學(xué)老師),她讀過之后提出2個(gè)問題:
1. 金磊老師所使用的“破圈法”應(yīng)該是用來求無向圖的“最小生成樹”的,而不能用于求“最短路徑”,譬如,將各路徑的權(quán)值改成下圖,則金老師的方法將不再奏效.求下圖從A到K的“最短路徑”可用Dijkstra算法.
2. 將上圖看成一個(gè)游樂場(chǎng),A看做售票處,B ~ K看成10個(gè)不同的游樂項(xiàng)目,各路徑權(quán)值看成兩個(gè)相鄰項(xiàng)目之間的交通費(fèi)用.問:從售票處A進(jìn)入游樂場(chǎng),玩遍所有10個(gè)游樂項(xiàng)目,再?gòu)氖燮碧?/span>A離開游樂場(chǎng),交通費(fèi)用最低的路線該如何規(guī)劃?
先來解決第1個(gè)問題.
以修改了路徑權(quán)值的圖為例,我們給出使用Dijkstra算法求解從A到K的“最短路徑”的過程,如以下各圖所示(有興趣了解Dijkstra算法的讀者,建議閱讀圖論的教材):
如果使用“破圈法”,得到的結(jié)果應(yīng)是問題圖的“最小生成樹”,求解過程如以下各圖所示:
關(guān)于第2個(gè)問題,其實(shí)質(zhì)就是“中國(guó)郵遞員問題”.此問題最早由我國(guó)著名數(shù)學(xué)家管梅谷教授提出并解決,是一個(gè)著名的圖論問題.因此,其解法就不宜在本文詳細(xì)闡述了,也超出了中學(xué)生能理解的范疇.有興趣了解“中國(guó)郵遞員問題”的讀者,建議找一本圖論的專著來研讀,當(dāng)可一窺其妙！
需要指出的是,使用“破圈法”得到“最小生成樹”之后,一般來說并不能從“最小生成樹”得到“最短路徑”.譬如,以最后的“最小生成樹”為例,從A到K只有一條路徑ABEFGJK= 20, 比實(shí)際上的“最短路徑”ABEIJK = 18要長(zhǎng).金老師的文章中得到“最小生成樹”恰巧包含了“最短路徑”,但這僅是巧合而已.這一點(diǎn)值得讀者朋友們注意.
聯(lián)系客服
