Standard A* Search Algorithm in C++

在看了NTU的AI课程之后,试着用C++来实现了A*搜索算法。它的思想就是Avoid expanding paths that are already expensive.。标准的A*搜索算法描述如下:

给出带权无向图,初始顶点,目标顶点,以及evaulation function。Evalutaion function包括

  • g(n):为到达顶点n,当前已有的花费(cost so far to reach n)
  • h(n):一个 从任意顶点 到 目标顶点 的估计花费(estimated cost to goal from n)
  • f(n):从 初始顶点 到 目标顶点 的估计花费(estimated total cost from the starting node to goal through n)

f(n) = h(n) + g(n)

 

例如有三个地点A, B, C,它们之间的图如下

A —— B —— C

A —— B权重为30,B —— C权重为40,

A —— C的直线距离为50,但是并没有A——C这条边(即不能直接从A开始,只经过一条边就到达C)

现在,给出初始顶点为A,目标顶点为C,h(n)如下

h(A) = 50

h(B) = 40

h(C) = 0

在一开始,我们将A放入名为froniter的优先队列中,froniter按照f(n)的值升序排序。

那么我们有f(A) = h(A) + g(A)。h(A)是由用户直接给出的,等于50。g(A)是我们为了到达C,已有的花费,在这个例子中,可以理解为已经走过的路程,因为我们是一开始就在A,还没有开始走,所以g(A)为0。于是f(A) = h(A) + g(A) = 50 + 0 = 50

froniter中的数据如下:

current from g(current) h(current)
A A 0 50

继续阅读Standard A* Search Algorithm in C++

A simple EventEmitter in C++

EventEmitter coming with node.js is handy most of the time, and I implement this useful utility in C++ after finishing writing Functor. Yes, we need Functor to make it much more easier to write this fabulous utility. (Why don't you use lamdba? I'll talk about that later in this post)

It's extremely simple to use EventEmitter in node.js

const EventEmitter = require('events');

class MyEmitter extends EventEmitter {}

const myEmitter = new MyEmitter();
myEmitter.on('event', () => {
    console.log('an event occurred!');
});
myEmitter.emit('event');

——https://nodejs.org/api/events.html

And the C++ version of EventEmitter need to be as easy as it is in node.js. As a matter of fact, this class made it.

#include <iostream>
#include <sstream>
#include <thread>
#include <vector>
#include "EventEmitter.hpp"

using namespace std;

class emitter : public EventEmitter {
};

int main(int argc, const char * argv[]) {
    emitter emitter;
    emitter.on("event", [&emitter](int data) {
        ostringstream osstream;
        osstream << "data: " << data << '\n';
        std::cout << osstream.str();
    });

    vector<thread> threads;
    for (int i = 0; i < 10; i++) {
        threads.emplace_back([&emitter, i]() {
            emitter.emit("event", i);
        });
    }

    for (auto &t : threads) t.join();
}

继续阅读A simple EventEmitter in C++

A simple EventEmitter in C++

node.js里面的EventEmitter非常好用,于是上次写完Functor之后,就顺理成章的写了这个EventEmitter,或者说,就是为了实现这个EventEmitter才写的Functor(后文会提到为什么要Functor,毕竟如果只看Functor本身的话,还不如直接用lamdba方便)。

在node.js中,使用EventEmitter非常简单,

const EventEmitter = require('events');

class MyEmitter extends EventEmitter {}

const myEmitter = new MyEmitter();
myEmitter.on('event', () => {
    console.log('an event occurred!');
});
myEmitter.emit('event');

——https://nodejs.org/api/events.html

那么现在这个C++版的EventEmitter也必须做到这样简单易用,事实上,它也的确和node.js的使用方式类似。

#include <iostream>
#include <sstream>
#include <thread>
#include <vector>
#include "EventEmitter.hpp"

using namespace std;

class emitter : public EventEmitter {
};

int main(int argc, const char * argv[]) {
    emitter emitter;
    emitter.on("event", [&emitter](int data) {
        ostringstream osstream;
        osstream << "data: " << data << '\n';
        std::cout << osstream.str();
    });

    vector<thread> threads;
    for (int i = 0; i < 10; i++) {
        threads.emplace_back([&emitter, i]() {
            emitter.emit("event", i);
        });
    }

    for (auto &t : threads) t.join();
}

继续阅读A simple EventEmitter in C++

Module Check——Usage of std::enable_if

最近写代码的时候,总能在不少STL的函数声明里看见可爱的std::enable_if,虽然自己偶尔用过,不过也只是直接用STL库里的std::is_arithmetic之类。

于是就去Google了std::enable_if,然后参考了如下几篇post,写了一个较为通用的Module Check。

所以还是先从一个小的问题开始讲起吧~

假设我们做了一个中间类作为接口,这个中间类有一个模版构造函数,它接受一个类实例和一个double类型的参数,并且总是调用一个固定的实例方法。

class Intermediate {
public:
    template <typename T>
    Intermediate(const T& object, double value) {
        object.method(value);
    }
};

现在我们有如下的类,

class A {
public:
    void method(double d) const {
        std::cout<<d<<'\n';
    }
};

class B {
public:
    void method(int i) const {
        std::cout<<i<<'\n';
    }
};

虽然如下代码可以编译运行,但是假如我们希望只有类A被这样调用才有效呢?

Intermediate inter_a_1(a, 2.33); // print 2.33
Intermediate inter_b_1(b, 2.33); // print 2

继续阅读Module Check——Usage of std::enable_if