Two-way breadth priority search method.

In the previous article, the breadth priority search method was said, and 8 digital issues were taken as an example. 8 Digital issues are relatively simple, generally not more than 30 steps to be solved. The search nodes will not exceed 10,00000. And the number of steps in this question is 56. If you use a wide priority search directly, the number of nodes will be more difficult.

######## Black ### # ## # is wall #White ######## | ####### White ### # ### black #### ####

The problem is to interchange the above two states.

Bidirectional Parent-Search I saw it on the "Artificial Intelligence" website. Its idea is to start searching from the start state and end state, with the search for, both parties will meet in the middle. This finds a canken, and it is the minimum step. The specific method is to find a node for each additional node, if the same status node is found, it is found.

The following programs and general range priority search have no difference, the difference is the judgment of two-way encounter.

/ * ----------- ######## Black ### # ## # is the wall # white ######## | ######## White ### # ### black ######## ----------- * / # include

TypeDef unsigned long long uint64; typef struct {char x; // The number of digits on the x and position Y; // where x is 0 position} PZ_MOVE;

TypedEf struct pz_node_tag {uint64 v; struct pz_node_tag * prev, * small, * Big;} PZ_Node;

#define row 3 # Define col 5 # Define Num (Row * COL) #define max_node 2000000 # define max_DEP 100 # define max_move 6

#define xchg (a, b) {a = a b; b = a - b; a = a - b;} #define trans (a, b) {long III; (b) = 0; for (iii = 0; III = 0; III-) / {/ b [iii] = TTT & 0xF; / TTT >> = 4; / } /} // convert a 64-bit integer A into an array B

// PZ_NODE m_ar1 [MAX_NODE]; long m_depth1; // search depth PZ_NODE m_out1 [MAX_DEP]; // output path PZ_NODE * m_root1; PZ_NODE m_ar2 [MAX_NODE]; long m_depth2; // search depth PZ_NODE m_out2 [MAX_DEP]; // Output path PZ_NODE * m_ROOT2;

// long move_gen (pz_node * mv) {long c = 0; char ST [NUM]; RTRANS (Node-> V, ST); IF ((ST [0]! = 0) && (ST [ 1] == 0)) {MV [C] .x = 1; MV [C] .y = 0; C ; IF (ST [2] == 0) {MV [C] .x = 2; MV [ C] .y = 0; C ;} IF (ST [6] == 0) {mv [c] .x = 6; MV [C] .y = 0; C ;}}

IF (ST [1]) {IF (ST [0] == 0) {mv [c] .x = 0; MV [C] .y = 1; C ;}

IF (ST [2] == 0) {MV [C] .x = 2; MV [C] .y = 1; C ; IF (ST [3] == 0) {MV [C] .x = 3 ; MV [C] .y = 1; C ;}}

IF (ST [6] == 0) {MV [C] .x = 6; MV [C] .y = 1; C ; IF (ST [11] == 0) {MV [C] .x = 11 ; MV [C] .y = 1; C ;}}}

IF (ST [2]) {IF (ST [1] == 0) {mv [C] .x = 1; MV [C] .y = 2; C ; IF (ST [0] == 0) { MV [C] .x = 0; MV [C] .y = 2; C ;}

IF (ST [6] == 0) {mv [c] .x = 6; MV [C]. Y = 2; C ;}}

IF (ST [3] == 0) {mV [c] .x = 3; MV [C]. Y = 2; C ; if (ST [4] == 0) {mv [c] .x = 4 ; MV [C] .y = 2; C ;} IF (ST [8] == 0) {mV [C] .x = 8; MV [C] .y = 2; C ;}}}

IF (ST [3]) {IF (ST [4] == 0) {mV [c] .x = 4; MV [C] .y = 3; C ;}

IF (ST [2] == 0) {mv [C] .x = 2; MV [C] .y = 3; C ; IF (ST [1] == 0) {MV [C] .x = 1 ; MV [C] .y = 3; C ;}}

IF (ST [8] == 0) {mV [C] .x = 8; MV [C] .y = 3; C ; IF (ST [13] == 0) {MV [C] .x = 13 ; MV [C] .y = 3; C ;}}}}

IF ((ST [4]! = 0) && (ST [3] == 0)) {mV [c] .x = 3; MV [C] .y = 4; C ; if (ST [2] = = 0) {MV [C] .x = 2; MV [C] .y = 4; C ;}

IF (ST [8] == 0) {MV [C] .x = 8; MV [C] .y = 4; C ;}}

