Búsqueda binaria-ish a través de conjunto parcialmente ordenado

Question

Tengo una función interesante. Lleva los subconjuntos de {1, ..., N} a enteros positivos, es decir, $ f: p ([n]) \ browarrow z ^ + $ . Sé que si S es un subconjunto de S ', $ f (s) . Además, si S y S "tienen la misma cardinalidad, el orden inducido por F es lexicográfico, por lo que, por ejemplo, $ f (\ {1,2,4}) . Dado un valor Z , me gustaría encontrar S tal que $ f (s) <= z $ y $ f (s) <= f (t) <= z $ implica $ f (s)= f (t) $ - es decir, quiero hacer una búsqueda en la celosía de los subconjuntos de [N].

Si sabía que el pedido era perfectamente lexicográfico, usaría una simple búsqueda binaria. No lo sé, y creo que no es (por ejemplo, $ f (\ {1,2,3,4,5,6 \}) $ es posiblemente mayor que $ f (\ {7 \}) $ ). ¿Hay algún algoritmo bueno de O (n) para hacer esta búsqueda en el POSET? Obviamente, para n de cualquier tamaño apreciable, tengo que calcular F en la mosca y no se puede confiar en el almacenamiento en memoria.

Aclaración después de una discusión en los comentarios: El $ f $ Estoy tratando con aditivo: específicamente, $ f (s)=sum_ {k \ En S} G (K) + F (\ OstSet) $ , con $ g $ una función de aumento monotónico. Esto puede ser más fácil que el caso general (que también es interesante, pero no mi problema en particular).

Answer 1

Aquí hay un algoritmo simple que se ejecuta en $ o (n ^ 2) $ tiempo y $ o (n) $ espacio, suponiendo que $ f (\ vaciasset) $ , $ f (\ {1 \}) $ , $ f (\ {2 \}) $ , $ \ cdots $ , $ f (\ {n \) $ se dan en una matriz.

La idea de inicio es casi lo mismo que lo que ha sido dado por la OP en su comentario. "Buscaremos en los subconjuntos de talla K usando el orden lexicográfico, para cada $ k $ de $ 0 $ a $ n $ . Conseje el mejor con el mejor valor de $ f $ . "

El problema es entonces cómo buscar el mejor valor de $ f $ en subconjuntos de tamaño $ k $ , llamado $ b_k $ , en $ o (n) $ tiempo. En lugar de la búsqueda binaria, verificaremos si $ n $ , $ n-1 $ , \ cdots, $ 1 $ debe incluirse en el mejor subconjunto por uno, tomando la verdadera ventaja del orden lexicográfico en los subconjuntos.

1. Inicializar $ b_k= f (\ vaciarset) $ . $ \ b_k $ será el mejor valor en subconjuntos de tamaño $ k $ al final de este procedimiento .
2. Inicializar $ cuenta= 0. $ $ \ contar $ es el número de elementos que tenemos Incluido en el mejor subconjunto hasta ahora.
3. verifique $ f (\ {n \}) $ . Si $ b_k + f (\ \ {n \}) + f (\ {1, 2, \ cdots, k-cuenta -1 \}) \ le z $ , $ n $ debe ser incluido. Añadir $ f (\ \ {n \}) $ a $ b_k $ y agregue 1 a $ cuenta $ .
4. Cheque $ f (\ {n-1 \}) $ . Si $ b_k + f (\ \ {n-1 \}) + f (\ {1, 2, \ cdots, k-cuenta-1 \}) \ le z $ , $ n-1 $ debe incluir. Agregar $ f (\ {n-1 \}) $ a $ b_k $ y agregue 1 a < Span Class="Math-contenedor"> $ cuenta $ .
5. y así sucesivamente.
6. hasta que hemos comprobado $ f (\ {1 \}) $ o $ cuenta== k $ < / span>.

Podríamos preguntarnos, si tomará $ o (n) $ para calcular cada $ f (\ {1 , 2, \ CDOTS, K-Count-1 \}) $ , computando cada $ b_k $ solo tomará $ O (n * n) $ tiempo. Sin embargo, desde $ f $ es aditivo, podemos calcular todas las sumas de prefijo de $ f (\ {1 \) $ , $ f (\ {2 \}) $ , $ \ cdots $ , < span class="Math-contenedor"> $ adelantado en $ o (n) $ tiempo. Luego se necesita $ o (1) $ para acceder a cada suma de prefijo.

Desde busca $ b_k $ toma $ o (n) $ tiempo, para cada $ K $ de $ 0 $ a $ n $ , El tiempo total de funcionamiento es $ o (n ^ 2) $ .

---

La descripción anterior del algoritmo salta el caso más fácil cuando $ f (\ vacyset) \ gt z $ . En ese caso, el algoritmo debe devolverlo que no existe tal subconjunto.