Algorithm 版 (精华区)

发信人: Lerry (Lerry), 信区: Algorithm
标  题: [合集]求n个数的全排列
发信站: 哈工大紫丁香 (2002年06月19日09:03:40 星期三), 站内信件


────────────────────────────────────────
 Lerry (想不开·撞树)                 于 2002年04月21日11:00:46 星期天 说道:

 在人工智能领域内，搏弈是很重要的一个研究分支。通过对搏弈
的研究，可以解决很多实际问题，使电脑智能向人类智能迈进一大步。
    在搏弈问题中，围棋无疑是其中最有难度的问题。围棋程序的主
要困难在于一，状态点过多。在各种棋类中，围棋在每一步棋选择的
自由度要远远超过其他棋类。这是造成搜索困难的主要原因。二，棋
子间关系抽象化。懂得围棋的人知道，围棋中每一个棋子的影响是受
当前棋局决定的，从某种意义上说，每一个棋子的效率还将受到今后
棋局发展的影响。三，胜利条件复杂，围棋的胜利是靠双方所占目数
的多少决定的。在棋局过程中，一般业余棋手也很难点清（主要是确
定）双方目数，对于电脑就尤显复杂了。第二、三点决定了电脑围棋
程序的估价函数异常复杂。
    由于以上原因，限制了电脑围棋的发展，世界电脑围棋冠军程序
手谈（Handtalk）也只相当于业余2、3级水平。这就构成了一种压力
和机遇，毕竟电脑围棋前途不可限量。
    从原则上讲，博弈程序必然有最后的极限－－扩展全部博弈树。
这也是人脑无法比拟的。但由于围棋的上述特点，我认为现阶段电脑
围棋应从模拟人脑思维过程出发，利用电脑的高速度和准确庞大的记
忆弥补其他方面的不足。
    任何一种博弈程序都至少需要决策（搜索）系统、估价函数和数
据库。由于程序所耗时间主要在决策系统中，所以估价函数和数据库
都应根据决策的需要而改进，而决策也就理所当然的成为电脑围棋的
核心。
    以往的程序大多是在当前棋局下利用数据库选出一定数量的可选
点集合。对每个点进行几乎相同的搜索，然后选出权值最高的点作为
下一步棋输出。但我们知道，一般人们不是这样下棋的。人们往往通
过对棋局进行估计，决定决策方向（往哪下），再具体考虑落点（如
何下）。这样，对一些不在正确行棋方向上的选点，哪怕是局部的好
点，也不会进行过多的考虑。其次，限于电脑围棋水平，在同时有几
个好点时应该采取模糊方法选取，即在不同权值的点下随机选取。
    具体来说，当程序面临一个棋局时，应能将棋局分解为一个个棋
块，即相互紧密关联的棋子（包括黑白双方）。首先调用低级估价函
数。低级估价函数是以棋块为单位，分别与数据库中模型匹配，检验
在此棋块中是否有“急所”，如：未完成的定式，死活棋，待整形的
棋等。当与数据库中无法匹配时，在局部可做小范围的搜索。对找到
的急所可以按类似下面的高级估价函数进行全局范围的估价。低级估
价函数主要解决局部对抗，中盘战斗等问题。
    然后程序调用高级估价函数。高级估价函数把棋盘分为九个部分，
四个角、四个边和中腹。对每一部分分析双方成果，如计算实地目数、
外势影响、方向，征子问题等等，并适当修正本部分和其他部分结果，
最后将九个部分汇总得出全局估价结果并找出最能影响棋局均衡度的
部分。这一函数主要解决程序大局观问题，在序盘，对大场和打入的
选择尤为重要。
    当有了估价结果后，选出一个或几个（主要根据时间和当前棋局
进行情况）落点方向，再进行局部搜索。
    在其他方面如：一、对数据库要求较高，要便于程序匹配数据，
且对每一步应有详细的数值评价，如，取得实地、占有外势，能否脱
先、甚至对将来的影响等。二、适当加如感情参数，如在局面领先下
尽量选择平稳，否则尽量导入复杂。三、加入学习机制，使电脑不断
积累成果。
    以上是我对电脑围棋的大致想法，有很多不完善之处，如棋局抽
象问题，模式匹配问题等等。希望这篇文章能起到抛砖引玉的作用，
使各位同“志”多提建议，不胜感激。

────────────────────────────────────────
 Lerry (想不开·撞树)                 于 2002年04月21日11:06:58 星期天 说道:

http://www.voicenet.com/~rybak/vnc.html
BMV:
                 Behavioral Model of Active Visual
                     Perception and Recognition
                   I. A. Rybak, A. V. Golovan, V. I. Gusakova,
                   N. A. Shevtsova, and L. N. Podladchikova
Table of Contents
      Approach
      Animated illustration (parallel-sequential image processing in
human vision)
      Model
      Examples of recognition of scene objects and faces
      Recent paper (postscript file):
       I. A. Rybak, V. I. Gusakova, A.V. Golovan, L. N. Podladchikova, and N
