寻一个解智力游戏的算法

kingstarer 2009-05-03 10:47:29
游戏截图见：
http://hiphotos.baidu.com/%BB%CA%BC%D2%BE%C8%D0%C71985/mpic/item/ff0062f8bf6fe12cd9f9fde8.jpg

规则介绍

游戏开始时会给出16个顺序混乱的棋子（分成4行4列），棋子上面有序号
要求把棋子按顺序排列

移动棋子规则：
一次只能把整行棋子往左或右移动一格
或者把整列棋子往上或下移动一枨

举例：
棋子初始状态
1 2 3 4
5 6 7 8
9 10 11 12
0 13 14 15

要求转换成
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0

-----------解题过程----------

将初始状态第四行往左移动一格变成

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0

即是结果状态
...全文
979 43 打赏 收藏 转发到动态 举报
写回复
用AI写文章
43 条回复
切换为时间正序
请发表友善的回复…
发表回复
kingstarer 2009-05-26
  • 打赏
  • 举报
 回复
LS贴的好像是16数码的代码，跟我这题还是有点区别的

不过我试了一下　速度还是蛮快的　也许能够借鉴里面的算法 谢谢了
baihacker 2009-05-26
  • 打赏
  • 举报
 回复 


15数码的IDA*算法

来源是CSDN的download中心

请自己去搜索IDA*算法.



"

现在机器解16码问题基本上采用松弛子问题启发式+结果数据库来做

单纯的Hamilton距离作启发式搜索深度大的话很难出解 

"

"

有很多无解的情况，可以用置换群理论中置换的奇偶性来快速判断有无解！

"



// IDA*（迭代式深度搜索）

// 把SIZE改成4就可以变成15数码问题

#include<stdio.h>

#include<string.h>

#include<math.h>

#include<conio.h>



#define SIZE 4

typedef char board[SIZE][SIZE];

board target = {1 ,2 ,3, 4,

				12, 13, 14, 5 ,

				11, 0, 15, 6 ,

				10, 9, 8, 7};		// 目标状态，改成15数码的话要同时改掉

board start;

long add[4][2]={-1,0,0,1,1,0,0,-1};



/*************************估价函数*****************************/

long targetplace[SIZE*SIZE][2];			// 这个估价函数是用来剪枝的

long CAL_H(board & node) {

	long i,j;

	long re = 0;

	for (i=0; i<SIZE; i++) for (j=0; j<SIZE; j++) if (node[i][j]) {

		re += abs(i - targetplace[node[i][j]][0])

			+ abs(j - targetplace[node[i][j]][1]);

	}

	return re;

}

/***************************************************************/



bool can_solve() {					// 搜索前判断是否可解

	long i,j,k1,k2;

	for (i=0; i<SIZE; i++) for (j=0; j<SIZE; j++) {

		if (start[i][j]==0) {

			start[i][j] = SIZE*SIZE;

			k1 = (SIZE-1-i) + (SIZE-1-j);

		}

		if(target[i][j]==0){

			target[i][j] = SIZE*SIZE;

			k2 = (SIZE-1-i) + (SIZE-1-j);

		}

	}

	for (i=0; i<SIZE*SIZE; i++) for (j=i+1; j<SIZE*SIZE; j++) {

		if (start[i/SIZE][i%SIZE] > start[j/SIZE][j%SIZE]) k1++;		

		if (target[i/SIZE][i%SIZE] > target[j/SIZE][j%SIZE]) k2++;		

	}

	for (i=0; i<SIZE; i++) for (j=0; j<SIZE; j++) {

		if (start[i][j]==SIZE*SIZE) start[i][j]=0;		

		if (target[i][j]==SIZE*SIZE) target[i][j]=0;		

	}

	return (k1%2)==(k2%2);

}



void out_board(board state,long step) {

	long i,j;

	printf("STEP %ld:\n", step);

	for(i=0;i<SIZE;i++){

		for(j=0;j<SIZE;j++){

			printf("%ld ", state[i][j]);

		}

		printf("\n");

	}

	printf("\n");

}



