使用遗传算法进行简单寻路

仿照AI IN GAME里的例子写了一遍
程序下载
（note:编辑config.txt来编写地图，第一二行：长，宽，第三四行：出发点，目的地，其余：地图，1表示障碍物）
简单的寻路问题如下所述:
地图为有限大小的矩形,由小方格组成,其中一些小方格不可以通过,给它命名叫障碍点,给定起点和终点求解一条连接两点的路线

(不 通过障碍点).由于是简单的寻路问题,不要求找到最优解.设想一个实际情况就像一个人在走棋盘迷宫,每次只能走一步,只能往前后左右四个方向走，某些位置 上有障碍.给定一个目的地， 如果可达则给出一条通路.图论中有经典的算法解决这个问题，但是遗传算法为解决这个问题提供了一个新的思路，结合这两种方法可以在令人满意的时间内解决规 模较小的寻路问题。
现在来抽象这个问题。用一个二维数组表示地图
bool map[width][height];
true表示有障碍，false表示没有.
初始点和结束点为地图中的两个坐标.
vector2 src;
vector2 dst;
给定这三个条件的情况下求解此问题。
在这个问题中我们将染色体编码定义为每一步所走的方向，因为只有一个方向log2(4)=2位编码可以确定方向。
按染色体所指示的方向移动，生成一个群体，一代一代的选择。