. A.
       Shevtsova.
       A model of attention-guided visual perception and recognition. Vision
 Ressearch
       (in press).
      Download DEMO for DOS/Windows
       DEMO demonstrates the ability of BMV model to recognize complex gray-
leve
       images (e.g. faces) invariantly in respect to shift, rotation and sca
le
      Press release:
        "Brain model recognizes images" by Andrew Wilson
        (published in Vision Systems Design, 1997, Vol. 2, No 3, pp. 11-12).
        "Learning system includes feedback control loop" by Colin Johnson
        (published in Electronic Engineering Times of 4/22/1996, pp. 33, 40)
.
        ( Abstract)
       Related attention and eye movement links
       Recognition, recognition...
      Approach
                                     The mind can only see what it is prepar
ed tto see.
                                                                Edward de Bo
no
During visual perception and recognition, human eyes move and successively f
ixatte at
the most informative parts of the image (Yarbus 1967). The eyes actively per
form
problem-oriented selection and processing of information from the visible wo
rld under
the control of visual attention (Burt 1988; Julesz 1975; Neisser 1967; Noton
 andd Stark
1971; Triesman and Gedal 1980, Yarbus 1967). Consequently, visual perception
 and
recognition may be considered as behavioral processes, and probably cannot b
e
completely understood in limited frames of neural computations without takin
g innto
account behavioral and cognitive aspects of these processes. (Click here to 
see an
animated illustration of parallel-sequential image processing in human visua
l syystem
based on both the sequential eye movements and the foveal structure of the r
etinna).
From the behavioral point of view, an internal representation (model) of new
circumstances is formed in the brain during conscious observation and active
examination. The active examination is aimed toward the finding and memorizi
ng o
functional relationships between the applied actions and the resulting chang
es i
sensory information. An external object becomes "known" and may be recognize
d whhen
the system is able to subconsciously manipulate the object and to predict th
e obbject's
reactions to the applied actions. According to this paradigm, the internal o
bjec
representation contains chains of alternating traces in "motor" and "sensory
"
memories. Each of these chains reflects an alternating sequence of elementar
y mootor
actions and sensory (proprioceptive and external) signals which are expected
 to arrive
in response to each action. The brain uses these chains as "behavioral progr
ams"" in
subconscious "behavioral recognition" when the object is (or is assumed) kno
wn. This
"behavioral recognition" has two basic stages: (i) conscious selection of th
e
appropriate behavioral program (when the system accepts a hypothesis about t
he
object), and (ii) subconscious execution of the program. Matching the expect
ed
(predicted) sensory signals to the actual sensory signals, arriving after ea
ch mmotor
action, is an essential operation in the program execution.
The above behavioral paradigm was formulated and developed in the context of
 vissual
perception and recognition in a series of significant works (Yarbus, 1967; N
otonn &
Stark, 1971; Didday & Arbib, 1975; Kosslyn et al., 1990; Rimey and Brown, 19
91).. Using
Yarbus
circumstances is formed in the brain during conscious observation and active
examination. The active examination is aimed toward the finding and memorizi
ng o
functional relationships between the applied actions and the resulting chang
es i
sensory information. An external object becomes "known" and may be recognize
d wh
the system is able to subconsciously manipulate the object and to predict th
e obhen
reactions to the applied actions. According to this paradigm, the internal o
bjecbject's
representation contains chains of alternating traces in "motor" and "sensory
"
memories. Each of these chains reflects an alternating sequence of elementar
y mo
actions and sensory (proprioceptive and external) signals which are expected
 tootor
in response to each action. The brain uses these chains as "behavioral progr
ams" arrive
subconscious "behavioral recognition" when the object is (or is assumed) kno
wn." in
"behavioral recognition" has two basic stages: (i) conscious selection of th
e
appropriate behavioral program (when the system accepts a hypothesis about t
he
object), and (ii) subconscious execution of the program. Matching the expect
ed
(predicted) sensory signals to the actual sensory signals, arriving after ea
ch m
action, is an essential operation in the program execution.
The above behavioral paradigm was formulated and developed in the context of
 vis
perception and recognition in a series of significant works (Yarbus, 1967; N
otonsual
Stark, 1971; Didday & Arbib, 1975; Kosslyn et al., 1990; Rimey and Brown, 19
91).n &
Yarbus 

────────────────────────────────────────
 cybernaut (大力神)                   于 2002年04月19日10:49:26 星期五 说道:

求n个数的全排列的算法,如 n=3,则全排列为
(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)

────────────────────────────────────────
 davidchang (Loading....)             于 2002年04月19日11:03:22 星期五 说道:

一般的组合数学书里都有排列和组合的生成算法
自己找找看吧
实际上就是个二重循环

────────────────────────────────────────
 sino (蚱蜢舟)                        于 2002年04月19日22:06:16 星期五 说道:

看个比较标准的吧，呵呵
Perm.pas
const fileout = 'perm.txt';
      MAXN = 100;
