Поиск пути

Delphi , Синтаксис , Математика

unit road_;

interface
uses
  Windows, Messages, SysUtils, Classes,
  Graphics, Controls, Forms,
  Dialogs, StdCtrls, Grids;

type
  TForml = class(TForm)
    StringGridl: TStringGrid;
    Edit1: TEdit;
    Edit2: TEdit;
    Label1: TLabel;
    Label2: TLabel;
    Label3: TLabel;
    Button1: TButton;
    Label4: TLabel;
    procedure FormActivate(Sender: TObject);
    procedure ButtonlClickfSender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;

implementation
{$R *.DFM}

procedure TForml.FormActivate(Sender: TObject);
var
  i: integer;
begin
  // нумерация строк
  for i := 1 to 10 do
    StringGridl.Cells[0, i] := IntToStr(i); // нумерация колонок

  for i := l to 10 do
    StringGridl.Cells[1, 0] := IntToStr(i);

  // описание предопределенной карты
  StringGridl.Cells[1,2]:='1'
  StringGridl.Cells[2,l]:='1'

  StringGridl.Cells[1, 3] := '1'
  StringGridl.Cells[3, 1] := '1'
  StringGridl.Cells[1, 4] := '1'
  StringGridl.Cells[4, 1] := '1'
  StringGridl.Cells[3, 7] := '1'
  StringGridl.Cells[7, 3] := '1'
  StringGridl.Cells[4, 6] := '1'
  StringGridl.Cells[6, 4] := '1'
  StringGridl.Cells[5, 6] := '1'
  StringGridl.Cells[6, 5] := '1'
  StringGridl.Cells[5, 7] := '1'
  StringGridl.Cells[7, 5] := '1'
  StringGridl.Cells[6, 7] := '1'
  StringGridl.Cells[7, 6] := '1'
end;

procedure TForml.ButtonlClick(Sender: TObject);
const
  N = 10; // кол-во вершин графа var
  map: array[1..N, 1..N] of integer; // Карта.map[i,j]ne 0,

  // если точки i и j соединены
  road: array[1..N] of integer;

  // Дорога - номера точек карты
  incl: array[1..N] of boolean; // incl[1]равен TRUE, если точка

  // с номером i включена в road
  start, finish: integer; // Начальная и конечная точки
  found: boolean; i, j: integer;

  procedure step(s, f, p: integer);
  var
    с: integer; // Номер точки, в которую делаем очередной шаг
    i: integer;
  begin
    if s = f then
    begin
      // Точки s и f совпали !
      found := TRUE;
      Labell.caption := Labell.caption + #13 + 'Путь:';
      for i := l to p - 1 do
        Labell.caption := Labell.caption + ' '
          + IntToStr(road[i]);
    end
    else
    begin
      // выбираем очередную точку
      for c:=l to N do
      begin // проверяем все вершины
        // точка соединена с текущей и не включена в маршрут
        if (map[s, c] <> 0) and (not incite1) then
        begin
          road[p] := c; // добавим вершину в путь
          incl[c] := TRUE; // пометим вершину как включенную
          step(c, f, p + l); incite] := FALSE;
          road[p] := 0;
        end;
      end;
    end;
  end; // конец процедуры step

