ベルマンフォード法について

間違ってたら教えてください。

ベルマンフォード法はいつ使うの?

負の大きさの辺を含んでも良いグラフについて、単一始点最短経路問題をとくアルゴリズムです。

計算量はO(VE)で、ダイクストラ法よりも遅いですが、ダイクストラ法はグラフが負の大きさの辺を含む場合には正しく動作しないので、負の大きさの辺を含む時に代わりに使うのに便利です。

どんなアルゴリズム?

その前に....

定義の説明と前提

・記号について

この記事では。グラフG=(V,E)が与えられた時、v∈Vについて、始点sからvまでの暫定の最短距離をv.d、暫定の最短路上でのvの先行点をv.πと表す。

※先行点:v1->v2のように頂点v1,v2がつながってる時,v2の先行点をv1という。ここから最短経路を復元する。

・緩和(relaxtion)

辺(u,v)の緩和はuを経由することでvへの基地の最短路を改善できるか否か判定し、改善できるならばv.dとv.πを更新すること。

要は最短経路を更新するってことだと思います。

・最短路は閉路を含まない

・負の閉路の時

負の閉路を回ることを繰り返せば、いくらでも小さい重みを持つ道を構成できるので、この実装においては不適とします。
ベルマンフォード法では、負の閉路の存在を検出できます。

・正の閉路の時
これは一般に成立します。

ある最短路cが正の閉路を含むと仮定すると、その正の閉路を取り除くことで、最短路を改善することができるので、cが最短路であることに矛盾。
故に最短路が正の閉路を含むことはない。

どんなアルゴリズム?

グラフG=(V,E)について、すべての辺を|V|-1回緩和すれば、最短路がわかるというアルゴリズムです。

なぜ、高々|V|-1回緩和すれば最短路がわかるかというと、最短路は閉路を含まないので、最短路は高々|V|-1本の辺で構成されるからです。

この問題をテストケースにしてください。
onlinejudge.u-aizu.ac.jp

サンプルソース

汚いソースコードで申し訳ないです...
C++14で動作します。上記の問題の解法となります。

#include <bits/stdc++.h>
using namespace std;
///////////////////////////////////////////
const long long int INF = INT64_MAX;
using ll = long long int; 
using Vi = vector<long long int>;
#define pb(x) push_back(x)
#define rep(i,N) for(ll i=0;i<N;i++)
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return true; } return false; }
void princ(auto x){cout<<x<<" ";}; void print(auto x){cout<<x<<"\n";};
///////////////////////////////////////////////////////////////////////////////////

ll v,e,r;

struct edge{/*重み付き,有向*/
    int to , cost;/*toは接続先*/
    edge(ll to_ ,ll cost_ = 1){ to=to_; cost=cost_; };/*全てのcost=1 <=> 無向グラフ*/
};
bool operator<(edge e1 ,edge e2){return e1.cost < e2.cost; }
bool operator>(edge e1 ,edge e2){return e1.cost > e2.cost; }
using graph =  vector< vector<edge> >;
bool ch_min(graph &g,ll j,ll k,Vi &dist,Vi &from){//頂点jから出るk番目の辺の緩和
    if(chmin(dist[g[j][k].to],dist[j] + g[j][k].cost)){
        from[g[j][k].to]=j;
        return true;
    }
    return false;
}
bool bellman_ford(graph &g,Vi &dist,Vi &from,ll source){//distは最短距離,fromは先行点
    bool flag = false;
    ll siz_ = g.size();
    dist.resize(siz_); from.resize(siz_);
    rep(i,siz_)dist[i]=INF;
    dist[source]=0;
    from[source]=-1;
    rep(i,siz_)rep(j,siz_)rep(k,g[j].size()){
        if(dist[j]!=INF)if(ch_min(g,j,k,dist,from) && i==siz_-1){//chminは<(<=はだめ)
            flag = true;
        }
    }
    return flag;
}

graph gg;
Vi dis,from;


int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    cin>>v>>e>>r;
    ll s,t,d;
    gg.resize(v);
    rep(i,e){
        cin>>s>>t>>d;
        gg[s].pb(edge(t,d));
    }
    if(bellman_ford(gg,dis,from,r)){
        print("NEGATIVE CYCLE");
    }else{
        rep(i,dis.size()){
            if(dis[i]!=INF)print(dis[i]);
            else print("INF");
        }
    }
    return 0;
}

【WRM007】Aquilaのソースコード

アルゴリズム部分だけです。

個人的には探索アルゴリズムに関しては他のどのチームにも劣らなかったと思っています。
(異論は認めます.)

ソースコード

Aquila-2019/Src/source at master · rakuseirobot/Aquila-2019 · GitHub

　↑　ここの data_structure.hpp & .cpp 、core.hpp & .cpp 、 iris.hpp & .cpp　にあります。

・iris.hpp & .cpp以外は単体で動作します。(テスト済み)
・実際の迷路探索はiris.cpp内の_h_stack_dfs();で動作します。
・ご自由にお使いください。
・わからないことがあればEmileに連絡お願いします。(Twitter等で.)
・多分バグが残ってます。

プログラムの設計スタイルについて

data_structureでデータ構造を定義して、coreでそれらを一つに管理しています。

そして、irisでI/Oを管理しています。

Mappingは重み無し無向グラフ (by自己参照構造体)で、nodeという名前です.(data_structureの中です)
そのnode内にAVLtreeを絡めてます.

関数の仕様について

マッピング用の自己参照構造体及び付随する関数

struct node{
     uint8_t x=100,y=100,z=10;//coordinate
     uint8_t flag,type;//for bfs, search 
     uint8_t color;//for 'real' bfs
     uint8_t depth=255,dist=255;//
     bl ac=false;//already checked?
     node* next[4]={np}; // 4neighborhood
     node* back=np; //backtrack (unused)
     node* child[2]={np,np};//AVLtree
     uint8_t height=0; //AVLtree
};

typeはそのマスのタイプです。
例えば、被災者(熱源)がいる、黒タイル、何もない、等..

それらを以下のようなクラスに一括で管理しています。

class core{
    node* now;
    node* start;//it may be unnecessary.But now, it is used in dfs.
    int dir;//0::<,1::^,2::>,3::v
    //for status
    node* ans;//dfs's answer.
    int flg;//0 or 1
    //for dfs
    queue q;//for bfs
    node* pre;//一つ前の頂点
public:
    bool blk_tile;
    AVLtree at;//avltree
    nodes mall;//newの代わり
    stack stk;//改造stack
    node* start_f[20];//間に合わず
    core();
    void turn_r();//map上で右回転
    void turn_l();//map上で左回転
    void w_now(node* u);//現在地書き込み
    int r_flg();//現在のflgの取得(map内の探索flg)
    node* r_now();//現在地取得
    node* r_start();//スタート地点取得
    node* r_pre();//移動前のnodeの取得
    void dfs(node* t,int x,int y,int z,int depth);//map内DFS(内部実装)
    node* find(int x,int y,int z);//map内探索クエリ
    void ins_node(node* x);//AVLtreeに挿入
    void cn_graph(node* v, node* u);//(node)vとuを接続
    void cn_tree(node* par,node* v);//node->backに関して接続
    void ap_node(node* t,int dire);//頂点追加クエリ
    node* ac_next(node* t,int now_dir,int dire,int dist);//頂点取得クエリ(内部)
    node* ac_next(int dire,int dist);//頂点取得クエリ
    bl ck_conect(node* s,node* t);//接続確認クエリ
    void go_st();//map内前進
    void cl_dist(node* t,int d);//頂点に書き込まれた距離のクリア(内部)
    void clear_dist();//頂点に書き込まれた距離のクリア
    void bfs(node* s,node* t);//map内bfs(距離算出用)

    /*ここからはDPの実装*/
    bool hamilton;//trueならans_vとvertex_size見て,最適化
    bool now_hami;//いま最適化されてるか?
    stack ans_v;//最適化された頂点集合
    node* vertex[M_V_SIZE+2];//vertexs
    int8_t vertex_size;
    //v[i]->v[i-1]->...(i=|v|,|v|-1,,1,0)
    uint8_t dist[M_V_SIZE+2][M_V_SIZE+2];
    //dist[s][t]:=distance(s->t)
    uint16_t dp[1<<(M_V_SIZE+2)][M_V_SIZE+2];//memo化
    //集合(set)のiで終わる最短ハミルトン路の長さを算出
    //ただし、始点v[0]と終点v[vertex_size]は固定
    //dp[(set)][i] :=ans(dp_calc)
    int8_t prev[1<<(M_V_SIZE+2)][M_V_SIZE+2];//backtrack
    //prev[(set)][i]:~dp[(Set)][i]の解をとる時の,前の頂点
    node* vertex_calc(int set,int i,int v_size);//内部実装
    bool dp_init();//頂点集合初期化及び最適化条件に合致するか判定
    bool dp_calc();//最適化
};

探索用関数

気が向けば書きます。が、受験生なので許して...

RCJerには見慣れない(かもしれない)アルゴリズム(DP等)を利用していますので、

読みにくいかもしれません。見る人がいれば頑張ってください。

Twitterで聞いて下さったら答えます。

もしこの技術が誰かの役に立つならうれしいです

