샅 샅 이 뒤 지 는 원리 와 장단 점

원 리 를 깊이 찾다.
깊이 검색 하 는 것 은 말 그대로 그 속 에 깊이 들 어가 결 과 를 직접 얻 는 검색 방법 이다.만약 한 사람 이 었 다 면, 그의 성격 은 틀림없이 소 처럼 고 집 스 러 웠 을 것 이다!그 는 한 시 에서 출발 하여 여행 을 가 는데, 단지 한 방향 으로 만 간다. 길이 끊 어 지지 않 는 한, 그 는 결코 방향 을 바 꾸 지 않 는 다.네 방향 이 모두 통 하지 않 거나 종점 을 만 나 지 않 는 한 그 는 결코 한 걸음 도 뒤로 물 러 서지 않 을 것 이다!그래서 그의 누 나 는 늘 그 를 비 웃 으 며 남쪽 벽 에 부 딪 히 지 않 고 뒤 돌아 보지 않 는 놈 이 라 고 말 했다.그 는 언니 의 비웃음 을 싫어 했 지만 친언니 와 갈등 을 일 으 키 고 싶 지 않 아 언니 에 게 자신의 여행 경험 을 이야기 해 주 고 언니 의 생각 을 개선 하기 로 했다.그 는 성 공 했 고 단지 한 번 만 말 했다.그 이후로 그의 누 나 는 다 시 는 그 를 비 웃 은 적 이 없 을 뿐만 아니 라, 그 를 보 는 눈빛 조차 칭찬 으로 가득 찼 다.그 는 자신의 길에 있 는 여러 가지 용감 함 이 누 나 를 정복 했다 고 생각 했 지만 그 는 몰 랐 다. 사실은 다른 이유 가 있 었 다.......................................................그러나 나 는 어디로 가면 목적지 에 도착 할 수 있 는 지 몰 랐 다. 그래서 나 는 한 곳 에 갈 때마다 현지 사람들 에 게 각 방향의 도로 상황 을 물 었 다.다른 사람 에 게 같은 방향 으로 반복 되 는 것 을 피하 기 위해 저 는 자신 에 게 1: 먼저 북쪽 으로 물 어보 고 길이 있 으 면 북쪽 으로 가 고 다음 곳 에 도착 할 때 이 규정 을 집행 합 니 다. 만약 에 북쪽 으로 통 하지 않 으 면 서쪽 으로 물 어 보 겠 습 니 다. 그 다음 에 남, 동 입 니 다. 만약 에 이 네 방향 이 모두 통 하지 않 거나 종점 에 도착 하면 저 는 지난 곳 으로 돌아 가 겠 습 니 다.가보 지 못 한 다른 방향 을 계속 탐색 하 다.나 는 또 그 를 도와 준 사람들 2 명 을 기억 해 야 한다 고 요구 했다. 그러나 나 에 게 도움 을 주 고 헛수고 를 하 게 한 사람들 은 3 명 을 잊 어야 한다.이런 규정 이 있 으 면 나 는 대담 하 게 앞으로 나 아 갈 수 있다. 목적지 에 도착 하지 못 할 까 봐 걱정 할 필요 도 없고 예전 의 길 을 반복 할 까 봐 걱정 할 필요 도 없다.하하 하..
장단 점 을 샅 샅 이 뒤지다

장점 1. 모든 해결 방안 을 찾 을 수 있다.

단점 1. 여러 번 옮 겨 다 니 며 가능 한 모든 경 로 를 검색 하고 표 지 를 한 후에 취소 해 야 한다.2. 깊이 가 큰 상황 에서 효율 이 높 지 않다

양식 을 샅 샅 이 뒤지다

void DFS() //N    DFS   
{
	if(   ) //       
	{
		…
		return;
	}
	for(inti=0;i<4;i++) //      
	{
    	DFS(N+1); //      
	}
}

원리
광 수 는 말 그대로 여러 가지 관리 와 인터넷 을 넓 히 는 검색 방법 입 니 다. 만약 에 광 수가 한 사람 이 라면 그녀 는 욕심 이 많 고 새로운 것 을 좋아 하고 낡은 것 을 싫어 할 것 입 니 다!그녀 는 한 시 에 여행 을 떠 났 다. 먼저 출발점 과 가 까 운 곳 을 모두 유람 한 다음 에 그녀 가 방금 유람 한 관광지 와 가 까 운 관광 지 를 모두 유람 했다. 이렇게 해서 모든 관광 지 를 한 번 유람 할 때 까지.광 수 는 맹목적 인 검색 법 에 속 하 는데 그 목적 은 그림 속 의 모든 노드 를 체계적으로 전개 하고 검사 하여 결 과 를 찾 는 것 이다.결과 의 가능 한 위 치 를 고려 하지 않 고 결 과 를 찾 을 때 까지 그림 전 체 를 철저히 검색 한 다 는 얘 기다.유사 한 나무의 층 별로 옮 겨 다 니 는 과정 은 다음 과 같다. 먼저 초기 Vi 를 방문 하고 이 를 방문 한 것 으로 표시 한 다음 에 Vi 에 방문 하지 않 은 모든 인접 점 Vi1, Vi2. Vit 를 방문 한 다음 에 모두 방문 한 것 으로 표시 한 다음 에 Vi1, Vi2... Vit 의 순서에 따라 모든 정점 에 방문 하지 않 은 인접 점 을 방문 하고 모두 방문 한 것 으로 표시 한다.이 유추 에 따 르 면 그림 의 모든 초기 Vi 와 경로 가 통 하 는 정점 이 방문 되 었 을 때 까지 입 니 다.
장단 점 을 널리 찾다.

장점 1. 최 단 또는 최소 문 제 를 해결 하 는 데 특히 효과 적 이 고 깊이 가 2. 각 노드 를 한 번 만 방문 하 며 결점 은 항상 최 단 경로 로 방문 되 기 때문에 두 번 째 경 로 는 첫 번 째 보다 짧 지 않 을 것 이다

.

단점 1. 메모리 소비량 이 많다 (대량의 배열 부 서 를 열 어 저장 상태 로 사용 해 야 한다)

양식 을 널리 찾다.

void BFS() 
{ 	… …//        
	while(!q.empty()) //       
	{	… …//      
		if(... …){… …}//       
		for(int i=0;i<4;i++)//    
		{ 
			k.x=p.x+dir[i][0];
	    	k.y=p.y+dir[i][1];
			//        
	     	if(judge())//      
			{
		    	… …//     
    		    vis[k.x][k.y]=1; //   	
	        	q.push(k); //  
			}
		}
	}
}

광 검색 인쇄 경로: 여러 개의 후계 노드 가 있 지만 전구 노드 는 하나 입 니 다.그래서 역방향 인쇄 경 로 를 찾 을 수 있 습 니 다. 즉, 종점 에서 출발 하여 출발점 으로 통 하 는 경 로 를 찾 을 수 있 습 니 다.
네 방향 을 두루 돌아다니다↩︎
표지↩︎
태그 취소↩︎