DFS and BFS notes (II): depth first search (implemented in C language)

Near the end of the semester （ pre ） junction （ xi ） Let's take a program design class .

Notes sorting and class exercises to complete the problem solving summary .

---

In fact, the search algorithm constructs a tree according to the initial conditions and extension rules “ Answer tree ” And the process of finding nodes that meet the target state . The search is “ General solutions ”, It plays an important role in the field of algorithms and artificial intelligence . But search has its limitations and flexibility , It is one of the most difficult algorithms to learn and use .

【 Learning goals 】 Facing problems ：1. Quickly build state space  2. Put forward a reasonable algorithm  3. Simple estimation of spatiotemporal performance

Categories of search

1 Blind search ：

· Breadth first search （Breadth First Search）

· Depth-first search （Depth First Search）

· Pure random search 、 Repeat search 、 Iteratively deepen the search 、 Iterative widening search 、 Column search ……

2 Heuristic search

Breadth first search （BFS）

QAQ Last one ：https://blog.csdn.net/m0_51588059/article/details/117562541

Depth first (DFS)

1） Construct a vertex element type Stack , In the initial state, the elements in it have only the root node ;

2） Match the top element of the stack with the target element Compare , If it is , Stop looking for ; otherwise , Continue with the procedure ;

3） remove Top element of stack , And the subsequent nodes of the top element of the stack are Add Into the stack ;

4） If the stack is empty , To find the failure ; otherwise , Turn to the second step .

Algorithm ideas

1、 Create an empty stack stack（ Used to store nodes ） And an empty list visit（ Used to store the accessed nodes ）

2、 In turn Starting point and adjacency point Join in stack and visit in

3、pop The last node in the stack , Get the adjacency point of the node from the graph

4、 If the adjacency point is not visit in , Then add the adjacent contact to stack and visit in

5、 Output pop Out of the node

6、 repeat 3、4、5, Until the stack is empty

Stack ： First in, then out , Only one side can access data , Call the end of the opening “ To the top of the stack ”, The sealed end is “ At the bottom of the stack ”

https://www.cnblogs.com/vacation/p/5179457.html
（1）． Select an appropriate angle to define the node state 
      Choose an appropriate angle to define the node state , It is an important step in designing search algorithm , Often the search algorithm can search from different angles , Which angle is easier to describe the node state （ Node definition ）, Which angle is more clear about the level of search （ Search depth ）, Which angle state transition relationship is easier to realize （ Generative formula ）, Which angle can search more efficiently （ prune ） wait , This is a problem that we need to consider comprehensively when choosing an appropriate angle to define the state .
（2）． Generative formula 
      The so-called production , That is, the relationship between the current node state and the next node state . The number of new nodes generated by each node is actually the search width of the node . Some production formulas are very simple and direct , For example, the problem of Full Permutation , Just enumerate the optional numbers , Some production formulas need to be changed slightly , for example , In the knight parade problem, the horse has 8 Jump , Each node can expand up to 8 New nodes , Each new node is obtained by adding an increment to the original node coordinates , So it can be used for Statement enumeration 8 The coordinate increment of two directions is enough . The quality of production , It can also directly affect the efficiency of the program .
（3）． Extension conditions 
      That is, what conditions are met before a node can be extended downward to generate a new node , That is to say, what conditions can be met before continuing the downward search . This extension condition is often an important part of constraining the size of the search tree , Many search optimization problems are pruned in this link .
（4）.  Target state 
      Determine the correct target state , That is, what conditions are met to output the scheme .
　　 One case is to search all the target nodes or any target node , One is to search the optimal target node , If you need to output a specific scheme , Also use an array to record each step of the search process .
（5）.  Preservation and restoration of state 
      If the process of expanding a child node needs to save the node state with global variables or variable formal parameters , The subroutine must restore its value after returning to the calling place .

The problem of crossing the river

Someone wants to take a dog 、 A chicken 、 A basket of rice crosses the river , But the boat needs people to row , You can only carry one thing across the river at most , and When people are not present , A dog bites a chicken 、 Chicken needs rice . Ask the person how to cross the river ?

State transition model and graph theory model .

analysis ：

· Exhaustive state , At the same time, it is necessary to judge the effectiveness of the action .

 · Breadth first search .

· It is necessary to avoid repeated states leading to dead cycles .

· Priority of actions ： Crossing the river is a priority ; Priority to return with goods .

modeling ：

establish （x1,x2,x3,x4） As a state model , The four positions represent （ people , Dog , chicken , rice ）, use 0 Represents the starting position ,1 Represents the end position . We need to （0,0,0,0）->(1,1,1,1).

The process ：

flow chart ：

Code ：

The classmate said that my thought was strange and I suspected that I didn't listen carefully in class . Pure use C I feel bad. I must go to study right away C++.

#include <stdio.h>
#include <stdlib.h>
typedef struct lineStack{
    int place[4];
    struct lineStack * next;
}lineStack;
//pop after , to update place by top 
lineStack* top(lineStack * stack,int a[]){
	if (stack->place!=NULL) {// Non empty  
		a[0]=stack->place[0];a[2]=stack->place[2];
		a[1]=stack->place[1];a[3]=stack->place[3];
      //  printf("now_stack_top:%d,%d,%d,%d\n",a[0],a[1],a[2],a[3]);   
    }
    else
	{
    	printf("null\n");	
	}
    return stack;
}
// Because last in first out , therefore stack Always the last  
lineStack* push(lineStack * stack,int a[]){
	//printf("push:%d,%d,%d,%d\n",a[0],a[1],a[2],a[3]);
    lineStack * line=(lineStack*)malloc(sizeof(lineStack));
    line->place[0]=a[0];line->place[1]=a[1];
	line->place[2]=a[2];line->place[3]=a[3];
    line->next=stack;// New node  
    stack=line;// to update  
    return stack;
}
lineStack * pop(lineStack * stack){
    if (stack->next!=NULL) {
        lineStack * p=stack;//stack Is the last position  
        stack=stack->next;
		printf("pop:%d,%d,%d,%d\n",p->place[0],p->place[1],p->place[2],p->place[3]);
        free(p);
    }
	else
        printf("null\n");
    return stack;
}
// Mobile method ( people , Dog , chicken , rice )
// according to 1-2-3-4-null The order of , Most at a time push One enters stack  
lineStack*  move(lineStack * stack,int place[4],int visit[100][4],int temp[4],int count_j) 
{
	//f1
	int flog;
	if(place[0]==place[1])
	{
		temp[0]=1-place[0];temp[1]=1-place[1];temp[2]=place[2];temp[3]=place[3];
		flog=1;
		if(temp[0]==0&&(temp[2]*temp[1]==1||temp[2]*temp[3]==1)||temp[0]==1&&(temp[2]+temp[1]==0||temp[2]+temp[3]==0))
		{	//printf("now:%d %d %d %d\n",temp[0],temp[1],temp[2],temp[3]);
			goto next2;// The plan is not feasible 
		} 
		for(int i=0;i<count_j;i++)
		{
			if(temp[0]==visit[i][0]&&temp[1]==visit[i][1]&&temp[2]==visit[i][2]&&temp[3]==visit[i][3])
				flog=0;// The node has already appeared 
		}
		if(flog)
		{
			stack=push(stack,temp);//new.push.
			return stack; 
		}
	}//f2 
	next2:;
	if(place[0]==place[2])
	{
		temp[0]=1-place[0];temp[1]=place[1];temp[2]=1-place[2];temp[3]=place[3];
		if(temp[0]==0&&(temp[2]*temp[1]==1||temp[2]*temp[3]==1)||temp[0]==1&&(temp[2]+temp[1]==0||temp[2]+temp[3]==0))
		{//	printf("now:%d %d %d %d\n",temp[0],temp[1],temp[2],temp[3]);
			goto next3;// The plan is not feasible  
			}
		flog=1;
		for(int i=0;i<count_j;i++)
		{
			if(temp[0]==visit[i][0]&&temp[1]==visit[i][1]&&temp[2]==visit[i][2]&&temp[3]==visit[i][3])
				flog=0;
		}
		if(flog)
		{
			stack=push(stack,temp);//new.push.
			return stack; 
		}
	}//f3
	next3:;
	if(place[0]==place[3])
	{
		temp[0]=1-place[0];temp[1]=place[1];temp[2]=place[2];temp[3]=1-place[3];
		if(temp[0]==0&&(temp[2]*temp[1]==1||temp[2]*temp[3]==1)||temp[0]==1&&(temp[2]+temp[1]==0||temp[2]+temp[3]==0))
		{//printf("now:%d %d %d %d\n",temp[0],temp[1],temp[2],temp[3]);
		goto next4;// The plan is not feasible  
		}
		flog=1;
		for(int i=0;i<count_j;i++)
		{
			if(temp[0]==visit[i][0]&&temp[1]==visit[i][1]&&temp[2]==visit[i][2]&&temp[3]==visit[i][3])
				flog=0; 
		}
		if(flog)
		{
			stack=push(stack,temp);//new.push.
			return stack; 
		}
	}//f4
	next4:;
		temp[0]=1-place[0];temp[1]=place[1];temp[2]=place[2];temp[3]=place[3];
		flog=1;
		if(temp[0]==0&&(temp[2]*temp[1]==1||temp[2]*temp[3]==1)||temp[0]==1&&(temp[2]+temp[1]==0||temp[2]+temp[3]==0))
		{//printf("now:%d %d %d %d\n",temp[0],temp[1],temp[2],temp[3]);
		goto next5;// The plan is not feasible 
		} 
		for(int i=0;i<count_j;i++)
		{
			if(temp[0]==visit[i][0]&&temp[1]==visit[i][1]&&temp[2]==visit[i][2]&&temp[3]==visit[i][3])
				flog=0;
		}
		if(flog)
		{
			stack=push(stack,temp);//new.push.
			return stack; 
		}
	next5:;
	temp[0]=temp[1]=temp[2]=temp[3]=-1; 
	return stack; //null
}

