Громкович Ю. Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию
Подождите немного. Документ загружается.
u, w, v W
u, v u v
w W
c({u, v}) ≤ c({u, w}) + c({w, v}).
cost (H) ≤ cost(W ).
cost (H) ≤ cost(W ) < 2 · cost(H
Opt
),
SB(I)
Opt
∆
TSP
(I)
=
cost (
H)
cost(H
Opt
)
< 2.
ut
n ≥ 3 K
n
n
K
n
SB
∗
n ≥ 4 I
n
∆ TSP
SB(I
n
)
Opt
∆ TSP
(I
n
)
≥
2n − 2
n + 1
.
• α x
• α
U = (Σ
I
, Σ
O
, L, M, cost, goal)
x ∈ L M(x)
f
x
: M(x) → P(M(x))
α ∈ f
x
(α) α ∈ M(x)
α α
β ∈ f
x
(α) α, β ∈ M(x) α ∈ f
x
(β)
β α α β
α, β ∈ M(x) k γ
1
, γ
2
, . . . , γ
k
∈ M(x)
γ
1
∈ f
x
(α), γ
i+1
∈ f
x
(γ
i
) i = 1, . . . , k − 1, β ∈ f
x
(γ
k
).
α β α β
M(x)
α ∈ f
x
(β) α, β ∈ M(x) α β
M(x) f
x
(α) α M(x)
α ∈ M(x) x
f
x
cost (α) = goal{cost(β) | β ∈ f
x
(α)}.
x ∈ L f
x
M(x) x ∈ L α ∈ M(x)
f :
[
x∈L
({x} × M(x)) →
[
x∈L
P(M(x))
f(x, α) = f
x
(α).
U
M(x)
M(x)
M(x)
α
α
MAX SAT
α α
5
α = 011 00
{01100, 11100, 00100, 01000, 01110, 01101}.
15
16
MAX SAT
aa bb
cc dd
TSP 2 Exchange
• {a, b} {c, d} |{a, b , c, d}| = 4
α 4 a, b, c, d
• α {a, d} {b, c}
{a, b} { c , d} {a, d} {b , c}
2 Exchange
H G {a, b}
{c, d} {e, f } |{a, b, c, d, e , f }| = 6 H 6
a, b, c, d, e, f H
k ≥ 3
k
M(x)
β β
Neigh
LS (Neigh)
x U
α ∈ M(x)
α
Neigh
x
β ∈ Neigh
x
(α)
17
4
cost (β) < cost(α) U
cost (β) > cost(α) U
α
LS(Neigh)
Neigh
MAX CUT
LS CUT
G = (V, E)
S = ∅
(S, V − S)
(∅, V )
v ∈ V
cost (S ∪ {v}, V −(S ∪ {v})) > cost(S, V − S)
cost (S − {v}, (V − S) ∪ {v}) > cost (S, V − S)
v
(S, V − S)
LS CUT 2
MAX CUT
LS CUT
MAX CUT G = (V, E)
R
LS
CUT
(G) ≤ 2.
(Y
1
, Y
2
) LS CUT (Y
1
, Y
2
)
18
f
x
v ∈ Y
1
Y
2
Y
2
Y
1
Y
1
Y
2
(Y
1
, Y
2
)
G Opt
MIN CUT
(G) |E|
R
LS
CUT
(G) =
Opt
MIN
CUT
(G)
cost ((Y
1
, Y
2
))
≤
|E|
|E|/2
= 2.
ut
LS CUT
MAX WEIGHT CUT
MAX CUT G = (V, E) c : E → IN
0
e c(e)
MAX WEIGHT CUT
2
MAX WEIGHT CUT
•
•
P 6= NP
NP
×
NP
Neigh LS Neigh
19
v
U = (Σ
I
, Σ
O
, L, M, cost, goal )
Neigh Neigh
x ∈ L x Neigh
x
x
Neigh
x ∈ L
α ∈ M(x) Neigh
x
(α)
U ∈ NPO
U
U
U
Neigh
LS(Neigh)
U
k Exchange TSP
k k Exchange
G
(H)
H G n
∗
k
k Exchange TSP
20
21
NPO
|α|
|x|
22
23
1
NP
U = (Σ
I
, Σ
O
, L, M, cost, goal )
U
x Int(x) =
(i
1
, i
2
, . . . , i
n
)
i
j
∈ IN
0
j = 1, 2, . . . , n
cost (α) ∈
1, 2, . . . ,
n
X
j=1
i
j
α ∈ M(x)
U ∈ NPO
P 6= NP U NP U
U ∈ NPO
U Neig h
x LS(Neigh
x
)
p(|x|)
p LS(Neigh
x
)
1
0
X
j∈Int(x)
j ≤ |x| · MaxInt(x)
U
|x| · MaxInt(x).
LS(Neigh)
O(p(|x|) · |x| · MaxInt(x)).
Neigh LS(Neigh)
x
U NP
P 6= NP
ut
24
Int(x)
TSP MAX CL
NP
TSP
2
3
√
n
25
s
E(s)
c
B
26
27
s E(s)
T
q s
s
q
E(q) ≤ E(s) s := q q
q
prob(s → q) = e
−
E(q)−E(s)
c
B
·T
s 1 − prob(s → q)
T
T 0
(s)
s
s
q q
s q
•
prob(s → q) = e
−
E(q)−E(s)
c
B
·T
.
•
T
prob(s → q)
T prob(∆E)
∆E
prob(∆E) = e
−∆E
c
B
·T
.
prob(s → q)
• prob(s → q) s q
E(q) − E(s)
• prob(s → q) T
T
T
T