Оптимальное распределение муравьёв по путям - sergeresko/Lem_in-explanation GitHub Wiki

Вот способ, который я придумал с самого начала. Он неэффективный, но правильный и даёт основную идею, которую потом можно усовершенствовать.

Пусть есть 7 муравьёв и, допустим, алгоритм Бхандари нашёл два пути разной длины:

   ( )----( )----( )
  /                 \
(7)                 ( )
  \                 /
  ( )-( )-( )-( )-( )

Слева start, справа end. В каждой комнате я буду отмечать, сколько в ней муравьёв.

Примем условно, что в start находится бесконечное число муравьёв.

Будем делать в цикле такие действия:

1. всех муравьёв, которые не находятся в start или end, сдвинуть в следующую комнату по направлению к end,
2. выпустить из start по одному муравью на каждый путь.

Когда какой-то муравей попадает в end, увеличиваем на единицу счётчик муравьёв, которые попали туда по соответствующему пути.

Вот, как будет выглядеть процесс:

   (1)----( )----( )  count1: 0
  /                 \
(∞)                 ( )
  \                 /
  (1)-( )-( )-( )-( ) count2: 0

   (1)----(1)----( )  count1: 0
  /                 \
(∞)                 ( )
  \                 /
  (1)-(1)-( )-( )-( ) count2: 0

   (1)----(1)----(1)  count1: 0
  /                 \
(∞)                 ( )
  \                 /
  (1)-(1)-(1)-( )-( ) count2: 0

   (1)----(1)----(1)  count1: 1
  /                 \
(∞)                 (1)
  \                 /
  (1)-(1)-(1)-(1)-( ) count2: 0

   (1)----(1)----(1)  count1: 2
  /                 \
(∞)                 (2)
  \                 /
  (1)-(1)-(1)-(1)-(1) count2: 0

   (1)----(1)----(1)  count1: 3
  /                 \
(∞)                 (4)
  \                 /
  (1)-(1)-(1)-(1)-(1) count2: 1

   (1)----(1)----(1)  count1: 4
  /                 \
(∞)                 (6)
  \                 /
  (1)-(1)-(1)-(1)-(1) count2: 2

При передвижении очередного муравья по любому из путей, количество муравьёв в end станет равно 7, т.е. все дойдут до конца, при этом будет count1 = 5, count2 = 2 или count1 = 4, count2 = 3.

Таким образом, все муравьи, которые ещё не пришли в end, оказались лишними, а count1 и count2 показывают, сколько муравьёв и куда в действительности нужно было отправить.

На основании этого нетрудно посчитать, сколько строчек решения это займёт.

Решение, которое от нас требуют выводить на экран, будет описывать как раз это движение муравьёв.

---

Дальше: Ссылки на алгоритм Бхандари