검색 (8 번 문제 상세 설명: BFS, A *, IDA *) - Eight (POJ 1077)
71400 단어 ACM 알고리즘(문제 풀이):수색 하 다.
int fac[] = { 1,1,2,6,24,120,720,5040,40320 };// 。
int Cantor( int s[])// 。
{
int sum = 0;
for(int i = 0;i<9;i++)
{
int cnt = 0;
for(int j=i+1;j<9;j++)
{
if( s[i] > s[j] ) cnt++;
}
sum+=(cnt*fac[9-i-1]);
}
return sum+1;
}
배열 중의 요소 가 A, B, C, D 라면 a4 = 3 은 나머지 요소 가 4 라 는 것 을 표시 할 때 3 위 (모두 0 위 부터 계산), 즉 D 를 얻 을 수 있 습 니 다.a3 = 1 은 남 은 요소 가 3 일 때 첫 번 째, 즉 B 를 나타 낸다.a2 = 0 은 남 은 요소 가 2 일 때 0 위, 즉 A 를 나타 내 고 마지막 a1 은 C 이다.#include else
printf("unsolvable
");
}
return 0;
} #include
')
{
if(ch<='9'&&ch>='0')
sou[i++] = ch - '0';
else if(ch=='x')
sou[i++] =0;
}
convert(sou,source);
start = clock();
i = search(source);
queue<int>q;
q.push(i);
i = search(target);
st[i].visit = 1;
st[i].step = 1;
q.push(i);
if(!(source.sta^target.sta)&&!(source.pos^target.pos))
{
printf("0
");
while(!q.empty())q.pop();
continue;
}
int index;
int count = 0;
bool isSolve = false;
while(!q.empty()&&!isSolve)
{
count ++;
index = q.front();
for(int j = 0; j < 4; j ++)
{
if(d[st[index].pos][j])
{
int flag = search(exchange(st[index],d[st[index].pos][j]));
if(!st[flag].step)
{
st[flag].step = st[index].step + 1;
st[flag].visit = st[index].visit;
q.push(flag);
}
else
{
if(st[flag].visit^st[index].visit)
{
isSolve = true;
printf("%d
",st[index].step+st[flag].step);
}
}
}
}
q.pop();
}
while(!q.empty())q.pop();
end = clock();
printf("Time:%dms
state number:%d
",end-start,count);
}
system("pause");
return 0;
}
#include
')
{
if(ch<='9'&&ch>='0')
sou[i++] = ch - '0';
else if(ch=='x')
sou[i++] =0;
}
convert(sou,source);
start = clock();
i = search(source);
st[i].f = h(st[i]);
priority_queue<int,vector<int>,cmp>q;
q.push(i);
int index;
int count = 0;
while(!q.empty())
{
count++;
index = q.top();
q.pop(); //!!!!
if(!(st[index].sta^target.sta)&&st[index].pos == target.pos)
{
printf("%d
",st[index].step);
break;
}
for(int j = 0; j < 4; j ++)
{
if(d[st[index].pos][j])
{
int flag = search(exchange(st[index],d[st[index].pos][j]));
if(!st[flag].step||st[flag].step > st[index].step + 1)
{
st[flag].step = st[index].step + 1;
st[flag].f = st[flag].step + h(st[flag]);
q.push(flag);
}
}
}
}
while(!q.empty())q.pop();
end = clock();
printf("Time:%dms
state number:%d
",end-start,count);
}
system("pause");
return 0;
}manhattan 거리 함수 기반 A * 검색:
#include
')
{
if(ch<='9'&&ch>='0')
sou[i++] = ch - '0';
else if(ch=='x')
sou[i++] =0;
}
convert(sou,source);
start = clock();
i = search(source);
st[i].f = h(st[i]);
priority_queue<int,vector<int>,cmp>q;
q.push(i);
int index;
int count = 0;
while(!q.empty())
{
count++;
index = q.top();
q.pop(); //!!!!
if(!(st[index].sta^target.sta)&&st[index].pos == target.pos)
{
printf("%d
",st[index].step);
break;
}
for(int j = 0; j < 4; j ++)
{
if(d[st[index].pos][j])
{
int flag = search(exchange(st[index],d[st[index].pos][j]));
if(!st[flag].step||st[flag].step > st[index].step + 1)
{
st[flag].step = st[index].step + 1;
st[flag].f = st[flag].step + h(st[flag]);
q.push(flag);
}
}
}
}
while(!q.empty())q.pop();
end = clock();
printf("Time:%dms
state number:%d
",end-start,count);
}
system("pause");
return 0;
}#include
",depth);
return true;
}
if(depth >= pathLimit) return false;
if( depth + diff > pathLimit ) return false;
for(int j = 0; j < 4; j ++)
{
if(d[a.pos][j] == prepos+1) continue;
if(d[a.pos][j])
{
state next = exchange(a,d[a.pos][j]);
if(IDAStar(next,depth+1, h(next),a.pos))
return true;
}
}
return false;
}
int main()
{
freopen("in.txt","r",stdin);
clock_t start,end;
int diff = 0;
for(int j=0;j<8;j++)temp[j] = j+1;
temp[8]=0;
convert(temp,target);
while(1)
{
int i = 0;
char ch;
while((ch=getchar())!='
')
{
if(ch<='9'&&ch>='0')
sou[i++] = ch - '0';
else if(ch=='x')
sou[i++] =0;
}
start = clock();
cnt = 0;
convert(sou,source);
pathLimit = h(source);
diff = pathLimit;
while(!IDAStar(source,0,diff,-1))pathLimit++;
end = clock();
printf("Time:%dms
state number:%d
",end-start,cnt);
}
system("pause");
return 0;
}manhattan 거리 함수 기반 검색:
#include
",depth);
return true;
}
if(depth > pathLimit) return false;
if( depth + diff > pathLimit ) return false;
for(int j = 0; j < 4; j ++)
{
if(d[a.pos][j] == prepos+1) continue;
if(d[a.pos][j])
{
state next = exchange(a,d[a.pos][j]);
if(IDAStar(next,depth+1, h(next),a.pos))
return true;
}
}
return false;
}
int main()
{
freopen("in.txt","r",stdin);
clock_t start,end;
int diff = 0;
for(int j=0;j<8;j++)temp[j] = j+1;
temp[8]=0;
convert(temp,target);
while(1)
{
int i = 0;
char ch;
while((ch=getchar())!='
')
{
if(ch<='9'&&ch>='0')
sou[i++] = ch - '0';
else if(ch=='x')
sou[i++] =0;
}
start = clock();
convert(sou,source);
pathLimit = h(source);
diff = pathLimit;
while(!IDAStar(source,0,diff,-1))pathLimit++;
end = clock();
printf("Time:%dms
depthlimit:%d
",end-start,pathLimit);
}
system("pause");
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
폭력 (납 계) - ACdream 1068제목 링크:http://acdream.info/problem?pid=1068 제목: 제목 보기 분석: 폭력, (MD, 직접 검색 하면 돼) AC 코드:...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