void output(long dep, char path[]) {			// 输出答案

	long i,j,x1,y1,x0,y0;

	board state;

	memcpy(state, start, sizeof(state));

	out_board(state,0);

	for(i=0;i<SIZE;i++)for(j=0;j<SIZE;j++)if(state[i][j]==0)x0=i,y0=j;

	for (i=0; i<dep; i++) {

		x1=x0+add[path[i]][0];

		y1=y0+add[path[i]][1];

		state[x0][y0] = state[x1][y1];

		state[x1][y1] = 0;

		x0 = x1, y0 = y1;

		out_board(state,i+1);

	}

	printf("The minimum number of steps is %ld.\n", dep);

}



/***********************************************************************************/



long ans;

char path[100000];



bool ida(board & node, long x0, long y0, long dep, long d, long h) {	

	long i,j,k,x1,y1,h1;

	if (memcmp(node, target, sizeof(target))==0) {

		output(dep, path);

		return 1;

	}

	if (dep==ans) return 0;

	

	board node1;

	for (i=0; i<4; i++) {

		if (((i%2)==(d%2)) && i!=d) continue;

		x1 = x0 + add[i][0];

		y1 = y0 + add[i][1];

		if (x1<0||y1<0||x1==SIZE||y1==SIZE) continue;

		memcpy(node1, node, sizeof(node1));

		node1[x1][y1] = 0;

		node1[x0][y0] = node[x1][y1];

		

		if (i==3 && y1<targetplace[node[x1][y1]][1]) h1=h-1;

		else if (i==1 && y1>targetplace[node[x1][y1]][1]) h1=h-1;

		else if (i==0 && x1<targetplace[node[x1][y1]][0]) h1=h-1;

		else if (i==2 && x1>targetplace[node[x1][y1]][0]) h1=h-1;

		else h1=h+1;

		if (h1+dep+1>ans) continue;			// 根据估价值(h1+dep)

									// 和假定的解的步数(ans)来剪枝

		path[dep] = i;

		if (ida(node1,x1,y1,dep+1,i,h1)) return 1;

	}

	return 0;

}



int main() {

	long i,j,k,x0,y0;

	long cs;

	//scanf("%ld", &cs);

	cs = 1;

	printf("input=\n");

	while (cs--) {

		for (i=0;i<SIZE;i++)for(j=0;j<SIZE;j++) {

			scanf("%ld",&k);

			start[i][j] = k;

			if (k==0) { x0=i; y0=j; }

		}



		for (k=1,i=0; i<SIZE; i++) for (j=0; j<SIZE; j++) {

			targetplace[target[i][j]][0] = i;

			targetplace[target[i][j]][1] = j;

		}	

		if (!can_solve()) { printf("This puzzle is not solvable.\n"); continue; }



		i = -1;

		j = CAL_H(start);

		for (ans=j; ; ans+=1) {

			if (ida(start,x0,y0,0,i,j)) {

				break;

			}

		}

	getch();

	}

	return 0;

}









附:

判断是否有解的代码

#include <iostream>

#include <cmath>

using namespace std;



int temp[2][10005];



int result;



int Merge(int* from, int* to, int l_len, int r_len)

{

    int i, j, k;

    for (i = j = k =0;i<l_len&&j<r_len;)

        if (from[i] < from[j+l_len]) to[k++]=from[i++], result+=j;

        else to[k++]=from[l_len+j++];

    while(i<l_len) to[k++]=from[i++], result+=j;

    while(j<r_len) to[k++]=from[l_len+j++];

}

int inv(int n,int a[])

