Форум умных людей > Задачи и головоломки > Математические задачи (Модераторы: Илья, Лев) > Ладьи в кубе
Страниц: 1 ... 4 5 [6]
« предыдущая тема следующая тема »
  Печать  
Автор Тема: Ладьи в кубе  (Прочитано 19977 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Кто как ее решает?
У Wiki мнение, что нужно решать "методом ветвей и границ или методом генетических алгоритмов, а также алгоритмом муравьиной колонии".

Я сомневаюсь, что подобные вещи были знакомы первым коммивояжерам. Поэтому предлагаю "геометрическое" решение, которое не требует особых манипуляций с данными. Простое и понятное:


Смотрим на карту, где мы пометили все нужные города. По самым дальним точкам строим эн-угольник, внутри которого находятся все остальные точки. Потом для ближайшей к угольнику (можно на глаз) точки изучаем возможность посетить ее по пути между двумя соседними точками угольника. Выбираем наименьший путь и так же далее, пока не включим все точки. Получится замкнутая кривая, т. е. неважно, откуда мы ехали - мы туда же вернемся. Все.
buka
Гений
*****
Offline Offline

Сообщений: 960

СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120



Просмотр профиля
� Ответ #75 : Август 24, 2011, 12:09:51 �
Если бы можно было получить инвариантное выражение для числа простреливаемых полей для одной ладьи, то это позволило бы нам получить не границу, а точное выражение.
Но, увы, я убедился, что это не может быть инвариантом...
Теперь я стараюсь получить другой инвариант...
Пока что - это всё, что могу сказать...
Записан
Страниц: 1 ... 4 5 [6]
  Печать  
« предыдущая тема следующая тема »
 
Перейти в: