Отправляет email-рассылки с помощью сервиса Sendsay

RFpro.ru: Программирование на языке Pascal

Подписаться Бесплатная «Золотая» новостная рассылка . Подписчиков 2.943 RSS
←   Июнь 2011   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


За последние 60 дней ни разу не выходила


Сайт рассылки: http://prog.rusfaq.ru/pascal
Открыта: 14-03-2002

Автор
Калашников О.А.

Статистика

2.943 подписчиков
0 за неделю
←   Все выпуски   →

RFpro.ru: Программирование на языке Pascal


Хостинг портала RFpro.ru:
Московский хостер
Профессиональный ХОСТИНГ на базе Linux x64 и Windows x64

РАССЫЛКИ ПОРТАЛА RFPRO.RU

Лучшие эксперты данной рассылки

Асмик Александровна
Статус: Академик
Рейтинг: 8321
∙ повысить рейтинг » 		Орловский Дмитрий
Статус: Академик
Рейтинг: 5655
∙ повысить рейтинг » 		Роман Селиверстов
Статус: Академик
Рейтинг: 2859
∙ повысить рейтинг »

/ КОМПЬЮТЕРЫ И СОФТ / Программирование / Pascal (Паскаль)

Номер выпуска:1198
Дата выхода:26.06.2011, 01:30
Администратор рассылки:Boriss (Академик)
Подписчиков / экспертов:166 / 173
Вопросов / ответов:1 / 1

Вопрос № 183676: Уважаемые эксперты! Пожалуйста, ответьте на вопрос:Дана матрица расстояний между населёнными пунктами. Решить задачу коммивояжера, т.е. построить маршрут, проходящий через все пункты и возвращающий в начальный, при котором суммарное расстояние минима...

Вопрос № 183676:

Уважаемые эксперты! Пожалуйста, ответьте на вопрос:Дана матрица расстояний между населёнными пунктами. Решить задачу коммивояжера, т.е. построить маршрут, проходящий через все пункты и возвращающий в начальный, при котором суммарное расстояние минимально.
0 3 93 13 33 9 57
4 0 77 42 21 16 34
45 17 0 36 16 28 25
39 90 80 0 56 7 91
28 46 88 33 0 25 57
3 88 18 46 92 0 7
44 26 33 27 84 39 0

Среда! Turbo Pascal! Пожалуйста, сделайте комментарии каждой строки! Спасибо!:-)

Отправлен: 20.06.2011, 19:23
Вопрос задал: Белгородцева Ольга Геннадьевна (Посетитель)
Всего ответов: 1
Страница вопроса »

Отвечает Andrew Kovalchuk (Профессионал) :
Здравствуйте, Белгородцева Ольга Геннадьевна!
Решение ЗК методом лексического перебора.
Код :
{
 Дана матрица расстояний между населёнными пунктами.
 Решить задачу коммивояжера, т.е. построить маршрут, проходящий через все пункты и возвращающий в начальный,
 при котором суммарное расстояние минимально.
0 3 93 13 33 9 57
4 0 77 42 21 16 34
45 17 0 36 16 28 25
39 90 80 0 56 7 91
28 46 88 33 0 25 57
3 88 18 46 92 0 7
44 26 33 27 84 39 0
}
uses
 crt;

const
 N = 7;
 C: array [1..N, 1..N] of byte = (
 ( 0,  3, 93, 13, 33,  9, 57),
 ( 4,  0, 77, 42, 21, 16, 34),
 (45, 17,  0, 36, 16, 28, 25),
 (39, 90, 80,  0, 56,  7, 91),
 (28, 46, 88, 33,  0, 25, 57),
 ( 3, 88, 18, 46, 92,  0,  7),
 (44, 26, 33, 27, 84, 39,  0)); {Матрица расстояний}

label
 Out; {Метка для завершающих операций}

var
 Tour, P: array [1..N] of word; {Оптимальный и текущие туры}
 l, s: word; {протяженность тура}
 i, j, k, min, ind: byte; {счетчики и индексы}
 All: boolean; {Признак окончания перебора}

{Программа решения задачи коммивояжера методом лексического перебора.}
begin
 clrscr;
 {Инициализация}
 All := false; {Перебраны не все варианты}
 l := MaxInt; {Оптимальный тур неизвестен}
 for i := 1 to N do
  P[i] := i; {Строим первый тур}
 repeat {Вычисляем его длину}
  s := 0;
  for i := 1 to (N - 1) do
   s := s + C[P[i], P[i+1]];
  s := s + C[P[n], P[1]];
  {Полагаем первый тур текущим}
  if (l > s) then begin
   Tour := P;
   l := s;
  end;
 
  {Генерируем все (N-1)! перестановок}
  for i := N downto 3 do begin
   if (P[i] < P[i-1]) then
    continue;
   min := N + 1;
   k := P[i-1];
  {Ищем миним. число из тех, что больше k и правее}
  for j:=i to N do
   if (P[j] > k) and (P[j] < min) then begin
    min := P[j];
    ind:=j;
   end;
  {Рокировка min и k}
  P[i-1] := min;
  P[ind] := k;
 
  {Элементы на местах от i до N упорядочиваем по возрастанию}
  for j := i to (N - 1) do begin
   min := N + 1;
   for k := j to N do 
    if (min > P[k]) then begin
     min := P[k];
     ind := k;
    end;
   k := P[j];
   P[j] := min;
   P[ind] := k;
  end;
  GoTo Out;
 end;
 {Проверяем перебраны ли все перестановки}
 All:=true;
Out:
 Until All;
 {Если перебраны все перестановки, то выдаем оптимальный тур}
 write('Minimum tour: ');
 for i:=1 to N do write(Tour[i], '-');
 write('1');
 writeLn(' length is ', l);
 writeln('Done. Press any key...');
 readkey;
end.

Дополнительные пояснения по мере их возникновения.
-----
Временная неудача лучше временной удачи

Ответ отправил: Andrew Kovalchuk (Профессионал)
Ответ отправлен: 20.06.2011, 20:48
Номер ответа: 267793
Украина, Киев

Вам помог ответ? Пожалуйста, поблагодарите эксперта за это!
Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 267793 на номер 1151 (Россия) | Еще номера »
  • Отправить WebMoney:

    • Оценить выпуск »
    Нам очень важно Ваше мнение об этом выпуске рассылки!

    Задать вопрос экспертам этой рассылки »

    Скажите "спасибо" эксперту, который помог Вам!

    Отправьте СМС-сообщение с тестом #thank НОМЕР_ОТВЕТА
    на короткий номер 1151 (Россия)
    Номер ответа и конкретный текст СМС указан внизу каждого ответа.

    Полный список номеров »

    * Стоимость одного СМС-сообщения от 7.15 руб. и зависит от оператора сотовой связи. (полный список тарифов)
    ** При ошибочном вводе номера ответа или текста #thank услуга считается оказанной, денежные средства не возвращаются.
    *** Сумма выплаты эксперту-автору ответа расчитывается из суммы перечислений на портал от биллинговой компании.

    © 2001-2011, Портал RFPRO.RU, Россия
    Авторское право: ООО "Мастер-Эксперт Про"
    Калашников О.А. | Гладенюк А.Г.
    Хостинг: Компания "Московский хостер"
    Версия системы: 2011.6.31 от 07.05.2011
    В избранное