{

    int l, start, i;

    int ret = 0;

    int* t = temp[1];

    for (l = 1; l < n; l<<=1)

    {

        for (start = 0; start+l*2<=n; start+=l*2)

            Merge(a+start, t+start, l, l);

        if (start+l<n) Merge(a+start, t+start, l, n-1-(start+l)+1);

        else for (;start<n;++start) t[start ] = a[start];

        l*=2;

        for (start = 0; start+l*2<=n; start+=l*2)

            Merge(t+start, a+start, l, l);

        if (start+l<n) Merge(t+start, a+start, l, n-1-(start+l)+1);

        else for (;start<n;++start) a[start] = t[start];



    }

}



char buff[10240];

int main()

{

    int n;

    while (scanf("%d\n", &n) == 1)

    {

        int off;

        int idx = 0;

        for (int i = 0; i < n; ++i)

        {

            int pos = 0;

            gets(buff);

            for (int j = 0; j < n - 1; ++j)

            {

                int t = 0;

                while (buff[pos] != ' ') t = t *10+buff[pos++]-48;

                ++pos;

                if (t == 0)

                {

                    off = abs(i-n+1) + abs(j-n+1);

                    t = 1000000000;

                }

                temp[0][idx++] = t;

            }

            

                int t = 0;

                while (buff[pos])t = t *10+buff[pos++]-48;

                ++pos;

                if (t == 0)

                {

                    off = abs(i-n+1);

                    t = 1000000000;

                }

                temp[0][idx++] = t;

        }

        result = 0;

        

        inv(n*n, temp[0]);

        if ((result + off) % 2 == 0) puts("YES");

        else puts("NO");

    }

    return 0;

}
kingstarer 2009-05-26
  • 打赏
  • 举报
 回复
要一列或者一行同时移动　空格没有特别的含义　你可以把它看成是0
光宇广贞 2009-05-26
  • 打赏
  • 举报
 回复
明白了……我刚看错了。
光宇广贞 2009-05-26
  • 打赏
  • 举报
 回复
你的移法是一个一个地移么？只有在空格附近的可以移向空格？那为什么红框可以一下标四个，这是什么意思？
kingstarer 2009-05-25
  • 打赏
  • 举报
 回复
现在游戏我自己都玩通关了，程序还是没写出来

看来人脑要的计算能力比普通程序复杂多了 :)
beyond071 2009-05-12
  • 打赏
  • 举报
 回复
挺好的贴 学习了
wwqna 2009-05-12
  • 打赏
  • 举报
 回复
这种移法，那个空格只能在四个角落里，楼主是不是这样子呀？
kingstarer 2009-05-12
  • 打赏
  • 举报
 回复
不是　空格能在任务地方

sniperhuangwei 2009-05-11
  • 打赏
  • 举报
 回复
用A*算法.
我解8码问题用的就是A*,效率不错
liliangbao 2009-05-09
  • 打赏
  • 举报
 回复
帮顶~
kingstarer 2009-05-09
  • 打赏
  • 举报
 回复
[Quote=引用 17 楼 kingstarer 的回复:]
ps: 发现我实现的双向广度搜索出来结果不是最优的　不知道是哪里面错了?
[/Quote]
原来是我生成子节点状态时漏了
lzh9955 2009-05-09
  • 打赏
  • 举报
 回复
牛人啊!!!!
kingstarer 2009-05-09
  • 打赏
  • 举报
 回复
LS误会了　这个游戏不是我写的　我只是一个普通玩家

你问我怎么解决屏闪是问道于盲:)
小y正在思考人生 2009-05-09
  • 打赏
  • 举报
 回复
对了，问下楼主题外问题，屏闪问题怎么解决的？
zhiyongtu 2009-05-09
  • 打赏
  • 举报
 回复
AI问题，正在学习。
kingstarer 2009-05-09
  • 打赏
  • 举报
 回复
是这个数　状态数太多了　如果照网上常用的八数码hash来做会溢出　

[Quote=引用 28 楼 litaoye 的回复:]
状态数量应该是16!吧。BSF的话，每次有12个分支。计算量确实不小。

引用 23 楼 kingstarer 的回复:
没用hash　状态数太大了　直接用的是map 重载了 <号为memcmp

