Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1478103
  • 博文数量: 217
  • 博客积分: 4362
  • 博客等级: 上校
  • 技术积分: 4179
  • 用 户 组: 普通用户
  • 注册时间: 2009-09-20 09:31
文章分类

全部博文(217)

文章存档

2017年(1)

2015年(2)

2014年(2)

2013年(6)

2012年(42)

2011年(119)

2010年(28)

2009年(17)

分类: LINUX

2011-09-25 21:54:52

<未完>
对于N皇后问题的算法的设计一般都是基于c语言或者c++算法进行设计的回溯算法,但是当N的值很大的时候,这个时候如果要计算N皇后解的话,是比较费时间的,因此,可以采用并发的方式进行相应算法的设计,以此来提高效率。

下面的算法是使用c语言进行设计的回溯算法:
  1. #include <stdio.h>
  2. #include <stdlib.h>

  3. #define N 11
  4. int sum = 0;
  5. int x[N];

  6. int check(int k)
  7. {
  8.     int i;

  9.     for(i = 0; i < k; i++) {
  10.         if(x[i]==x[k] || abs(k-i)==abs(x[k]-x[i])) {
  11.             return 0;
  12.         }
  13.     }
  14.     return 1;
  15. }

  16. //递归算法
  17. void Backtrack(int t)
  18. {
  19.     int i;
  20.     if(t > N) {
  21.         sum = sum+1;
  22.         printf("%d\n", sum);
  23.     } else {
  24.         for(i = 0; i < N; i++) {
  25.             x[t] = i;
  26.             if(check(t)) {
  27.                 Backtrack(t+1);
  28.             }
  29.         }
  30.     }
  31. }

  32. int main()
  33. {
  34.     Backtrack(4);
  35.     printf("sum=%d\n", sum);
  36.     return 0;
  37. }

使用erlang语言进行并行开发,代码的核心算法并未给出,待续完成。
%% nqueensbitv2.erl
-module(nqueensbitv2).
-export([start/1,startSearch/3,collect/3,startAllThread/1]).
-define(LOG(X), io:format("~p  ~p  ~p~n", [?MODULE, ?LINE, X])).

%% 模块的外部调用函数,开始计算N皇后的计算。
%% NQueens:表示的是皇后的个数。
start(NQueens) ->
%% 如果皇后个数小于4的话,不符合N皇后问题的计算,所以直接退出。
if(NQueens < 4) -> 
io:format("Can't solve Nqueens problem less then 4.~n");
true -> 
%% 创建一个收集处理的进程。
CollectID = spawn(?MODULE, collect, [[],0,self()]),
%% 创建NQeens个进程,每一个进程分别处理一种情况。
createNthreads(NQueens ,CollectID ,NQueens),
%% 上面的操作结束之后,该进程等待结束的消息。
receive
{finished,Solutions} ->
io:format("Find Solutions:~w.~n",[Solutions]);
_ ->
ok
end
end.

%% 收集处理进程所干的事情
%% ChildPIDS:记录已经创建好的进程的PID,是一个列表类型
%% Solutions:记录已经计算出来的N皇后问题的解的个数
%% ChildPIDS:记录此进程创建者PID,也就是start进程
collect(ChildPIDS,Solutions,ParentPID)->
receive
startChild -> 
spawn(nqueensbitv2,startAllThread,[ChildPIDS]),
collect(ChildPIDS,Solutions,ParentPID);  
{addchild,ChildP} -> 
collect([ChildP|ChildPIDS],Solutions,ParentPID);  
{finished,ChildP} -> 
LeftPIDS = lists:delete(ChildP,ChildPIDS),
if(LeftPIDS == []) -> 
ParentPID ! {finished,Solutions};
true -> 
collect(LeftPIDS,Solutions,ParentPID)
end;
{found,SolutionPath} ->
collect(ChildPIDS,Solutions + 1,ParentPID);
{found,_} -> collect(ChildPIDS,Solutions + 1,ParentPID);
_ -> ok
end.

%% 创建N个进程,每一个进程都是相互独立的
createNthreads(_,CollectID,0) ->
CollectID ! startChild;
createNthreads(N,CollectID,Nthread) ->
?LOG(N), 
?LOG(CollectID), 
?LOG(Nthread),
ChildP = spawn(nqueensbitv2,startSearch,[N,CollectID,Nthread]),
CollectID ! {addchild,ChildP},
createNthreads(N,CollectID,Nthread - 1).

%% 启动创建好的计算进程,让其开始计算
startAllThread([]) -> ok;
startAllThread([Child|Childs]) -> ?LOG(Childs),
Child ! startSearch,
startAllThread(Childs).


%% 单个独立计算进程所进行的计算
startSearch(NQueens,CollectID,NthThread) ->
%% 核心算法
阅读(1408) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~