WRM007 Aquila アルゴリズム解説

目次

※ここからは、頂点の数はV,辺の数はEとする.(頂点=Vertex,辺=edge)
また大会の終了後にソースコードを公開する予定にしている.

マッピング

30cm*30cmのマスを1つの頂点として重み無し無向グラフ(unweighted graph)を構築し、
それを地図としている.(※グラフの構築方式は構造体を連結する連結リスト方式.)
しかし、ナイーブなグラフの実装では頂点の存在判定の時間計算量はO(E)となってしまうので、
別にAVLtree(平衡2分探索木)を構築し、計算量をO(log V)程度まで改善した.
これらの2つの構造と現在のロボットの向き、その他内部での探索に必要なパラメータを
1つのクラスに集約して管理することで、単純さを保っている.
また、
地図となるグラフ上での最短距離をBFSを用いて算出し、後述の頂点間移動を最適な物にしている.
具体的に言うと、単一始点最短経路問題(Single Source Shortest Path problem)を解いている.
(※BFSは、グラフの任意の辺の重みが等しいと見なせることから、ダイクストラ法を適用しているのと同じと見なせる.
(∵全ての重みが同じ集合の要素をpriority queueから取り出すのは、
queueからその集合の要素を取り出すのと同じ.)　
実は、ダイクストラ法は最良優先探索(Best-First-Search)と呼ばれる、BFSを拡張した問題のクラスに所属している. )

