人工智能、数理算法

oraclelang

一种快速可预制的随机数组产生方法 wxh zt




本文介绍了一种简单、快捷、实用的随机数组产生方法，经调试通过。附件为全部程序代码请审阅。

　　在工程软件的设计和安全系统设计中，建立模型、产生密码经常需要使用到随机数组。然而计算机不会产生绝对随机的随机数，计算机只能产生“伪随机数”。其实绝对随机的随机数只是一种理想的随机数，即使计算机怎样发展，它也不会产生一串绝对随机的随机数。计算机只能生成相对的随机数，即伪随机数。
　　伪随机数并不是假随机数，而是指有规律的数，事实上都是由计算机经过一定的算法计算得到的。大家常用的方法是根据一个给定的数作为种子，如采用变化的时间作为种子，调用srand((unsigned)time(NULL))后执行rand()从而获得一个随机数。很显然，相同或相近的种子得到的随机数将会是完全一样或互相接近。
　　因此要产生真正意义的随机数，那么种子首先必须是随机的。随机的种子可以通过外接的硬件随机发生器产生，据说最新的intel处理器即采用了读取cpu上热噪声的方法来获取随机数。当无法利用硬件的随机发生器时，我们常采用的办法是，在两次调用srand((unsigned)time(NULL))之间加入一定时间的延时。但当需要产生一个很大的随机数组时，这种延时是漫长而不可忍受的。而且事实上由于延时具有规律性，产生的随机数也不那么随机。
　　一种容易想到的产生随机数组的方法是设计出复杂的算法，从而减小数组结果的规律性。这种方法需要很高的技巧，也不太适合一般程序的调用。
　　此外，在很多情况下，我们不仅要求产生随机的数组，同时还对产生的数组有统计规律上的要求。如必须服从正态分布，均匀分布等。简单的调用srand和rand函数无法满足需要。
Matlab是一种功能强大的工程数学软件，利用其随机数组产生模块，我们能很容易的得到服从各种分布形式的大数组，其随机数产生的原理即是基于复杂的算法的。因此我们自然想到利用matlab产生的随机数表来作为随机数池，从中获得我们所需要的随机数组。
　　本随机数组产生方法由三部分组成：其一是txt文件的随机数池，这里我利用matlab产生1000个服从正态分布的随机数，10个一排，每两个数字之间间隔3个空格，行首3个空格存为文本文档，第一个数序号为0，然后按先行后列序号依次排列到999；其二和三分别是从随机数池中捞取随机数的函数类的.h文件和.cpp文件。
　　在捞取随机函数的函数类中，定义CStdioFile的file1，打开作为随机数池的txt文档。首先以时间作为种子，产生一个0－999的随机数，读取随机数池中从以这个值为序号的开始的数，直到读够所需的随机数组。序号如果超出数池的范围则跳到数池的开始，继续读取。
　　调用本函数类，需要输入int m_Collect_Times,double *a_Random,int m_Txt_Line,int m_Txt_Row,int m_Txt_Spacing分别代表取点个数、取得的随机数组的存储位置、随机数池行数、列数、数池中两数间空格个数。并将"C:\\Yg\\Debug\\ramdom1000txt"改为你的随机数池文件的位置，" "中的空格数改为你所使用的空格数。

下面为本函数类中的主要函数代码：

