Hill climbing is an optimization technique which is a local
search algorithm. It is an algorithm that starts with a random solution to a
problem. By changing a single element of the solution it attempts to find a
better solution. Hill climbing is sometimes called greedy local search because
it grabs a good neighbor state without thinking ahead about where to go next.
To find a global maxima random restart hill climbing is
used. Random restart hill climbing is a series of hill climbing searches. From
randomly generated initial state until a goal is found.
board setup: n queens, one queen per column
successors : The successors of a state are all possible states generated by moving a single queen to another square in the same column. Meaning, there are n queens on the board and each queen can move to n-1 defined positions. So, each state has n*(n-1) successors.
heuristic cost function h : h is the number of pairs of queens that are attacking each other
Basic hill climbing creates a random state of the board. Then it finds the highest value successor of the current state(for n queen the lowest valued successor), which is called the neighbor. If the heuristic cost value of the neighbor is less than the heuristic cost value of the current state, then the neighbor becomes the current state. If not then the current solution is the minima of the current hill.
What random restart does is, it runs the hill climbing until the global minima is found. In each hill climbing, it creates a new initial state of the board then runs the hill climbing algorithm to find the minima of the hill. It stops when the global minima is reached.
h(board)
1 returns the number of attacking pair on board
highest_valued_successor_of_current(current)
1 best_h ← ∞
2 best_successor ← NULL
3 while(new successor can be created)
4 successor ← new_successor(current)
5 if h(successor) < best_h
6 best_h ← h(successor)
7 best_successor ← successor
8 return successor
hill_climbing()
1 current ← A random state of the board
2 while(1)
3 neighbor ← highest_valued_successor_of_current(current)
4 if h(neighbor) >= h(current)
5 return current
6 neighbor ← current
random_restart_hill_climbing()
1 final_h ← ∞
2 best_board ← NULL
3 while(final_h != 0)
4 result ← hill_climbing()
5 now_h ← h(result)
6 if final_h > now_h
7 final_h ← now_h
8 best_board ← result
9 return best_board
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
FINAL: | |
Total Iteration needed : 13 | |
number of conflict on final board : 0 | |
board: | |
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 | |
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 | |
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 | |
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 | |
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 | |
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 | |
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 | |
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 | |
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 | |
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | |
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 | |
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | |
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 | |
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 | |
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 | |
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 |
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
#include<bits/stdc++.h> | |
using namespace std; | |
#define si 16 /// 16 queen | |
///for generating random numbers | |
random_device rseed; | |
mt19937 rgen(rseed()); // mersenne_twister | |
uniform_int_distribution<int> idist(0,si-1); // [0,15] | |
int iteration = 0; | |
void show_board(vector<int> a){ | |
int b[si][si]; | |
memset(b,0,sizeof(b)); | |
for(int i=0;i<a.size();i++){ | |
b[a[i]][i] = 1; | |
} | |
for(int i=0;i<si;i++){ | |
for(int j=0;j<si;j++){ | |
cout<<b[i][j]<<" "; | |
} | |
cout<<"\n"; | |
} | |
} | |
vector<int> make_node(){ | |
vector<int> board; | |
bool vis[20]; | |
memset(vis,false,sizeof(vis)); | |
srand(time(0)); | |
for(int i=1;i<=si;i++){ | |
int num = idist(rgen); | |
while(vis[num]==true) | |
num = idist(rgen); | |
board.push_back(num); | |
vis[num] = true; | |
} | |
return board; | |
} | |
int h(vector<int> current){ | |
int val,row1,col1,row2,col2; | |
val = 0; | |
for(int i=0;i<current.size();i++){ | |
row1 = current[i]; | |
col1 = i; | |
for(int j=i+1;j<current.size();j++){ | |
row2 = current[j]; | |
col2 = j; | |
if((row1==row2) || (col1==col2) || (abs(row1-row2)==abs(col1-col2)) ){ | |
val++; | |
} | |
} | |
} | |
return val; | |
} | |
vector<int> get_highest_valued_successor_of_current(vector<int> current){ | |
vector<int> successor,best_successor; | |
int best_h = INT_MAX; | |
int row,col; | |
for(int i=0;i<current.size();i++){ | |
row = current[i]; | |
col = i; | |
for(int j=0;j<si;j++){ | |
if(row == j) continue; | |
current[i] = j; | |
successor = current; | |
current[i] = row; | |
int now = h(successor); | |
if(now<best_h){ | |
best_successor = successor; | |
best_h = now; | |
} | |
} | |
} | |
return best_successor; | |
} | |
vector<int> hill_climbing(){ | |
/// index is the column number of the queen and the value is the row number | |
vector<int> current = make_node(); | |
vector<int> neighbor; | |
while(1){ | |
neighbor = get_highest_valued_successor_of_current(current); | |
if(h(neighbor)>=h(current)) return current; | |
current = neighbor; | |
} | |
} | |
vector<int> random_restart_hill_climbing(){ | |
int val = INT_MAX; | |
vector<int> best; | |
iteration = 0; | |
while(val!=0){ | |
iteration++; | |
vector<int> result = hill_climbing(); | |
int now = h(result); | |
if(val>=now){ | |
best = result; | |
val = now; | |
} | |
} | |
return best; | |
} | |
int main(){ | |
vector<int> result = random_restart_hill_climbing(); | |
cout<<"FINAL:\n"; | |
cout<<"Total Iteration needed : "<<iteration<<"\n"; | |
cout<<"number of conflict on final board : "<<h(result)<<"\n"; | |
cout<<"board: \n"; | |
show_board(result); | |
return 0; | |
} | |
No comments:
Post a Comment