神奇推銷員
(一)問題:推銷員要將每戶人家都訪問到,但為了節省時間及精力,每戶人家必不重複走到!是否每次出門訪問時,都可找到一條「推銷員路線」?對於不同點數、不同線路連節方式的圖形,要如何輕易地分辨是否有推銷員路線?(二)解決過程:以 0、1 為字元,由數個 0、1 組成字串,將圖形中每個點用字串表示,例如: 以二字元表示四個點 00、01、11、10若路線為 00 01 11 10,則可用「記憶輪」0011 表示,記憶輪中尾數後一字元「0」與首數前一字元「0」是可連接起來的,此路線即為推銷員路線。當然圖形中的點要用字串標示,需要多次嘗試!而四個點以上就必需要用三字原來表示?例如:七個點 001、011、111、110、101、010、100若路線為 001 011 111 110 101 010 100,且首尾可接的起來,則可用「記憶輪」0011101 表示,記憶輪中尾數後兩字元「00」與首數前兩字元「00」是可連接起來的,此路線即為推銷員路線。經過多次嘗試、推論並驗證後得到:圖形若有推銷員路線,其路線必可用記憶輪來表示(三)結果:1. 我們利用簡化圖形來標點,並利用記憶輪,可使得在較難看出是否有推銷員路線的圖形中,較快找到通路、來判斷其是否有通路。2.雖然過程中有一些簡單圖形很容易就可以看出是否有推銷員路線,但利用記憶輪的方式來討論,可以幫助我們在面對更複雜的圖形時,能夠將其推廣進而解決問題。3.有時找到的通路雖然無法表示成記憶輪,但它確實是條推銷員路線,亦符合當初我們的目的。對推銷員而言,如此則可判別圖形是否有推銷員路線,若有,則路線為何。