Participación 9 resuelta: PWS vs DTS

💡 En simple

El ejercicio da un árbol con tres soluciones parciales (s1, s2, s3) y pide contar pasos (aristas recorridas) con tres estrategias: un solo proceso, PWS y DTS. Luego, speedup y eficiencia.

El truco para no perderse: primero cuenta las aristas de cada subárbol (una tabla) y después todo es sumar y tomar máximos.

Sobre esta solución

Es una resolución propia (la del grupo para la participación, revisada y verificada con un programa que recorre el árbol). Los conteos de aristas y los pasos del DFS coinciden con la ejecución. Donde el enunciado deja lugar a otra interpretación, está indicado.

Enunciado (láminas 34–37)

El DAG muestra el árbol de búsqueda con tres soluciones parciales s1, s2, s3. Cada nodo cuesta O(1). Se pide la cantidad de pasos (aristas) para encontrar la solución global:

• (a) con PWS, con costos definidos por los niveles m = 1, m = 2 y m = 3. En PWS los procesos deben terminar su búsqueda local: el costo lo fija el proceso que más demora.
• (b) con DTS, particionando en dos momentos (m = 1 y m = 2), con el mismo costo para todos los procesos.
• (c) speedup y eficiencia en cada caso: ¿cuál tiene mejor speedup y cuál mayor eficiencia? Analizar.

Paso 0: leer el árbol

R [P0]                                   nivel 0
├── A [P0]                               nivel 1 (m = 1)
│   ├── a1 [P0]                          nivel 2 (m = 2)
│   │   ├── x1 ── 2 hojas                nivel 3 → nivel 4 (m = 3)
│   │   ├── x2 ── s1
│   │   └── x3 ── 2 hojas
│   └── a2 [P1]
│       ├── y1 ── 1 hoja
│       └── y2 ── 1 hoja
├── B [P1]
│   ├── b1 [P2]
│   │   ├── z1 ── 1 hoja
│   │   └── s2                           (nivel 3)
│   └── b2 [P3]
│       ├── w1 ── 1 hoja
│       └── w2 ── 2 hojas
└── C [P2]
    ├── c1 [P4]
    │   ├── v1 ── 1 hoja
    │   ├── v2 ── 1 hoja
    │   └── v3 ── 1 hoja
    └── s3 [P5]                          (nivel 2)

36 nodos ⇒ 35 aristas (un árbol siempre tiene nodos − 1 aristas). Las soluciones están a distinta profundidad: s3 en el nivel 2, s2 en el 3 y s1 en el 4.

Tabla de aristas por subárbol

Cuenta “de abajo hacia arriba”: aristas de un subárbol = (número de hijos) + (aristas de cada hijo).

Subárbol	Cómo se cuenta	Aristas	Solución (paso local en DFS)
a1	3 hijos + 2 + 1 + 2	8	s1 (5)
a2	2 hijos + 1 + 1	4	—
b1	2 hijos + 1	3	s2 (3)
b2	2 hijos + 1 + 2	5	—
c1	3 hijos + 1 + 1 + 1	6	—
s3	hoja	0	es la solución
A	2 + 8 + 4	14	s1 (6)
B	2 + 3 + 5	10	s2 (4)
C	2 + 6 + 0	8	s3 (8)
R	3 + 14 + 10 + 8	35

Secuencial

DFS de izquierda a derecha. Contando aristas:

• s1: R→A (1), A→a1 (2), a1→x1 (3), dos hojas (4, 5), a1→x2 (6), x2→s1 (7).
• s2: se termina A (1 + 14 = 15), R→B (16), B→b1 (17), b1→z1 (18), hoja (19), b1→s2 (20).
• s3: es el último nodo del recorrido: paso 35.

Como la solución global necesita las tres, T_s = 35 pasos.

(a) PWS con m = 1, 2, 3

Cada proceso tiene el árbol entero y hace un DFS desde la raíz, limitado a su umbral. p = 3.

Proceso	Umbral	Aristas que recorre	Soluciones (paso)
P0	m = 1 (profundidad 1)	3	ninguna
P1	m = 2 (profundidad 2)	3 + 6 = 9	s3 (9)
P2	m = 3 (profundidad 4, todo el árbol)	35	s1 (7), s2 (20), s3 (35)

Con TASKWAIT, el tiempo lo fija el más lento:

$$T_\text{PWS} = \max(3,\ 9,\ 35) = 35 \text{ pasos}$$

Trabajo total 3 + 9 + 35 = 47 aristas: 12 redundantes.

Interpretación de m = 3

En la figura, la línea m = 3 pasa por el último nivel (profundidad 4), así que ese umbral cubre el árbol completo. Si alguien leyera m = 3 como “profundidad 3”, P2 no llegaría a s1 (que está en el nivel 4) y PWS no encontraría la solución global en esa ronda: habría que subir el umbral y repetir, y el tiempo sería aún mayor. Con cualquiera de las dos lecturas, PWS no mejora al secuencial.

(b) DTS con partición en m = 1 y m = 2

Todos usan el mismo umbral (el árbol completo) y cada uno recibe un subárbol distinto. Se sigue la asignación de procesos de la figura.

1. Momento m = 1. P0 expande R y genera A, B, C para P0, P1, P2: 3 pasos secuenciales.
2. Momento m = 2. P0, P1 y P2 expanden su nodo a la vez: A → a1 (P0), a2 (P1); B → b1 (P2), b2 (P3); C → c1 (P4), s3 (P5). Cada uno recorre 2 aristas: 2 pasos.
3. Búsqueda local. Los 6 procesos recorren su subárbol de nivel 2. Manda el más grande, a1, con 8 aristas.

$$T_\text{DTS} = 3 + 2 + \max(8,\ 4,\ 3,\ 5,\ 6,\ 0) = 13 \text{ pasos}$$

Solución	Quién la encuentra	Paso
s3	P2, al expandir C en el momento m = 2	3 + 2 = 5
s2	P2, en el subárbol b1 (paso local 3)	5 + 3 = 8
s1	P0, en el subárbol a1 (paso local 5)	5 + 5 = 10

Las tres soluciones están en el paso 10 y el algoritmo termina en el 13. Sin redundancia: 3 + 6 + 26 = 35 aristas.

Para comparar, DTS con un solo momento (m = 1, p = 3): T = 3 + máx(14, 10, 8) = 17 pasos; s2 en 7, s1 en 9, s3 en 11.

Otra forma de contar la expansión

Aquí cada arista generada en la frontera cuesta 1 paso, como en el secuencial. Si tu profesor considerara que expandir un nodo (generar todos sus hijos a la vez) cuesta 1 paso, los tramos de partición valen 1 + 1 y T_DTS = 2 + 8 = 10. Escribe siempre el supuesto en el examen; con él declarado, cualquiera de las dos lecturas es defendible.

(c) Speedup y eficiencia

S = T_s / T_p, E = S / p, con T_s = 35.

Modelo	p	Tp	S	E	Trabajo
Secuencial	1	35	1	1	35
PWS (m = 1, 2, 3)	3	35	35/35 = 1.00	1/3 = 0.33	47
DTS, un momento	3	17	35/17 = 2.06	2.06/3 = 0.69	35
DTS, dos momentos	6	13	35/13 = 2.69	2.69/6 = 0.45	35

• Mejor speedup: DTS con dos momentos (2.69).
• Mayor eficiencia: DTS con un momento (0.69).
• PWS: no acelera (S = 1, E = 1/3).

Análisis

¿Por qué PWS no acelera aquí? Para tener la solución global hay que llegar a s1, en el nivel 4. Algún proceso debe recorrer el árbol completo, y en PWS ese proceso parte de la raíz igual que el secuencial; los demás solo repiten la parte de arriba. PWS sirve cuando no se sabe a qué profundidad está la solución y se usa IDA*: varios umbrales a la vez reemplazan rondas sucesivas. Aquí el umbral máximo ya cubre todo el árbol, así que no hay rondas que ahorrar.

¿Por qué DTS con 6 procesos no tarda la mitad que con 3? Pasa de 17 a 13 pasos, no a 8.5:

• Desbalance: los subárboles de nivel 2 tienen 8, 4, 3, 5, 6 y 0 aristas. El promedio es 26/6 ≈ 4.3, pero manda el mayor (8). P5 recibe s3 directamente y queda ocioso desde el paso 5.
• Tramo secuencial: generar la frontera cuesta 5 de los 13 pasos (38 %). Es el término b^k de la complejidad de DTS.

