Supongamos que tengo un poset "S" y un predicado monótono "P" en S. Quiero encontrar uno o todos los elementos máximos de S que satisfagan a P.
EDITAR : Estoy interesado en minimizar el número de evaluaciones de P .
¿Qué algoritmos existen para este problema y qué propiedades y operaciones adicionales requieren en S?
¿Qué pasa con casos especiales importantes, como:
- S es un orden lineal, entonces la búsqueda binaria regular funciona, siempre y cuando tenga una operación de "búsqueda intermedia"
- S es una red
- S es una red de subconjuntos
- S es una red multiset
- ...
Los dos últimos casos parecen particularmente importantes, por ejemplo, para el diseño de experimentos: tiene un conjunto de parámetros booleanos o reales, y desea encontrar la combinación más pequeña posible que reproduzca un patrón particular (por ejemplo, una prueba fallida).
Respuestas:
No he pensado mucho en esto, así que corrígeme si me equivoco.
Digamos que es el ancho del poset.w
Para el poset que es la unión de cadenas disjuntas, necesita al menos w log n evaluaciones de P simplemente aplicando el límite inferior estándar en la complejidad de la consulta de búsqueda binaria a cada cadena.w w lognorte PAGS
Como proporciona comparaciones de forma gratuita, puede calcular una descomposición en cadena del poset en cadenas de forma gratuita. Utilizar búsqueda binaria en cada cadena para identificar el primer elemento que satisface P . Luego repase los elementos identificados y elimine los dominados. El número de evaluaciones de P es O ( w log n ) . Esto identifica todos los elementos máximos, ya que puede haber como máximo un elemento máximo por cadena.w PAGS PAGS O ( w logn )
AGREGADO: En realidad estoy viendo un algoritmo recursivo simple para hacerlo mucho mejor ( ) para la red de subconjuntos 2 [ n ] ( EDIT : domotor describió la estrategia general en su respuesta). Aquí estoy asumiendo que P es monótono hacia abajo (es decir, los subconjuntos { X : P ( X ) = 1 } forman un conjunto más bajo), que es lo que quiero decir. Entonces, aquí está el algoritmo para encontrar un miembro del conjunto inferior:O ( n ) 2[ n ] PAGS { X: P( X) = 1 }
a) Prueba . Si es 0, entonces pare.PAGS( ∅ )
b) Prueba .PAGS( { n } )
bi) Si 0, entonces recurse en (OK, ya que ningún conjunto que contenga n puede estar en el conjunto inferior).2[ n - 1 ] norte
b.ii) Si 1, entonces existe un miembro del conjunto inferior en la subred . Esta subred es isomorfa a 2 [ n - 1 ], por lo que una vez más podemos recurrir. Más precisamente, podemos ejecutar el algoritmo para 2 [ n - 1 ] , pero cuando el algoritmo pide evaluar P ( Y ) , evaluamos P ( X ) donde X = Y ∪ { n } .{ X: n ∈ X} 2[ n - 1 ] 2[ n - 1 ] PAGS( Y) PAGS( X) X= Y∪ { n }
Entonces, en cada paso, recurrimos a una sub-red que es la mitad del tamaño de la original. En general, necesitamos evaluar como máximo 2 n veces (de hecho, puede implementar el algoritmo para evaluar el predicado n + 1 veces como señala Yoshio, ya que solo necesita verificar ∅ una vez).PAGS 2 n n + 1 ∅
fuente
Generalización de la búsqueda binaria: búsqueda en árboles y órdenes parciales similares a bosques
fuente
fuente
Además, puede haber muchos elementos máximos que satisfagan P, por lo que incluso generar todos ellos puede llevar mucho tiempo, por lo que creo que solo hay esperanza de encontrar uno máximo.
En general, la búsqueda binaria funciona si puede seleccionar elementos de forma recursiva de modo que después de que se quede con los elementos anteriores o los elementos anteriores se eliminen, y en cada uno de estos conjuntos se elimine una proporción fija de los elementos.
P.ej. si S es una cuadrícula dimensional fija, entonces hay un algoritmo rápido: siempre reduzca a la mitad una coordenada mientras mantiene las otras mínimas, así que pregunte, por ejemplo, en el primer paso (n / 2,0, ..., 0).
fuente
fuente