搜索过程中不会重复（3 * 3 测试通过），每个状态生成12个节点　如果判断节点已在close表里面则不进open表
[/Quote]
绿色夹克衫 2009-05-09
  • 打赏
  • 举报
 回复
状态数量应该是16!吧。BSF的话，每次有12个分支。计算量确实不小。

[Quote=引用 23 楼 kingstarer 的回复:]
没用hash　状态数太大了　直接用的是map 重载了 <号为memcmp

搜索过程中不会重复（3 * 3 测试通过），每个状态生成12个节点　如果判断节点已在close表里面则不进open表
[/Quote]
kingstarer 2009-05-09
  • 打赏
  • 举报
 回复
编译器 : vs 2005
kingstarer 2009-05-09
  • 打赏
  • 举报
 回复
doublegrade.cpp



// denshanfa.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"

#include "doublegrade.h"



bool no_result(STATE start, STATE end)

{

	sort(start.m_array, start.m_array + AEEAY_SIZE);

	sort(end.m_array, end.m_array + AEEAY_SIZE);

	return !(start == end);

}



//两个状态不同棋子数

int get_distince(const STATE& src, const STATE& desc)

{

	int distince = 0;



	for (int i = 0; i < HIGHTH; i++)

	{

		for (int j = 0; j < WITHLEN; j++)

		{

			if (src.m_array[i * WITHLEN + j] != desc.m_array[i * WITHLEN + j])

			{

				distince++;

			}

		}

	}



	return distince + src.m_generation - 1;

}



bool is_nearer(const P_STATE& left, const P_STATE& right)

{

	return left->m_distince < right->m_distince;

}



void init_state(char *filename, char *array)

{

	FILE *fp = fopen(filename, "r");



	if (fp == NULL)

	{

		cerr << "can not open file " << filename << endl;

		return;

	}



	int tmp;

	for (size_t i = 0; i < HIGHTH; i++)

	{

		for (size_t j = 0 ; j < WITHLEN; j++)

		{

			fscanf(fp, "%d", &tmp);

			array[i * WITHLEN + j] = tmp;

		}

	}

}



int domain(int argc, char* argv[])

