#MonthOfCode day 18 - search
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import random | |
# This code implements the so-called "descent method" which is a kind of NEIGHBOR SEARCH METHOD | |
# often used in optimization. | |
# I apply it to the simple problem of finding the minimum value in a huge random matrix | |
# I count the nb of values tested to show how this kind of search is efficient in practice | |
# I initiale a random matrix and compute the global min. value on-the-fly to know | |
# if the descent method eventually succeeds in finding it. | |
N = 128 ; M = 128 | |
MAX_VAL = 255 | |
global_min = MAX_VAL | |
matr = list() | |
for i in xrange(N): | |
tmp_row = list() | |
for j in xrange(M): | |
rand_number = random.randint(1, MAX_VAL) | |
tmp_row.append(rand_number ) | |
if(rand_number<global_min): | |
global_min = rand_number | |
matr.append( tuple(tmp_row)) | |
del tmp_row | |
# defining concepts of "solution" and "neighborhoord" for our context | |
class OptPbSolution: | |
def __init__(self, coord_i, coord_j): | |
self.i = coord_i | |
self.j = coord_j | |
self.val = matr[self.i][self.j] | |
def __str__(self): | |
return str(self.val) | |
def dumpCoords(self): | |
return '('+str(self.i)+', '+str(self.j)+')' | |
def getNeighbors(self): | |
l_coord = list() | |
if self.i >0: | |
l_coord.append( (self.i-1, self.j) ) | |
if self.i+1 < N: | |
l_coord.append( (self.i+1, self.j) ) | |
if self.j >0: | |
l_coord.append( (self.i, self.j-1) ) | |
if self.j+1 < M: | |
l_coord.append( (self.i, self.j+1) ) | |
tmp_l = [ OptPbSolution( *coord) for coord in l_coord ] | |
return tmp_l | |
def detBetterSol( neighbors, s): | |
'''returns the solution in neighbors that has the lowest value''' | |
min_value = neighbors[0].val | |
print neighbors[0].val | |
candidate = neighbors[0] | |
for i in xrange(1, len(neighbors)): | |
print neighbors[i].val | |
if (neighbors[i].val < min_value): | |
min_value = neighbors[i].val | |
candidate = neighbors[i] | |
return candidate | |
def runDescentMethod(): | |
'''returns the minimum found along with the nb of tested solutions''' | |
nb_tested = 1 | |
# step1: choosing an initial solution we call s, I proceed randomly | |
init_sol = OptPbSolution( | |
random.randint(0,N-1), random.randint(0,M-1) ) | |
print " init. solution:",str(init_sol)," coords:",init_sol.dumpCoords() | |
s = init_sol | |
while ( True ): | |
# step2: find the best solution s' in N(s) the neighborhood of s | |
neighbors = s.getNeighbors() | |
s_quote = detBetterSol( neighbors, s ) | |
nb_tested+=len(neighbors) | |
# step3: stop if there is no s' in N(s) better than s, repeat step2 otherwise | |
if s_quote.val>=s.val: | |
break | |
s = s_quote | |
print " best solution found in the neighborhood",str(s)," coords:",s.dumpCoords() | |
print "Descent Search terminated." | |
return (s.val, nb_tested) | |
# MAIN ALGORITHM , we perform 6 successive Descent method searching | |
meta_min, total_tested = runDescentMethod() | |
for i in xrange(5 ): | |
tmp_m, tmp_tested = runDescentMethod() | |
if(meta_min > tmp_m): | |
meta_min = tmp_m | |
total_tested += tmp_tested | |
print "FINAL STATS-- best value found:",meta_min | |
print "nb of values tested:",total_tested | |
print "total nb of values:",N*M | |
if( meta_min==global_min): | |
print "the global minimum has been found!" | |
else: | |
print "the global minimum was:",global_min |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment