Search Problems

Loading...

Del curso dictado por University of California San Diego

Advanced Algorithms and Complexity

220 calificaciones

University of California San Diego

Advanced Algorithms and Complexity

220 calificaciones

Curso 5 de 6 en SpecializationData Structures and Algorithms

You've learned the basic algorithms now and are ready to step into the area of more complex problems and algorithms to solve them. Advanced algorithms build upon basic ones and use new ideas. We will start with networks flows which are used in more typical applications such as optimal matchings, finding disjoint paths and flight scheduling as well as more surprising ones like image segmentation in computer vision. We then proceed to linear programming with applications in optimizing budget allocation, portfolio optimization, finding the cheapest diet satisfying all requirements and many others. Next we discuss inherently hard problems for which no exact good solutions are known (and not likely to be found) and how to solve them in practice. We finish with a soft introduction to streaming algorithms that are heavily used in Big Data processing. Such algorithms are usually designed to be able to process huge datasets without being able even to store a dataset.

De la lección

NP-complete Problems

Although many of the algorithms you've learned so far are applied in practice a lot, it turns out that the world is dominated by real-world problems without a known provably efficient algorithm. Many of these problems can be reduced to one of the classical problems called NP-complete problems which either cannot be solved by a polynomial algorithm or solving any one of them would win you a million dollars (see Millenium Prize Problems) and eternal worldwide fame for solving the main problem of computer science called P vs NP. It's good to know this before trying to solve a problem before the tomorrow's deadline :) Although these problems are very unlikely to be solvable efficiently in the nearest future, people always come up with various workarounds. In this module you will study the classical NP-complete problems and the reductions between them. You will also practice solving large instances of some of these problems despite their hardness using very efficient specialized software based on tons of research in the area of NP-complete problems.

Brute Force Search5:42

Search Problems9:44

Traveling Salesman Problem7:57

Hamiltonian Cycle Problem8:09

Longest Path Problem1:42

Integer Linear Programming Problem3:08

Independent Set Problem3:07

Conoce a los instructores

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Daniel M Kane
Assistant Professor
Department of Computer Science and Engineering / Department of Mathematics
Neil Rhodes
Adjunct Faculty
Computer Science and Engineering

We will now give a formal definition of a Search Problem.

And we will do this by considering the famous boolean satisfiability problem.

The input for this problem is a formula in conjunctive normal form,

which is usually abbreviated just as CNF.

So a formal and conjunctive number form is just a set of clauses.

In this case, in this example, we have five clauses.

This is the first one.

This is the second one.

The third one, the fourth one, and the last one.

Each clause is a logical, is a logical or, or a disjunction of a few literals.

For example, the first one is a disjunction of literals x, y, and z.

The second one is the disjunction of x and the negation of y.

The third one is a disjunction of y and not z, or a negation of z, and so on.

So x, y and z are Boolean variables.

These are variables that take Boolean values.

The Boolean values are true and false and

we will usually use 1 instead of true and 0 instead of false.

So what this formula tells us is the first

clause actually constrains the values of x,

y, and z to be so that either x = 1,

or y = 1, or z = 1, right?

So this is just x, or y, or z.

The second clause tells use that either x must be true, or

the negation of y must be true.

That is, either x = 1, or y = 0 and so on.

For example, the last clause tells us

that either x = 0 or y = 0, or z = 0.

Then, the Boolean Satisfiability problem, or just Satisfiability problem,

which is also abbreviated as SAT usually, is stated as follows.

Given a formula in conjunctive normal form,

we would like to check whether it is satisfiable or not.

That is, whether it is possible to assign Boolean values to all variables so

that all clauses are satisfied.

If it is possible, we need to output a satisfying assignment.

If it is not possible, we need to report that no such assignment exists.

Now we give a few examples.

In the first example, we're given a formula over two variables, x and y.

It contains three clauses, and it is satisfiable.

To satisfy it, we can assign the value 1 to x and the value 0 to y.

Let's check that it indeed satisfies all three clauses.

Well, in the first clause, x is satisfied.

In the second clause, not y is satisfied.

And, in the last clause X is satisfied.

In the second example,

we illustrate that a formula may have more than just one satisfying assignment.