IF ((ST [10]! = 0) && (ST [11] == 0)) {mv [c] .x = 11; MV [C] .y = 10; C ; if (ST [12] = = 0) {MV [C] .x = 12; MV [C] .y = 10; C ;}

IF (ST [6] == 0) {mv [C] .x = 6; MV [C] .y = 10; C ;}} IF (ST [11]) {IF (ST [10] == 0 ) {Mv [c] .x = 10; MV [C] .y = 11; C ;}

IF (ST [12] == 0) {mV [C] .x = 12; MV [C] .y = 11; C ; IF (ST [13] == 0) {mv [c] .x = 13 ; MV [C] .y = 11; C ;}}

IF (ST [6] == 0) {mV [c] .x = 6; MV [C] .y = 11; C ; IF (ST [1] == 0) {mv [c] .x = 1 ; MV [C] .y = 11; C ;}}}}}

IF (ST [12]) {IF (ST [11] == 0) {mv [C] .x = 11; MV [C] .y = 12; C ; IF (ST [10] == 0) { MV [C] .x = 10; MV [C] .y = 12; C ;}

IF (ST [6] == 0) {MV [C] .x = 6; MV [C]. Y = 12; C ;}}

IF (ST [13] == 0) {MV [C] .x = 13; MV [C] .y = 12; C ; IF (ST [14] == 0) {MV [C] .x = 14 ; MV [C] .y = 12; C ;}

IF (ST [8] == 0) {MV [C] .x = 8; MV [C]. Y = 12; C ;}}}

IF (ST [13]) {IF (ST [14] == 0) {mv [c] .x = 14; MV [C] .y = 13; C ;} if (ST [12] == 0) {MV [C] .x = 12; MV [C] .y = 13; C ; IF (ST [11] == 0) {mv [c] .x = 11; MV [C] .y = 13; C ;}}

IF (ST [8] == 0) {MV [C] .x = 8; MV [C] .y = 13; C ; IF (ST [3] == 0) {MV [C] .x = 3 ; MV [C] .y = 13; C ;}}}

IF ((ST [14]! = 0) && (ST [13] == 0)) {mv [c] .x = 13; MV [C] .y = 14; C ; if (ST [12] = = 0) {MV [C] .x = 12; MV [C] .y = 14; C ;}

IF (ST [8] == 0) {MV [C] .x = 8; MV [C] .y = 14; C ;}}

IF (ST [6]) {IF (ST [1] == 0) {mV [C] .x = 1; MV [C] .y = 6; C ; IF (ST [0] == 0) { MV [C] .x = 0; MV [C] .y = 6; C ;}

IF (ST [2] == 0) {mV [c] .x = 2; MV [C]. Y = 6; C ;}}

IF (ST [11] == 0) {mv [c] .x = 11; MV [C] .y = 6; C ; if (ST [10] == 0) {mv [c] .x = 10 ; MV [C] .y = 6; C ;}

IF (ST [12] == 0) {mV [c] .x = 12; MV [C] .y = 6; C ;}}}

IF (ST [8]) {IF (ST [3] == 0) {mv [C] .x = 3; MV [C] .y = 8; C ; IF (ST [4] == 0) { MV [C] .x = 4; MV [C] .y = 8; C ;}

IF (ST [2] == 0) {mv [C] .x = 2; MV [C] .y = 8; C ;}}

IF (ST [13] == 0) {mv [c] .x = 13; MV [C]. Y = 8; C ; IF (ST [14] == 0) {mv [c] .x = 14 ; MV [C] .y = 8; C ;}

IF (ST [12] == 0) {MV [C] .x = 12; MV [C] .y = 8; C ;}}}

Return C;

/ * / long move (pz_node * n1, pz_move * mv, pz_node * n2) // take a step, return the result of a step {char SS [Num]; RTRANS (N1-> V, SS); XCHG (SS [MV-> X], SS [MV-> Y]); TRANS (SS, N2-> V); Return 0;}

/ * / long add_node1 (pz_node * node, long r) {pz_node * p = m_root1; pz_node * q; while (p) {q = p; if (p-> v == node-> v) returnography; Else if (Node-> V> P-> V) P = P-> BIG; Else IF (Node-> V V) P = P-> Small;}

M_AR1 [r] .prev = node-> iprev = node-> prev; m_AR1 [r] .small = null; m_ar1 [r] .big = null; if (Node-> V> Q -> v) {q-> BIG = & m_AR1 [r];} else if (node-> v v) {q-> small = & m_AR1 [r];} Return 1;}

