Algoritmos aproximados y heurísticos
para problemas NP-Hard
¿Cómo resolver problemas NP-HARD?
No pretendemos encontrar la “mejor” solución
sino una “buena” solución.
Algoritmos aproximados
Algoritmos heurísticos
Problemas NP-Hard
Técnicas de diseño
Algunas técnicas específicas que pueden
aplicarse para resolver problemas NP-HARD
son:
Ø Greedy heurístico
Ø Búsqueda Local
Ø Backtracking
Ø Branch & Bound
Problemas NP-Hard
Técnicas de diseño
TODAS las técnicas de diseño podrían ser usadas o
combinadas para resolver problemas NP-HARD.
Por ejemplo, Sanjeev Arora propone una original
combinación de técnicas para resolver TSP euclideano.
Propone un algoritmo de aproximación que combina
divide y conquista, programación dinámica, greedy y
técnicas específicas para algoritmos geométricos.
Problemas NP-Hard
Búsqueda local
Algoritmos de búsqueda local
Ø Comenzar con una solución al azar.
Ø Aplicar a la solución actual una transformación de
un conjunto de transformaciones para mejorar la
solución. La solución “mejorada” pasa a ser la
solución actual.
Ø Repetir hasta que ninguna transformación en el
conjunto de transformaciones produzca mejoras.
Problemas NP-Hard
Búsqueda local
Los algoritmos de búsqueda local son efectivos como heurísticas
para la resolución de problemas cuya solución exacta requiere un
tiempo exponencial.
Ø Comenzar con un número de soluciones y aplicar transformaciones locales a cada una de ellas, hasta lograr soluciones localmente óptimas, es decir que ninguna transformación del conjunto seleccionado puede mejorarla.
Ø Seleccionar la solución localmente óptima que tiene menor costo. Si somos afortunados podría ser la solución globalmente óptima
Problema del viajante
Búsqueda Local
3
7 4
6 5
8
2 6
4 3a
a
b
e
c
c
d
d
e
b
7
3
6
5
4
COSTO = 25
Solución inicial para una instancia de TSP
Problema del viajante
Búsqueda Local
Generar los circuitos candidatos intercambiando
pares de arcos no adyacentes.a b
dc
Si el costo (a,b) + costo(d,c) > costo(a,c) + costo(b,d)
• eliminar del circuito a los arcos (a,b) y (c,d)
• agregar al circuito los arcos (a,c) y (b,d)
Problema del viajante
Búsqueda Local
a
ec
d b
7
3
6
5
4
COSTO = 25
Posibles transformaciones
Pares de arcos que no son adyacentes y generan soluciones factibles locales
(a,e) (b,d)
(a,e) (d,c)
(e,b) (d,c)
(e,b) (c,a)
(b,d) (c,a)
Cantidad de transformaciones para circuitos de tamaño N es
N (N-3) / 2
Problema del viajante
Búsqueda Local
a
ec
d b
7
3
6
5
4
COSTO = 25
Posibles transformaciones
a
d
e
b
a e
c d
3 6
7
6
7
5
87
Costo = 21
Costo = 22
Problema del viajante
Búsqueda Local
a
ec
d b
7
3
6
5
4
COSTO = 25
Posibles transformaciones
e
c
b
d
e b
a c
3
3
5
4
46
8 3
Costo = 25
Costo = 25
Problema del viajante
Búsqueda Local
a
ec
d b
7
3
6
5
4
COSTO = 25
Posibles transformaciones
b
a
d
c
a
d e
b
c
Costo = 25
Costo = 21
4 7
6
4
43
3
6
5
Problema del viajante
Búsqueda Local
Repetir para la solución localmente óptima
a
d e
b
c
43
5
Posibles transformaciones
(a,b) (e,d)
(a,b) (d,c)
(b,e) (d,c)
(b,e) (c,a)
(e,d) (c,a)
6
3
Problema del viajante
Búsqueda Local
¿Qué cantidad de transformaciones?
Para que sea “tratable” la cantidad de
transformaciones debe ser de orden polinomial.
Transformar solamente soluciones localmente
óptimas y acotar las transformaciones a un
orden polinomial no nos garantiza llegar a la
solución óptima.
Problema del viajante
Búsqueda Local
Nuestra estrategia sólo transforma si “mejora”.
La solución óptima puede llegar a partir de
transformaciones que “empeoran” el costo!!
Pero buscaremos una buena solución en
promedio…
Problema del viajante
Búsqueda Local
Costo = 25 Costo = 27
Costo = 19
a
d c
b
e
73
6
5
4
a
d b
c
e
74
6 4
6
a
e b
c
d
24
6
4
3
4
6
“empeora”
“HACIA LA ÓPTIMA”
…
Problema del viajante
Búsqueda Local
Consideraciones
Los algoritmos heurísticos basados en esta
técnica deben ser de complejidad temporal
polinomial
ØNo se pueden generar todas las transformaciones
posibles!! La complejidad sería exponencial.
ØLos algoritmos que transforman soluciones factibles
deben ser polinomiales, de orden bajo.
Problema del viajante
Búsqueda Local
La técnica de búsqueda local para el viajante que
transforma intercambiando 2 arcos se la conoce
como “2-opting”.
La técnica puede generalizarse considerando el
intercambio de k arcos no adyacentes y se la conoce
como “k-opting”
El número de diferentes transformaciones es O(nk)
para todo k ≥ 2. Por ejemplo para k = 2 es exactamente
n(n-3)/2.
Problema del viajante
Búsqueda local
“3-opting”
1. (a,f) (d,e) (b,c) (circuito original)
2. (a,f) (c,e) (d,b) (un 2-opting)
3. (a,e) (f,d) (b,c) (otro 2-opting)
4. (a,e) (f,c) (b,d) (un 3-opting)
5. (a,d) (c,e) (b,f) (otro 3-opting)
6. (a,d) (c,f) (b,e) (otro 3-opting)
7. (a,c) (d,e) (b,f) (un 2-opting)
8. (a,c) (d,f) (b,e) (un 3-opting)
a
f
e d
c
b
Problema del viajante
Búsqueda local
“3-opting”
(a,e) (f,c) (b,d) (un 3-opting)
a
f
e d
c
b
a b
d
c
f
Problema del viajante
Búsqueda Local
La técnica de búsqueda local permite encontrar un circuito
óptimo para problemas de tamaño acotado.
Un conocido programa en C para resolver TSP es “Concorde
TSP Solver”. Ha sido aplicado para resolver variedad de
problemas, siendo sumamente eficiente para grandes instancias. Ha sido usado para obtener la solución óptima de 106 de las
110 instancias de la TSPLIB (un biblioteca de instancias del TSP
simétrico); la instancia más grande tiene 15112 vértices.
www.tsp.gatech.edu/concorde.html
Problemas NP-HARD
Problema del viajante
Sugerencia
Ø Implementar un algoritmo heurístico basado
en PRIM.
Ø Implementar búsqueda local para el viajante.
Ø Realizar un análisis empírico de ambas
implementaciones
Ø Experimentar con Concorde Solver
Problemas NP-HARD
El problema de la mochila
Dado un conjunto de n objetos de tamaños s1,s2,…sn y una
mochila de capacidad C (s1,s2,…sn y C son enteros positivos)
encontrar un subconjunto de objetos que maximice el uso de
la mochila.
Entrada: <s1,s2,…sn, C>
El problema requiere encontrar un subconjunto T de {1,2,…,n}
que
Ø maximice ST = Σ si
iεT
Ø sujeto a la restricción ST ≤ C.
Las soluciones factibles son subconjuntos de objetos que
satisfacen las restricciones
Problemas NP-HARD
El problema de la mochila
Describiremos una secuencia de algoritmos
acotados polinomialmente que garanticen
soluciones cada vez más cercanas a la óptima, si
bien, incrementan el tiempo de ejecución.
El algoritmo Ak considera subconjuntos de T de
a lo sumo k elementos
Problemas NP-HARD
El problema de la mochila
S = <54,45,43,29,23,21,14,1>
C = 110
K Subconjuntos Objetos SUMA
de tamaño K agregados
0 {} 54, 45,1 100
MAXSUM = 100 SET= {54,45,1}
Problemas NP-HARD
El problema de la mochilaK Subconjuntos Objetos SUMA
de tamaño K agregados
1
{54} 45,1 100
{45} 54,1 100
{43} 54,1 98
{29} 54,23,1 107
{23} 54,29,1 107
{21} 54,29,1 105
{14} 54,29,1 98
{1} 54, 45
MAXSUM = 107 SET= {29,54,23,1}
Problemas NP-HARD
El problema de la mochilaK Subconjuntos Objetos SUMA
de tamaño K agregados
2
{54,45} 1 100
{54,43} … …
{54,29}
…
{54,1}
{45,43}
…
MAXSUM = SET=
3
…
Problemas NP-HARD
El problema de la mochila
Algoritmo Ak1.Ordenar el tamaño de los objetos en orden decreciente. Sea la secuencia
resultante si1, si2,…, sin;
2. SET ={};
MAXSUM = 0;
3. for c/subconjunto T de {1,2,…,n} y |T|≤ K
{SUM = Σ si ;iεT
-- Incluir restantes objetos mientras no superen a C
for (j=1.. n/ ij ∉ T)
{if SUM + sij ≤ C
{SUM = SUM +sij;
T = T U {ij}; }
if MAXSUM < SUM
{MAXSUM = SUM; SET = T;}
}
Problemas NP-HARD
El problema de la mochila
Probaremos que
Ø Ao ∈ O(nlog n)
Ø ∀ k > 0, Ak ∈ O(k nk+1)
Problemas NP-HARD
El problema de la mochila
Ø #subconjuntos de tamaño 1 hasta k es menor o igual que (1 + k nk)
Ø Costo de agregado de objetos por subconjunto es O(n)
Ak ∈ O(max (n log n, k nk+1 + n))
Ao ∈ O(nlog n)
∀ k > 0, Ak ∈ O(k nk+1)
Problemas NP-HARD
El problema de la mochila
Sugerencia:
a)Investigue en la bibliografía de la materia si este algoritmo puede considerarse de aproximación o heurístico.
b) Con qué técnica/s de diseño de algoritmos se relaciona?
c) Suponiendo que Ak devuelve una solución factible ¿Con qué técnicas podría integrarla para mejorar la solución?
Problemas NP-HARD
Coloreo de un grafo
Dado un grafo G = (V,E) y un conjuto finito de
colores S, un coloreo es un mapping C:V-> S,
tal que si existe un arco (v,w) ε E, luego
C(v) < > C(w).
Problemas NP-HARD
Coloreo de un grafo
Coloreo secuencial
for ( i=2; i <= n; i++)
{c = 1;
while (g. adyacentesColoreados(i, c))
++c;
g.colorear(i, c);
}
Problemas NP-HARD
Coloreo de un grafo
Transformaciones sobre soluciones parciales
Intercambio de dos colores en un coloreo parcial:
Supongamos que los vértices v1,v2,…vp-1 han
sido coloreados usando los colores 1,2,…c (c≥2).
Se desea colorear a vp que es adyacente a un
vértice de cada color (1,2,…,c).
Problemas NP-HARD
Coloreo de un grafo
Transformaciones sobre soluciones parciales
Para cada par de colores asignados (i, j) /1 ≤ i ≠ j ≤ c:
Ø Construir subgrafos Gij de G cuyos vértices son todos los vértices de G coloreados con los colores i y j, y sus arcos todos los que conectan a dichos vértices.
Ø Identificar los componentes conectados de Gij
Ø Si vp está conectado en cada componente a vértices de un color del par, luego es posible intercambiar colores y colorear a vp con uno ya asignado.
Problemas NP-HARD
Coloreo de un grafo
Gi j: subgrafo de G cuyos vértices son todos los
vértices de G coloreados con los colores i y j, y
todos los arcos entre dichos vértices
S1ij
S4ij
S2ij
i
jj
i
i
i
ji
j
j
j
v
i
i
S3ij
vp
Problemas NP-HARD
Coloreo de un grafo
Ski j: componentes conectados en de Gij
vp está conectado a vértices coloreados con i y con j en al menos un
componente. Luego NO es posible un intercambio.
S1ij
S4ij
S2ij
i
jj
i
i
i
ji
j
j
j
i
i
S3ij
vp
Problemas NP-HARD
Coloreo de un grafo
Ski j: componentes conectadas en de Gij
vp está conectado a vértices de un solo color en cada componente. Luego es
posible intercambiar colores
S1ij
S4ij
S2ij
i
jj
i
i
i
ji
j
j
j
v
i
i
S3ij
vp
Problemas NP-HARD
Coloreo de un grafo
Intercambio de colores en S3ij y S4
ij y coloreo
de vp
S1ij
S4ij
S2ij
i
jj
i
j
j
ij
i
i
i
v
i
j
S3ij
vp
Problemas NP-HARD
Coloreo de un grafo
Sugerencias
Ø Implementar en C++ un algoritmo para
colorear un grafo basado en transformaciones
parciales.
Ø Analizar otras alternativas por búsqueda local
para este problema.
Problemas NP-HARD
Backtracking
Características
Ø Puede aplicarse en problemas de optimización, con o sin restricciones.
Ø La solución se calcula a partir de una secuencia de decisiones.
Ø Existe una función que permite averiguar si una secuencia de decisiones, la solución actual en curso, viola o no las restricciones.
Ø Existe una función solución que permite determinar si una secuencia de decisiones factibles es solución.
Problemas NP-HARD
Backtracking
Características
Ø Existe una forma sistemática y organizada de
generar y recorrer el espacio que contiene a todas
las posibles secuencias de decisiones.
Ø El espacio de soluciones factibles puede modelarse
mediante un árbol n-ario.
Problemas NP-HARD
Backtracking
Características del espacio de búsqueda
Ø Cada camino de la raíz a un nodo es una secuencia de
decisiones.
Ø El espacio de búsqueda no debe incluir soluciones
repetidas
Ø Una solución es factible si no viola las restricciones
Ø Una secuencia de decisiones puede ser “prolongable”
o “no prolongable”
Problemas NP-HARD
Backtracking- Espacio de búsqueda
Problema de la mochila
Modela subconjuntos de objetos{1,2,..,n}
∈∈∈∈
∉∉∉∉
objeto 1
objeto 2
objeto 3
…
…
objeto n
# espacio de búsqueda ∈∈∈∈ O(2n)
[1,1,-,-,…,-]
[0,1,-,-,…,-]
[o,-,-,…,-]
[0,0,-,-,…,]
Problemas NP-HARD
Backtracking- Espacio de búsqueda
Problema de la mochila
Modela subconjuntos de objetos{1,2,3,4}
{1}
{1,2} {1,3} {1,4}
{1,2,3} {1,2,4} {1,3,4}
{1,2,3,4} #nodos ∈ O(nn)
Problemas NP-HARD
Backtracking-Espacio de búsqueda
Problema del viajante
La raíz árbol es un vértice, los nodos circuitos en
construcción y las hojas circuitos.
<1>
<1,2> <1,3> <1,4>
<1,2,3> <1,2,4> <1,3,2> <1,3,4> <1,4,2> <1,4,3>
<1,2,3,4,1> <1,2,4,3,1> <1,3,2,4,1> <1,3,4,2,1> <1,4,2,3,1> <1,4,3,2,1>
Problemas NP-HARD
Backtracking- Esquema
void Back (estado d, solucion *d)
{ int nrohijo=1;
estado siguiente;
if (hoja(d)) calcular-solucion(d,sol);
else { nrohijo =1;
while (hijos(d,nrohijo, &siguiente)
{ if !podado(siguiente, sol)
Back(siguiente, sol);
++nrohijo;
}
}
}
Problemas NP-HARD
Backtracking- Esquema
El esquema anterior poda con respecto a costos de
soluciones factibles completas. Por ejemplo, en el
viajante podríamos usar como cota el valor de la
solución provista por un algoritmo heurístico.
Otra alternativa es podar a partir de cotas predictivas
sobre los nodos del árbol del espacio de búsqueda.
Branch& Bound : búsqueda informada
Problemas NP-HARD
Backtracking- Poda
Poda: permite eliminar ciertas zonas del espacio
de búsqueda.
Un nodo en curso se poda cuando existe
información que la solución en curso, pese a
cumplir las restricciones y ser “prolongable", no
conducirá a la solución resultado.
Problemas NP-HARD
Backtracking- Poda
La poda se basa en una función de estimación que
determina para un nodo en expansión una cota
inferior o superior, según sea un problema de
minimización o maximización respectivamente.y = f (v)
costoMejorSolución < (costoSolucionActual + y)
MINIMIZACIÓN
vv y = f(v)
costoMejorSolucion > (CostoSolucionActual + y)
MAXIMIZACIÓN
f debe ser efectiva y “barata”
Backtracking-Ramificación y Poda
(Branch & Bound)
Los nodos del espacio de búsqueda se pueden etiquetar como:
Vivos: Prometedor, no se han generado aún todos sus hijos
Muertos: Se han generado todos sus hijos o no es prometedor
“En expansión”: En cualquier instante pueden existir varios
nodos vivos y muertos y sólo uno en expansión. El nodo a
considerar es el “más prometedor” entre los nodos vivos.
Prometedor: la información que tenemos de ese nodo indica que
expandiéndolo se puede conseguir una solución mejor que la
solución en curso.
Los nodos vivos se mantienen en una estructura lineal (listas,
pilas, filas) o colas de prioridad(heap). El valor que el nodo vivo
“promete” es la clave del ordenamiento en la cola de prioridad.
Backtracking- (Branch & Bound)
Problema del viajante
Otro espacio de búsqueda para el viajante a partir de la
pertenencia de arcos.
Todos
¬(a,b)(a,b)
(a,b)(a,c)
(a,b)¬(a,c)
¬(a,b)(a,c)
¬(a,b)¬(a,c)
Backtracking- (Branch & Bound)
Problema del viajante
Consideraciones para generar el espacio de
búsqueda.
Ø El arco incluido no debe formar un ciclo.
Ø El grado de incidencia de un nodo es 2.
Ø Se permite sólo un ciclo que es el que
contiene exactamente una vez a cada nodo.
Branch & Bound
Problema del viajante
3
7 4
6 5
8
2 6
4 3
Circuito para una instancia de TSP
a b
c
d
e
Conjunto de arcos
(a,b)
(a,c)
(a,d)
(a,e)
(b,c)
(b,d)
(b,e)
(c,d)
(c,e)
(d,e)
Backtracking- (Branch & Bound)
Problema del viajante
Todos los circuitos
Circuitos sin
(a,b)
Circuitos
con (a,b)
Circuitos con
(a,b) y sin
(a,c)
Circuitos con
(a,b) y (a,c)
Circuitos con
(a,c) y sin
(a,b)
Circuitos sin
(a,b) y (a,c)
(a,b)
(a,c)
¬(a,d)
(a,d)
¬(a,b)
(a,c)
(a,c)
¬(a,b)
(a,d)
(a,c)
(a,d)
¬(a,b)
(a,b)
¬(a,c)
(a,d)
(a,b)
(a,d)
¬(a,c)
¬(a,b)
¬(a,c)
¬(a,d)
Problema NP-HARD
Problema del viajante
3
7 4
6 5
8
2 6
4 3
Circuito para una instancia de TSP
a b
c
d
e
Cota inferior para todoslos circuitos
d a b
a b e
b c a
a d c
b e d
2 3
3 3
4 4
2 5
3 6
Cota = (2+3+4+2+3 +3+3+4+5+6)/2
Cota = 17.5
Branch & Bound
Problema del viajante
3
7 4
6 5
8
2 6
4 3
Circuito para una instancia de TSP
a b
c
d
e
Cota inferior para todoslos circuitos sin (a,b)
d a c
c 4 b e
b c a
a d c
b e d
2 4
3
4 4
2 5
3 6
Cota = (2+4+4+2+3 +4+3+4+5+6)/2
Cota = 18.5
Branch & Bound
Problema del viajante
17.5
17.5
(a,b)
18.5
¬ (a,b)
20.5
(a,c) ¬(a,d)
¬(a,e)
18
¬(a,c)
18.5
(a,c)
21
¬(a,c)
(a,d) (a,e)
Los hijos no son nodosfactibles ( grado de incidencia es 2)
ab d
d a e
Branch & Bound
Problema del viajante
Ramificar (Branch) el más prometedor
17.5
17.5
(a,b)
18.5
¬ (a,b)
20.5
(a,c) ¬(a,d)
¬(a,e)
18
¬(a,c)
18.5
(a,c)
21
¬(a,c)
(a,d) (a,e)
18
(a,d)
¬(a,e)
23
¬(a,d)
(a,e)
Branch & Bound
Problema del viajante
Ramificar (Branch) el más prometedor17.5
17.5
(a,b)
18.5
¬ (a,b)
20.5
(a,c) ¬(a,d)
¬(a,e)
18
¬(a,c)
18.5
(a,c)
21
¬(a,c)
(a,d) (a,e)
18
(a,d)
¬(a,e)
23
¬(a,d)
(a,e)
(b,c)
¬(b,d)
¬(b,e)
(c,e)
(d,e)
¬(c,d)
abceda
Costo=23
¬(b,c)
(c,d)
(c,e)
¬(b,d)
¬(d,e)
(b,e)
abecda
Costo=21
Branch & Bound
Problema del viajante
Podar y Ramificar el más prometedor17.5
17.5
(a,b)
18.5
¬ (a,b)
20.5
(a,c) ¬(a,d)
¬(a,e)
18
¬(a,c)
18.5
(a,c)
21
¬(a,c)
(a,d) (a,e)
18
(a,d)
¬(a,e)
23
¬(a,d)
(a,e)
18.6
(a,d)
¬(a,e)
23.5
¬(a,d)
(a,e)
(b,c)
¬(b,d)
¬(b,e)
(c,e)
(d,e)
¬(c,d)
abceda
Costo=23
¬(b,c)
(c,d)
(c,e)
¬(b,d)
¬(d,e)
(b,e)
abecda
Costo=21
podar
podar
podar
Branch & Bound
Problema del viajante
Expandir el “más prometedor”17.5
17.5
(a,b)
18.5
¬ (a,b)
20.5
(a,c) ¬(a,d)
¬(a,e)
18
¬(a,c)
18.5
(a,c)
21
¬(a,c)
(a,d) (a,e)
18
(a,d)
¬(a,e)
23
¬(a,d)
(a,e)
18.6
(a,d)
¬(a,e)
23.5
¬(a,d)
(a,e)
(b,c)
¬(b,d)
¬(b,e)
(c,e)
(d,e)
¬(c,d)
abceda
Costo=23
¬(b,c)
(c,d)
(c,e)
¬(b,d)
¬(d,e)
(b,e)
abecda
Costo=21
¬(b,c)
(b,d)
(b,e)
(c,e)
¬(d,e)
¬(c,d)
ace bda
Costo= 23
(b,c)
¬(c,d)
¬(c,e)
¬(b,d)
(d,e)
(b,e)
acbeda
Costo= 19
Branch & Bound
Problema del viajante
En resumen
Ø Definir el modelo de espacio de búsqueda
Ø Definir la cota, función de estimación
Ø Ramificar (branch)
Ø Elegir el nodo “más prometedor” y expandirlo
Ø Podar (bound)
Problema del viajante
TSP-asimétrico
Recordar la solución de programación dinámica
Representación del grafo C
0988
120136
10905
2015100
1 2 3 4
1
2
3
4
Problema del viajante
TSP-asimétrico
C21= g(2, Φ) = 5
C31= g(3, Φ) = 6
C41= g(4, Φ) = 6
2 1
13
14
0988
120136
10905
2015100
Problema del viajante
TSP-asimétrico
C23 + g(3, Φ)= g(2,{3}) = 15
C24 + g(4, Φ)= g(2,{4}) = 18
C32 + g(2, Φ) = g(3,{2}) = 18
C34 + g(4, Φ) = g(3,{4}) = 20
C42 + g(2, Φ) = g(4,{2}) = 13
C43 + g(3, Φ) = g(4,{3}) = 15 3
2
4
4
3
23
4
1
132
42
1
1
1
1
Problema del viajante
TSP-asimétrico
g(2,{3,4}) = min (C23+g (3,{4}), C24+ g (4,{3})) = 25
g(3,{2,4}) = min (C32+g (2,{4}), C34+ g (4,{2})) = 25
g(4,{2,3}) = min (C42+g (2,{3}), C43+ g (3,{2})) = 23
3 4 12
2 4 3 1
Problema del viajante
TSP-asimétrico
g (1, {2,3,4}) = min (C12 + g(2,{3,4}),
C13 +g(3,{2,4}),
C14 + g(4,{2,3}))
g (1, {2,3,4}) = min (35, 40, 43) = 35
g(2,{3,4})
1 2 1
Problema del viajante
TSP-asimétrico
g (1, V-{1}) = min (C1k + g(k, V-{1,k})
2≤k≤n
g (i, S) = min (Cij + g(j, S-{j}))
j∈S i∉S; 1∉S
|S|=k (0≤ k<n)