poj 1077 hdu 1043 8 수 코드 문제 DBFS (양 방향 광도 우선 검색) a * 알고리즘 강 척 전개
60436 단어 poj
int getcode(int perm[], int len)
{
int ret = 0;
for (int i = 0; i < len; ++i) {
int cnt = 0;
for (int j = i + 1; j < len; ++j) {
if (perm[i] > perm[j]) {
++cnt;
}
}
// fac
ret += fac[len - 1 - i] * cnt;
}
return ret;
}또 다른 작은 최적화 도 있다. 바로 우리 가 0 을 무시 한 후에 (빈 칸 이 9 로 표시 하면 9 를 무시 하 는 것) 이다. 한 걸음 한 걸음 이동 한 후에 전체 배열 의 역순 수의 패 리 티 는 변 하지 않 는 다. 역순 수 는 현재 숫자 다음 에 이 수의 개수 보다 적 으 면 모두 합 친 것 이다.둘째, 일반적인 해법 은 일반적인 bfs 를 사용 하 는 것 이다. 모든 상태 [26, 4, 1, 3, 7, 5, 8] 에 대해 이동 할 수 있 는 상 태 를 확대 하고 강 탁 을 사용 하여 이 상 태 를 표시 하 는 것 이다. 이 상 태 는 이전에 나타 난 적 이 있 는 지 없 는 지 를 표시 하고 하나의 부모 노드 배열 로 부모 노드 를 저장 하 며 현재 노드 에 대해 한 방향 배열 로 부모 노드 에서 현재 노드 로 이동 하 는 방향 을 저장 하고 해 를 찾 은 후에저 장 된 부모 노드 위치 에 따라 전체 경 로 를 얻 고 마지막 으로 출력 하면 됩 니 다.위 에서 언급 한 작은 최 적 화 를 더 할 수 있다.그러나 이 효율 은 높 지 않 아 poj 에서 통과 할 수 있 고 hdu 에서 시간 을 초과 할 수 있 습 니 다.코드 는 다음 과 같 습 니 다:
/*************************************************************************
> File Name: 1077.cpp
> Author: gwq
> Mail: [email protected]
> Created Time: 2015 08 12 10 35 19
************************************************************************/
#include
");
}
int bfs(void)
{
clr(vis, 0);
head = 1;
tail = 2;
memcpy(st[head], oritmp, sizeof(oritmp));
clr(fa, -1);
fa[1] = -1;
direct[1] = '*';
vis[getcode(st[head])] = 1;
while (head < tail) {
//print(st[head]);
if (memcmp(st[head], goal, sizeof(goal)) == 0) {
return head;
}
int idx = 0;
for (int i = 0; i < 9; ++i) {
if (st[head][i] == 0) {
idx = i;
}
}
int x = idx / 3;
int y = idx % 3;
//printf("%d %d %d
", idx, x, y);
//getchar();
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
int nidx = nx * 3 + ny;
if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {
memcpy(st[tail], st[head], sizeof(st[head]));
swap(st[tail][nidx], st[tail][idx]);
fa[tail] = head;
direct[tail] = mm[i];
if (try_insert(tail)) {
++tail;
}
}
}
++head;
}
return 0;
}
/*
* poj 1077 ac， hdu1043 tle
*/
int main(int argc, char *argv[])
{
fac[0] = 1;
for (int i = 1; i <= 15; ++i) {
fac[i] = fac[i - 1] * i;
}
while (fgets(strtmp, 100, stdin) != NULL) {
int len = strlen(strtmp);
orilen = 0;
for (int i = 0; i < len; ++i) {
if (isdigit(strtmp[i])) {
oritmp[orilen++] = strtmp[i] - '0';
} else if (strtmp[i] == 'x') {
oritmp[orilen++] = 0;
}
}
int p = bfs();
if (p == 0) {
printf("unsolvable
");
continue;
}
string ans;
//printf("%d
", p);
while (fa[p] != -1) {
ans.pb(direct[p]);
p = fa[p];
}
reverse(ans.begin(), ans.end());
cout << ans << endl;
}
return 0;
}알고리즘 을 최적화 하기 위해 모든 상태 에서 목표 상태 로 가 는 경 로 를 미리 처리 할 수 있 습 니 다. 마지막 으로 특정한 상태 에 대해 직접 경 로 를 출력 하면 됩 니 다.검색 할 때 대상 상태 에서 검색 을 시작 하고 경 로 를 기록 합 니 다.poj 에 데이터 가 적 기 때문에 이런 방법 으로 시간 을 초과 할 수 있 습 니 다.코드 는 다음 과 같 습 니 다:
/*************************************************************************
> File Name: 1077pre.cpp
> Author: gwq
> Mail: [email protected]
> Created Time: 2015 08 12 19 07 45
************************************************************************/
#include
");
} else {
printf("unsolvable
");
}
}
return 0;
}3. a * 알고리즘 은 먼저 A 알고리즘 을 소개 합 니 다. BFS 알고리즘 에서 모든 상태 n 에 대해 평가 함수 f (n) = g (n) + h (n) 를 설정 하고 Open 표 에서 노드 를 선택 하여 확장 할 때마다 f 값 이 가장 작은 노드 를 선택 하면 이 검색 알고리즘 을 계발 식 검색 알고리즘 이 라 고도 부 르 고 A 알고리즘 이 라 고도 부 릅 니 다.평가 함수 f (n) 에서 g (n) 는 시작 상태 에서 현재 상태 n 까지 의 대가 이 고 h (n) 는 현재 상태 n 에서 목표 상태 까지 의 평가 대가 이다.
A 알고리즘 에서 평가 함 수 를 잘못 선택 하면 해 를 찾 지 못 하거나 찾 은 해 가 가장 좋 은 것 이 아 닙 니 다.따라서 평가 함수 에 대해 제한 을 두 어 알고리즘 이 최 적 화 를 찾 도록 해 야 한다.A * 알고리즘 은 평가 함수 에 대해 특정한 제한 을 하고 가장 좋 은 A 알고리즘 을 찾 도록 하 는 것 입 니 다.
f * (n) = g * (n) + h * (n), 그 중에서 f * (n) 는 초기 노드 S0 에서 출발 하여 노드 n 을 거 쳐 목표 노드 에 도착 하 는 최소 걸음 수 (진실 치) 이 고 g * (n) 는 S0 에서 출발 하여 n 에 도착 하 는 최소 걸음 수 (진실 치) 이 며 h * (n) 는 n 에서 출발 하여 목표 노드 에 도착 하 는 최소 걸음 수 (진실 치) 이 며 평가 함수 f (n) 는 f * (n) 의 평가 값 이다.
f (n) = g (n) + h (n), 그리고 만족: g (n) 는 S0 에서 n 까지 의 실제 걸음 수 (반드시 가장 좋 은 것 은 아니다) 이기 때문에 g (n) > 0 및 g (n) > = g * (n), h (n) 는 n 에서 목표 까지 의 평가 걸음 수 로 항상 너무 낙관적 인 것 으로 추정 된다. 즉, h (n) < = h * (n) 와 h (n) 가 서로 어 울 리 면 A 알고리즘 은 A * 알고리즘 으로 바뀐다.
h (n) 상용 이란 임의의 s1 에서 s2 까지 h (s1) < = h (s2) + c (s1, s2) 를 만족 시 키 면 c (s1, s2) 가 s1 에서 s2 로 이동 하 는 걸음 수 를 h 상용 이 라 고 한다.h. 호환성 은 한 걸음 한 걸음 앞으로 나 아가 면서 f 가 점점 증가 하 는 것 을 확보 할 수 있 습 니 다. 그러면 A * 는 더욱 효율 적 으로 최 적 화 를 찾 을 수 있 습 니 다.일반적으로 h (n) < = h * (n) 를 만족 시 키 는 전제 에서 h (n) 의 값 은 클 수록 좋다.
일반적으로 현재 노드 에서 목표 노드 까지 의 직선 거리 나 맨 해 튼 거 리 를 평가 함수 h 로 하지만 구체 적 인 문 제 를 구체 적 으로 분석 해 야 한다.
다음은 위조 코드 입 니 다.
OPEN = priority queue containing START
CLOSED = empty set
while lowest rank in OPEN is not the GOAL:
current = remove lowest rank item from OPEN
add current to CLOSED
for neighbors of current:
cost = g(current) + movementcost(current, neighbor)
if neighbor in OPEN and cost less than g(neighbor):
remove neighbor from OPEN, because new path is better
if neighbor in CLOSED and cost less than g(neighbor): **
remove neighbor from CLOSED
if neighbor not in OPEN and neighbor not in CLOSED:
set g(neighbor) to cost
add neighbor to OPEN
set priority queue rank to g(neighbor) + h(neighbor)
set neighbor.s parent to current
reconstruct reverse path from goal to start
by following parent pointers그러나 실제로 우리 가 평소에 쓰 는 A * 는 이 모양 이 아니 라 일반적인 bfs 와 유사 합 니 다. fifo 대기 열 을 우선 대기 열 로 바 꾸 고 다른 것 은 유사 합 니 다.
A * 알고리즘 을 사용 한 코드 는 다음 과 같 습 니 다. 평가 함 수 는 맨 해 튼 거 리 를 사용 합 니 다.
/*************************************************************************
> File Name: 1043_astar.cpp
> Author: gwq
> Mail: [email protected]
> Created Time: 2015 08 13 16 44 33
************************************************************************/
#include
");
}
printf("%d ", perm[i]);
}
}
bool check(void)
{
if (st == goalcode) {
return true;
} else {
return false;
}
}
};
int geth(int s[])
{
int h = 0;
for (int i = 0; i < 9; ++i) {
if (s[i] == 0) {
continue;
}
int x = (s[i] - 1) / 3;
int y = (s[i] - 1) % 3;
int nx = i / 3;
int ny = i % 3;
h += abs(x - nx) + abs(y - ny);
}
return h;
}
bool operator return u.h != v.h ? u.h > v.h : u.g > v.g;
}
int check(int s[])
{
int num = 0;
for (int i = 0; i < 9; ++i) {
if (s[i] != 0) {
for (int j = i + 1; j < 9; ++j) {
if (s[i] > s[j] && s[j] != 0) {
++num;
}
}
}
}
return num % 2;
}
void bfs(void)
{
priority_queue q;
clr(vis, 0);
clr(pre, -1);
clr(direct, '*');
int code = getcode(ori);
Node u = Node(ori, geth(ori), 0, oripos / 3, oripos % 3, code, oripos);
vis[code] = 1;
q.push(u);
while (!q.empty()) {
u = q.top();
q.pop();
//u.output();
//getchar();
if (u.check()) {
string path;
int p = u.st;
while (pre[p] != -1) {
path += direct[p];
p = pre[p];
}
reverse(path.begin(), path.end());
printf("%s
", path.c_str());
return;
}
for (int i = 0; i < 4; ++i) {
int nx = u.x + dx[i];
int ny = u.y + dy[i];
int npos = nx * 3 + ny;
Node v;
if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {
memcpy(v.perm, u.perm, sizeof(u.perm));
swap(v.perm[npos], v.perm[u.pos]);
int nh = geth(v.perm);
int ng = u.g + 1;
int ncode = getcode(v.perm);
v.h = nh;
v.g = ng;
v.f = v.h + v.g;
v.x = nx;
v.y = ny;
v.pos = npos;
v.st = ncode;
if (!vis[ncode] && !check(v.perm)) {
pre[ncode] = u.st;
direct[ncode] = mm[i];
q.push(v);
vis[ncode] = 1;
}
}
}
}
cout << "unsolvable" << endl;
}
int main(int argc, char *argv[])
{
fac[0] = 1;
for (int i = 1; i < 20; ++i) {
fac[i] = fac[i - 1] * i;
}
goalcode = getcode(goal);
while (fgets(str, 100, stdin) != NULL) {
len = strlen(str);
orilen = 0;
for (int i = 0; i < len; ++i) {
if (isdigit(str[i])) {
ori[orilen++] = str[i] - '0';
} else if (str[i] == 'x') {
oripos = orilen;
ori[orilen++] = 0;
}
}
if (check(ori)) {
printf("unsolvable
");
continue;
}
bfs();
}
return 0;
} 4. DBFS 양 방향 광도 우선 검색 알고리즘 (pdf 참조) DBFS 알고리즘 은 BFS 알고리즘 에 대한 확장 입 니 다.BFS 알고리즘 은 대상 노드 를 만 날 때 까지 넓 은 우선 순위 로 계속 확장 합 니 다.DBFS 알고리즘 은 시작 노드 와 대상 노드 두 방향 에서 넓 은 우선 순위 로 동시에 확장 되 었 습 니 다. 한 대기 열 에 다른 대기 열 에 확 장 된 노드 가 나타 날 때 까지 두 확장 방향 에 교점 이 있 는 것 과 같 습 니 다. 그러면 하나의 경 로 를 찾 았 다 고 볼 수 있 습 니 다.
DBFS 알고리즘 은 BFS 알고리즘 에 비해 양 방향 으로 확장 하 는 방법 을 사 용 했 기 때문에 검색 트 리 의 폭 이 현저히 줄 어 들 고 시간 과 공간 복잡 도가 뚜렷하게 향상 되 었 습 니 다.DBFS 는 노드 수가 적은 쪽 을 선택 할 때마다 확장 을 합 니 다. 기계 적 으로 확장 하 는 것 이 아 닙 니 다.
DBFS 프레임 워 크:
void dbfs()
{
1. q0 , q1;
2. , :
1) q0 q1 , q0;
2) q1
3. q0 , q0 ;
4. q1 , q1 ；
}이 문제 의 코드 는 다음 과 같다.
/*************************************************************************
> File Name: 1077dbfs.cpp
> Author: gwq
> Mail: [email protected]
> Created Time: 2015 08 12 17 09 43
************************************************************************/
#include
%d..%d", code, no);
for (int i = 0; i < 9; ++i) {
if (i % 3 == 0) {
//printf("
");
}
//printf("%d ", st[no][head[no]][i]);
}
if (vis[ono][code]) {
//printf("done
");
string ans;
int pos = head[no];
if (no) {
for (int i = 0; i < tail[0]; ++i) {
int tmp = getcode(st[0][i]);
if (tmp == code) {
pos = i;
break;
}
}
} else {
pos = head[no];
}
int p = pos;
//printf("
%d.....
", pos);
while (fa[0][p] != -1) {
ans += direct[0][p];
p = fa[0][p];
}
reverse(ans.begin(), ans.end());
//cout << ans << endl;
if (no == 0) {
for (int i = 0; i < tail[1]; ++i) {
int tmp = getcode(st[1][i]);
if (tmp == code) {
pos = i;
break;
}
}
} else {
pos = head[no];
}
p = pos;
//printf("%d.....%d
", pos, head[no]);
while (fa[1][p] != -1) {
ans += direct[1][p];
p = fa[1][p];
}
printf("%s
", ans.c_str());
return;
}
int idx = 0;
for (int i = 0; i < 9; ++i) {
if (st[no][head[no]][i] == 0) {
idx = i;
break;
}
}
int x = idx / 3;
int y = idx % 3;
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
int nidx = nx * 3 + ny;
if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {
memcpy(st[no][tail[no]], st[no][head[no]], sizeof(st[no][head[no]]));
swap(st[no][tail[no]][idx], st[no][tail[no]][nidx]);
int ncode = getcode(st[no][tail[no]]);
if (!vis[no][ncode]) {
vis[no][ncode] = 1;
fa[no][tail[no]] = head[no];
direct[no][tail[no]] = mm[no ? (i + 2) % 4 : i];
++tail[no];
}
}
}
++head[no];
}
printf("unsolvable
");
}
int main(int argc, char *argv[])
{
fac[0] = 1;
for (int i = 1; i < 20; ++i) {
fac[i] = fac[i - 1] * i;
}
while (fgets(strtmp, 20, stdin) != NULL) {
//printf("fgets
");
int len = strlen(strtmp);
orilen = 0;
for (int i = 0; i < len; ++i) {
if (isdigit(strtmp[i])) {
oritmp[orilen++] = strtmp[i] - '0';
} else if (strtmp[i] == 'x') {
oritmp[orilen++] = 0;
}
}
for (int i = 0; i < 9; ++i) {
if (i % 3 == 0) {
//printf("
");
}
//printf("%d ", oritmp[i]);
}
//printf("
");
//printf("%d
", getcode(oritmp));
if (check(oritmp)) {
printf("unsolvable
");
continue;
}
dbfs();
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POJ3071: Football(확률 DP)Consider a single-elimination football tournament involving 2n teams, denoted 1, 2, …, 2n. After n rounds, only one team...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
