Skip to content
This repository has been archived by the owner on Feb 12, 2018. It is now read-only.

Files

Latest commit

55200e6 · Dec 3, 2012

History

History

kesarev

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
Dec 3, 2012
Dec 3, 2012
Dec 3, 2012
Dec 3, 2012
Dec 3, 2012
Dec 3, 2012
Dec 3, 2012
Dec 3, 2012

SMART ANT

Задача Умный муравей.

Постановка задачи

Задано тороидальное поле(Уходя за край поля, муравей появляется с другого его края) n x n клеток, на нем заданным образом расположены k яблок. Необходимо построить конечный управляющий автомат Мили из l состояний, описывающий муравья, который за m ходов съедает все яблоки. Изначально муравей находится в верхней левой клетке тора и смотрит вправо. Муравей может видеть, есть ли яблоко в клетке перед ним, и на каждом шаге должен выполнять одно из трех действий:

  1. повернуться на 90 градусов налево
  2. повернуться на 90 градусов направо
  3. переместиться на клетку вперед и съесть яблоко, если оно есть в клетке

Формат входной файла

В первой строке входного файла содержатся числа n l m, описание которых выше. Далее записаны n строк по n символов в каждой, которые описывают тор. Символ '*' соответствует наличию яблока, '.' - отсутствию. Должно быть гарантировано, что в левой верхней клетке тора нет яблока! Примеры входного файла можно посмотреть в папке './tests/'.

Формат выхода

В первой строке выводится имя файла, поданного на вход. Во второй строке выводится номер стартового состояния. В следующих l строках описываются состояния автомата в формате t0 t1 a0 a1, где t0 и a0 - номер состояния, в которое нужно перейти, если яблока перед муравьем нет, и действие, которое совершает муравей на данном переходе, а t1 и a1 - номер состояния, в которое нужно перейти, если перед муравьем есть яблоко, и действие, которое совершает муравей на данном переходе.

Usage:

python ./main.py <input_file>

Использованая литература

  1. http://is.ifmo.ru/download/ant_ga_min_number_of_state.pdf
  2. http://rudocs.exdat.com/docs/index-229491.html