{

	P_NODE_DEQUE up_open_tab;

	P_NODE_DEQUE down_open_tab;

	P_NODE_DEQUE substate;

	P_NODE_MAP close_tab;

	const char UP_FIRST_FIND = 1;

	const char UP_SECOEND_FIND = 2;

	const char HAD_UP = UP_FIRST_FIND | UP_SECOEND_FIND;

	const char DOWN_FIRST_FIND = 4;

	const char DOWN_SECOEND_FIND = 8;

	const char HAD_DOWN = DOWN_FIRST_FIND | DOWN_SECOEND_FIND;



	char star_state_array[HIGHTH * WITHLEN] = 

	{

		2, 15, 0, 3,

		4, 10, 8, 5,

		12, 9, 6, 11,

		13, 1, 7, 14

	};



	char end_state_array[HIGHTH * WITHLEN] = 

	{

		1, 2, 3, 4,

		5, 6, 7, 8,

		9, 10, 11, 12,

		13, 14, 15, 0

	};

/*

	char star_state_array[HIGHTH * WITHLEN] = 

	{

		1, 2, 3,

		4, 5, 6,

		7, 0, 8

	};



	char end_state_array[HIGHTH * WITHLEN] = 

	{

		1, 2, 3,

		4, 5, 6,

		7, 8, 0

	};

*/

	init_state("start.txt", star_state_array);

	init_state("end.txt", end_state_array);



	P_STATE stare_state = new STATE(star_state_array);

	P_STATE end_state = new STATE(end_state_array);

	P_STATE state, up_state, down_state;



	if (no_result(*stare_state, *end_state))

	{

		cout << "no result" << endl;

		return 0;

	}



	stare_state->m_father = NULL;

	stare_state->m_generation = 1;

	stare_state->m_distince = 0;

	stare_state->m_distince = get_distince(*stare_state, *end_state);

	end_state->m_father = NULL;



	up_open_tab.push_back(stare_state);

	close_tab[stare_state] |= UP_FIRST_FIND;

	down_open_tab.push_back(end_state);

	close_tab[end_state] |= DOWN_FIRST_FIND;



	bool findend = false;



	if (*end_state == *stare_state)

	{

		up_state = stare_state;

		down_state = end_state;

		findend = true;

	}



	while( up_open_tab.size() != 0 && down_open_tab.size() != 0 && !findend)

	{

		if (down_open_tab.size() > up_open_tab.size()) //状态数小的表优先搜索

		{

			DEBUG_COUT(cout << "open_tab.size() = " << up_open_tab.size() << endl);

			state = up_open_tab.front();

			up_open_tab.pop_front();



			P_NODE_MAP_ITER it = close_tab.find(state);



			//已正向遍历过的结点不再处理

			if (it->second == UP_SECOEND_FIND)

			{

				substate.clear();

			}

			else

			{

				//生成子节点

				get_next(substate, *state);

			}



			//对于每一个子节点判断是否已在反向遍历中出现过　

			DEBUG_COUT(cerr << __FILE__ << ":" << __LINE__ << endl);

			for (size_t i = 0; i < substate.size(); i++)

			{

				//cout << "------------" << i << "--------------" << endl;

				//substate[i]->show();

				DEBUG_COUT(cerr << __FILE__ << ":" << __LINE__ << endl);

				P_NODE_MAP_ITER it = close_tab.find(substate[i]);

				if (it == close_tab.end())

				{

					up_open_tab.push_back(substate[i]);

					close_tab[substate[i]] = UP_FIRST_FIND;

				}

				else

					if (  (it->second  & HAD_DOWN) > 0  )

					{

						DEBUG_COUT(cerr << __FILE__ << "*************find had down***************" << __LINE__ << endl);



						up_state = substate[i];

						down_state = it->first;

						findend = true;

						break;

					}

					DEBUG_COUT(cerr << __FILE__ << ":" << __LINE__ << endl);

			}

			//cout << "***************************************" << endl;

		} 

		else

		{

			DEBUG_COUT(cout << "open_tab.size() = " << down_open_tab.size() << endl);

			state = down_open_tab.front();

			down_open_tab.pop_front();



			P_NODE_MAP_ITER it = close_tab.find(state);



			if (it->second == DOWN_SECOEND_FIND)

			{

				substate.clear();

			}

			else

			{

				get_next(substate, *state);

			}





			DEBUG_COUT(cerr << __FILE__ << ":" << __LINE__ << endl);

			for (size_t i = 0; i < substate.size(); i++)

			{

				//cout << "------------" << i << "--------------" << endl;

				//substate[i]->show();

				DEBUG_COUT(cerr << __FILE__ << ":" << __LINE__ << endl);

				P_NODE_MAP_ITER it = close_tab.find(substate[i]);

				if (it == close_tab.end())

				{

					down_open_tab.push_back(substate[i]);

					close_tab[substate[i]] = DOWN_FIRST_FIND;

				}

				else

					if (  (it->second  & HAD_UP) > 0  )

					{

						DEBUG_COUT(cerr << __FILE__ << "*************find had up***************" << __LINE__ << endl);



						up_state = it->first;

						down_state = substate[i];

						findend = true;

						break;

					}

					DEBUG_COUT(cerr << __FILE__ << ":" << __LINE__ << endl);

			}

			//cout << "***************************************" << endl;

		}

	}



	if (findend)

	{

		cout << "******************find the result*********************" << endl;

		size_t i = 1;

		STATE *pstate = down_state.get()->m_father;

		vector< STATE * > ve_pstates;



		while (pstate != NULL)

		{

			ve_pstates.push_back(pstate);

			pstate = pstate->m_father;

		}



		for (size_t n = ve_pstates.size(); n != 0; n--)

		{

			cout << "******************step " << i++ << "*********************" << endl;

			ve_pstates[n - 1]->show();

		}



		pstate = up_state.get();



		while (pstate != NULL)

		{

			cout << "******************step " << i++ << "*********************" << endl;

			pstate->show();

			pstate = pstate->m_father;

		}

	}

	else

	{

		cout << "no result" << endl;

	}

	cout << "end domain" << endl;





	return 0;

}