For example, for

this formula there is a satisfying assignment which assigns the value 1 to x,

y, and z and there is another satisfying assignment which is shown here.

Okay, for the last formula, the last formula is unsatisfiable.

And probably the most straightforward way to check this is just to list all possible

truth assignments to x, y and z.

So there are eight such assignments.

Let me list them all.

Then for each of these assignments,

we need to check that each of them falsifies at least one clause.

For example, the first one falsifies the first clause.

When x, and y, and z = 0, the first clause is falsified, right?

For the second one, it falsifies the clause y or not z, right?

The third one falsifies the clause x or naught y and so on.

So it can be checked that each of these eight

assignments falsifies at least one clause.

So another way of showing that this formula is satisfiable is the following.

Let's first try to assign the value zero to x.

Then let's take a look at the following clause.

So it is x or not y.

x is already assigned zero.

So the only way to satisfy this clause is to assign the value 0 to y.

So setting x to 0 forces us to set y to 0 also.

Now let's take a look at this clause.

It forces us to set the values 0 to z, also.

But then we see that this clause is already falsified, right,

which tells us that our initial move, I mean to assign 0 to x was a wrong move.

That we need to assign the value 1 to x.

Let's try to do this.

If x = 1, let's take a look at the following clause.

Not x is already falsified in this clause, so we need to assign the value 1 to z.

Now let's take at this clause.

Not z is already falsified here so

we need to assign the value 1 to y.

But then this clause is falsified.

So no matter how we assign x, it forces us to some other assignments and in the end,

we falsify some clause which justifies that this formula is unsatisfiable.

That is a canonical hard problem.

It has applications in various branches of computer science.

In particular because many hard combinatorial problems

are reduced very easily to the satisfiability problems.

I mean, many hard combinatorial problems can be stated very naturally in terms

of SAT and then when a problem is stated in terms of SAT, we can use

a so-called SAT solver, which is a program that solves the satisfiability problem.

There are many such programs and

there is even a [INAUDIBLE] competition of SAT solvers.

SAT is also a classical example of a so-called search problem.

In a search problem, we're given an instance site, or

just and and our goal is to final a solution for this instance.

A solution S or to report that there is not such solution.

For example, in case of the SAT problem, an instance I

is a formula in conjunctive normal form and S is a satisfied assignment.

For this formula, we need to check whether there is a satisfying assignment and

to return one if it exists.

Or to report that this formula is unsatisfiable.

This is, that there is no satisfying assignment.

A natural property to require from a such problem is that we can

quickly check with a given Solution S is indeed a solution for I.

For example, in case of SAT, it is easy.

If we are given a truth assignment of values to all the variables,

we can quickly check whether it satisfies all the clauses.

Namely, we just count all the clauses from left to right and for each clause,

we check whether it contains literal that satisfies this clause.

Another natural property is that we require the length of S to be

bounded by polynomial in the lengths of I.

Right, so we want S to be not very large.

We do not want S to have, for example, exponential size in the length of I.

In this case, it would require us an exponential time just to write down

a solution for the instance I.

So once again, the natural property of a search problem is the following.

We have an algorithm which checks whether the given solution S

is indeed a solution for an instance I in time,

which is bounded by polynomial in the lengths of I only.

This also forces S, the length of S, to be bounded by a polynomial of I.

In fact, it is convenient to define a search problem

through such a very fine algorithm.

Namely we say that this search problem is defined by an algorithm C that takes

two parameter as an input.

An instance I and a candidate solution S.

It should run in time polynomial I, in the length of I, and we say that S is

a solution for the instance I if C of I, S returns true.

For example, SAT is clearly a search problem.

In this case, once again, I is a CNF formula and

S is a truth assignment of Boolean values to variables.

And this algorithm, C, just scans all the clauses and

checks whether each clause contains a literal that is

satisfied by the given assignment, S.

Of course, it's surrounding time is polynomial in the lengths of the formula.

Great.

In the next part, we will see a few examples of search problems that arise

frequently in factors for which we still don't know polynomial time algorithms.

Explora nuestro catálogo

Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.

Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.

© 2018 Coursera Inc. Todos los derechos reservados.

Descargar en la App Store

Consíguelo en Google Play