var fout :text;
    n , i :integer;
    permut , position :array [ 1..MAXN ] of integer;
    dir :array [ 1..MAXN ] of integer;
procedure PrintPermutation;
begin
for i := 1 to n do
  write(fout, ' ', permut[i] );
writeln(fout);
end;
procedure Switch ( p1 , p2 :integer);
var xch :integer;
begin
xch := permut[ p1 ];
permut[ p1 ] := permut[ p2 ];
permut[ p2 ] := xch;
position[ permut[ p1 ] ] := p1;
position[ permut[ p2 ] ] := p2;
end;
procedure GeneratePermutation ( nn :integer);
var ii :integer;
begin
if (nn = n + 1) then
  PrintPermutation
else
  begin
    GeneratePermutation ( nn + 1 );
    for ii := 1 to nn - 1 do
      begin
Switch ( position[nn] , position[nn]+dir[nn] );
GeneratePermutation ( nn + 1 );
      end;
    dir[nn]:=-dir[nn];
  end;
end;
begin
readln(n);
for i := 1 to n do
  begin
    permut[i] := i;
    position[i] := i;
    dir[i] := -1;
  end;
assign( fout , fileout);
rewrite( fout );
GeneratePermutation (1);
close ( fout );
end.
Perm.cpp
#include <stdio.h>
const char *fileout = "perm.txt";
const int MAXN = 100;
FILE *fout;
int n , i;
int permut[ MAXN + 1 ] , position[ MAXN + 1 ];
int dir[ MAXN + 1 ];
void PrintPermutation()
{
for ( i = 1 ; i <= n ; i++ )
  fprintf(fout , " %d" , permut[i]);
fprintf(fout , "\n");
}
void Switch ( int p1 , int p2 )
{
int xch = permut[p1];
permut[ p1 ] = permut[ p2 ];
permut[ p2 ] = xch;
position[ permut[ p1 ] ] = p1;
position[ permut[ p2 ] ] = p2;
}
void GeneratePermutation ( int nn )
{
int ii;
if ( nn == n + 1 )
  {
  PrintPermutation();
  }
else
  {
  GeneratePermutation ( nn + 1 );
  for ( ii = 1 ; ii <= nn - 1 ; ii++ )
    {
    Switch ( position[nn] , position[nn] + dir[nn] );
    GeneratePermutation ( nn + 1 );
    }
  dir[nn] = - dir[nn];
  }
}
void main()
{
scanf("%d" , &n );
for ( i = 1 ; i <= n ; i++ )
  {
  permut[i] = i;
  position[i] = i;
  dir[i] = -1;
  }
fout=fopen(fileout,"wt");
GeneratePermutation(1);
fclose(fout);
}
Input
        The first line contains a single integer: N ( 1 <= N <= 100 ). 
The 2nd line contains N integers separated by blanks. They are the given
 permutation with N elements. 
Sample Input
4
2 3 1 4
Hint
        Run the 2 given programs fon N=4 and you will notice that the 
permutation 2 3 1 4 will be on the 17th line of the file perm.txt . 
Problem Source: Romanian Open Contest, December 2001
Author: Mugurel Ionut Andreica 
Credits:
        The Pascal and C++ programs of the 3 programmers are improved 
(and, obviously, modified) versions of 2 programs written by Frank 
Ruskey (I found them on the web). So, thanks Frank ! 
Print   View Problem Statistics   Discuss   Submit
hq

────────────────────────────────────────
 sino (蚱蜢舟)                        于 2002年04月19日22:08:14 星期五 说道:

这只是方法之一哦，不过不少书上都有这个方法。

────────────────────────────────────────
 allen (大力水手)                     于 2002年04月19日22:28:57 星期五 说道:

给一个c++的递归算法，比较精炼..hehe
template<class T>
void Perm(T list[], int k, int m)
{
    int i;
    if(k==m) {
        for(i=0;i<=m;i++)
            cout<<list[i];
        cout<<endl;
    }
    else {
        for(i=k;i<=m;i++) {
            Swap(list[k], list[i]); //Swap为交换两个变量值的函数
            Perm(list, k+1, m);
            Swap(list[k], list[i]);
        }
     }
}

────────────────────────────────────────
 sino (蚱蜢舟)                        于 2002年04月20日10:03:39 星期六 说道:

我理解此方法只能用于一个互不相同的串
这段程序适用于含相同元素的情况：
var
    n:string;
    tot:integer;
    used:array[1..255]of boolean;
procedure tryit(l:integer);
var
    i:integer;
    c:char;
begin
    c:=' ';
    if l=m+1 then inc(tot)
    else
        for i:=1 to length(n) do 
            if (used[i]=false) and (c<>n[i]) then begin
                c:=n[i]; used[i]:=true;
                tryit(l+1); used[i]:=false;
            end;
end;
begin
    readln(n);
    fillchar(used,sizeof(used),0);
    Sort(n);
    tryit(1);
end.

────────────────────────────────────────