PROGRAM PRG13_3;

{ЖАДНЫЙ АЛГОРИТМ}

VAR M:SET OF 1..10;

STR: ARRAY[1..1O] OF BYTE;

A,N, L, X, Y, J, I, MIN.COST:INTEGER;

METR: ARRAY [1..10, 1..10] OF BYTE;

PROCEDURE IN_METR;

{Формирование матрицы}

VAR I,J:INTEGER;

BEGIN

FOR l:=1 TO N DO

FOR J:=l TO N DO

IF I=J THEN METR[I,J]:= 0

ELSE

BEGIN

METR[I,J]:=1 + RANDOM(N);

METR[J,I]:=METR[I,J];

END;

END;

PROCEDURE OUT_METR;

{Вывод матрицы на экран}

VAR I,J:INTEGER;

BEGIN

FOR l:=1 TO N DO

BEGIN

FOR J:=1 TO N DO

WRITE (METR[I,J]:4);

WRITELN;

END;

END;

BEGIN

WRITELN('BBEДИTE РАЗМЕР МАТРИЦЫ');

READLN(N);

IN_METR;

OUT_METR;

WRITELN('BBEДИTE НОМЕР ГОРОДА, ИЗ КОТОРОГО НАЧИНАЕТСЯ МАРШРУТ');

READLN(X);

М:=[Х];

STR[1]:=X;

А:=Х;

FOR J:=1 TO N-1 DO

BEGIN

MIN:= MAXINT;Y:=1;

FOR l:=1 TO N DO

IF (METR[X,I]<MIN)AND NOT(I IN M)AND(METR[X,l]<>0) THEN

BEGIN

MIN:=METR[X,I];

Y:=l;

END;

COST:=COST+MIN;

M:=M+[Y];

STR[J+1]:=Y;

X:=Y

END;

WRITELN('COST =', COST + METR[A,X]);

FOR l:=1 TO N DO

WRITE(STR[I]:5);

WRITELN(' ',A);

END.

Для решения задачи:

- формируем тело программы и описываем переменные;

- создаем описание процедуры INMETR для формирования матрицы расстояний METR;

- создаем описание процедуры OUTMETR для вывода мат­рицы расстояний на экран;

- в основной программе вызываем процедуры IN_METR и OUT_METR, вводим город X, из которого начинаем движение;

- организуем два вложенных цикла, с помощью которых нахо­дим самый короткий маршрут;

- выводим результат на экран.

Переменные:

в процедуре IN_METR:

I, J - переменные циклов.

в процедуре OUT_JMETR:

I, J - переменные циклов.

в основной программе:

М - множество городов, которые посетил коммивояжер;

STR - последовательность городов в самом коротком маршруте;

N - количество городов;

А - первый город, из которого коммивояжер начинает маршрут;

L, X, Y, MIN - вспомогательные переменные;

J, I - переменные циклов;

COST - стоимость наименьшего маршрута, т. е. его длина;

METR - матрица расстояний.