int main()
{
	lineStack * stack=NULL,*p;//stack 
	// Mark the position of the header node .
	int place[4]={0,0,0,0};// Starting state 
	int visit[100][4]={0};// Whether there has been any  
	visit[0][0]=0;visit[0][1]=0;visit[0][2]=0;visit[0][3]=0;// The starting element enters visit 
	stack=push(stack,place);
	int count_j=1;
	int temp[4]={0};
	while(1) // Into the loop 
	{	
		// Adjacency of the current item to push
		p=stack;// Record location , Determine whether push success  
		//printf("stack_top:%d %d %d %d \n",stack->place[0],stack->place[1],stack->place[2],stack->place[3]) ;
		stack=move(stack,place,visit,temp,count_j);
		//printf("top:%d %d %d %d\n",temp[0],temp[1],temp[2],temp[3]);	
		if(temp[0]==1&&temp[1]==1&&temp[2]==1&&temp[3]==1)
		{
			printf(" River crossing scheme ：\n");
			for(lineStack*temp=stack;temp->next!=NULL;temp=temp->next)
				printf("(%d %d %d %d) ",temp->place[0],temp->place[1],temp->place[2],temp->place[3]);
			printf("\n");
			// to update 
			place[0]=visit[count_j][0]=temp[0];place[1]=visit[count_j][1]=temp[1];
			place[2]=visit[count_j][2]=temp[2];place[3]=visit[count_j][3]=temp[3];
			count_j++;
			// Continue to cycle  
			stack=pop(stack);
			top(stack,place);
			continue;
		}
			
		if(p==stack)
		{// The end of the  
			if(stack->next==NULL)
			{	// All over 
				return 0; 
			}
			stack=pop(stack);
			top(stack,place);
			printf("place_after_pop:%d %d %d %d\n",place[0],place[1],place[2],place[3]);
		}
		else
		{// to update visit+place
			place[0]=visit[count_j][0]=temp[0];place[1]=visit[count_j][1]=temp[1];
			place[2]=visit[count_j][2]=temp[2];place[3]=visit[count_j][3]=temp[3];
			printf("place_after_push:%d %d %d %d\n",place[0],place[1],place[2],place[3]);
			count_j++;
		}
	}	
}

 

problem ：

· There is no way to find a second way , use visit Store the traversed nodes , To avoid repetition , But the involvement should not Including the road to success The node of ,（ There is only one node on the road to success （0,1,0,1） Is essential ）.

· The analysis is not exhaustive .

Not completely traversing this tree . I really won't change , Can't find C Only C++ Of ·, I owe this question .

PLUS：C Language stack stack summary

（ I found that Baidu Encyclopedia actually has a definition of this, and it is really and comprehensively written, even with the implementation of the algorithm ：https://baike.baidu.com/item/%E6%A0%88/12808149）

· The linear table A kind of . Open your mouth to access data “ To the top of the stack ”, The sealed end is “ At the bottom of the stack ” Take the data .

· First in, then out Structure . Including sequential chain stack .

· The stack has four functions :1 Push (push)2 Full sentence (isFull)3 Out of the stack (pop)4 Sentenced to empty (isEmpty).

· To avoid “ Overflow ” and “ underflow ”.

· Chain stack general Unwanted Create a header node , The head node will increase the complexity of the program , Just create a header pointer .

---

Reference resources ：

·https://blog.csdn.net/weixin_45705162/article/details/108296417

·https://blog.csdn.net/t11383/article/details/91129812

·https://blog.csdn.net/nail_candy/article/details/90741681

·http://data.biancheng.net/view/9.html

·https://www.cnblogs.com/vacation/p/5179457.html

·https://blog.csdn.net/jjzhoujun2010/article/details/6856164

·https://blog.csdn.net/m0_37961948/article/details/80245008

---

Maturity is a bright but not dazzling brilliance , A kind of mellow but not greasy sound , A kind of calm that no longer needs to observe others , A kind of atmosphere that finally stops appealing to the surrounding , A smile that ignores noise , A kind of extreme indifference , It's a kind of unspoken thick , A height that is not steep .——《 Sudongpo broke through 》