void CRandomArrayFromTxt::GetRandomArrayFromTxt(int m_Collect_Times,
double *a_Random,
int m_Txt_Line,
                                             int m_Txt_Row,
int m_Txt_Spacing)
{

    int m,mx,my,cl;   
    srand((unsigned)time(NULL));  // 生成时间种子
    m=rand()%m_Txt_Line;          // 返回一个0-m_Txt_Line-1的随机数,即查表的起始位置
    mx=m%m_Txt_Row;               // 查表起始位置的列号，文件头为0行0列
    my=m/m_Txt_Row;               // 查表起始位置的行号

    cl=(m_Collect_Times+mx-1)/m_Txt_Row+1;  // 需要从数表中读取的行数

    // 打开txt文本的数表。   
    CStdioFile file1( "C:\\Yg\\Debug\\ramdom1000.txt",
Cfile::modeNoTruncate | Cfile::modeRead | Cfile::typeText);


    CString strc;   
    int ct=0;  // 用于记录当前已经取得的随机数个数
    for(m=0;m<my;m++)
    {
        file1.ReadString(strc);
    }

    // 取出有用的行，直到取够为之
    for(int n=0;n<cl;n++)  
    {  
if(n+my==m_Txt_Line)
file1.SeekToBegin();

// 数表不够长，重新定位到文件头
file1.ReadString(strc);

         if(n==0) // 如果是取得的第一行
{
          int aw1,aw2;
         aw1=strc.GetLength();
         for(m=0;m<mx+1;m++)  // 过掉前面无用的空格
{
     aw1=strc.GetLength();
     aw2=strc.Find("   "; // 找到作为间隔的前三个空格所在位置
     strc=strc.Right(aw1-aw2-m_Txt_Spacing); // 取这三个空格右边的所有字符串
}

         // 下面取出剩下的字符串中每三个空格前面的字符串，就是所要查一个数据
for(m=0;m<m_Txt_Row-mx&&ct<m_Collect_Times;m++)  
{
              aw2=strc.Find("  ";// 找到作为间隔的后三个空格所在位置
              if(mx==m_Txt_Row-1||m==m_Txt_Row-mx-1)
a_Random[ct]=atof(strc);
     else
                  a_Random[ct]=atof(strc.Left(aw2)); // 保存数据到数组
     aw1=strc.GetLength();  
     aw2=strc.Find("   ";   // 找到作为间隔的前三个空格所在位置
     strc=strc.Right(aw1-aw2-m_Txt_Spacing); // 取这三个空格右边的所有字符串
     ct++;
}  
}
         else
         {
GetRandomArrayFromALine(strc,a_Random,
m_Collect_Times,
m_Txt_Row,
m_Txt_Spacing,
ct);
                 ct+=m_Txt_Row;
}  
    }
    file1.Close();
}

///////////////////////
// 从一行中取出数字
///////////////////////
void CRandomArrayFromTxt::GetRandomArrayFromALine(CString strc,
              double *a_Random,
     int m_Collect_Times,
     int m_Txt_Row,
     int m_Txt_Spacing,
     int ct)
{
    int aw1,aw2;
    aw1=strc.GetLength();
    aw2=strc.Find("   ";
    strc=strc.Right(aw1-aw2-m_Txt_Spacing); // 取这三个空格右边的所有字符串
    for(int m=0;m<m_Txt_Row&&ct<m_Collect_Times;m++)
    {
        aw2=strc.Find("   ";
        if(m==m_Txt_Row-1)
            a_Random[ct]=atof(strc);
else
            a_Random[ct]=atof(strc.Left(aw2));// 保存数据到数组
        aw1=strc.GetLength();
aw2=strc.Find("   ";// 找到作为间隔的前三个空格所在位置
        strc=strc.Right(aw1-aw2-m_Txt_Spacing); // 取这三个空格右边的所有字符串

oraclelang

Contents
  Introduction
  Path Scoring
  Summary of the A* Method


  Printable version
  Discuss this article




This article has been translated into Spanish and French. Other translations are welcome.

While it is easy once you get the hang of it, the A* (pronounced A-star) algorithm can be complicated for beginners. There are plenty of articles on the web that explain A*, but most are written for people who understand the basics already. This one is for the true beginner.
虽然掌握了A*（读作A-star）算法就认为它很容易，对于初学者来说，它却是复杂的。网上有很多解释A*的文章，不过大多数是写给理解了基础知识的人。本文是给初学者的。

oraclelang

This article does not try to be the definitive work on the subject. Instead it describes the fundamentals and prepares you to go out and read all of those other materials and understand what they are talking about. Links to some of the best are provided at the end of this article, under Further Reading.
本文并不想成为关于这个主题的权威论文。实际上它讨论了基础知识并为你做一些准备，以便进一步阅读其他资料和理解它们讨论的内容。本文的后面列出了几个最好的文章，在进阶阅读中。


Finally, this article is not program-specific

oraclelang

Finally, this article is not program-specific. You should be able to adapt what's here to any computer language. As you might expect, however, I have included a link to a sample program at the end of this article. The package contains two versions: one in C++ and one in Blitz Basic. It also contains executables if you just want to see A* in action.
最后，本文不是编程规范的。你应该能够改写这里的东西到任何计算机语言上。如你所期望的，同时，我包含了一个示例程序的链接，在本文后面结束的地方。这个程序包有两个版本：一个是C++，另一个用Blitz Basic语言编写。如果你只是想看看A*的行为，里面也含有可执行exe文件。


But we are getting ahead of ourselves. Let's start at the beginning ...

oraclelang

The first thing you should notice is that we have divided our search area into a square grid. Simplifying the search area, as we have done here, is the first step in pathfinding. This particular method reduces our search area to a simple two dimensional array. Each item in the array represents one of the squares on the grid, and its status is recorded as walkable or unwalkable. The path is found by figuring out which squares we should take to get from A to B. Once the path is found, our person moves from the center of one square to the center of the next until the target is reached.
你应该注意的第一件事是，我们把搜索区域分割成了方块的格子。简化搜索区域，如你目前完成的那样，这是寻路的第一步。这个特殊方法把搜索区域简化成了一个二维数组。数组的每一个项目代表了格子里的一个方块，它的状态记录成可行走和不可行走。通过计算出从A到达B应该走哪些方块，就找到了路径。一旦路径找到，我们的人从一个方块的中心移动到下一个方块的中心，直到抵达目标。

oraclelang

These center points are called "nodes". When you read about pathfinding elsewhere, you will often see people discussing nodes. Why not just refer to them as squares? Because it is possible to divide up your pathfinding area into something other than squares. They could be rectangular, hexagons, or any shape, really. And the nodes could be placed anywhere within the shapes ? in the center or along the edges, or anywhere else. We are using this system, however, because it is the simplest.
这些中心点称作“节点”。当你在其它地方阅读关于寻路时，你将经常发现人们讨论节点。为什么不直接把它们认为是方块呢？因为有可能你要把你的寻路区域以非方块的东西来分割。它们可能是矩形，六角形，或任何形状，真的。而节点可以放到形状内的任何位置。在中心，或者沿着边缘，或其它地方。然而我们使用这个系统，因为它最简单。

oraclelang

开始搜索Starting the Search
Once we have simplified our search area into a manageable number of nodes, as we have done with the grid layout above, the next step is to conduct a search to find the shortest path. In A* pathfinding, we do this by starting at point A, checking the adjacent squares, and generally searching outward until we find our target.
一旦我们把搜索区域简化成了可以管理的大量节点，就象我们上面所做的那样采用格子的布局，下一步就是引导一个搜索来找出最短路径。在A*寻路的做法，我们从开始点A做起，检查它周围的方块，并且向外普通的搜索，直到找到目标。


We begin the search by doing the following:
我们这样开始搜索：

oraclelang

Begin at the starting point A and add it to an "open list" of squares to be considered. The open list is kind of like a shopping list. Right now there is just one item on the list, but we will have more later. It contains squares that might fall along the path you want to take, but maybe not. Basically, this is a list of squares that need to be checked out.
从开始点A起，添加它到待考虑的方块的“开放列表”。开放列表有点象购物列表。此时只有一个项目在里面，但很快我们会得到更多。它包含了你可能取用的沿途的方块，也可能不用它。基本上，这是需要检查的方块的列表。

Look at all the reachable or walkable squares adjacent to the starting point, ignoring squares with walls, water, or other illegal terrain. Add them to the open list, too. For each of these squares, save point A as its "parent square". This parent square stuff is important when we want to trace our path. It will be explained more later.
观察开始点邻近的所有可到达或可行走的方块，忽略有墙，水或其他非法地形的方块。也把它们添加到开放列表。对每一个方块，保存A 点作为它们的“父亲”。这个父亲方块在跟踪路径时非常重要。后面会更多的解释。

Drop the starting square A from your open list, and add it to a "closed list" of squares that you don't need to look at again for now.
把开始方块A从开放列表中取出，并放到“封闭列表”内，它是所有现在不需要再关注的方块的列表。

oraclelang

At this point, you should have something like the following illustration. In this diagram, the dark green square in the center is your starting square. It is outlined in light blue to indicate that the square has been added to the closed list. All of the adjacent squares are now on the open list of squares to be checked, and they are outlined in light green. Each has a gray pointer that points back to its parent, which is the starting square.
在此，你应该有了类似下图的东西。在这个图中，中间的深绿色的方块就是开始方块。它有浅蓝色的外框，表示它被添加到封闭列表了。所有的相邻方块现在都进入要检查的方块的开放列表中了，它们有浅绿的外框。每一个都有灰色的指针指回它的父亲，它就是开始方块。

oraclelang

Next, we choose one of the adjacent squares on the open list and more or less repeat the earlier process, as described below. But which square do we choose? The one with the lowest F cost.
下一步，我们从开放列表中，选出一个相邻的方块，然后多多少少重复早先的过程，下面会说到。但是我们选择哪一个呢？具有最小F值的那个。