孙亮 0206159.cs

java 实现最短路算法

using System;
using System.Collections.Generic;
using System.Text;



namespace 禁忌搜索算法
{
    public class Program
    {
        public const int ArrayLength = 5;  //定义常量，指定数组的长度
        public const int LargeMax = 1000000;  //定义常量，指定数组的长度
        public int RunSumTime = 0;

        public int[,] C_Array = new int[ArrayLength, ArrayLength] {{8,10,10,15,2},
                                                                   {14,21,17,10,2},
                                                                   {14,18,22,25,3},
                                                                   {16,19,20,24,2},
                                                                   {8,11,11,10,2}};
        public int[,] X_Array = new int[ArrayLength, ArrayLength] {{0,0,0,0,0},
                                                                   {0,0,0,0,0},
                                                                   {0,0,0,0,0},
                                                                   {0,0,0,0,0},
                                                                   {0,0,0,0,0}};
        public int[] H_Array = new int[ArrayLength * 10];
        public int RunTime;
        public Program()
        {
        }

        public void InitArray()
        {
            int Count = 0,i = 0, j = 0;
            bool flag = true;
            while (Count  < ArrayLength)  //1的个数
            {
                Random rd = new Random();
                int row = rd.Next(ArrayLength);
                int col = rd.Next(ArrayLength);

                for (i = 0; i < ArrayLength; i++)  //检测列
                {
                    if (X_Array[i, col] == 1)
                    {
                        flag = false;
                        break;
                    }
                }
                for (j= 0; j < ArrayLength; j++)  //检测行
                {
                    if (X_Array[row, j] == 1)
                    {
                        flag = false;
                        break;
                    }
                }

                if (flag)
                {
                    X_Array[row, col] = 1;
                    Count++;
                    
                }

                flag = true;
                               
            }

            


        }

        //根据两个数组计算其值
        public int CaltulatValueOfTwoArray(int[,] C_Array, int[,] X_Array)
        {
            int Z_Value = 0, i, j;
            for (i = 0; i < ArrayLength; i++)
                for (j = 0; j < ArrayLength; j++)
                {
                    if (X_Array[i, j] > 0)
                        Z_Value = Z_Value + C_Array[i, j];
                }

            return Z_Value;
        }

        //在指定的数组中搜索指定的值，判断其是否已经在数组中
        public bool SearchValue(int[] H_Array, int temp)
        {
            int i = 0;

            while (i < H_Array.Length)
            {
                if (H_Array[i] == temp)    //找到的情况
                    return true;
                i++;
            }

            return false;　　　　　　　　　//没有找到的情况

        }

        //在指定的数组中搜索最小的值
        public int GetMinValue(int[] H_Array)
        {
            int i = 0, Min;

            Min = H_Array[i];
            i++;

            while (i < H_Array.Length)
            {
                if (Min > H_Array[i])
                    Min = H_Array[i];
                i++;
            }

            return Min;　　　　　　　　　//没有找到的情况

        }

        public void PrintArray(int[,] X_Array)
        {
            for (int i = 0; i < ArrayLength; i++)
            {
                for (int j = 0; j < ArrayLength; j++)
                {
                    Console.Write("   "+X_Array[i,j].ToString());
                }
                Console.WriteLine();
            }

        }


        //对数组进行交换，根据给定的某行某列
        public int[,] ChangeArrayByCol(int[,] X_Array, int i, int j)
        {
            int[,] ArrayChanged = new int[ArrayLength, ArrayLength];
            int Col, Row, temp;

            for (Col = 0; Col < ArrayLength; Col++)  //从列开始循还
                for (Row = 0; Row < ArrayLength; Row++)
                {
                    if (Col == i)
                        ArrayChanged[Row, Col] = X_Array[Row, j];
                    else if (Col == j)
                        ArrayChanged[Row, Col] = X_Array[Row, i];
                    else
                        ArrayChanged[Row, Col] = X_Array[Row, Col];

                }

            return ArrayChanged;
        }


        public static void Main(string[] args)
        {
            int Firstchange, SecondChange, Temp;
            int Min = 1, Index = 0, MinValue;
            int[,] Temp_X_Array = new int[ArrayLength, ArrayLength];
             int[,] Temp0_X_Array = new int[ArrayLength, ArrayLength];
            int i, j;
           
            Program TestProgram = new Program();

            TestProgram.InitArray();
            Console.WriteLine("随机产生的初始矩阵为：");
            TestProgram.PrintArray(TestProgram.X_Array  );

            //while (true)
            //{ 
            
            Console.Write("禁忌搜索算法搜索步数     为：" );
            TestProgram.RunSumTime = Convert.ToInt32( Console.ReadLine());

                
               //清空参数 
                Index = 0;
                for (i = 0; i < TestProgram.H_Array.Length; i++)
                    TestProgram.H_Array[i] = Program.LargeMax;

                  TestProgram.H_Array[Index] = TestProgram.CaltulatValueOfTwoArray(TestProgram.C_Array, TestProgram.X_Array);
                  Min = TestProgram.H_Array[Index]-1;         
                  MinValue = TestProgram.GetMinValue(TestProgram.H_Array);

                 //开始禁忌
                  TestProgram.RunTime = 0;
                  while (TestProgram.RunTime < TestProgram.RunSumTime)//Min < MinValue
                　{
                    MinValue = TestProgram.GetMinValue(TestProgram.H_Array);

                   
                    for (Firstchange = 0; Firstchange < ArrayLength - 1; Firstchange++)   //判断交换的次数
                        for (SecondChange = Firstchange + 1; SecondChange < ArrayLength; SecondChange++)
                        {
                            Temp_X_Array = TestProgram.ChangeArrayByCol(TestProgram.X_Array, Firstchange, SecondChange);
                            Temp = TestProgram.CaltulatValueOfTwoArray(TestProgram.C_Array, Temp_X_Array);

                            if ((Min > Temp) && (!TestProgram.SearchValue(TestProgram.H_Array, Temp))) //表中没有，存该值           
                            {

                                Min = Temp;
                                Temp0_X_Array = Temp_X_Array;
                            }

                        }

                    TestProgram.X_Array = Temp0_X_Array;
                    Index++;
                    TestProgram.H_Array[Index] = Min;

                    TestProgram.RunTime++;
                　}

                 Console.WriteLine("禁忌搜索算法得到的最优目标值为：" + TestProgram.GetMinValue(TestProgram.H_Array).ToString());
               // Console.WriteLine("禁忌搜索算法搜索次数为：" + TestProgram.RunTime.ToString());
                Console.WriteLine("禁忌搜索算法得到最优解矩阵形式为：");
                TestProgram.PrintArray(TestProgram.X_Array);
            //}


        }
    }
   
}