Algorithms For Dummies

 

   

  PART 5 

 Challenging Difficult Problems

want to know more about random walks, go to 

http://www.mit.edu/~kardar/ 

teaching/projects/chemotaxis(AndreaSchmidt)/random.htm

.

A random walk on a line is the easiest example of a random walk. On average, 

k

2

 

steps of a random walk are required to arrive at a k distance from the starting 

point. This expected effort explains why RandomWalkSAT requires 

2*k

2

 random 

chances to amend the starting solution. The number of chances provides a high 

probability  that  the  algorithm  will  fix  the  k  clauses.  Moreover,  it  works  as  the 

random card guessing game discussed in the previous chapter. As the algorithm 

proceeds,  choosing  the  right  answer  becomes  easier.  The  external  replications 

guarantee an escape from unfortunate internal-loop random choices that may 

stop the process in a local solution.

def sat2(clauses, n, start=create_random_solution):

    for external_loop in range(round(log2(n))):

        solution = start(n, clauses)

        history = list()

        for internal_loop in range(2*n**2):

            response = check_solution(solution, clauses)

            unsatisfied = len(response)

            history.append(unsatisfied)

            if unsatisfied==0:

                print ("Solution in %i external loops," %

                       (external_loop

+1), end=" ")

                print ("%i internal loops" %

                       (internal_loop

+1))

                break

            else:

                r1 = random.choice(response)

                r2 = np.random.randint(2)

                clause_to_fix = clauses[r1][r2]

                solution[abs(clause_to_fix)] = (

                 clause_to_fix>0)

        else:

            continue

        break

    return history, solution

Now that all the functions are correctly set, you can run the code to solve a prob-

lem. Here’s the first example, which tries the circuit created by seed 0 and uses 

1,000 logic gates.

---

CHAPTER 18