Welcome, guest | Sign In | My Account | Store | Cart

This is a template method for the hill climbing algorithm. It doesn't guarantee that it will return the optimal solution. If the probability of success for a given initial random configuration is p the number of repetitions of the Hill Climbing algorithm should be at least 1/p. Note: generate_configuration() is not implemented yet but is quite easy to understand what it does.

Python, 89 lines
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89``` ```def eight_queens(): """ The famous 8Queens problem! """ repetitions = 100 best_val = min_val best_conf = None for i in range(repetitions): A = generate_configuration() b_A = hill_climbing(A) v_b_A = value(b_A) if value(b_A)< best_val: best_val = v_b_A best_conf=b_A return best_conf def sons(A): """ The sons of the configuration A for an 8Queen problem is obtained reducing properly the space of the solutions. In particular, the son is obtained changing the row index of one of the queen. In total we have seven possible movement among the column, therefore the number of sons will be 7x8=56. """ tmp_A = list(A) N = len(A) for i in range(N): for r in range(7): tmp_A = list(tmp_A) q = tmp_A.pop(i) tmp_A.insert(i, ((q[0]+1)%7, q[1]) ) yield tmp_A raise StopIteration def value(A): """ The heuristic for the 8Queen problem is this: h(A) = number of attack that the queens have between each other. The data structure representation for the chessboard will be a list of tuples each of them representing the coordinates of a the position of a queen. Complexity: O(N^2) """ N = len(A) h=0 for i in range(N-1): for j in range(i+1, N): q1 = A[i] q2 = A[j] if q1[0] == q2[0]: h+=1 elif q1[1] == q2[1]: h+=1 elif q1[0]+q1[1] == q2[0]+q2[1]: h+=1 elif q1[0]-q1[1] == q2[0]-q2[1]: h+=1 return h def hill_climbing(A): """ A represents a configuration of the problem. It has to be passed as argument of the function sons(A) ans value(A) that determines, respectively, the next configuration starting from A where Hill Climbing Algorithm needs to restart to evaluate and the heuristic function h. This function represents a template method. """ best_val = sys.sizemax best_conf = None for conf in sons(A): val = value(conf) if best_val > val: best_conf = conf best_val = val if best_conf > value(A): return A return hill_climbing(best_conf) ```

Robo 10 years, 4 months ago

Hi,

thanks for the code! Helped me a lot.

I have one question: Not sure, but shouldn't the '<' sign in line 86 be relaced with a '>'? Because you have found a configuration that is better than the initial configuration A, so you want to go on using hill-climbing instead of returning the initial configuration. Also, you mixed up the variable names a bit in the end I think, but that just as a side note.

Filippo Squillace (author) 10 years, 4 months ago

Thanks Robo! You are right, I did some mistakes there. Changed the recipe.

I am happy that this recipe helped you ;)

ihateuselessregistration 9 years, 4 months ago

Line 7 references a value called "min_val", but it is never defined. And i have no clue what "generate_configuration()" is supposed to do.

Filippo Squillace (author) 9 years, 4 months ago

Hi,

You are right. Indeed the purpose of this recipe is just to show the template function hill_climbing(A) which it can be applied for any kind of problem like the 8 Queen.

As mentioned from the recipe description the min_val variable and generate_configuration function depends on the way you define the data structure (array of list, matrix, etc) which is beyond the purpose of this recipe since I do not want to make a recipe sounds like a bible :)

Thanks

J Dawg 8 years, 10 months ago

Hi - What is generate_configuration supposed to do? Create a list / array and randomly insert values? My generate_configuration generates a 2D array of 8 elements, for the row and col of each queen. Should it be random?

 Created by Filippo Squillace on Wed, 6 Jun 2012 (MIT)

### Required Modules

• (none specified)