FPGA開発日記

カテゴリ別記事インデックス https://msyksphinz.github.io/github_pages , English Version https://fpgadevdiary.hatenadiary.com/

おねえさんの問題を解いてみる

超高速グラフ列挙アルゴリズム?〈フカシギの数え方〉が拓く,組合せ問題への新アプローチ?

超高速グラフ列挙アルゴリズム?〈フカシギの数え方〉が拓く,組合せ問題への新アプローチ?

www.youtube.com

せっかく買ったので、夜を徹する覚悟で読み始めたのだが、いきなり詰まった。プログラムを書いてみようと思って、C++でいじいじしていたらもう朝になりかけている...実装能力無いなあ。。。

#include <iostream>
#include <list>
#include <vector>
#include <utility>
#include <stdlib.h>
#include <sys/time.h>

typedef std::pair<int, int> cood_pair;

bool find (int x, int y, std::vector<cood_pair *> *visited);
int combination (int size, int x, int y, std::vector<cood_pair *> *visited);
std::vector<cood_pair *>* copy_vector (std::vector<cood_pair *> vector);


double get_dtime(void){
    struct timeval tv;
    gettimeofday(&tv, NULL);
    return ((double)(tv.tv_sec) + (double)(tv.tv_usec) * 0.001 * 0.001);
}


int main (int argc, char *argv[])
{
    if (argc != 2) {
        std::cerr << "Usage: " << argv[0] << " size\n";
        exit (EXIT_FAILURE);
    }
    int size = atol (argv[1]);

    std::vector<cood_pair *> *visited = new std::vector<cood_pair *>;

    double d0, d1;
    d0 = get_dtime ();
    int ret = combination (size, 0, 0, visited);
    d1 = get_dtime ();
    std::cout << "Elapsed = " << (d1 - d0) << "\n";

    // std::cout << "Ret = " << ret << "\n";
}


bool find (int x, int y, std::vector<cood_pair *> *visited)
{
    std::vector<cood_pair *>::iterator it = visited->begin();
    while (it != visited->end()) {
        if ((*it)->first == x && (*it)->second == y) {
            return true;
        }
        it++;
    }
    return false;
}


std::vector<cood_pair *>* copy_vector (std::vector<cood_pair *> *vector)
{
    std::vector<cood_pair *> *copy_visited = new std::vector<cood_pair *>;
    std::copy(vector->begin(), vector->end(), back_inserter(*copy_visited));
    return copy_visited;
}


int combination (int size, int x, int y, std::vector<cood_pair *> *visited)
{
    if (x < 0 || y < 0) {
        return 0;
    } else if (x >= size || y >= size) {
        return 0;
    } else if (x == (size-1) && y == (size-1)) {
        return 1;
    }

    if (find (x, y, visited)) {
        return 0;
    }

    cood_pair *new_xy = new cood_pair(x, y);
    visited->push_back (new_xy);

    int count = 0;

    std::vector<cood_pair *> *copy_visited;

    copy_visited = copy_vector (visited);
    count += combination (size, x    , y - 1, copy_visited);
    delete copy_visited;

    copy_visited = copy_vector (visited);
    count += combination (size, x - 1, y    , copy_visited);
    delete copy_visited;

    copy_visited = copy_vector (visited);
    count += combination (size, x + 1, y    , copy_visited);
    delete copy_visited;

    copy_visited = copy_vector (visited);
    count += combination (size, x    , y + 1, copy_visited);
    delete copy_visited;

    return count;
}

f:id:msyksphinz:20150711033332p:plain

このアルゴリズムの基本は、一度辿った線は二度と辿れないという方式だが、線を隣接する点に置き換えて、二度同じ点を辿れない探索のアルゴリズムとして実装することができる。

とりあえず実装してみたが、正しく出来てそうだ。計測時間は以下のとおり。まあ予想どおり、サイズが増えるごとに酷く探索範囲が広くなる。

size time
1 0.00
2 1.19209e-06
3 0.000251055
4 0.00627494
5 0.641955
6 163.631