travelingshop_unit.pas

本源码是一个算法

//----------------------
//单元名  ：TravelingShop_Unit
//功能    ：货郎担算法类
//创建时间：2003.12.31
//作者    ：zbird
//E-Mail  :[e-mail]
//----------------------
unit TravelingShop_Unit;

interface

uses
  Graphics, SysUtils, Classes, Inc, Dialogs;

//定义城市纪录
type
  TCity = record
    X: integer;
    Y: integer;
  end;

//TTravelingShop类
type
  TTravelingShop = class
  private
    Cities: array of TCity;             //城市数组 [1..x]
    CitiesDistance: array of array of real; //各个城市间的距离[1..x, 1..x]
    CitiesToured: array of integer;     //是否已经遍历过
    CityNumber: integer;                //城市的数目
    ShortTestLength: real;              //“最短”路径的长度
    ShortestDistance: array of real;    //最短路径
    TouredLength: real;                 //已经走过的距离
    //获取两个城市之间的距离
    function GetDistance(a_ACity, a_BCity: TCity): real;
    //生成距离矩阵
    procedure GetAllDistance;
    //遍历城市
    procedure GoThroughCities(a_TempPath, a_CitiesToured: array of integer; a_CitiesNum:
      integer);
    procedure DrawRoad;
    procedure DrawCities;
    procedure GetShortestDistance;
  public
    ShortTestPath: array of integer;    //“最短”路径
    Canvas: TCanvas;
    constructor Create(a_Number: integer; a_Canvas: TCanvas); //构造函数
    destructor Destroy;
    procedure CreateCities;             //生成城市
    procedure FindShortTestPath;        //寻找最短路径
    procedure Draw;                     //对画布进行重画
  end;

implementation

{ TCity }

//生成城市
procedure TTravelingShop.CreateCities;
var
  i, j, TempWidth, TempHeight: integer;
begin
  Randomize;                            //为生成随机数作准备
  //生成各个城市节点
  for i := 0 to CityNumber - 1 do
  begin
    Cities[i].X := Random(g_Width);
    Cities[i].Y := Random(g_Height);
  end;
  GetAllDistance;
  GetShortestDistance;                  //“最短路径”列表
  DrawCities;                           //绘制城市
end;

//获得两个城市之间的距离
function TTravelingShop.GetDistance(a_ACity, a_BCity: TCity): real;
begin
  Result := Sqrt(Sqr(a_ACity.X - a_BCity.X) + Sqr(a_ACity.Y - a_BCity.Y));
end;

//获得各个城市之间的距离
//并将其添加到数组CitiesDistance[]；
procedure TTravelingShop.GetAllDistance;
var
  i, j: integer;
begin
  //A->B的距离
  for i := 0 to CityNumber - 2 do
  begin
    for j := i to CityNumber - 1 do
    begin
      CitiesDistance[i, j] := GetDistance(Cities[i], Cities[j]) //两点之间的距离；
    end;
  end;
  //B->A的距离
  for i := 0 to CityNumber - 2 do
  begin
    for j := i to CityNumber - 1 do
    begin
      CitiesDistance[j, i] := CitiesDistance[i, j]; //两点之间的距离；
    end;
  end;
end;

//好像用处不大
procedure TTravelingShop.GetShortestDistance;
var
  i, j, k, x, ti, tj: integer;
  TempDis: real;
begin
  ShortestDistance[0] := 0;
  x := 0;
  for i := 0 to CityNumber - 1 do
    for j := i + 1 to CityNumber - 1 do
      begin
        x := x + 1;
        if CitiesDistance[i, j] <> 0 then
          ShortestDistance[x] := CitiesDistance[i, j]
        else
          ShortestDistance[x] := 10000;
      end;

    for i := 1 to CityNumber do
      for j := i + 1 to x do
      begin
        if (ShortestDistance[i] > ShortestDistance[j]) then
        begin
          TempDis := ShortestDistance[i];
          ShortestDistance[i] := ShortestDistance[j];
          ShortestDistance[j] := TempDis;
        end;
      end;

  for k := 0 to CityNumber do
    ShortestDistance[k + 1] := ShortestDistance[k] + ShortestDistance[k + 1];
end;

//绘制城市
procedure TTravelingShop.DrawCities;
var
  i: integer;
  Color: TColor;
begin
  //清空画板先
  Canvas.FillRect(Canvas.ClipRect);
  for i := 0 to CityNumber - 1 do
  begin
    Color := Canvas.Brush.Color;
    Canvas.Brush.Color := clYellow;
    Canvas.Ellipse(Cities[i].X - g_CitySize, Cities[i].Y - g_CitySize, Cities[i].X +
      g_CitySize, Cities[i].Y + g_CitySize);
    Canvas.Brush.Color := Color;
    Canvas.TextOut(Cities[i].X, Cities[i].Y + g_CitySize, inttostr(i));
  end;
end;

//绘制路
procedure TTravelingShop.DrawRoad;
var
  i, TempCity: integer;
begin
  TempCity := 0;
  for i := 1 to CityNumber - 1 do
  begin
    Canvas.MoveTo(Cities[ShortTestPath[TempCity]].X, Cities[ShortTestPath[TempCity]].Y);
    Canvas.LineTo(Cities[ShortTestPath[i]].X, Cities[ShortTestPath[i]].Y);
    TempCity := i;
  end;
  Canvas.MoveTo(Cities[ShortTestPath[CityNumber - 1]].X, Cities[ShortTestPath[CityNumber
    - 1]].Y);
  Canvas.LineTo(Cities[ShortTestPath[0]].X, Cities[ShortTestPath[0]].Y);
end;

//遍历城市
//a_TempPath临时路径
//a_CitiesToured是否已经经过（0否1是）
//a_CitiesNum已经遍历的城市数目
procedure TTravelingShop.GoThroughCities(a_TempPath, a_CitiesToured: array of integer;
  a_CitiesNum: integer);
var
  i: integer;
  TempLength: real;
begin
  if a_CitiesNum = 0 then
  begin
    a_CitiesNum := a_CitiesNum + 1;
    TouredLength := 0;
    a_TempPath[0] := 0;
    a_CitiesToured[0] := 1;
    GoThroughCities(a_TempPath, a_CitiesToured, a_CitiesNum);
  end
  else
    if a_CitiesNum = CityNumber then
    begin
      //计算此经历顺序所走的路程
      TempLength := TouredLength + CitiesDistance[a_TempPath[CityNumber - 1], 0];
      //比较路程
      if TempLength < ShortTestLength then
      begin
        //更新最短路程及其经历顺序
        ShortTestLength := TempLength;
        for i := 0 to CityNumber - 1 do
          ShortTestPath[i] := a_TempPath[i];
      end;
    end
    else begin
      if (TouredLength + ShortestDistance[CityNumber - a_CitiesNum]) < ShortTestLength then
      begin
        for i := 0 to CityNumber - 1 do
        //选择未经历的城市
          if a_CitiesToured[i] <> 1 then
          begin
          //加入已经历城市
            a_CitiesToured[i] := 1;
            a_TempPath[a_CitiesNum] := i;
            TouredLength := TouredLength + CitiesDistance[a_TempPath[a_CitiesNum - 1],
              i];
          //已经历城市个数+1
            a_CitiesNum := a_CitiesNum + 1;
          //调用下一层
            GoThroughCities(a_TempPath, a_CitiesToured, a_CitiesNum);

          //恢复本层的状态：
            a_CitiesToured[i] := 0;
          //已经历城市及个数
            a_CitiesNum := a_CitiesNum - 1;
            TouredLength := TouredLength - CitiesDistance[a_TempPath[a_CitiesNum - 1],
              i];
          end;
      end;
    end;
end;

//查找最短路径
//CitiesNum已经经历城市的个数
//TempPath经历的路径
//CitiesToured保存第I个城市是否已经经历
procedure TTravelingShop.FindShortTestPath;
var
  i, CitiesNum: integer;
  TempPath, CitiesToured: array of integer;
begin
  SetLength(TempPath, CityNumber);
  SetLength(CitiesToured, CityNumber);
  CitiesNum := 0;
  //遍历各城市
  GoThroughCities(TempPath, CitiesToured, CitiesNum);

  DrawRoad;
end;

//TCity的构造函数，对TCity进行初始化。
constructor TTravelingShop.Create(a_Number: integer; a_Canvas: TCanvas);
begin
  ShortTestLength := g_MaxLenght;
  Canvas := a_Canvas;
  CityNumber := a_Number;
  //为动态数组分配内存
  SetLength(Cities, CityNumber);
  SetLength(CitiesDistance, CityNumber, a_Number);
  SetLength(CitiesToured, CityNumber);
  SetLength(ShortTestPath, CityNumber);
  SetLength(ShortestDistance, CityNumber * (CityNumber - 1) div 2 + 1);
end;

destructor TTravelingShop.Destroy;
begin
  Cities := nil;
  CitiesDistance := nil;
  CitiesToured := nil;
end;

procedure TTravelingShop.Draw;
begin
  DrawCities;
  DrawRoad;
end;

end.