目前最快的N皇后问题算法!!!

IceCraft 2006-04-24 01:20:14
最近老师布置了一道算法题目--N皇后问题。这个算法在本科时已经做过,现在的要求是尽可能的提高算法的执行效率。如果采用传统的办法,用3个数组来记录列、主对角线和次对角线的方式,虽然优化过语句,并且使用对称原则来减少一半的运算时间,但在1.66Ghz的机器上计算16皇后仍需要100多秒。
有的同学使用多线程方式来改进了算法,有效利用了服务器的多个CPU同时计算,好像在4CPU机器上用了17秒。但我觉得这并没有体现出算法的高效。
昨天在google上有幸找到了一个难得一见的算法,在1.66Ghz的机器上计算16皇后才用了35秒,是我目前见到的最快的皇后问题算法了。简单的看了一下算法原理,它有别于传统的数组判断模式,而是采用了位运算。我也跟踪了几个变量的位结构变化情况,但是直到今天仍没能理解作者对该算法的设计思想和算法原理。
因此期望CSDN中的算法高手不吝赐教,能对这个算法做个注释,并描述一下算法原理,在下感激不仅!

-----------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

long sum = 0, upperlim = 1;

void test(long row, long ld, long rd)
{

if (row != upperlim)
{
long pos = upperlim & ~(row | ld | rd);
while (pos)
{
long p = pos & -pos;

pos -= p;
test(row + p, (ld + p) << 1, (rd + p) >> 1);
}
} else
sum++;
}

int main(int argc, char *argv[])
{
time_t tm;
int n = 16;

if (argc != 1)
n = atoi(argv[1]);
tm = time(0);
if ((n < 1) || (n > 32))
{
printf(" 只能计算1-32之间\n");
exit(-1);
}
printf("%d 皇后\n", n);
upperlim = (upperlim << n) - 1;

test(0, 0, 0);
printf("共有%ld种排列, 计算时间%d秒 \n", sum, (int) (time(0) - tm));
}
-------------------------------
...全文
27039 135 打赏 收藏 转发到动态 举报
写回复
用AI写文章
135 条回复
切换为时间正序
请发表友善的回复…
发表回复
lzjyf 2010-06-05
  • 打赏
  • 举报
回复
星辰拜师行么··
nankezhishi 2006-10-09
  • 打赏
  • 举报
回复
回溯永远是最慢的.

启发式算法,如遗传算法\局部搜索.

1000后问题 数秒解决.

当然,在下不会.
gezichong 2006-08-28
  • 打赏
  • 举报
回复
xmhl 2006-06-20
  • 打赏
  • 举报
回复
mark
ayw215 2006-06-19
  • 打赏
  • 举报
回复
强人好多啊
templarzq 2006-06-19
  • 打赏
  • 举报
回复
mark
wupei 2006-06-19
  • 打赏
  • 举报
回复
upup
tanlerstar 2006-06-13
  • 打赏
  • 举报
回复
哎!你们太狠了!!
学习学习!
POPO_POPO 2006-06-11
  • 打赏
  • 举报
回复
随时关注此帖
2006-06-11
  • 打赏
  • 举报
回复
学习...
heihei2004 2006-06-11
  • 打赏
  • 举报
回复
强,mark
sunbird69 2006-06-11
  • 打赏
  • 举报
回复
mark
mgdcs 2006-06-11
  • 打赏
  • 举报
回复
输入20的话,时间很长啊
SamuelKevin 2006-06-11
  • 打赏
  • 举报
回复
shoucang
transcendself 2006-06-06
  • 打赏
  • 举报
回复
good
daseny 2006-05-27
  • 打赏
  • 举报
回复
mark
一到周末心就飞了,等等再看吧。
呵呵,也许是昨天被几个线程折磨惨了……
Cybergate 2006-05-27
  • 打赏
  • 举报
回复
太优美了,我当时也写了个位运算的,但远远没这么精炼啊。
shellyyee 2006-05-27
  • 打赏
  • 举报
回复
长见识了....只是留名学习...
gengjindong 2006-05-27
  • 打赏
  • 举报
回复
C语言并不难。
只不过是有点烦。
如何能学好数据结构那就要看自己的自学能力了。
一个天才都不敢说出一个好的学习方案。
所以万事得靠自己。
网上有好多有关C语方的视频。我希望自己能在自学预习的情况下多看一些学习教程。
snailbreak 2006-05-26
  • 打赏
  • 举报
回复