begin
  Label1.caption: = ' ';
  // инициализация массивов
  for i := l to N do
    road[i] := 0;

  for i := l to N do
    incl[i] := FALSE;

  // ввод описания карты из SrtingGrid.Cells
  for i := l to N do
    for j := 1 to N do
      if StringGrid1.Cells[i, j] <> '' then
        map[i, j] := StrToInt(StringGridl.Cells[i, j];
      else
        map[i, j] := 0;

  start := StrToInt(Editl.text);
  finish := StrToInt(Edit2.text);
  road[l] := start; // внесем точку в маршрут
  incl[start] := TRUE; // пометим ее как включенную
  step(start, finish, 2); //ищем вторую точку маршрута
  // проверим, найден ли хотя бы один путь
  if not found then
    Labell.caption := 'Указанные точки не соединены!';
end;

end.

При запуске программы в момент активизации формы приложения происходит событие onActivate, процедура обработки которого заполняет массив StringGridl.cells значениями, представляющими описание карты. Этаже процедура нумерует строки и столбцы таблицы, заполняя зафиксированные ячейки первого столбца и первой строки StringGridl.

Поиск маршрута инициирует процедура TFormi.Buttoniciick, которая запускается щелчком на кнопке Поиск. Данная процедура для поиска точки, соединенной с исходной точкой, вызывает процедуру step, которая после выбора первой точки, соединенной с начальной, и включения ее в маршрут вызывает сама себя. При этом в качестве начальной точки задается уже не исходная, а текущая, только что включенная в маршрут.

Here's a translation of the text into Russian:

Это программное обеспечение на Delphi, которое симулирует алгоритм поиска в графе для поиска кратчайшего пути между двумя узлами на карте-лоскутке. Программа использует компонент StringGrid для представления карты и компонент Edit для ввода начального и конечного узлов.

Вот разбивка кода:

1. Процедура FormActivate вызывается при активации формы. Она инициализирует grid, заполняя его числами от 1 до 10 в первой колонке и строке.
2. Процедура ButtonClick вызывается при клике кнопки "Поиск". Она читает карту из StringGrid, конвертирует ее в двумерный массив целых чисел и затем вызывает процедуру step, чтобы начать поиск кратчайшего пути.

Процедура step - рекурсивная функция, которая исследует каждый узел в графе, проверяет, является ли он связанным с текущим узлом, и добавляет его в путь, если это так. Если она находит узел, который связан с конечным узлом, она возвращает и устанавливает переменную found в true.

Программа использует булевый массив incl для отслеживания посещенных узлов и целочисленный массив road для хранения кратчайшего пути, найденного до сих пор.

Вот некоторые предложения по улучшению кода:

1. Используйте более описательные имена переменных вместо одиночных букв, таких как i, j и s.
2. Рассмотрите использование более эффективного алгоритма, такого как алгоритм Дейкстры или поиск A*, который может найти кратчайший путь в графе.
3. Добавьте обработку ошибок для случаев, когда начальный и конечный узлы не найдены на карте.
4. Используйте комментарии для объяснения того, что делает каждый участок кода.

Вот обновленная версия кода с некоторыми улучшениями:

unit road;
interface
uses
  Windows, Messages, SysUtils, Classes,
  Graphics, Controls, Forms,
  Dialogs, StdCtrls, Grids;

type
  TForm1 = class(TForm)
    StringGrid1: TStringGrid;
    Edit1: TEdit;
    Edit2: TEdit;
    Label1: TLabel;
    Label2: TLabel;
    Label3: TLabel;
    Button1: TButton;
    Label4: TLabel;
    procedure FormActivate(Sender: TObject);
    procedure ButtonClick(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;

implementation

{$R *.DFM}

procedure TForm1.FormActivate(Sender: TObject);
begin
  // Инициализация grid с числами от 1 до 10 в первой колонке и строке
  for i := 1 to 10 do
    StringGrid1.Cells[0, i] := IntToStr(i);

  for i := 1 to 10 do
    StringGrid1.Cells[i, 0] := IntToStr(i);

  // Инициализация массива карты
  var
    map: array[1..10, 1..10] of integer;
    start, finish: integer;

  // Чтение карты из grid и конвертация ее в двумерный массив целых чисел
  for i := 1 to 10 do
    for j := 1 to 10 do
      if StringGrid1.Cells[i, j] <> '' then
        map[i, j] := StrToInt(StringGrid1.Cells[i, j])
      else
        map[i, j] := 0;

  // Установка начального и конечного узлов
  start := StrToInt(Edit1.Text);
  finish := StrToInt(Edit2.Text);

  // Инициализация массива road для хранения кратчайшего пути
  var
    road: array[1..10] of integer;
    incl: array[1..10] of boolean;

  // Инициализация массива road и установка начального узла как первого узла в пути
  for i := 1 to 10 do
    road[i] := 0;
  incl[start] := TRUE;
  road[1] := start;
end;

procedure TForm1.ButtonClick(Sender: TObject);
var
  found: boolean;
begin
  // Инициализация надписи и результата поиска
  Label4.Caption := '';

  // Вызов процедуры step для начала поиска кратчайшего пути
  if not SearchPath(start, finish) then
    Label4.Caption := 'Указанные точки не соединены!';
end;

procedure TForm1.SearchPath(var s, f: integer);
var
  c: integer;
begin
  if s = f then
  begin
    // Установка переменной found в true и конструирование пути
    found := TRUE;
    Label4.Caption := 'Путь:';
    for i := 1 to Length(road) - 1 do
      Label4.Caption := Label4.Caption + '  ' + IntToStr(road[i]);
  end
  else
  begin
    // Исследование каждого узла в графе и добавление его в путь, если он связан с текущим узлом
    for c := 1 to 10 do
      if map[s, c] <> 0 and not incl[c] then
      begin
        road[Length(road) + 1] := c;
        incl[c] := TRUE;
        SearchPath(c, f);
        road[Length(road)] := 0;
        incl[c] := FALSE;
      end;
  end;
end;

end.

Обратите внимание, что я добавил некоторые комментарии для объяснения того, что делает каждый участок кода, и также рефакторировал некоторые части кода для лучшей читаемости.

В статье описывается программный код на Delphi, который реализует поиск пути между двумя точками на карте.

Комментарии и вопросы

Получайте свежие новости и обновления по Object Pascal, Delphi и Lazarus прямо в свой смартфон. Подпишитесь на наш Telegram-канал delphi_kansoftware и будьте в курсе последних тенденций в разработке под Linux, Windows, Android и iOS

:: Главная :: Математика ::