April 15, 2017
6
COMBINATORIAL SEARCHING (F5C: 15 Apr 2017 0919)
7.2.2.1
baktrak tree
distane
Hamming distane
diversity
uniform
quasi-uniform
NP-hard
unique solution
instant insanity
grope
binary operation
multipliation tables
EXERCISES | First Set
x
5.
[
26
℄ Let
T
be any tree. Construt an unsolvable exat over problem for whih
T
is the baktrak tree traversed by Algorithm D; a
unique
olumn should have the mini-
mum size whenever step D? is enountered. Illustrate your onstrution when
T
=
.
6.
[
25
℄ Continuing exerise 5, let
T
be a tree in whih ertain leaves have b een
distinguished from the others and designated as \solutions."
a) Show that some suh trees never math the behavior of Algorithm D.
b) Charaterize all suh trees that
do
arise, having solutions where indiated.
x
10.
[
21
℄ Mo dify Algorithm D so that it doesn't require the presene of any primary
olumns in the rows. A valid solution should not ontain any purely seondary rows;
but it must interset every suh row. (For example, if only olumns 1 and 2 of (
20
)
were primary, the only valid solutions would b e to hoose rows
f
2
;
3
g
or
f
3
;
4
g
.)
15.
[
M21
℄ The solution to an exat over problem with matrix
A
an b e regarded as
a binary vetor
x
suh that
xA
= 11
: : :
1. The
distane
between two solutions
x
and
x
0
an then be dened as the Hamming distane
d
(
x; x
0
) =
(
x
x
0
), the numb er of
plaes where
x
and
x
0
dier. The
diversity
of
A
is the minimum distane b etween two
of its solutions. (If
A
has at most one solution, its diversity is innite.)
a) Is it possible to have diversity 1?
b) Is it p ossible to have diversity 2?
) Is it possible to have diversity 3?
d) Prove that if
A
represents a
uniform
exat over problem, the distane b etween
solutions is always even.
e) Most of the exat over problems that arise in appliations are at least
quasi-
uniform
, in the sense that they have a nonempty subset
C
of primary olumns
suh that
A
j
C
has the same numb er of 1s in every row. (For example, every
polyomino or polyub e paking problem is quasi-uniform, b eause every row of the
matrix sp eies exatly one piee name.) Can suh problems have odd distanes?
19.
[
M16
℄ Given an exat over problem
A
, onstrut an exat over problem
A
0
that
has exatly one more solution than
A
does. [Consequently it is NP-hard to determine
whether an exat over problem with at least one solution has more than one solution.℄
Assume that
A
ontains no all-zero rows.
20.
[
M25
℄ Given an exat over problem
A
, onstrut an exat over problem
A
0
suh
that (i)
A
0
has at most three 1s in every olumn; (ii)
A
0
and
A
have exatly the same
numb er of solutions.
21.
[
M21
℄ Continuing exerise 20, onstrut
A
0
having
exatly
three 1s p er olumn.
x
24.
[
30
℄ Given an
m
n
exat over problem
A
with exatly three 1s p er olumn,
onstrut a generalized \instant insanity" problem with
N
=
O
(
n
) ubes and
N
olors
that is solvable if and only if
A
is solvable. (See 7.2.2{(
36
) .)
x
26.
[
M24
℄ A
grope
is a set
G
together with a binary op eration
Æ
, in whih the identity
x
Æ
(
y
Æ
x
) =
y
is satised for all
x
2
G
and
y
2
G
.
a) Prove that the identity (
x
Æ
y
)
Æ
x
=
y
also holds, in every grop e.
b) Whih of the following \multipliation tables" dene a grop e on
f
0
;
1
;
2
;
3
g
?
0 1 2 3
1 0 3 2
2 3 0 1
3 2 1 0
;
0 3 2 1
3 2 1 0
2 1 0 3
1 0 3 2
;
0 1 3 2
1 0 2 3
3 2 1 0
2 3 0 1
;
0 2 3 1
3 1 0 2
1 3 2 0
2 0 1 3
;
0 3 1 2
2 1 3 0
3 0 2 1
1 2 0 3
:
我的内容管理
展开