JF
加载更多回复(115)
一、 功能简介 本课件是一个动态演示数据结构算法执行过程的辅助教学软件, 它可适应读者对算法的输入数据和过程执行的控制方式的不同需求, 在计算机的屏幕上显示算法执行过程中数据的逻辑结构或存储结构的变化状况或递归算法执行过程中栈的变化状况。整个系统使用菜单驱动方式, 每个菜单包括若干菜单项。每个菜单项对应一个动作或一个子菜单。系统一直处于选择菜单项或执行动作状态, 直到选择了退出动作为止。 二、 系统内容 本系统内含84个算法,分属13部分内容,由主菜单显示,与《数据结构》教科书中自第2章至第11章中相对应。各部分演示算法如下: 1. 顺序表 (1)在顺序表中插入一个数据元素(ins_sqlist) (2)删除顺序表中一个数据元素(del_sqlist) (3)合并两个有序顺序表(merge_sqlist) 2. 链表 (1)创建一个单链表(Crt_LinkList) (2)在单链表中插入一个结点(Ins_LinkList) (3)删除单链表中的一个结点(Del_LinkList) (4)两个有序链表求并(Union) (5)归并两个有序链表(MergeList_L) (6)两个有序链表求交(ListIntersection_L) (7)两个有序链表求差(SubList_L) 3. 栈和队列 (1)计算阿克曼函数(AckMan) (2)栈的输出序列(Gen、Perform) (3)递归算法的演示  汉诺塔的算法(Hanoi)  解皇后问题的算法(Queen)  解迷宫的算法(Maze)  解背包问题的算法(Knap) (4)模拟银行(BankSimulation) (5)表达式求值(Exp_reduced) 4. 串的模式匹配 (1)古典算法(Index_BF) (2)求Next 函数值(Get_next)和按Next 函数值进行匹配 (Index_KMP(next)) (3)求 Next 修正值(Get_nextval)和按 Next 修正值进行匹配(Index_KMP(nextval)) 5. 稀疏矩阵 (1)矩阵转置 (Trans_Sparmat) (2)快速矩阵转置 (Fast_Transpos) (3)矩阵乘法 (Multiply_Sparmat) 6. 广义表 (1)求广义表的深度(Ls_Depth) (2)复制广义表(Ls_Copy) (3)创建广义表的存储结构(Crt_Lists) 7. 二叉树 (1)遍历二叉树  二叉树的线索化  先序遍历(Pre_order)  中序遍历(In_order)  后序遍历(Post_order) (2) 按先序建二叉树(CrtBT_PreOdr) (3) 线索二叉树  二叉树的线索化  生成先序线索(前驱或后继) (Pre_thre)  中序线索(前驱或后继) (In_thre)  后序线索(前驱或后继) (Post_thre)  遍历中序线索二叉树(Inorder_thlinked)  中序线索树的插入(ins_lchild_inthr)和删除(del_lchild_inthr)结点 (4)建赫夫曼树和求赫夫曼编码(HuffmanCoding) (5)森林转化成二叉树(Forest2BT) (6)二叉树转化成森林(BT2Forest) (7)按表达式建树(ExpTree)并求值(CalExpTreeByPostOrderTrav) 8. 图 (1)图的遍历  深度优先搜索(Travel_DFS)  广度优先搜索(Travel_BFS) (2)求有向图的强连通分量(Strong_comp) (3)有向无环图的两个算法  拓扑排序(Toposort)  关键路径(Critical_path) (4)求最小生成树  普里姆算法(Prim)  克鲁斯卡尔算法(Kruscal) (5)求关节点和重连通分量(Get_artical) (6)求最短路径  弗洛伊德算法(shortpath_Floyd)  迪杰斯特拉算法(shortpath_DIJ) 9. 存储管理 (1)边界标识法 (Boundary_tag_method) (2)伙伴系统 (Buddy_system) (3)紧缩无用单元 (Storage_compactio
数据结构与算法 排序算法 内排序 八大基础排序 选择排序 简单选择排序 思想 每次选择最大的数插入到末尾中 做法 外层for循环控制次数 内层for循环找出最大的值的角标 找出最大角标后,进行交换 优化思路 同时获取最大值和最小值,然后分别插入数组的首部和尾部 堆排序 思想 使用大顶堆的思想来排序,每次建堆后交换 做法 总体:建堆-替换 建堆 只要左子树或右子树大于当前根节点,则替换 替换后会导致下面的子树发生了变化,因此同样需要进行比较,直至各个节点实现父>子这么一个条件(递归) 交换排序 冒泡排序 思想 每次俩俩交换,将最大值交换到末尾 做法 外层for控制循环次数 内层for控制比较次数 每次循环之后,比较次数都会减少一次 优化思路 如果一趟排序后没有发生位置变化,那么此时就是有序了 快速排序 思想 每次将比支点小的放在支点左边,比支点大的放在支点右边 做法 外循环while只要i和j不碰撞查找 内层两个while循环分别查找出比支点小的和比支点大的角标 如果i<=j满足条件,就交换 一趟排序后,支点的左边都比支点小,支点右边都比支点大 只要满足L算法 希尔排序 思想 用增量来将数组进行分隔,直到增量为1。底层干的还是插入排序干的活 做法 最外层for外循环控制增量的数量,每次/2 第二层for循环控制每次增量那组开始进行插入排序,直至完毕 第三层while循环找到要插入到哪个位置 归并排序 思想 将两个已排好序的数组合并成一个有序的数组 做法 递归拆分出两个有序的数组,从mid的位置开始拆分,递归出口:只有一个值的时候就不用拆分了 合并两个有序的数据 分别往两个数组填充已有序的数据 比较两个数组的值谁小,谁小就放到我们的数组中 如果比较完之后还有剩余的数据,那么用while直接添加到我们的总数组中 优化思路 当递归到规模足够小时,利用插入排序 归并前判断一下是否还有必要归并 只在排序前开辟一次空间 基数(桶)排序 思想 分配,回收(分配到不同的位置上,然后回收)..不断分配..回收来进行排序,直到有序 做法 分配一个[array.length][10列]的二维数组来装我们的元素 最外层for循环控制要分配和回收的次数(根据最大值) 将元素的个、十、百位依次放到桶子上(第一次就是放个位,第二次放十位) 依据每列回收桶子,两个for循环 外排序 查找算法 二分查找 分块查找 哈希查找 贪心算法 求最小生成树的Prim算法和Kruskal算法 爬山问题 回溯算法 n皇后问题 动态规划Dynamic Planning 应用 求最长公共子序列LCS 矩阵连乘问题 爬楼梯问题 找零问题 0-1背包问题 分治算法Divide and Conquer 应用:归并排序 其它 Rabin fingerprints 文件指纹算法 BitMap 位图算法 BloomFilter 布隆过

69,322

社区成员

发帖
与我相关
我的任务
社区描述
C语言相关问题讨论
社区管理员
  • C语言
  • 花神庙码农
  • 架构师李肯
加入社区
  • 近7日
  • 近30日
  • 至今
社区公告
暂无公告

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