/ * / long add_node2 (pz_node * node, long r) {pz_node * p = m_root2; pz_node * q; while (p) {q = p; if (p-> v == node-> v) returnography; Else if (Node-> V> P-> V) P = P-> BIG; Else IF (Node-> V V) P = P-> Small;}

M_AR2 [r] .prev = node-> iprev = node-> prev; m_AR2 [r] .small = null; m_AR2 [r] .big = null; if (node-> v> q -> v) {Q-> BIG = & m_AR2 [r];} else if (node-> v v) {q-> small = & m_AR2 [r];}

Return 1;}

/ * Get the depth of the node * / long get_node_depth (pz_node * node) {long d = 0; while (node-> prev) {d ; node = node-> prev;}

Return D;

/ * Search for this node in Tree 2 whether this node exists * / pz_node * check_ok1 (pz_node * node) {pz_node * p = m_root2; while (p) {if (p-> v == node-> v) Return P; Else IF (Node-> V> P-> V) P = P-> BIG; Else IF (Node-> V V) P = P-> Small;}

Return NULL;

/ * Search for this node to the tree 1 * / pz_node * check_ok2 (pz_node * node) {pz_node * p = m_root1; while (p) {if (p-> v == node-> v) return p; Else IF (Node-> V> P-> V) P = P-> BIG; Else IF (Node-> V V) P = P-> Small;}

Return NULL;

/ * Return value: success - return 1, the number of nodes is not enough - (- 1), no solution - (- 2) * / long bfs_search (char * begin, char * end) {long h1 = 0, R1 = 1, H2 = 0, R2 = 1, C, I; PZ_Node Node, * pnode; PZ_MOVE MV [MAX_MOVE]; // Each situation is up to 4 kinds of ways TRANS (End, M_AR2 [0] .v); trans (begin, m_ar1 [0] .V); m_AR1 [0] .prev = null; m_root1 = m_AR1; m_root1-> small = null; m_root1-> BIG = NULL; M_AR2 [0] .prev = null; m_root2 = m_AR2; m_root2-> Small = NULL; M_ROOT2-> BIG = NULL; while ((h1 v; pnode = pnode-> prev; } PNODE = & node; m_depth1 = 0; while (pnode) {m_out1 [m_depth1 ]. v = pnode-> v; pnode = pnode-> prev;}

Return 1;}}}

H1 ; c = move_gen (& M_AR2 [H2], MV); for (i = 0; i v; pnode = pnode-> prev;} pnode = & node; m_depth2 = 0; while (pnode) {m_out2 [m_depth2 ]. v = pnode-> v; PNODE = PNODE-> prev;}

Return 1;}}}

H2 ; Printf ("/ RSearch ...% D /% D @% D |% D /% D @% D", H1, R1, GET_NODE_DEPTH (& M_AR1 [H1]), H2, R2, GET_NODE_DEPTH (& M_AR2 [H2 ]));

IF ((h1 == r1) && (h2 == r2)) {RETURN-2;} else {return -1;}}

/ * * / void output (void) {long i, j, k; char ss [num]; for (i = m_depth1 - 1; i> = 0; I -) {RTRANS (m_out1 [i] .v, SS); for (j = 0; j

Printf ("/ n");

Printf ("/ n");

For (i = 1; i

Printf ("/ n");

Printf ("/ n");}}

/ * * / int main (void) {ified [Num] = {1, 2, 3, 4, 5, 15, 0, 15, 0, 15, 6, 7, 8, 9, 10} ; // 0 Represents space, 15 denotes wall char end [Num] = {6, 7, 8, 9, 10, 15, 0, 15, 0, 15, 1, 2, 3, 4, 5}; # else Char Begin [Num] = {1, 1, 1, 1, 1, 15, 0, 15, 0, 15, 2, 2, 2, 2, 2}; // 0 indicate space, 15 denotes wall char end [ Num] = {2, 2, 2, 2, 2, 15, 0, 15, 0, 15, 1, 1, 1, 1, 1}); # endif long r = bfs_search (begin, end); printf (" / N "); if (r> = 0) {OUTPUT ();} else {printf (" BFS_Search Returns% D / N ", R);

Return 0;}