For Blog

A_star_algorithm.cs

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using QuickGraph; // グラフ構造を表現するためにQuickGraphを使う。このために、当ホルダ内の3つのdllを参照設定している

namespace Search
{
    public partial class Search : Form
    {
        //QuickGraphライブラリのBidirectionalGraphを使って問題を表現するグラフgを定義する
        BidirectionalGraph<Node, TaggedEdge<Node, int>> g = new BidirectionalGraph<Node, TaggedEdge<Node, int>>();

        //タグ付き辺を指定することで、このタグの中に辺の重みやゴールへの見積もりhなどを記述する。
        //頂点には、名前と評価関数ｈの値を入れる
        static Node vs = new Node("S", 100);
        static Node va = new Node("A", 7);
        static Node vb = new Node("B", 4);
        static Node vc = new Node("C", 6);
        static Node vd = new Node("D", 4);
        static Node ve = new Node("E", 2);
        static Node vf = new Node("F", 3);
        static Node vg = new Node("G", 0);
        static Node vh = new Node("H", 4);
        static Node vi = new Node("I", 2);

        //始点から終点に至る弧を作成。弧にはint型のタグとしてコストを入れる。
        TaggedEdge<Node, int> e1 = new TaggedEdge<Node, int>(vs, va, 1);//初期化の第3引数（ここでは１）がタグとして挿入した辺のコスト
        TaggedEdge<Node, int> e2 = new TaggedEdge<Node, int>(vs, vb, 3);
        TaggedEdge<Node, int> e3 = new TaggedEdge<Node, int>(va, vb, 1);
        TaggedEdge<Node, int> e4 = new TaggedEdge<Node, int>(va, vf, 6);
        TaggedEdge<Node, int> e5 = new TaggedEdge<Node, int>(vb, vc, 6);
        TaggedEdge<Node, int> e6 = new TaggedEdge<Node, int>(vb, vf, 6);
        TaggedEdge<Node, int> e7 = new TaggedEdge<Node, int>(vb, vh, 3);
        TaggedEdge<Node, int> e8 = new TaggedEdge<Node, int>(vc, vd, 5);
        TaggedEdge<Node, int> e9 = new TaggedEdge<Node, int>(vc, vh, 2);
        TaggedEdge<Node, int> e10 = new TaggedEdge<Node, int>(vc, vi, 4);
        TaggedEdge<Node, int> e11 = new TaggedEdge<Node, int>(vd, vi, 2);
        TaggedEdge<Node, int> e12 = new TaggedEdge<Node, int>(ve, va, 1);
        TaggedEdge<Node, int> e13 = new TaggedEdge<Node, int>(vf, ve, 7);
        TaggedEdge<Node, int> e14 = new TaggedEdge<Node, int>(vf, vh, 2);
        TaggedEdge<Node, int> e15 = new TaggedEdge<Node, int>(vh, vi, 1);
        TaggedEdge<Node, int> e16 = new TaggedEdge<Node, int>(vh, vg, 7);
        TaggedEdge<Node, int> e17 = new TaggedEdge<Node, int>(vi, vg, 5);
       
        List<Node> OPEN = new List<Node>();
        List<Node> CLOSED = new List<Node>();

        public Search()
        {
            InitializeComponent();
        }
        //問題グラフの作成
        private void button1_Click(object sender, EventArgs e)
        {
            //頂点の追加
            g.AddVertex(vs); g.AddVertex(va); g.AddVertex(vb); g.AddVertex(vc); g.AddVertex(vd);
            g.AddVertex(ve); g.AddVertex(vf); g.AddVertex(vg); g.AddVertex(vh); g.AddVertex(vi);
            //弧の追加
            g.AddEdge(e1); g.AddEdge(e2); g.AddEdge(e3); g.AddEdge(e4); g.AddEdge(e5);
            g.AddEdge(e6); g.AddEdge(e7); g.AddEdge(e8); g.AddEdge(e9); g.AddEdge(e10);
            g.AddEdge(e11); g.AddEdge(e12); g.AddEdge(e13); g.AddEdge(e14); g.AddEdge(e15);
            g.AddEdge(e16); g.AddEdge(e17);
            //グラフの印刷
            foreach (var vertex in g.Vertices)
                foreach (var edge in g.OutEdges(vertex))
                    Console.WriteLine(((Node)edge.Source).name + "-(" + edge.Tag.ToString() + ")->" + ((Node)edge.Target).name);
        }
        public void printList(string name, List<Node> list)
        {
            Console.Write(name + ": ");
            foreach (Node n in list) Console.Write(n.name + "(" + n.f + ") ");
            Console.WriteLine();
        }
        //Openリスト、Closedリストの印刷用
        public void printPath(Node start, Node goal)
        {
            Console.Write("ゴールへの道: " + goal.name + "<-");
            Node f = goal.father;
            while (f != start) { Console.Write(f.name + "<-"); f = f.father; }
            Console.Write(f.name + " \n");
            Console.WriteLine();
        }
        //Aアルゴリズムによるゴール探索を行う
        private void searchStart_Click(object sender, EventArgs e)
        {
            OPEN.Clear();
            CLOSED.Clear();

            OPEN.Add(vs);
            vs.g = 0;

            Node n;
            Node m;
            while (OPEN.Count != 0)
            {
                printList("OPEN  ", OPEN); printList("CLOSED", CLOSED); Console.WriteLine();
                n = OPEN.ElementAt(0); OPEN.RemoveAt(0);
                if (n == vg) { Console.WriteLine("成功"); printPath(vs, vg); return; }
                CLOSED.Add(n);
                foreach (var edge in g.OutEdges(n))
                {
                    m = (Node)edge.Target;//nを展開して子節点mを求める。
                    int f_m_n = n.g + edge.Tag + m.h;//子節点mについてf(m/n)=g(n)+Cn,m+h(m) を計算する。
                    //子節点mがOPENにもCLOSEDにも含まれていなければ
                    if (OPEN.Contains(m) == false && CLOSED.Contains(m) == false)
                    {
                        m.father = n;
                        m.f = f_m_n;
                        m.g = n.g + edge.Tag;
                        OPEN.Add(m);
                    }
                    //子節点mがOPENに含まれていて
                    if (OPEN.Contains(m) == true && f_m_n < m.f)
                    {
                        m.f = f_m_n;
                        m.father = n;
                        m.g = n.g + edge.Tag;
                    }
                    //子節点mがCLOSEDに含まれていてf(m/n)<f(m) ならば
                    if (CLOSED.Contains(m) == true && f_m_n < m.f)
                    {
                        m.father = n;
                        m.f = f_m_n;
                        m.g = n.g + edge.Tag;
                        OPEN.Add(m);
                        CLOSED.Remove(m);
                    }
                }
                //OPEN内の節点を評価値の小さい順に並べ替える。
                //下記の書き方はC#のListクラスに対するSortメソッドの呼び出し法による。
                OPEN.Sort(delegate(Node x, Node y)
                {
                    return (x.f - y.f);//Nodeのfの値の昇順でソート
                });
            }
            Console.WriteLine("失敗");
        }

    }
    //グラフの頂点
    public class Node
    {
        public string name;
        public int f;//探索上の評価関数ｆ
        public int g;//探索上の評価関数ｇ
        public int h;//探索上の評価関数ｈ
        public Node father;
        //頂点のコンストラクタ。
        public Node(string name, int h)
        {
            this.name = name;
            this.h = h;
            this.f = 0;
        }
    }
}