彨婝偵偍偗傞嵟戝暘婒悢

幝揷 惓恖(撧椙彈巕戝妛棟妛晹)

僎乕儉偺暋嶨偝傪應傞堦偮偺巜昗偲偟偰, 嬊柺偵偍偗傞暘婒悢, 偡側傢偪偦偺帪揰偱偺壜擻側拝庤悢, 偑峫偊傜傟傞([1]). 彨婝偵偍偄偰, 偦偺悢偑 593偱偁傞嬊柺偺懚嵼偑 [2] 偵偍偄偰帵偝傟偰偄傞. 偙偺悢偼埻岄偍傛傃 僠僃僗偺嵟戝暘婒悢傛傝傕戝偒側傕偺偱偁傞.

杮曬崘偱偼, 偙偺593偑彨婝偵偍偗傞嵟戝悢偱偁傞偙偲傪帵偡.

柦戣. 彨婝偵偍偗傞嵟戝暘婒悢偼593偱偁傞.

傑偢, 暘婒悢傪峫偊傞嬊柺偲偼
(1) 憃曽偺嬍偑斦忋偵懚嵼偡傞.
(2) 40枃偺嬵傪偡傋偰巊梡偟偰偄傞.
(3) 愭庤斣.偡側傢偪, 屻庤嬍偵墹庤偑妡偐偭偰偄側偄
(4) 弶宍偐傜幚尰壜擻
偲偡傞. 傕偪傠傫, (4)偩偗偱忦審偲偟偰偼廫暘偱偁傞偑, 偙偙偱偼姼偊偰 忦審(1),(2),(3)偵拲堄偟偰偍偔.

壜擻側嬊柺悢偼桳尷偱偁傞偐傜, 暘婒悢偺嵟戝抣偑懚嵼偡傞. 偙偺抣傪 M 偲彂偔偙偲偵偡傞. [2] 傛傝, 柧傜偐偵 M >= 593 偱偁傞. 嵟戝抣 M 傪幚尰偡傞嬊柺偺堦偮傪Q偲偍偔.

偝偰, 暘婒悢偼

(斦柺偺嬵傪摦偐偡)+(帩嬵傪懪偮)

偲昞傢偝傟傞.

曗戣. Q偵偍偄偰,愭庤偺帩嬵偼旘妏嬥嬧宩崄曕傪奺堦枃偼娷傓.

徹柧. 椺偊偽旘偑帩嬵偵側偄偲偡傞.斦柺偵偁傞旘偵傛傞壜擻側巜偟庤偼 嵟戝32捠傝偱偁傞偑, 偙偺旘傪帩嬵偵偡傞偲旘傪懪偮庤偑彮側偔偲傕41捠傝偼懚嵼偡傞(斦偺彙栚81偐傜嬵偺憤悢40傪堷偄偨傕偺). 懠偺嬵偵偮偄偰傕摨條.(廔)

偙偺曗戣傛傝, 嵟戝暘婒悢傪峫偊傞偵偼忋婰(1)-(4)偺忦審偵壛偊偰

(5) 愭庤偺帩嬵偼旘妏嬥嬧宩崄曕傪奺堦枃偼娷傓

傪壛偊偰傛偄.

奺嬊柺偺暘婒悢傪挷傋傞帪, 斦柺偵壗傕側偄忬懺偐傜嬵傪1枃偢偮抲偄偰偄偒,暘婒悢偺曄壔傪偨偳偭偰偄偔偙偲偵偡傞.

娭悢 H(x,Y) 傪, 嬵 x 傪斦柺 y (in Y) 偵抲偄偨偲偒偺

(斦柺偺嬵 x 偵傛傞壜擻側巜偟庤) -(斦柺 y 偑嵡偑傟偨偙偲偵傛傞帩嬵傪懪偮庤偺尭彮悢)

偺嵟戝抣偲偡傞( x 偑惉偭偰偄傞応崌傕峫椂偡傞). 椺偊偽,

H(嬧, 堦抜栚) = 4-4 = 0
(嬧堷偒2捠傝 * 惉晄惉偺慖戰 = 4 , 旘妏嬥嬧偺懪偪応強偺尭彮傛傝 -4 )

偱偁傞.

傑偨, Y 傪徣棯偟偨応崌偼斦柺慡懱傪昞偡偙偲偲偡傞. 偙偺偲偒昁梫側 H 偺抣傪楍婰偡傞偲,

H(旘, 堦抜栚) = 32-4 = 28, H(旘, 擇抜栚) = 32-6 = 26

H(妏, 嶰抜栚) = 24-7 = 17, H(妏, 擇抜栚) = 20-6 = 14

H(嬥) = 6-6 = 0,

H(嬧, 擇抜栚) = 10-6 = 4, H(嬧, 嶰抜栚) = 10-7 = 3,

H(宩) = 6-6 = 0,

H(崄, 嬨抜栚) = 10-7 = 3,

H(曕) = 6-6 = 0,

H(愭庤嬍, 擇抜栚) = 8-6 = 2,

H(屻庤嬍, 擇抜栚) = 0-6 = -6, H(屻庤嬍, 堦抜栚) = 0-4 = -4

偱偁傞.

斦柺偵壗傕(憃曽偺嬍傕)側偔, 帩嬵偵旘妏嬥嬧宩崄曕偑偁傞忬懺偺暘婒悢偼, 偦傟偧傟偺懪偰傞応強傪峫偊傟偽

81*4 + 72*2 + 63 = 531

偲側傞. 偙偙偱, 宩, 崄, 曕偺懪偪応強偵偼惂栺偑偁傞偙偲偵拲堄偟偰偍偔. 屻庤偺嬵,愭庤偺嬥, 宩, 曕傪斦忋偵抲偄偰傕暘婒悢偼憹偊側偄偙偲, 偍傛傃忦審(5)偐傜, H 傪梡偄偰

M <= 531 + 28 + 17 + 4*3 + 3*3 + 2 - 4 = 595

偲偄偆昡壙偑弌棃傞.

柦戣偺徹柧. M > 593 偱偁傞偲壖掕偡傞.偙偺偲偒, M 傪幚尰偡傞嬊柺偵 偍偄偰旘偍傛傃屻庤嬍偼斦柺堦抜栚偵側偗傟偽側傜側偄.偝傕側偗傟偽,

H(旘,堦抜栚) - H(旘, 擇抜栚) = 2

H(屻庤嬍, 堦抜栚) - H(屻庤嬍, 擇抜栚)=2

偱偁傞偙偲傛傝 M <= 595-2 = 593 偲側傞偐傜偱偁傞. 偙偙偱忦審(3)傪峫偊傞. 旘偲屻庤嬍偑堦抜栚偵偁傝,屻庤嬍偵墹庤偑妡偐偭偰偄側偄偙偲偐傜,旘偼偁傞堦抜栚偺彙(屻庤嬍偺偁傞偲偙傠)偵偼摦偗側偄.偙偺偙偲偐傜, 壜擻側巜偟庤偺嵟戝悢偐傜彮側偔偲傕2尭彮偡傞偙偲偵側傞.傛偭偰 M>593 偵斀偡傞.(徹柧廔)

嶲峫暥專

[1] 徏尨恗, 彨婝悽奅.

[2] 栰嶈徍峅, 儘僕僇儖側彨婝擖栧.