Стили и методы программирования


Взаимодействие процессов и распараллеливание - часть 6


Если нет дорог из текущего местонахождения, то агент ликвидируется - он зашел в тупик.

  • Переход к следующему моменту времени - для каждого агента осуществляется один шаг передвижения по текущей дороге. Это можно интерпретировать как задержку выполнения программы на время, необходимое для перемещения в свой следующий пункт (мерой времени в данном случае служит расстояние между пунктами).
  • Осуществляется переход к пункту 1.
  • Видно, что алгоритм завершает работу, когда найден путь из A в B либо когда все агенты оказываются ликвидированы.

    Как и обычно, более жесткие условия на окончательную программу влекут за собой во многих отношениях более мягкие требования к прототипу (нужно расширить возможности его перестройки в разные варианты окончательной программы), но при этом желательно максимально возможное повышение уровня понятий прототипа. Если в конце концов программа будет реализована квазипараллельно, не нужно обращать внимание на то, сколько агентов могут действовать одновременно. В частности, в случае заведомого наличия пути из A в B можно не проверять запретность либо ослабить ее до случая, когда предок данного агента посещал данный город, и, следовательно, он оказался на запомненном пути. В этом случае не потребуется запоминание глобальной, а точнее, общей для всех агентов информации о графе дорог и городов.

    Приведенный алгоритм нуждается в запоминании сведений о пройденном пути в локальных данных агентов. Таким образом, локальные данные каждого из агентов, которые будут ликвидированы, хранятся напрасно. Если же их забывать, то искомый путь не может быть получен, получаются лишь некоторые его характеристики. Этого недостатка лишено решение с помощью обратного блуждания, т.е. от B к A. Для него все работает точно так же, за исключением следующего:

    • локальная информация об агентах и их путях не запоминается;
    • в качестве пометки о посещении указывается, из какого города агент пришел в данный город (это можно называть пометкой-рекомендацией).

    В результате, когда какой-либо из агентов достигнет A, последовательность, начинающаяся с A и выстраивающаяся по пометкам-рекомендациям, дает искомый путь.




    Начало  Назад  Вперед