Задача Коммивояжера

Тема в разделе "Pascal and Delphi", создана пользователем ritmix93, 19 июн 2013.

  1. ritmix93

    ritmix93 New Member

    Регистрация:
    19 июн 2013
    Сообщения:
    1
    Симпатии:
    0
    Имеется N населённых пунктов, пронумерованных от 1 до N. Некоторые пары населенных пунктов соединены дорогами. Известны стоимости проездов по этим дорогам. Определить, можно ли попасть по этим дорогам из первого пункта в N-ный. Если да, то найти маршрут с минимальной стоимостью проезда.

    program proezd;

    const
    Max = 5;

    var
    A: Array[1..Max, 1..Max] Of Integer;
    { *Матрица расстояний между городами. *}
    f: text;
    N: integer;
    B: Array[1..Max, 1..Max] Of Byte;{^Вспомогательный
    массив, элементы каждой строки матрицы
    сортируются в порядке возрастания, но сами
    элементы не переставляются, а изменяются
    в матрице В номера столбцов матрицы А.*}
    Way, BestWay: Array[1..Max] Of Byte;{*Хранится
    текущее решение и лучшее решение. *}
    Nnew: Array[1..Max] Of Boolean;{*3начение
    элемента массива False говорит о том,
    что в соответствующем городе коммивояжер
    уже побывал. *}
    BestCost: Integer;{*Стоимость лучшего решения. *}


    procedure Solve(v, Count: Byte; Cost: Integer);
    {*v - номер текущего города; Count - счетчик числа
    пройденных городов; Cost - стоимость текущего
    решения. *}
    var
    i: Integer;
    begin
    if Cost > BestCost Then Exit;{*Стоимость текущего
    решения превышает стоимость лучшего из
    ранее полученных. *}
    if Count = N Then begin
    Cost := Cost + A[v, 1];
    Way[N] := v;{*Последний город
    пути. Добавляем к решению стоимость
    перемещения в первый город и сравниваем
    его с лучшим из ранее полученных. *}
    if Cost < BestCost Then begin
    BestCost := Cost;
    BestWay := Way; end;
    Exit;{*Оператор нарушает структурный стиль
    программирования ~ "любой фрагмент логики
    должен иметь одну точку входа и одну точку
    выхода. Следует убрать его" . *}
    end;

    Nnew[v] := False;
    Way[Count] := v;{*Город с номером v
    пройден, записываем его номер в путь
    коммивояжера. *}
    for i := 1 To N do
    if Nnew[B[v, i]] Then Solve(B[v, i],
    Count + 1, Cost + A[v, B[v, i]]); {*Поиск города, в который
    коммивояжер может пойти из города,
    с номером v.*}
    Nnew[v] := True; {^Возвращаем город с номером v
    в число непройденных. *}
    end;

    var
    i, j: integer;

    begin
    assign(f, 'f:\1.txt');
    reset(f);
    i := 1;
    j := 1;
    while not eof(f) do
    begin
    while not eoln(f) do
    begin
    read(f, a[i, j]);
    inc(j);
    end;
    readln(f);
    inc(i);
    end;
    solve();
    writeln('лучшая цена-', BestCost);
    end.



    Просьба исправить и доработать
     
Загрузка...
Похожие Темы - Задача Коммивояжера
  1. nuke4303
    Ответов:
    4
    Просмотров:
    1.443
  2. Янчик
    Ответов:
    0
    Просмотров:
    473
  3. TrishaRay
    Ответов:
    1
    Просмотров:
    778
  4. elzim
    Ответов:
    0
    Просмотров:
    929
  5. ShaoKahn
    Ответов:
    0
    Просмотров:
    1.116

Поделиться этой страницей