(左图为初始地图，红色表示出发点和目的地，黑色表示障碍物，白色表示无障碍地区。)
(右图为结果图，灰色表示寻找到的路径）
实际上遗传算法为这种问题的求解提供了一种完全不同的思路，就是说与图论不同的思路。
而是把线路看作”基因”(Gene)，形成一个随机的初始解的群体（种群），然后像生物界里所进行的一样，基因杂交，编译，生物优胜劣汰，一代一代的自然选择，最后得到一个比较优的解。（实际上遗传算法不能保证一定可以找到最优解，甚至不能保证找到解）。

川历历汉阳树，芳草萋萋鹦鹉州

五一的最后一天跟lzc去黄鹤楼玩了一下，休息了一天，玩得很开心
中间还发生了一点小小的争论，现在想来论语心得里将人际关系还是很有道理的。不论怎样，友直，友谅，友多闻，益矣。
崔颢《黄鹤楼》
昔人已乘黄鹤去，此地空余黄鹤楼。
黄鹤一去不复返，白云千载空悠悠。
晴川历历汉阳树，芳草萋萋鹦鹉洲。
日暮乡关何处是？烟波江上使人愁。
然后就是贴照片了(lzc照相技术还是不错的，我就en..,呵呵)

(恶搞编钟，因为不喜欢上面的字）

Blog上贴代码的心得

Blog的sp们都没有为coder们提供特殊服务的意思，往上面贴个代码很是麻烦。因为HTML语言会忽略空格，所以排版是一团糟…

以前用csdn的blog还不错的，无奈太慢并且界面太死板。现在终于找到一种方法可以把代码像样得贴上去了。

从Visual Studio里直接拷贝是不行的，因为会加上很多换行，就是</bp>，而且格式通常会乱

这里使用cpp expert和word 2007

Cpp expert下载

Cpp expert是把C++代码转换为html，pdf等文档（还有图片）的工具，word 2007就更好了，附带了blog写作和管理功能。

1. 安装cpp expert.设置一下, tools->editor options->editor 把smart tab 和 use tab character 前面的勾去掉。Auto indent mode前面的勾也可以去掉
   
2. 把代码拷贝到cpp expert 左侧的编辑栏中，如果用Visual Studio 的话最好使用空格代替tab(设置方法如下，tools->options->text editor->C/C++->Tabs->Insert Spaces)
   
3. 点击右侧的save as html，保存为一份网页文件，这份文件里就已经没有多余的</bp>了。
   
4. 打开word 2007，新建博客文档，如果以前没有使用的话会提示输入用户信息和sp信息。用浏览器打开刚才的html文件，吧内容拷贝进来，发布…，完成了
   

以下是样例（我觉得效果还可以）

#include "stdafx.h"

#include "SmpWindow.h"



CAppModule _Module;



int WINAPI _tWinMain(IN HINSTANCE hInstance, IN HINSTANCE hPrevInstance, IN LPSTR lpCmdLine, IN int nShowCmd )

{

    _Module.Init(NULL, hInstance);



    SmpWindow wndMain;

    if( NULL == wndMain.CreateEx() )

        return 1;        // window creation failed

    wndMain.ShowWindow(nShowCmd);

    wndMain.UpdateWindow();



    MSG msg;

    while( GetMessage(&msg, NULL, 0, 0) )

    {

        TranslateMessage(&msg);

        DispatchMessage(&msg);

    }



    _Module.Term();

    return msg.wParam;

}

"null pointer assignment"的由来

很久以前见到过，当时不明白，看了《C专家编程》后明白了
Thanks to sendoh

"无效的指针可能成为程序员的噩梦，人们很容易用一个无效的指针来引用内存。在所有的虚拟内存结构体系里，一旦一个指针进行解引用操作时所引用的内存地址超出了虚拟内存的地址空间，操作系统就会终止这个进程。但MS-DOS并不支持虚拟内存，即使内存访问失败，它也无法立即捕捉到这种情况。
然而，在MS-DOS系统中可以动点小脑筋，在程序结束后检测解除引用空指针的情况，在Microsoft C和Broland C中都采取了这种方法。在进入程序之前，保存内存地址为零的（内存）的值。在程序结束时，系统检查这个地址的值与原来的是否相同。如果不同，基本上可以确定你的程序中使用了空指针来访问内存，运行时系统会打出一条"null pointer assignment"信息"。

更有趣的事情发生在《创世纪 VI》的一个副产品上，Saveage Empire。是《游戏编程全接触》的作者说的。在快要发布的时候屏幕上会打印"Error:(null)pointer assignment"，然而空指针很难被找出，于是这样修复了这个问题，用16进制编辑器修改了可执行文件中的这个文本串改为"Thanks for playing Savage Empire."。注意，它们是等长的...

Logger中操纵器的实现

代码下载
我突然想起 std::endl 这样一个东西,很想看看究竟它是怎么实现的.就像jjhou先生在<<stl 源码剖析>>中说的"under the hood".
endl的实现(Visual Studio 7.1版本):
代码下载
我突然想起 std::endl 这样一个东西,很想看看究竟它是怎么实现的.就像jjhou先生在<<stl 源码剖析>>中说的"under the hood".
endl的实现(Visual Studio 7.1版本):

_CRTIMP2 inline basic_ostream<char, char_traits<char> >&
    __cdecl endl(basic_ostream<char, char_traits<char> >& _Ostr)
    {    // insert newline and flush byte stream
        _Ostr.put('\n');
        _Ostr.flush();
        return (_Ostr);
    }

流的这一端:

    _Myt& operator<<(ios_base& (__cdecl *_Pfn)(ios_base&amp;))
{    // call ios_base manipulator
      (*_Pfn)(*(ios_base *)this);
      return (*this);
}

基本原理就是:
1.模板特化了operator<<的一个版本.
2.使用了访问者模式,最终endl调用的还是_Oster的成员函数.
应用到Logger上:

class Logger
{
public:
    typedef Logger& (*pfn)(Logger& );

    Logger& operator<<(pfn mani)
    {
        mani(*this);
        return *this;  
    }
    ......
};

Logger el(Logger& stream)
{
    stream << '\n';
    return stream;
}

测试一下:
P.S.把模板代码贴成html真是麻烦<要换成&lt;,>要换成&gt;,连&自己也要换成&amp;有没有简单点的办法...
测试一下:
Logger a;
a << 1 << el << std::string("(temp comment)") << el;
a << 1.001 << el << 't' << el;
a.Print();
system("PAUSE");