Por eso la eficiencia baja de 0.69 a 0.45 aunque el speedup suba. Es el compromiso de las láminas 24–26: partir más profundo da más procesos y más speedup, pero el árbol no balanceado y el tramo secuencial limitan la eficiencia. Para mejorarla haría falta balance de carga dinámico: por ejemplo, que P5 y P2, que terminan pronto, pidan a P0 parte del subárbol a1.

Si se mide hasta tener las tres soluciones (no hasta que todos terminan): DTS con dos momentos las tiene en el paso 10 (S = 3.5) y con uno en el paso 11 (S = 3.18). PWS sigue en 35.

Míralo paso a paso

Elige el modo y dale Play. El diagrama de abajo muestra en qué pasos trabaja cada proceso: los huecos son tiempo ocioso.

Búsqueda en el árbol de la participación 9: secuencial, PWS y DTS

Un paso = recorrer una arista. Cada color es un proceso. Dale Play y mira quién trabaja en cada paso, dónde aparece cada solución y cuándo termina el último proceso.

Secuencial (DFS)PWS (m = 1, 2, 3)DTS (corte en m = 1)DTS (cortes en m = 1 y m = 2)

⏮︎◀︎▶︎ Play▶︎⏭︎

0.5×1×2×4×

paso 0/13

T_p (último proceso)13 pasos

Trabajo hasta ahora0 aristas

Redundante0

S = 35 / T_p2.69

E = S / p (p = 6)0.45

s1aún no

s2aún no

s3aún no

Dos momentos de partición (3 + 2 pasos) y 6 búsquedas locales. Manda el subárbol a1 (8 aristas): 5 + 8 = 13. P5 recibe directamente s3 y no tiene nada que buscar.

Variantes para practicar

1. Si s3 estuviera en el lugar de la última hoja de c1 (nivel 4), ¿cambia T_DTS con dos momentos?

Ver solución

No cambia el tiempo: T sigue siendo 3 + 2 + 8 = 13, porque manda a1. Cambia cuándo aparece s3: ahora la encuentra P4 al final de c1 (subárbol de 6 aristas), en el paso 5 + 6 = 11; el nodo de nivel 2 de P5 queda como una hoja sin solución. Las tres soluciones estarían en el paso 11.

2. Con DTS en dos momentos, ¿qué pasaría si P5 (ocioso desde el paso 5) pudiera tomar la mitad del subárbol a1 (por ejemplo, la rama x3, de 3 aristas)?

Ver solución

P0 se queda con x1 y x2 (3 + 2 = 5 aristas, contando a1→x1, a1→x2, las 2 hojas y x2→s1) y P5 con a1→x3 y sus 2 hojas (3 aristas). Si el traspaso no cuesta pasos, el máximo local baja a máx(5, 4, 3, 5, 6, 3) = 6 y T = 5 + 6 = 11: S = 35/11 = 3.18, E = 0.53. Es el efecto del balance de carga dinámico. En la realidad el traspaso cuesta comunicación, así que la mejora sería algo menor.

3. ¿Qué tendría que pasar para que PWS fuera mejor que DTS?

Ver solución

Que la profundidad de la solución fuera desconocida y la búsqueda necesitara varias rondas de IDA* (umbral creciente). Por ejemplo, si el secuencial tuviera que hacer 3 rondas (umbral 1, luego 2, luego 3), su tiempo sería 3 + 9 + 35 = 47, y PWS, haciéndolas a la vez, tardaría 35: S = 1.34. Con árboles profundos y muchas rondas, la ventaja crece.

Autoevaluación

0/5 correctas · 0 respondidas Reiniciar

1. ¿Cuántas aristas tiene el árbol?

a) 36b) 35c) 34d) 27

2. T_PWS en el ejercicio es…

a) 9b) 13c) 35d) 47

3. T_DTS con dos momentos:

a) 3 + 2 + 8 = 13b) 3 + 14 = 17c) 35/6d) 5 + 4.3

4. ¿Cuál tiene la mayor eficiencia?

a) PWSb) DTS un momento (0.69)c) DTS dos momentos (0.45)d) todos igual

5. ¿Por qué E baja al pasar de 3 a 6 procesos en DTS?

a) por trabajo redundanteb) por desbalance de subárboles y el tramo secuencial de particiónc) por comunicación MPId) porque hay más soluciones

Fuente ·U5.3 Algoritmos-busqueda.pdf (láminas 27–37) · participacion9_busqueda.pdf · programa propio: dfs_tareas.cpp