8-15 巡回セールスマン問題

問題

・ロンドン から パリ は 340Km
・ロンドン から マドリッド は 1270Km
・ロンドン から ローマ は 1450Km
・ロンドン から アテネ は 2400Km
・ロンドン から チューリヒ は 780Km
・パリ から マドリッド は 1060Km
・パリ から ローマ は 1120Km
・パリ から アテネ は 2100Km
・パリ から チューリヒ は 490Km
・マドリッド から ローマ は 1370Km
・マドリッド から アテネ は 2370Km
・マドリッド から チューリヒ は 1250Km
・ローマ から アテネ は 1040Km
・ローマ から チューリヒ は 700Km
・アテネ から チューリヒ は 1620Km

として順回路を求める。

ソース

using System;
using System.Linq;
using System.Collections.Generic;

class Program
{
    struct GraphDef
    {
        internal string FromPos;
        internal string ToPos;
        internal int Kyori;
    }

    struct JyoutaiDef
    {
        internal int Level;
        internal string GenzaiPos;
        internal string Path;
        internal int SumKyori;
    }

    static void Main()
    {
        var GraphArr = new GraphDef[15];
        GraphArr[0].FromPos  = "ロンドン"  ; GraphArr[0].ToPos  = "パリ"      ; GraphArr[0].Kyori  =  340;
        GraphArr[1].FromPos  = "ロンドン"  ; GraphArr[1].ToPos  = "マドリッド"; GraphArr[1].Kyori  = 1270;
        GraphArr[2].FromPos  = "ロンドン"  ; GraphArr[2].ToPos  = "ローマ"    ; GraphArr[2].Kyori  = 1450;
        GraphArr[3].FromPos  = "ロンドン"  ; GraphArr[3].ToPos  = "アテネ"    ; GraphArr[3].Kyori  = 2400;
        GraphArr[4].FromPos  = "ロンドン"  ; GraphArr[4].ToPos  = "チューリヒ"; GraphArr[4].Kyori  =  780;
        GraphArr[5].FromPos  = "パリ"      ; GraphArr[5].ToPos  = "マドリッド"; GraphArr[5].Kyori  = 1060;
        GraphArr[6].FromPos  = "パリ"      ; GraphArr[6].ToPos  = "ローマ"    ; GraphArr[6].Kyori  = 1120;
        GraphArr[7].FromPos  = "パリ"      ; GraphArr[7].ToPos  = "アテネ"    ; GraphArr[7].Kyori  = 2100;
        GraphArr[8].FromPos  = "パリ"      ; GraphArr[8].ToPos  = "チューリヒ"; GraphArr[8].Kyori  =  490;
        GraphArr[9].FromPos  = "マドリッド"; GraphArr[9].ToPos  = "ローマ"    ; GraphArr[9].Kyori  = 1370;
        GraphArr[10].FromPos = "マドリッド"; GraphArr[10].ToPos = "アテネ"    ; GraphArr[10].Kyori = 2370;
        GraphArr[11].FromPos = "マドリッド"; GraphArr[11].ToPos = "チューリヒ"; GraphArr[11].Kyori = 1250;
        GraphArr[12].FromPos = "ローマ"    ; GraphArr[12].ToPos = "アテネ"    ; GraphArr[12].Kyori = 1040;
        GraphArr[13].FromPos = "ローマ"    ; GraphArr[13].ToPos = "チューリヒ"; GraphArr[13].Kyori =  700;
        GraphArr[14].FromPos = "アテネ"    ; GraphArr[14].ToPos = "チューリヒ"; GraphArr[14].Kyori = 1620;

        var stk = new Queue<JyoutaiDef>();
        var AnswerList = new List<JyoutaiDef>();

        JyoutaiDef WillEnq;
        WillEnq.Level = 1;
        WillEnq.GenzaiPos = "ロンドン";

        for (int I = 0; I <= GraphArr.GetUpperBound(0); I++) {
            if (GraphArr[I].FromPos == "ロンドン") {
                WillEnq.GenzaiPos = GraphArr[I].ToPos;
                WillEnq.Path = "ロンドン" + "," + GraphArr[I].ToPos;
                WillEnq.SumKyori = GraphArr[I].Kyori;
                stk.Enqueue(WillEnq);
            }
        }

        int answerSumKyori = int.MaxValue;
        while (stk.Count > 0) {
            JyoutaiDef WorkJyoutai = stk.Dequeue();

            string wk = "," + WorkJyoutai.Path + ",";

            if (wk.Contains(",ロンドン,") && wk.Contains(",パリ,") &&
                wk.Contains(",マドリッド,") && wk.Contains(",ローマ,") &&
                wk.Contains(",アテネ,") && wk.Contains(",チューリヒ,")) {
                AnswerList.Add(WorkJyoutai);
                answerSumKyori = WorkJyoutai.SumKyori;
                continue;
            }

            if (WorkJyoutai.SumKyori > answerSumKyori) continue;

            WillEnq.Level = WorkJyoutai.Level + 1;

            for (int I = 0; I <= GraphArr.GetUpperBound(0); I++) {
                if (GraphArr[I].FromPos == WorkJyoutai.GenzaiPos) {
                    if (("," + WorkJyoutai.Path + ",").Contains("," + GraphArr[I].ToPos + ","))
                        continue;
                    WillEnq.GenzaiPos = GraphArr[I].ToPos;
                    WillEnq.Path = WorkJyoutai.Path + "," + GraphArr[I].ToPos;
                    WillEnq.SumKyori = WorkJyoutai.SumKyori + GraphArr[I].Kyori;
                    stk.Enqueue(WillEnq);
                }
                else if (GraphArr[I].ToPos == WorkJyoutai.GenzaiPos) {
                    if (("," + WorkJyoutai.Path + ",").Contains("," + GraphArr[I].FromPos + ","))
                        continue;
                    WillEnq.GenzaiPos = GraphArr[I].FromPos;
                    WillEnq.Path = WorkJyoutai.Path + "," + GraphArr[I].FromPos;
                    WillEnq.SumKyori = WorkJyoutai.SumKyori + GraphArr[I].Kyori;
                    stk.Enqueue(WillEnq);
                }
            }
        }

        int answerCnt = 0;
        foreach (JyoutaiDef each in AnswerList.OrderByDescending(X => X.SumKyori).ThenBy(X => X.Path)) {
            Console.WriteLine("answer{0} 距離は{1} 経路は{2}", ++answerCnt, each.SumKyori, each.Path);
        }
    }
}

実行結果

省略
answer114 距離は5090 経路はロンドン,パリ,マドリッド,ローマ,チューリヒ,アテネ
answer115 距離は4940 経路はロンドン,パリ,チューリヒ,ローマ,アテネ,マドリッド
answer116 距離は4860 経路はロンドン,パリ,チューリヒ,アテネ,ローマ,マドリッド
answer117 距離は4740 経路はロンドン,チューリヒ,パリ,マドリッド,ローマ,アテネ
answer118 距離は4560 経路はロンドン,マドリッド,パリ,チューリヒ,ローマ,アテネ
answer119 距離は4490 経路はロンドン,パリ,チューリヒ,マドリッド,ローマ,アテネ
answer120 距離は4390 経路はロンドン,パリ,マドリッド,チューリヒ,ローマ,アテネ

解説

幅優先探索で、その時点の解の中での最小距離を枝切り条件に使用してます。