Ответы пользователя Mercury13 по тегу «Алгоритмы»

Алгоритм генератора заявок для моделирования СМО с пуассоновским потоком?

Mercury13 @Mercury13

Программист на «си с крестами» и не только

class Event {  //  интерфейс
public:
  virtual double time() = 0;   // когда потребуется внимание со стороны менеджера событий
  virtual void process() = 0;  // команда обработать событие
  // virtual int type() = 0;      // можно пристроить, если по какой-то причине надо отличать кресло от генератора клиентов
};

class EventSink {  // интерфейс
  virtual void add(Event& x);
}

class Shop;

class Chair : protected Event {
private:
  double fTime;
  bool fIsOccupied;
public:
  Shop& shop;
  virtual double time() override { return fTime; }
  virtual void process() override;
  {
     что-то типа…
     если shop.nWaiting != 0 {
        --shop.nWaiting;
        occupy(time);
     } else {
         isOccupied = false;
     }
  }
  void occupy (double aTime) {
        time = aTime + время обслуживания клиента
        shop.manager.add(*this);
   }
   bool isOccupied() { return fIsOccupied; }
};

class CustomerGenerator : protected Event {
   // Устроен аналогично Chair, служит для генерации потока клиентов
public:
  virtual void process() override {
     если shop.nWaiting == 0 и кресло свободно {
        shop.chair.occupy(fTime);
     } else {
        ++shop.nWaiting;
     }
     fTime += экспоненциальное время ожидания;
     manager.add(*this);
  }
  void init() {
     fTime = 0;
     process();
  }
};

class Shop {
public:
   Chair chair;  // можно несколько кресел
   CustomerGenerator generator;
   int nWaiting;  // сколько человек в очереди
   EventSink& manager;
}

class Manager : public EventSink {
   Event* events[2];   // события отсортированы по времени
   int nEvents;

   void add(Event& x) override {
      // вставить двоичным поиском x в нашу очередь;  тут же можно сделать ограничение
      // «обработать 1000 клиентов» или «работать 8 часов».
   }

   И самое главное — «жизненный цикл».
   shop.generator.init();
   Пока очередь не пуста…
   • вытащить из неё событие
   • process его!
}

Как оно работает?
1. на 5-й минуте приходит посетитель. Значит, генератор вносится в очередь со временем 5 минут.
2. Выбираем генератор из очереди. Поскольку в парикмахерской очереди нет, он садится в кресло (в список вносится кресло со временем 5+8 = 13 минут), в список вносится генератор со временем 5 + 3 = 8 минут.
3. Из этой пары выбираем генератор (у него 8 минут, против 13 минут у кресла). Он вносит нашего товарища в очередь (теперь в очереди один), в очередь вносится генератор со временем 8+4 = 12 минут.
4. Снова в очереди кресло и генератор, и минимальное время у генератора. Теперь в парикмахерской ждут двое, и генератор вносим в очередь на время 12 + 30 = 42 минуты.
5. Теперь минимальное время у кресла, и оно обслуживает ещё одного посетителя, внося себя в очередь на (13 + 8 = 21 минуте.
6. И снова минимальное время у кресла, оно вносит себя в очередь на 21 + 8 = 29 минут.
7. Пришла 29 минута, но стричь-то некого! В очереди менеджера остался один генератор.
8. Выбираем из очереди генератор, и так далее…

(простите, что я написал сумбурно, ведь есть очередь событий в менеджере и очередь клиентов в парикмахерской).

Не забудьте, что события добавляют не в хвост очереди, а куда угодно — ведь событие может, в свою очередь, каскадом вызвать другие события.

Войдите на сайт