言いたいこと

焼きなましをするときにはこんな感じにクラスを作ると個人的にいい感じでした:

主に以下の2つのクラスからなります:
- Stateクラス: 問題の状態を保持するクラスです。状態に関するクエリと状態を変更するためのコマンドのメソッドを提供します。問題によっては状態の一部を切り出して別クラスにしてそれを保持することもリマス。
- Neighborhoodクラス: 近傍操作を司る抽象クラスです。Stateクラスへのポインタを保持し、execメソッドで状態を変更・rollbackメソッドで状態の変更の取り消しを行います。具体的な近傍操作はNeighborhoodクラスを実装する形で作っていきます。

このようなクラス設計をすることで以下のようなメリットがあったと思っています:

関心ごとの分離
- Stateは状態に関するクエリと状態を変更するコマンドを提供し、Neighborhoodクラスはstateが提供するコマンドとクエリを使って近傍操作のロジックを実装する、というように役割を明確にできます。
  - Stateに近傍操作のロジックを持たせても良いのですが、気を抜いているとStateが際限なく膨れていき、どこに何があったかを理解するのに負荷が大きくなります。近傍操作を切り出すことでこれを防ぐことができます。
近傍操作をする際に状態管理の実装の詳細を隠蔽できる(これも関心ごとの分離の一種かも)
- 近傍操作のロジックはstateクラスのpublicメソッドを通じて状態を操作することになります。したがってStateがどのように状態を管理しているかを近傍操作をする際には気にする必要がなくなります。
- マラソンをやっていると状態管理の高速化がポイントになることが多いですが、状態管理を低レベルでどのようにやっているのか(例えば配列を使っているのか、bitを使っているのかなど)を近傍操作のロジックとは独立して変更することができます
近傍操作の選択やrollbackの記述をシンプルにできる
- 近傍操作を実装したクラスは全てNeighborhoodを実装しているので、ポリモーフィズムの恩恵を受けることができ、コードがシンプルにできます
場合によってはState部分には単体テストを入れてもいいかも
- マラソンマッチでバグりやすいのは状態管理のロジックだと思います。こういうところにテストが入れられると楽になりそう。
- 特にStateで外部に公開している部分(command, query)の外部から見た挙動は結構変わりにくいのではないかという気がします。内部的な実装が変わっても使い続けられるテストが書けるならテストを入れてしまっても良いような気がします。

批判・自分はこうやっているなどのコメントをお待ちしてます^^

実装紹介

Introduction to Heuristic Contestを例にとって実装を紹介したいと思います*1。

Submission #36086112 - Introduction to Heuristics Contest

Introduction to Heuristic Contestでのクラスたち

Scheduleクラス: コンテストのスケジュールを全体的に管理するクラス
- スケジュールの問い合わせ、スケジュールの変更・それにに伴うスコアの差分計算などを行う

class Schedule
{
private:
    vector<set<int>> contest_held_dates;
    void greedy_determine_schedule();
    int contest_remove_cumul_penalty_diff(int day, int contest);
    int contest_insert_cumul_penalty_diff(int day, int contest);

public:
    vec_int schedule;
    Schedule();
    void cout_ans(vec_int &_schedule);

    int score;
    int get_contest_at(int day) { return schedule.at(day - 1); };
    void set_contest(int day, int new_contest);
};

Neighborhoodクラス: 近傍操作のための抽象クラス

class Neighborhood
{
protected:
    Schedule *schedule;

public:
    virtual void exec() = 0;
    virtual void roll_back() = 0;
    virtual int score() = 0;
};

SingleContestExchangeクラス: 特定の日のコンテストをランダムに他のものに変更する

class SingleContestExchange : Neighborhood
{
private:
    // privateにはコンストラクタの他、rollbackで必要になる状態を保持しておく
    SingleContestExchange(Schedule *_schedule) { schedule = _schedule; };
    int day;
    int contest;
    int original_contest;

public:
    static Neighborhood *neighborhood;
    static Neighborhood *get_object(Schedule *schedule)
    {
        // Singletonパターン: パフォーマンスのためにオブジェクトを使いまわしたい
        if (neighborhood == nullptr)
        {
            neighborhood = new SingleContestExchange(schedule);
        }
        return neighborhood;
    };
    void exec();
    void roll_back();
    int score() { return schedule->score; };
};

Neighborhood *SingleContestExchange::neighborhood = nullptr;

void SingleContestExchange::exec()
{
    day = ro.get_rand(1, 366);
    contest = ro.get_rand(0, 25);
    original_contest = schedule->get_contest_at(day);
    schedule->set_contest(day, contest);
}

void SingleContestExchange::roll_back()
{
    schedule->set_contest(day, original_contest);
}

ContestPairSwapクラス: 2つの日を選択してコンテストを入れ替える

class ContestPairSwap : public Neighborhood
{
private:
    ContestPairSwap(Schedule *_schedule) { schedule = _schedule; };
    int day1;
    int day2;
    int contest1;
    int contest2;

public:
    static Neighborhood *neighborhood;
    static Neighborhood *get_object(Schedule *schedule)
    {
        if (neighborhood == nullptr)
        {
            neighborhood = new ContestPairSwap(schedule);
        }
        return neighborhood;
    };
    void exec();
    void roll_back();
    int score() { return schedule->score; };
};

Neighborhood *ContestPairSwap::neighborhood = nullptr;

void ContestPairSwap::exec()
{
    day1 = ro.get_rand(1, 366);
    day2 = ro.get_rand(max(1, day1 - day_diff), min(365, day1 + day_diff));
    if (day2 >= day1)
    {
        day2++;
    }
    contest1 = schedule->get_contest_at(day1);
    contest2 = schedule->get_contest_at(day2);
    if (contest1 == contest2)
        return;

    schedule->set_contest(day1, contest2);
    schedule->set_contest(day2, contest1);
}

void ContestPairSwap::roll_back()
{
    schedule->set_contest(day1, contest1);
    schedule->set_contest(day2, contest2);
}

近傍を選択する関数

Neighborhood *select_neighborhood(Schedule &schedule)
{
    float val = ro.get_float();
    if (val <= ratio1)
    {
        return SingleContestExchange::get_object(&schedule);
    }
    else
    {
        return ContestPairSwap::get_object(&schedule);
    }
}

焼きなまし部分

void annealing(
    Schedule &schedule,
    float time_ratio, int &count, int &best_score,
    float T0, float T1, vec_int &best_schedule)
{
    float start_time = get_time(false);
    float ct = start_time;
    float time_duration = TIME_LIMIT * time_ratio - start_time;
    int score = schedule.score;

    while (true)
    {
        if (count % 30 == 0)
        {
            ct = get_time(false);
        }
        if (ct > TIME_LIMIT * time_ratio)
        {
            break;
        }
        Neighborhood *neighbor = select_neighborhood(schedule); // 近傍をランダムに選択
        neighbor->exec(); // 近傍操作を実行
        int new_score = neighbor->score();
        int diff = new_score - score;

        if (( is_valid_transition(diff, ct, time_ratio, time_duration, T0, T1)))
        {
            if (best_score < new_score)
            {
                best_score = new_score;
                best_schedule = schedule.schedule;
            }
            score = new_score;
        }
        else
        {
            // 変更がリジェクトされたので、状態をロールバックする
            neighbor->roll_back();
        }
        count++;
    }
    cerr << "best_score:" << best_score << endl;
}

*1:このくらいの規模だったら特に設計とか考える必要はないと思いますが...

yunix_kyopro’s blog

焼きなましをするときの設計に関するメモ

言いたいこと

実装紹介