Pesquisa binária-ish através do conjunto parcialmente ordenado

Question

Eu tenho uma função interessante. É preciso subconjuntos de {1, ..., n} para inteiros positivos, isto é, $ f: p ([n]) \ righttarrow z ^ + $ . Eu sei que se s é um subconjunto de s ', $ f (s) . Além disso, se s e s 'têm a mesma cardealidade, a ordenação induzida por f é lexicográfica, então, por exemplo, $ f (\ \ \ \ \ f (\ {1,3,4 \ \}) $ . Dado um valor z , eu gostaria de encontrar tal que $ f (s) <= z $ e $ f (s) <= f (t) <= z $ implica $ f (t)= f (t) $ - isto é, quero fazer uma pesquisa sobre a rede de subconjuntos de [n].

Se eu soubesse que o pedido era perfeitamente lexicográfico, usaria uma simples busca binária. Eu não sei disso, e acredito que não é (por exemplo, $ f (\ \ \ \ \ \ \ \}) $ é possivelmente maior que $ f (\ \ \ {7 \}) $ ). Existe um bom algoritmo O (n) para fazer esta pesquisa no poset? Obviamente, para N de qualquer tamanho apreciável, tenho que calcular f on-the-fly e não posso confiar no armazenamento na memória.

Esclarecimento após uma discussão nos comentários: A classe $ F $ Eu estou lidando é aditivo - especificamente, $ f (s)=sum_ {k \ Em S} g (k) + f (\ FORTSET) $ , com $ g $ uma função monotonicamente aumentando. Isso pode ser mais fácil do que o caso geral (que também é interessante, mas não meu problema particular).

Answer 1

Aqui está um algoritmo simples que é executado em $ O (n ^ 2) $ tempo e $ O (N) $ espaço, assumindo que $ f (\ FORTSET) $ , $ f (\ \ \ \ \}) $ , $ f (\ {2 \}) $ , $ \ cdots $ , $ f (\ \ \ \}) $ são dados em uma matriz.

A ideia inicial é sobre o mesmo que o que foi dado pelo OP em seu comentário. "Vamos procurar em subconjuntos de tamanho K usando a ordem lexicográfica, para cada $ k $ de $ 0 $ a $ N $ . Reter a um com o melhor valor de $ f $ . "

O problema é, então, como procurar o melhor valor de $ f $ em subconjuntos de tamanho $ K $ , com o nome $ b_K $ , em $ O (N) $ tempo. Em vez de busca binária, vamos verificar se $ n $ , $ N-1 $ , \ CDOts, $ 1 $ deve ser incluído no melhor subconjunto um por um, tomando a vantagem real da ordem lexicográfica em subconjuntos.

.
1. inicialize $ b_k= f (\ FORTSET) $ . $ \ b_K $ vai ser o melhor valor em subconjuntos de tamanho $ K $ no final deste procedimento .
2. inicialize $ contagem= 0. $ $ \ contagem $ é o número de elementos que temos incluído no melhor subconjunto até agora.
3. check $ f (\ {n \}) $ . Se $ b_k + f (\ {n \}) + f (\ {1, 2, \ CDOts, k-contagem -1}) \ le z $ , $ n $ deve ser incluído. Adicionar $ f (\ \ \ \ \}) $ para $ b_k $ e adicione 1 a $ contagem $ .
4. check $ f (\ \ \ \ \ \ \ \ \ \}) $ . Se $ b_K + f (\ {N-1 \}) + F (\ {1, 2, \ cdots, K-count-1 \}) \ le z $ , $ n-1 $ deve ser incluído. Adicionar $ f (\ {n-1 \}) $ para $ b_k $ e adicione 1 a < span class="contentor de matemática"> $ contagem $ .
5. e assim por diante.
6. até que tenha verificado $ F (\ \ \ {1 \}) $ ou $ contagem== K $ < / span>.

Podemos perguntar, se ele vai tomar $ O (N) $ para calcular cada $ f (\ {1 , 2, \ cdots, K-count-1 \}) $ , computação cada $ b_K $ só vai tomar $ O (n * n) $ tempo. No entanto, uma vez que $ F $ é aditivo, podemos calcular todas as somas do prefixo da $ f (\ \ \ \ {1 \}) $ , $ f (\ \ \ \ {2 \}) $ , $ \ cdoz $ , < span class="math-container"> $ f (\ {N \}) $ inicial em $ O (N) $ tempo. Em seguida, é preciso $ O (1) $ para acessar cada soma prefixo.

Uma vez que a pesquisa $ b_K $ leva $ O (N) $ tempo, para cada $ K $ de $ 0 $ a $ N $ , o tempo total de execução é $ o (N ^ 2) $ .

---

.

A descrição acima do algoritmo pula o caso mais fácil quando $ f (\ FORTSET) \ gt z $ . Nesse caso, o algoritmo deve retornar que não existe tal subconjunto.