、A*算法的程序编写原理
  我在《初识A*算法》中说过,A*算法是最好优先算法的一种。只是有一些约束条件而已。我们先来看看最好优先算法是如何编写的吧。如图有如下的状态空间:(起始位置是A,目标位置是P,字母后的数字表示节点的估价值)。
  如图有如下的状态空间:(起始位置是A,目标位置是P,字[……]

继续阅读

题意:贪吃蛇问题。给定地图坐标,贪吃蛇的长度和位置,还有一些障碍物坐标,求蛇头移动到指定点的最小步数。
在这里我们将蛇的状态描述为如下三元组(x,y,state),其中 (x,y)是蛇头的坐标,state 记录的是身体的状态,由于身体最长为七段,每一段相对于前一段只有上下左右四种状态,仅需[……]

继续阅读

#include

int n;

int time[60];

int now[60];

int first[60];

int begin;

int last;

int min;

int temp;

bool isOK(int first, int inv) {
for (int i = first; i < 60; i += inv) {
if (time[i] – now[i] <= 0)
return false;
}
return true;
}

void mark(int first, int inv, int one_of_p_or_n) {
for (int i = first; i < 60; i += inv) {
now[i] += one_of_p_or_n;
}
}

void find(int x) {
if (x == 60) {

if (temp min) {

return;
}
if (time[x] – now[x] <= 0) {

int i;
for (i = x + 1; i 0) {
break;
}
}
find(i);
return;
}
for (int i = begin;i 0) {
if (isOK(x, x – i)) {

first[i]–;
mark(x, x – i, 1);
find(x);
mark(x, x – i, -1);
first[i]++;
}
}
}

if (x < last) { //找某条bus route上的第一班车,存在first里面
first[x]++;
now[x]++;
temp++;
find(x);
first[x]–;
now[x]–;
temp–;
}
}
int main() {
scanf("%d", &n);
if (!n) {
printf("0");
return 0;
}
scanf("%d", &temp);
time[temp]++;
begin = temp;
for (int i = 1; i < n; i++) {
scanf("%d", &temp);
time[temp]++;
}
last = temp;
min = n / 2;
temp = 0;
find(begin);
printf("%d\n", min);
return 0;
}
[……]

继续阅读

#include
#include
#include
using namespace std;
int fac[] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 };//…
int order(const char *s, int n)
{
int i, j, temp, num;
num = 0;
for (i = 0; i < n-1; i++)
{
temp = 0;
for (j = i + 1; j < n; j++) {
if (s[j] < s[i])
temp++;
}
num += fac[s[i] -1] * temp;
}
return num;
}
bool is_equal(const char *b1, const char *b2)
{ for(int i=0; i<9; i++)
if(b1[i] != b2[i])
return false;
return true;
}
struct node{
char board[9];
char space;//空格所在位置
};
const int TABLE_SIZE = 362880;
int hash(const char *cur)
{ return order(cur, 9);
}
char visited[TABLE_SIZE];
int parent[TABLE_SIZE];
char move[TABLE_SIZE];
int step[4][2] = {{-1, 0},{1, 0}, {0, -1}, {0, 1}};//u, d, l, r
void BFS(const node & start){
int x, y, k, a, b;
int u, v;
node cflag;
u = hash(start.board);
//start.vvvalue=u;
parent[u] = -1;
visited[u] = 1;
queue que;
que.push(start);
node tmp, cur;
while(!que.empty()){
cflag= que.front();
que.pop();
//get_node(u, cur);
// u=cflag.vvvalue;
u=hash(cflag.board );
k = cflag.space;
x = k / 3;
y = k % 3;
for(int i=0; i<4; ++i){
a = x + step[i][0];
b = y + step[i][1];
if(0<=a && a<=2 && 0<=b && b=0; –i){
if(path[i] == 0)
printf(“u”);
else if(path[i] == 1)
printf(“d”);
else if(path[i] == 2)
printf(“l”);
else
printf(“r”);
}
printf(“\n”);
}
int main(){
node start;
char c;
int k;
for(int i=0; i>c;
if(c == ‘x’){
start.board[i] = 9;
start.space = i;
}
else
start.board[i] = c – ‘0’;
}
for(k=0; k<TABLE_SIZE; ++k)
visited[k] = 0;
BFS(start);
if(visited[0] == 1)
print_path();
else
printf("unsolvable\n");
return 0;
}[……]

继续阅读