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)

5 comments

Robo 10 years, 4 months ago  # | flag

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  # | flag

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  # | flag

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  # | flag

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 :)

Feel free to place a link of your solution here as additional reference.

Thanks

J Dawg 8 years, 10 months ago  # | flag

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)
Python recipes (4591)
Filippo Squillace's recipes (12)

Required Modules

  • (none specified)

Other Information and Tasks