• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

Оптимальный алгоритм перемещения объектов в квадратной решетке

Москалев А., Морозенко В. В.

Для произвольного натурального п рассматривается задача оптимального перемещения объектов в графе, который является декартовым произведением n-вершинной цепи на себя. Предполагается, что из каждой вершины в каждую должен быть перемещен ровно один объект, причем за один такт по любому ребру может быть перемещено не более одного объекта. Описывается алгоритм, который осуществляет перемещение всех объектов за минимальное число тактов, и доказывается его оптимальность.