Evaluation of the Iwata–Yokoi Algorithm

(1)

NTNU Norwegian University of Science and Technology Faculty of Information Technology and Electrical Engineering Department of Computer Science

Master ’s thesis

Halvard Hummel

Evaluation of the Iwata–Yokoi Algorithm

Master’s thesis in Computer Science

Supervisor: Magnus Lie Hetland

June 2020

(2)

(3)

Halvard Hummel

Evaluation of the Iwata–Yokoi Algorithm

Master’s thesis in Computer Science Supervisor: Magnus Lie Hetland June 2020

Norwegian University of Science and Technology

Faculty of Information Technology and Electrical Engineering

Department of Computer Science

(4)

(5)

G=(V,E) T µV

T T

T

(6)

(7)

G=(V,E) TµV

T T

T

(8)

(9)

T

(10)

(11)

T

T T

T Pj

T

(12)

T

Pj

T

(13)

(14)

(15)

G=(V,E) T µV

T T

T

O^°^{V E}²^¢

(16)

+

T

O^(E^!⁾ ^! 2.373

T

(17)

T

(18)

(19)

T

G=(V,E)

v₀,e₁,v₁,...,e_n,v_n e_i v_i_°1 v_i

v₀ v_n

ei vi°1

vi

a,b,...,z,1,2,3,...

a°1°3°2°c

(20)

abcbcb

T

P

T Pj j T

P Pj T

P T Pj

T

T T

T

O^(E) ^E ^V

(21)

T

Q P_j T

T

G=(V,E) T µV

T G T

T P T T

G=(V,E)

TµV T

T T

(22)

T

G=(V,E)

T µV T G T

∏(T;G)

∏(T;G)=min

X

1 2

"

X

t2T

d(Xt)° (G\X)

#

X |T| Xt µV Xt

t2T d(S)

SµV G\S odd(G\X) Ci

G\X d(Ci)

T

|T| T

T

T T

T

(23)

T

n T

n+1 T n

T

T G

T P

s t T

s t

T

T T W

∞(W)

v0 vn

(24)

T T Q

T

T T

T

(25)

(26)

B1

s u

(27)

2|V|

T

T T

T P

P

T

T P

Pj j

T P

P P

P µ(Q) P

T s t

P s t

T T

s t Pj

P_j T

(28)

Pj

T P

Pj Pj T

T

P_j T

Pj

T

Pj Pj

Pj

t

P_j P_j

P_j t

(29)

P_j

pst pt s x x Pj

Pj

s t

pst

pt s T s t

Pj

T s t pst p^§_st

pt s p^§_st

P_j

st t s T

T st

t s

Pj p^§_{t s} Pj

p^§_{t s} pst

P T

Pj

T Pj

T

T P

P

(30)

P

T

T T

T Pj

Pj

Pj T

Pj

P

u r

T

Pj

T

(31)

P T

P

P P

P

T T

P

(32)

T

|E|

O^{(V E)}

O^(E⁾

P P

O^(V⁾ O^(V⁾

O^{(V E)} O^°^{V E}²^¢

O^°^V²^E+E²¢

O^(V⁾ O^(E)

O^°^V²+E¢

(33)

O^(V⁾ O^(E⁾

O^(V⁾ O^°^V²^¢

(34)

(35)

P P

T

P

(36)

str tr uvr

uv r

sr tuvr

(37)

sr tr

P

T r t tr u s

ustuv t str sr s

Pj T

s t

t vutr sr s

T u v

t vusr s

T

(38)

(Q)

∞ ∞(Q)

p ∞

pn

Q⁰

e Q.

e.

pn

e.sr c6=e.d st p==∞pn

e Q⁰ e.

p=e.

Q⁰

(39)

Q⁰ Q Q⁰

Q⁰ Q⁰

Q⁰

Q Q⁰

Q Q Q⁰

Q⁰ e

e Q

Q⁰ e

Q Q⁰

Q Á

Q e

e

e p e ∞[pn]

e

Q

e e

e e p

e ∞[pn]

Á O^(Q) O^(Q⁾

(40)

O^(Q⁾

O^(Q) O^(Q⁾ Á

(Q)

Q Q

Q

Q Q⁰

µ(Q)°µ(Q⁰)+2

P

P µP(Q)°µP(Q⁰)+1

T

(41)

2

P P

P

P P

P

P P

P

P Á

O^(E⁾ P

(42)

P

O^(Q) ^Q O^(E⁾

Á

O^(V⁾ O^(V⁾

O^(V⁾

(43)

O^(E)

Pj

T

T s°6°r t°5°8°r r°7°5°4°9°t P1 P2 P3

s°7°5°4°9°6°6°4°5°8°t 7°5°4°9

P3 6°6 P1 4°5 P3

5°8 P2

T

sr tr tr t sr tr tr t

P P3 7°5°4°9

P3 4°5

(44)

P3

7°5°4°9°6°6°4°5 P3

7 5 7°5

s°7°5°8°t t

sr t tr t

p_st p_{t s}

pst(7°5)=pst(5°4)=pst(4°9)=1 pt s(5°4)=2 pst pt s

Pj

(1)=1 (1)=1 (2)6=1 (2)6=1

e P3 r t

5°4 p^§_{t s} p_st=1<2=p_{t s}§ (1)=1

p^§_{t s}

(45)

e p^§_{t s} pst(e) (pst(e))=1 pst(e)<pt s§ c°7

7°5 5°4 4°9 9°b

4°9 pst=1<2=p^§_{t s} (1)=1

P3

Pj

pt s pst P3

t°9°4°5°7°r T

Pj

Pj T

Pj Pj

Pj

T P_j

P2 t°8°r t°5°4°6°6°9°4°5°7°s

(46)

B1

B₁ P₁

B2

B₂ 4°6

B₁,9,4,5,7

B2

B₂(5)°8

tr t sr tr tr tr s P3

5°4 4°9

p^§_st

P1 6

B1 4°6

B2

5°8

B1 B2

(47)

7°5 8°5

4 6 9

p^§_st p^§_{t s}

p^§_{t s} p^§_st)

st t s

Pj

p^§_st p^§_{t s}

Pj Pj

T

(48)

enter(x) leave(x) x Pj

f i r st(x) l ast(x) x Pj

P_j

T

Pj Pj

Pj f i r st l ast

p^§_st l ast(pt s(e⁰))=e⁰

e⁰ pt s(e⁰)>p^§_st leave(pt s(e⁰))=1 l ast(pt s(e⁰))=e⁰

Pj Pj

P_j P_j

p^§_st e f i r st(pst(e))=e

Pj

s t

Pj

Pj t

P_j p_st

p_{t s} P_j

(49)

pt s(e⁰)>p^§_st Pj

pt s p^§_st

leave(pt s(e⁰)) 1

P_j t

P_j

P_j P_j

Pj

Pj Pj

T

Pj Pj

Pj

p^§_st Pj e⁰

pt s(e⁰)>p^§_st Pj

e⁰ e⁰

P_j P_j

Pj

p^§_st Pj

Pj pt s(e⁰)>p^§_st Pj

Pj leave(pt s(e⁰))=1 l ast(pt s(e⁰))=e⁰ Pj

Á

p^§_st p^§_{t s}

f i r st(p_st(e⁰))=e⁰ pst(e⁰)<p^§_{t s} enter(pst(e⁰)=1 f i r st(pst(e⁰))=e⁰ leave(pt s(e))=e

p^§_st

(50)

s t

Pj

P_j

P_j t

P_j p_st p_{t s}

P_j pst(e⁰)<p^§_{t s}

enter(pst(e⁰))=1

Pj Pj

Pj

Pj Pj

e⁰ Pj

Pj e⁰

f i r st(p_st(e⁰))=e⁰ P_j

P_j

Pj

Pj e⁰ Pj

e⁰ Pj

s e⁰ p_{t s}^§ Pj

e⁰ pst(e⁰)<p^§_{t s}

enter(pst(e⁰))=1 e⁰

f i r st(pst(e⁰))=e⁰ e⁰

Á

(51)

P

P T P

T

T T

T

T T

T

(52)

T

T T

O^(E⁾

T T

T

T T

T

Pj

T

Á

(53)

T T

T

(Q,Pj) l

e Q.

e2Pj e.sr c==e.d st l==

l e l e l

T T

T

T T

Pj

T T T

T

(54)

Pj

T

Pj

P_j

T

T T T

T T

T

T T

T

(55)

T

P_j P_j

Pj

T

(56)

t stuvuvuv t str vuvuv

T

t vuvuvutr vuvuv

T P

Pj

P_j T

(57)

(58)

T T

Á

O^(Q⁾ O^(E)

Á

(59)

T

T O^(V⁾

T

|V|

T |V|

T T T

T T

O^(V⁾

|V| T

|V| |V|

P1

P1 P1

T

|V|°2 |V| T

|V|²°2|V| O^(V⁾ T

(60)

T

T T

T

|V|°2

T T

T

P |V| P

O^(V⁾ ^T

|V|²

T T

T

T |E|

O^(E⁾

O^(V⁾

T O^(V⁾

T

T O^(E)

T T

P P

T

(61)

P

T

P T

T P

T T

P T

T

T P

sst t

P T

P

T T

P

sst t P_j

P P

(62)

T T

T

T T

T

Pj

T

Pj

T Pj

Pj

T

Pj

(63)

Pj

T Pj

P_j

Pj Pj

Pj

P_j P_j

Pj

(64)

T

Pj

T P_j

T

Pj

T

(65)

T T

T

Á T

Pj

T Pj

T T

T T T

Pj

Pj T

T

Pj Pj

T

T T

Á

Pj

T

T P_j

(66)

T

T Pj

Pj

T Pj

T

P_j P_j

Pj Pj

T

Pj

T Pj

Pj

P_j Pj

(67)

T

T Pj

T

P_j T

T

P_j P_j

Pj

(68)

Pj

T Pj

Pj Pj

P_j P_j

T T

Pj

T

P_j

T

Pj

P_j P_j

P_j

Pj

(69)

¯

¯ ¯

¯

P_j

T Pj

T

Pj

T Pj

P_j

P_j P_j

P_j

Pj

T

Pj

T P_j

(70)

T Pj

Pj

T ...tt¯... ¯t t...

Á T

P

(71)

P

T

Pj T

P

P P_j

P P

P_j

T P

P

Pj

Pj P

Pj

P P

Á P_j

Pj

Pj Pj

1 2 Pj

2 3

Pj

(72)

Pj

P_j

T Pj

T

Pj

T P_j

T T

T Pj

Pj Pj

T Á

Pj Pj

Pj

P_j P

P

T

T Pj

P

(73)

Pj

P_j

P P_j

Pj

P

Pj Pj

Pj

Pj Pj

Pj

P_j

P P_j

Pj Pj

Pj

Pj Pj

Pj

P_j P_j

P_j

P Á

P

(74)

W O^(W+V) O^(V⁾

W

T

T T T

T T

T

T Á

(75)

T

T T

T

(Q,Pj) ØØPjØØ

i,v Pj.

v. 6= ∏v.

v.

i

v. ==

v. i

v P_j[1 : °1] P_j[ +1 : ] v.

pj Q.Pj

p⁰_j e pj. e.sr c. 6= e.d st. 6=

ØØØp⁰_jØØØ>0 p⁰_j

Q Pj

Pj Pj[1 : °1]+Pj[ : ]

T T

T

P_j

(76)

T (Q,Pj,seg ment s)

s1

s2ØØ ØØ==1

s1. ==s1.

Q[s1. :s1. ] s1

Q[s1. :s1. ]

ØØ ØØ>1

s1. 6=s2.

Q[s1. :s2. ] Pj s1. s2.

s1

Q[s1. :s1. ] s2

Q[s2. :s2. ]

s1. s s1. t

Q[s1. :s2. ]

s1n s1 s2p s2

s

s. ==s1.

s1n s s2p s2

s2p==s2 s2p s

Pj[s1. :s1n. ] Pj[s2p. :s2. ] Q[s1n. :s2p. ]

Q[s2p. :s2. ] Pj S1n. s2.

Q[s1. :s1n. ] P_j S1. s2p.

Q

Q[s2p. :s2. ] Pj S2p. s2.

Q[s1. :s1n. ] Pj S1. s1n.

(77)

sN Pj

sN sN. Pj

sN. sN. Pj

O^°^Q+Pj¢

O^°^Q+Pj¢ T

T

O^°^P^j^¢ O^°^Q+Pj¢

Pj

O^(Q)

O^°^Pj¢

O^(Q)

O^°^Q+Pj¢

Á

O^°^Q+P_j¢

T

O^°^P^j^¢

Pj

O^(Q⁾ Pj

O^(Q⁾

O^(Q) O^°^Q+P_j¢

(78)

T O^°^Pj¢

O^°^Q+Pj¢

Á

T

(Q,P) µP(Q)>0

Q

Q P

O^(V+Q) O^(E)

|V| O^(E⁾

T

O^°^Q+Pj¢

O^(E⁾ O^(E⁾

O^(E) O^{(V E)}

Á

(79)

T

P T

T

T T

T

T P_j

T

T T

P

T Pj

T T

P_j P_j

P_j

Pj Pj

T Pj

Pj T

Pj

T Pj

(80)

T

T T Pj

T Pj T

P_j T

P_j T P_j

P_j

T Pj

Á

T T

T

(81)

P_j

T

T T

T Pj

T T (Q,P)

P^§

µ_P(Q)>0 Q

T P^§

Q Pj P^§

Pj

Q P

T T

(82)

T Pj

T

n T

n+1T

n+1 T

T

T Á

T

T T

T

Pj O^(V⁾

O^°^V⁺^P^j^¢

T P^§

T |V|

T O^°^V²^¢

T T

|E| T

O^°^V²+E¢

V P_j E

O^°^V²+E¢

T O^{(V E}⁾ O^{(V E)}

Á

(83)

T

T T

T

Pj T

T

T Pj

T T

T

(84)

T

Á T

O^(V⁾ ^T O^(V⁾

T

X T

T

2X+1

T

X 2X T

2X+1 Á

X T

2X+1

(85)

T Pj

T X+1

2X+1 Á

2X+1 X O^(V⁾

X

T

(Q,P) P^§

µP(Q)>0 Q

Q

T P^§

Q

Q Q

Pj P^§ Pj

Q P

(86)

n T

n+1 T

Pj n+1T

T

Á

O^°^V²^¢

T O^(V⁾

Pj

O^(V⁾

O^(V⁾ ^T O^(V⁾

O^°^V²^¢

W O^(V+W) T

O^(V⁾ O^(V⁾

P_j O^(V⁾

O^°^V²^¢

O^°^V²^¢ Á

O^°^V²^¢

(87)

T

Pj

T T

P_j

T

T T

T

(88)

(89)

(90)

T T

T

(91)

+

T

(92)

(93)

T

(94)

(95)

NTNU Norwegian University of Science and Technology Faculty of Information Technology and Electrical Engineering Department of Computer Science