Algorithms For Dummies

 Challenging Difficult Problems

Realizing that the starting  

point is important

Even  though  the 

RandomWalkSAT

 algorithm has a runtime complexity of 

O(log

2

k * k

2

)

 at worst, with k the number of inputs, you can speed it up by hack-

ing the starting point. In fact, even though starting with a random configuration 

means that a quarter of the clauses remains unsatisfied at the start on average, 

you can fix many of them using a pass over the data.

The problem with clauses is that many require a true input, and simultaneously, 

many others require a false input. When all clauses require an input to be true 

or false, you can set it to the required condition, which satisfies a large number 

of  clauses  and  makes  solving  the  residual  ones  easier.  The  following  new 

RandomWalkSAT

  implementation  includes  a  start  phase  that  immediately  solves 

the situations in which an input requires a specific true or false setting by all the 

clauses they interact with:

def better_start(n, clauses):

    clause_dict = dict()

    for pair in clauses:

        for clause in pair:

            if abs(clause) in clause_dict:

                clause_dict[abs(clause)].add(clause)

            else:

                clause_dict[abs(clause)] = {clause}

    solution = create_random_solution(n)

    for clause, value in clause_dict.items():

        if len(value)==1:

            solution[clause] = value.pop() > 0

    return solution

The code defines a new function for the cold start where, after generating a ran-

dom  solution,  it  scans  through  the  solution  and  finds  all  the  inputs  associated 

with a single state (true or false). By setting them immediately to the required 

state, you can reduce the number of clauses requiring amendment, and have the 

local search do less work and complete earlier.

n = 1000

# Solvable seeds = 0,1,2,3,4,5,6,9,10

# Unsolvable seeds = 8

clauses = create_clauses(n, seed=0)

---

CHAPTER 18