int main(int argc, char *argv[])

{

	RUNTIME(domain, (argc, argv));



	return 0;

}
加载更多回复（23）
游戏编程中的寻路算法研究
近年来，游戏产业的快速发展带动了游戏中人工智能（Artificial Intelligence，简称AI）的发展，越来越多的游戏采用人工智能技术提高游戏的可玩性。在电子游戏中，玩家操控主要角色，而其他角色的行为逻辑由人工智能操纵，这些角色我们称之为NPC（Non-Player Character，非玩家控制角色）。大部分游戏在开发过程中都会遇到路径探索问题，快速、准确地计算出游戏角色从地图中的A点
Java数据结构与算法 day13 程序员十大常用算法
文章目录第十三章 十大常用算法二分查找算法(非递归)分治算法动态规划算法KMP算法贪心算法普利姆算法克鲁斯卡尔算法克鲁斯卡尔算法介绍克鲁斯卡尔算法图解说明克鲁斯卡尔算法分析如何判断是否构成回路-举例说明？鲁斯卡尔算法的代码说明迪杰斯特拉算法(这个没怎么懂！！！)弗洛伊德算法回溯算法全劇終！！！ 第十三章 十大常用算法 本章源码：https://github.com/name365/Java-Data-structure 二分查找算法(非递归) 二分查找算法(非递归)介绍 前面我们讲过了二分查找算法，
数据结构和算法之常用 10 种算法
目录 1.二分查找算法(非递归) 2.分治算法 2.1分治算法最佳实践-汉诺塔 3.动态规划算法 4.KMP 算法 4.1KMP 算法最佳应用-字符串匹配问题 5.贪心算法 5.1贪心算法最佳应用-集合覆盖 6.普里姆算法 7.克鲁斯卡尔算法 8.迪杰斯特拉算法 9.弗洛伊德算法 10.马踏棋盘算法 1.二分查找算法(非递归) 二分查找法只适用于从有序的数列中进行查找(比如数字和字母等)，将数列排序后再进行查找 二分查找法的运行时间为对数时间 O(㏒₂n) ，即查找..
大厂程序员必备十大基础算法 -- 分治算法
1. 分治算法 1.1 分治算法介绍 分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)…… 分治算法可以求解的一些经典问题 二分搜索 大整数乘法 ...
Java数据结构和算法---程序员常用10种算法
1.二分查找算法 二分查找算法(非递归)介绍 ①二分查找法只适用于从有序的数列中进行查找(比如数字和字母等)，将数列排序后再进行查找 ②二分查找法的运行时间为对数时间O(㏒₂n) ，即查找到需要的目标位置最多只需要㏒₂n步，假设从[0,99]的队列(100个数，即n=100)中寻到目标数30，则需要查找步数为㏒₂100 , 即最多需要查找7次( 2^6 < 100 < 2^7)递归二分查找复习: ·思路 ①首先确定该数组的中间下标 mi...
C++ 语言

64,701

社区成员

250,492

社区内容

发帖
与我相关
我的任务
社区描述
C++ 语言相关问题讨论，技术干货分享，前沿动态等
c++ 技术论坛（原bbs）
社区管理员
  • C++ 语言社区
  • encoderlee
  • paschen
加入社区
  • 近7日
  • 近30日
  • 至今

加载中

查看更多榜单
社区公告
  1. 请不要发布与C++技术无关的贴子
  2. 请不要发布与技术无关的招聘、广告的帖子
  3. 请尽可能的描述清楚你的问题，如果涉及到代码请尽可能的格式化一下

试试用AI创作助手写篇文章吧

+ 用AI写文章