・AVLtree(Adelson-Velskii and Landis'tree)とは
任意のノードについて、
そのノードの左右の部分木の高さの差が1以下という条件を満たす2分探索木の事である.
探索に費やす時間計算量はO(log |V|)である.
多くの場合、1.挿入　2.削除　3.探索　の3つのクエリに答えるように実装するが、
このロボットのプログラム中では削除クエリは実装していない.
また挿入クエリにおいて、挿入されたノードについて、
左右の部分木の高さの差が1よりも大きくなると木を回転させることで
上記の条件を満たすようにしている.
詳しい説明はこのロボットの本質ではないので省略する.(木の回転が非常に可愛いので必見である!)
またAVLtreeを選択したのは,
挿入クエリよりも探索クエリの方がはるかに高頻度であり、挿入された順だと,ソート済みの列を挿入するのに近い動作をすることになり、
B木では平衡構造が崩れやすく、逐次的に探索する事が予想されることから、
SplayTreeも適切ではないと考えられたからである. (∵ノード移動時に毎回探索している)

(改良)深さ優先探索(DFS)

深さ優先探索(Depth-First-Search)とは
　訪問したい頂点をstack(Last In First Out)に積み、それを順に訪れる探索手法である.
　一般にグラフをDFSする事で、そのグラフの持つ性質を明らかにできる事がある.
(ex.有向グラフ中での強連結成分分解,木判定 等)
また、時間計算量はO(E)である.
実装は再帰を用いるのが最も簡単であろう.(∵マイコン上での再帰は関数の処理"stack"に搭載される)

※幅優先探索(Breadth-First-Search)とは
　DFSと違って、こちらは訪問したい頂点をqueue(First In Fast Out)に積むという点が違う.
　こちらも時間計算量はO(E)である.
　だが、DFSと最も大きな違いとなるのはBFSは解の発見時の、
(探索の起点となる頂点からの)解の深さが最短になるということである.
　このロボットではこの性質を用いて,頂点間の移動を最適化している.

訪問したい頂点を単一のstackに管理し、順に訪問している.
ほとんどナイーブなDFSであるが、stack内の頂点の順を工夫(☆)している.
左手法よりもmappingの実現という点を除けば単純であり、全探索が保証されるので、
DFSを選択した.

☆stack内の頂点の最適化について------------------------------------------------
最短ハミルトン路問題と呼ばれる問題を解いている.
これは、頂点集合に含まれる全ての頂点を通るような最短の道を求める組み合わせ最適化の問題である.
実際の実装では、始点を現在地に、終点をスタート地点におき、
動的計画法(Dynamic Programming)により、
・dp[S+{u}][u] = min(dp[S][t] + dist[t][u]) ....(※)
　　という漸化式を解くことで実現している.(細かく詰めると,bitDPの配るDPである)
※dp[S][t]は頂点集合Sに含まれる頂点をすべて通り、かつ頂点tで終わるような最短の道の長さを表す.

動的計画法が使用できるのは、
・部分構造最適性(部分問題も同じ最適化問題であり,その問題同士が独立している事.
これによって解を結合していく事で解が作られる.)
・部分問題重複性(同じ部分問題が何度も出現する事.解を保存しておくことで計算を高速化する(メモ化という).)
の2つをこの問題が満たすからである。

また、頂点集合は元のstack内の配列をコピーし、"添え字集合"のようにして、2進数で表現している.
(ex. 0100:={2} , 0001:={0})

細かい工夫と苦労した事

①細かい工夫
アルゴリズム関連の実装部分については、移動に関連する手続きは、
全て頂点間の移動によって表現した.
そうすることで抽象性が上がり、より一般的で強力な概念の導入が容易になるからである.
(勿論抽象性が高い方がバグも少なく、多くの人間にとって分かり易いという利点もある.)
その実装をC++風のコードにより以下に示す.

struct node{
int x,y,z;
node* next[4];//その頂点の4近傍を配列に管理.
int dist;//bfsにより算出された頂点間距離は全て頂点中に保存し、管理.
int flag;//現在の探索において、訪問済みか否か.
/*実際のコードは一連の大会の終了後に公開する事を計画している.実際のコードを単純化している.*/
}

move_four_n(node* s){//s∈{現在地のnodeの4近傍}
/*現在地のnodeの4近傍への移動を表現.*/
/*全ての方向について逐次判定し、移動するとループから抜ける.*/
/*現在地のnodeのアドレスもここで変更される.*/
}

move_vertex(node* t,node* s){/*頂点tから頂点sへの移動*/
bfs(s,t);/*sをrootとして、tを幅優先探索する.*/
node* now = /*現在地のノード*/;
while(now != s){
for(int i=0;i<4;i++){
if(now->next[i]->dist < now->dist){
move_four_n(now->next[i]);
break;
}//これは、現在のnodeより1node分近い頂点が存在すれば、それが最短に確定するからである.(背理法で示される.・・・☆)
}
}
}
///////////////////////////

(☆の証明)
bfsの探索の起点となるnodeをsとし、現在のnodeをnowと表現する.(now≠s,s:=const.)
また、頂点s、頂点u間の距離をsからuへの最短経路に含まれる辺の数とし、
これをdist(u)と表す事にする.(dist(u)∈ℤ)

dist(u) < dist(now) - 1 となるuの存在を仮定し、それをrと置く.(ただし,頂点rは頂点nowの4近傍に含まれる)
この時、rはnowの4近傍に含まれるから、rはnowに隣接する.

つまり、dist(now) = min(dist(r)+1) (r∈nowの4近傍)をふまえて、
dist(r)が最小となるr=r1(r∈nowの4近傍)と置くと、
dist(r1) + 1 = dist(now) であるから、
dist(r1) <= dist(r) (r∈nowの4近傍)と合わせて、
dist(now) <= dist(r) + 1 (r∈nowの4近傍)を満たす.
これは仮定に反する.

ゆえに、示された. //

②苦労した事
・C++のnew,deleteが使えなかったので、
配列を用意してそこから取り出していかなくてはならなかった事.
・(PC上で動かすプログラムと違って)非常に副作用が多い事.
・AVLtreeの実装.
・アルゴリズムの動作確認.
・バグの発生時にメモリを読まなくてはならない事.

アルゴリズムに触れる方法

このパネルを読む人の多くは相当にアルゴリズムの知識を持っていると思われるが、
弊校の後輩や、来年度以降にこの競技に参加したいと考える方のために記しておく.
(1)本(又は記事)を読む.(場合によっては証明をなぞる)
(2)具体例を出して、その手法の動作を自分の手で確かめる.(イメージを掴む)
(3)実装する.
の順にやると理解しやすい傾向にあると私は考える.(人によって良い方法は変わると思う)
「アルゴリズムクイックリファレンス」、「アルゴリズムイントロダクション(1巻,2巻)」等の書籍が分かりやすいかもしれない.

〇実現できなかったアイデアについて.)

・経路修正
紙面上の実験では、周囲3*3ブロック分の地形が一致すれば,
uniqueに頂点が定まる気がするが,状況によるので何とも言えない.
・A*のようなゲーム木の探索
迷路の探索状況をゲームの盤面とみなして、盤面評価関数を作成する.
そして、ゲーム木を探索する.これがうまくいけば、非常に効率の良い結果が得られるであろうが、
1.盤面のサイズ
2.評価関数の調整
が非常に難しいし、平均的にみて性能が良い手法と断言する事は非常に難しい.
・被災者が存在するブロック,又は,開始地点のブロックのみを頂点とし、
他は全て辺とする重み付きグラフを構築する.
これは組み込みの側との兼ね合いが非常に難しい上に、実装にも困難が伴うが、
思考的な面では、より簡潔に考える事ができると思われる.

ここまで読んでくださってありがとうございました.
そして、関係者、運営の皆様、今までと今のチームメイトの友人達、6年間ありがとうございました.