Jump to content
killezio

Dúvida em lógica

Recommended Posts

killezio

aqui está o enunciado do exercício:

"

You own a milkshake shop. There are N different flavors that you can prepare, and each flavor can be prepared "malted" or "unmalted". So, you can make 2N different types of milkshakes.

Each of your customers has a set of milkshake types that they like, and they will be satisfied if you have at least one of those types prepared. At most one of the types a customer likes will be a "malted" flavor.

You want to make N batches of milkshakes, so that:

  • There is exactly one batch for each flavor of milkshake, and it is either malted or unmalted.
  • For each customer, you make at least one milkshake type that they like.
  • The minimum possible number of batches are malted.

Find whether it is possible to satisfy all your customers given these constraints, and if it is, what milkshake types you should make.

If it is possible to satisfy all your customers, there will be only one answer which minimizes the number of malted batches.

"

Já estou ás voltas nisto há alguns dias e não consigo perceber porque é que este exercício se insere na categoria de complexidade "P" e não "NP". A única explicação que encontrei diz que tem a haver com o facto de no máximo, cada <costumer> gosta de um sabor do tipo <malted>. E com isto aqui está a solução que eles dão

"

On the surface, this problem appears to require solving the classic problem "Satisfiability," the canonical example of an NP-complete problem. The customers represent clauses, the milkshake flavors represent variables, and malted and unmalted flavors represent whether the variable is negated.

We are not evil enough to have chosen a problem that hard! The restriction that makes this problem easier is that the customers can only like at most one malted flavor (or equivalently, the clauses can only have at most one negated variable.)

Using the following steps, we can quickly find whether a solution exists, and if so, what the solution is.

  • Start with every flavor unmalted and consider the customers one by one.

  • If there is an unsatisfied customer who only likes unmalted flavors, and all those flavors have been made malted, then no solution is possible.

  • If there is an unsatisfied customer who has one favorite malted flavor, then we must make that flavor malted. We do this, then go back to step 2.

  • If there are no unsatisfied customers, then we already have a valid solution and can leave the remaining flavors unmalted.

Notice that whenever we made a flavor malted, we were forced to do so. Therefore, the solution we got must have the minimum possible number of malted flavors.

With clever data structures, the above algorithm can be implemented to run in linear time.

"

Mesmo com isto não percebo o impacto na diferença em que aqui um "costumer" gosta no máximo de um "malted" "flavor". Poderá ser também porque não consegui entender o problema que eles referem na primeira linha "Satisfiability problem" e outro que é "Horn Clauses".

Por isso venho aqui pedir ajuda a alguém que me possa explicar melhor a situação toda. ( para o caso de dúvidas. eu sei o objetivo do problema, simplesmente não percebo como resolvê-lo em tempo linear como é referido na última linha da solução deles, até porque não percebo como torná-lo num problema linear "P")

Agradeço toda a ajuda!

Edited by killezio

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.