Algorithms For Dummies

  Performing Local Search 

     351

on the Dummies site as part of the downloadable code; see the Introduction for 

details.)

import numpy as np

import random

from math import log2

import matplotlib.pyplot as plt

% matplotlib inline

def signed(v):

    return v if np.random.random()<0.5 else -v

def create_clauses(i, seed=1):

    np.random.seed(seed)

    return [(signed(np.random.randint(i)), signed(

                np.random.randint(i))) for j in range(i)]

def create_random_solution(i, *kwargs):

    return {j:signed(1)==1 for j in range(i)}

def check_solution(solution, clauses):

    violations = list()

    for k,(a,b) in enumerate(clauses):

        if not (((solution[abs(a)]) == (a>0)) |

                ((solution[abs(b)]) == (b>0))):

            violations.append(k)

    return violations

After setting these functions, you have all the building blocks for a 

sat2

 function 

to solve the problem. This solution uses two nested iterations: The first replicates 

many starts; the second picks unsatisfied conditions at random and makes them 

true. The solution runs in polynomial time. The function isn’t guaranteed to find 

a solution, if one exists, but chances are, it will provide a solution when one exists. 

In  fact,  the  internal  iteration  loop  makes 

2*k

2

  random  attempts  to  solve  the 

circuit,  which  usually  proves  enough  for  a  random  walk  on  a  line  to  reach  its 

destination.

A random walk is a series of computations representing an object that moves away 

from  its  initial  position  by  taking  a  random  direction  at  every  step.  You  might 

imagine a random walk as the journey of a drunken person from one light pole to 

the  next.  Random  walks  are  useful  for  representing  a  mathematical  model  of 

many real-world aspects. They find applications in biology, physics, chemistry, 

computer  science,  and  economics,  especially  in  stock  market  analysis.  If  you 

---

352