Eight -- A * 알고리즘
오늘 또 팔 수 코드 를 꺼 내 서 한 번 썼 습 니 다. 지난번 에 이 문 제 를 여름 방학 합숙 훈련 때 썼 던 기억 이 납 니 다. 그때 POJ 에서 지 낼 수 있 었 는데 HDU 에서 제출 하면 TLE 입 니 다. POJ 에서 만 설명 할 수 있 습 니 다. 이 문 제 는 데이터 가 너무 물 러 서 ~ ~ 이번에 쓴 것 도 주로 A * 알고리즘 을 배우 기 위해 서 였 죠?하지만 내 가 쓴 A * 는 HDU 에 1000 + ms, 멘 붕.계발 함수 가 잘 처리 되 지 않 았 나 봐 요.
알고리즘: A *, BFS, IDA *
BFS 코드:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define MAX 363000
using namespace std;
char ch[30];
bool vis[MAX];
int d_r[4] = {1,-1,0,0} ; //
int d_c[4] = {0,0,1,-1} ;
bool success ;
char path[4] = {'d','u','r','l'} ; //
int fac[11] = {1,1,2,6,24,120,720,5040,40320,362880} ;
struct Node{
int num[11]; //
int ka; // KT
}start,goal; //
queue<Node> q ;
struct Node2{
int pre; // (KT )
int way ; //
}state[MAX];
// KT
inline int KT(int n,int num[])
{
int i,j,t,sum=0 ;
for(i=1;i<=n;i++)
{
t = 0 ;
for(j=i+1;j<=n;j++)
if(num[j] < num[i]) t++;
sum += t *fac[n-i] ;
}
return sum + 1 ;
}
inline int recode(char s)
{
if(s == 'x') return 0;
else return s - '0' ;
}
void find(int way,Node now)
{
int num[5][5],i,j,t,pos_r,pos_c;
Node a ;
for(i=1;i<=3;i++)
{
for(j=1;j<=3;j++)
{
num[i][j] = now.num[(i-1)*3+j];
if(num[i][j] == 9)
{
pos_r = i ; pos_c = j ;
}
}
}
int new_r = pos_r + d_r[way] ;
int new_c = pos_c + d_c[way] ;
if(new_r>=1 && new_r<=3 && new_c>=1 && new_c<=3)
{
int temp = num[pos_r][pos_c] ;
num[pos_r][pos_c] = num[new_r][new_c] ;
num[new_r][new_c] = temp ;
t= 1 ;
for(i=1;i<=3;i++)
for(j=1;j<=3;j++)
a.num[t++] = num[i][j] ;
a.ka = KT(9,a.num);
if(!vis[a.ka])
{
q.push(a);
vis[a.ka] = true;
state[a.ka].pre = now.ka ;
state[a.ka].way = way ;
if(a.ka == goal.ka)
{
success = true ;
}
}
}
}
void PRINT(int ka) //
{
int pre_ka = state[ka].pre ;
if(pre_ka == -1) return ;
PRINT(pre_ka);
printf("%c",path[state[ka].way]);
}
int BFS(Node start)
{
int i,j;
Node now ;
while(!q.empty()) q.pop();
memset(vis,false ,sizeof(vis));
vis[start.ka] = true;
q.push(start);
success = false ;
state[start.ka].pre = -1 ;
state[start.ka].way = 0 ;
while(!q.empty())
{
now = q.front(); q.pop();
for(i=0;i<4;i++)
{
find(i,now);
if(success)
break ;
}
if(success)
break;
}
if(success)
PRINT(goal.ka);
else
printf("unsolvable
");
}
int main()
{
int i,j,num,t,pos_x;
//freopen("1in.txt","r",stdin);
//freopen("1out.txt","w",stdout);
for(i=1;i<=9;i++)
{
goal.num[i] = i ;
}
goal.ka = 1 ;
while(gets(ch)!=NULL)
{
t = 1 ;
for(i=0;ch[i]!=0;i++)
{
if(ch[i] == ' ') continue ;
start.num[t] = recode(ch[i]) ;
if(start.num[t] == 0)
{
start.num[t] = 9 ;
}
t++ ;
}
start.ka = KT(9,start.num);
BFS(start); //
}
return 0;
}
A * 알고리즘: 이 문 제 는 엄 밀 히 말 하면 A * 를 사용 한 것 이 아니 라 is 를 사 용 했 습 니 다.ok () 함수 가 지나 간...#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cstdlib>
#include<cmath>
#define MAX 363000
using namespace std;
int d_r[4] = {0,0,-1,1} ; //
int d_c[4] = {1,-1,0,0} ;
char path[4] = {'r','l','u','d'} ; //
int fac[11] = {1,1,2,6,24,120,720,5040,40320,362880} ;
int d_x[10] = {0,1,1,1,2,2,2,3,3,3} ;
int d_y[10] = {0,1,2,3,1,2,3,1,2,3} ;
int vis[MAX] ;
char ans[MAX] ;
struct Node{
int num[11]; //
int ka,space; // KT
int h,g ;
friend bool operator < (const Node & x,const Node & y)
{
return (x.h+x.g) > (y.h+y.g) ;
}
}start,a,now; //
priority_queue<Node> q ;
struct Node2{
int pre; // (KT )
int way ; //
}state[MAX];
// KT
inline int KT(int n,int num[])
{
int i,j,t,sum=0 ;
for(i=1;i<=n;i++)
{
t = 0 ;
for(j=i+1;j<=n;j++)
if(num[j] < num[i]) t++;
sum += t * fac[n-i] ;
}
return sum ;
}
inline int cal_h(int num[])
{
int h = 0;
for(int i=1;i<=3;i++)
{
for(int j=1;j<=3;j++)
{
int Num = num[(i-1)*3+j] ;
h += abs(i - d_x[Num])+abs(j-d_y[Num]) ;
}
}
return h;
}
inline void swap(int &a, int &b)
{
int temp = a; a = b ; b = temp ;
}
void PRINT(int ka) //
{
int pre_ka = ka ,t=0;
while(state[pre_ka].way != -1)
{
t++;
ans[t] = path[state[pre_ka].way] ;
pre_ka = state[pre_ka].pre ;
}
for(int j=t;j>=1;j--)
{
printf("%c",ans[j]);
}
printf("
");
}
void A_star(Node start)
{
int i,j ,temp,pos_r,pos_c,new_r,new_c;
start.ka = KT(9,start.num) ;
start.g = 0 ;
start.h = cal_h(start.num) ;
while(!q.empty()) q.pop();
memset(vis,0,sizeof(vis)); //0: ,1: ;
vis[start.ka] = 1 ;
q.push(start);
state[start.ka].pre = -1 ;
state[start.ka].way = -1 ;
while(!q.empty())
{
now = q.top(); q.pop();
if(now.ka == 0)
{
PRINT(0) ;
return ;
}
pos_r = (now.space-1)/3 + 1 ;
pos_c = (now.space-1)%3 + 1 ;
for(i=0;i<4;i++)
{
temp = now.space ;
new_r = pos_r + d_r[i] ;
new_c = pos_c + d_c[i] ;
a = now ;
if(new_r<1 || new_r>3 || new_c<1 || new_c>3) continue ;
a.space = (new_r-1)*3 + new_c ;
swap(a.num[a.space],a.num[temp]) ;
a.ka = KT(9,a.num);
if(vis[a.ka]==0)
{
a.g = now.g + 1 ;
a.h = cal_h(a.num) ;
q.push(a);
vis[a.ka] = 1;
state[a.ka].pre = now.ka ;
state[a.ka].way = i ;
}
}
}
printf("unsolvable
");
}
bool is_ok(int num[])
{
int sum = 0 ;
int num1[11] ,t=1;
for(int i=1;i<=9;i++)
{
if(num[i]!=9)
{
num1[t++] = num[i] ;
}
}
for(int i=1;i<=8;i++)
{
for(int j=1;j<i;j++)
{
if(num1[j]>num1[i]) sum++;
}
}
if(sum%2==0) return true;
else return false ;
}
int main()
{
int i,j,num,t,pos_x;
char ch[5];
while(cin>>ch[1]>>ch[2]>>ch[3])
{
for(i=1;i<=3;i++)
{
if(ch[i] == 'x')
{
start.num[i] = 9 ;
start.space = i;
}
else
start.num[i] = ch[i] - '0' ;
}
for(i=4;i<=9;i++)
{
cin>>ch[0] ;
if(ch[0] == 'x')
{
start.num[i] = 9 ;
start.space = i ;
}
else
start.num[i] = ch[0] - '0' ;
}
if(is_ok(start.num))
A_star(start); //
else
printf("unsolvable
");
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.