Минимум числа путей

Albus
Сообщений: 59
Зарегистрирован: 11 июн 2019, 10:46

Минимум числа путей

Сообщение Albus » 27 ноя 2021, 18:50

Собственно, родил такую задачу. Пусть есть $n$ стен, в каждой стене по $3$ двери, одна из дверей заминирована. Задача провести робота через все стены, чтобы он не взорвался. Это делается путем дачи роботу некоего листа с маршрутом из общего каталога, расположение мин нам известно.
Задача - найти минимальное число листов с маршрутом в каталоге, чтобы при любом расположении мин нашелся хотя бы один лист с безопасным маршрутом.
Для $n=1$ очевиден ответ $2$ листа (маршруты $(1),(2)$), для $n=2$ надо $3$ листа (маршруты $(1,1), (2,2),(3,3)$), а что там с $n=3$ и т.д.? Желательно еще в пределе очень большого $n$

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Минимум числа путей

Сообщение zykov » 27 ноя 2021, 20:53

Для [math] вышло 5.
[math]

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Минимум числа путей

Сообщение zykov » 28 ноя 2021, 10:50

Посчитал для [math], вышло 8.

Код: Выбрать все

   1   1   1   1
   2   2   2   2
   3   3   1   1
   2   2   3   3
   3   1   2   3
   1   3   2   3
   3   1   3   2
   1   3   3   2

Вобщем есть подозрение, что [math] при [math].
A061419, A081226, A156623
Можно ещё так записать [math], где [math].
(Там в A081226 в формуле упоминается золотое сечение, но это не верно, хотя [math] и близко к [math].)

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Минимум числа путей

Сообщение zykov » 29 ноя 2021, 15:00

zykov писал(а):Source of the post Вобщем есть подозрение, что Q(n+1)=⌈32Q(n)⌉ при Q(1)=2.

Эта формула точно даёт нижнюю границу.
Когда переходим от [math] к [math], то добавляем стену. Тогда все записи в каталоге можно приписать к трём классам (пересекающимся) - "в новой стене не 1", "в новой стене не 2", "в новой стене не 3". Каждый класс будет содержать минимум [math] членов.
Если [math] - количество записей, для которых в новой стенке [math], то [math]. Значит [math], т.е. [math].

Для [math] эта нижняя граница достижима.
Но вот 12 для [math] не уверен. Полный перебор там нереален. Жадный алгоритм дал в лучше случае 14.
Пробовал руками подобрать 12 - не выходит и кажется, не может выйти...
Последний раз редактировалось zykov 29 ноя 2021, 18:57, всего редактировалось 1 раз.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Минимум числа путей

Сообщение zykov » 29 ноя 2021, 18:54

zykov писал(а):Source of the post Пробовал руками подобрать 12 - не выходит и кажется, не может выйти...

Нет, всё таки вышло подобрать регулярный вариант (в каждом столбце ровно по 4 раза каждая цифра).

Код: Выбрать все

   1   1   1   1   1
   1   2   2   3   3
   1   1   3   2   3
   1   3   1   3   2
   2   2   2   2   2
   2   3   3   1   1
   2   3   1   2   3
   2   1   3   3   2
   3   1   2   3   1
   3   2   1   1   3
   3   2   3   2   1
   3   3   2   1   2

Так что для [math] тоже нижняя граница достижима.

Скорее всего [math] и [math] тоже можно регулярно построить (оба на 3 делятся).
А вот про [math] уже не знаю. Там на 3 не делится. Хотя вот для 5 и 8 получилось.

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Минимум числа путей

Сообщение Ian » 30 ноя 2021, 11:02

Хорошая задача. Что-то есть общее с viewtopic.php?f=4&t=529 например то, что в каждом сечении (стене) каталог должен быть распределен как можно более равномерно (число вхождений 1,2 и 3 на каждой стене не могут различаться более чем на 1) И действительно, если есть каталог, в котором гарантированно обходится любой набор мин, а число вхождений на 1м месте номера 1 на два больше чем номера 2, каталог можно хитро преобразовать, что их станет поровну и в новом каталоге также гарантированно обходится любой набор мин.Доказательство немного путаное, при нашей терминологии. Заменим в одном маршруте 1 на 2,тогда станет поровну маршрутов, начинающихся с 1 и 2, и в них поменяем местами хвосты-подкаталоги.Рассматриваем набор мин, якобы опровергающий новый (более равномерный) каталог. Если он начинается с мины 1, то набор, начинающийся с мины 2 -опровергает каталог, с которого мы начали, противоречие. Если он начинается с мин 2 или 3, то сам опровергает исходный каталог, тоже противоречие. Значит можно искать только каталоги, в которых числа используемых дверей на каждой стенке отличаются максимум на 1. И конечно формальная перенумерация дверей на каждой стенке переводит хороший каталог снова в хороший. Все это сокращает перебор

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Минимум числа путей

Сообщение zykov » 01 дек 2021, 13:39

Ian писал(а):Source of the post Что-то есть общее с viewtopic.php?f=4&t=529

В той другой была чистая комбинаторика (вот и ответ там через биномиальный коэффициент).
Тут же есть геометрический аспект.
Мне больше напоминает Hamming code для коррекции ошибок при двоичной кодировке.
Например про Hamming(7,4) во втором томе трёхтомника Кострикина "Введение в алгебру" есть упражнение (глава 5 "Квадрики", параграф 3 "Проективные пространства"). Там эта задача решается через проективное пространство над [math].

В данном случае можно рассмотреть линейное пространство над [math]. Если например мы в каталог добавляем вектор из единиц, то это разрешает все комбинации мин в позициях 2 и 3 - гиперкуб со стороной 2.
Т.е. задачу можно сформулировать так: как покрыть это пространство целиком минимальным количеством гиперкубов со стороной 2.
Можно и обычное пространство взять, гиперкуб со стороной 3 в тороидальной топологии, надо покрыть его минимальным количеством гиперкубов со стороной 2.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Минимум числа путей

Сообщение zykov » 01 дек 2021, 13:45

Очевидная нижняя граница [math]. Но учитывая дискретность легко доказать более строгую нижнюю границу [math].
Интересно, что для [math] эта нижняя граница достижима. Будет ли дальше достижима?

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Минимум числа путей

Сообщение zykov » 02 дек 2021, 02:21

zykov писал(а):Source of the post Интересно, что для n=1..5 эта нижняя граница достижима.

Для [math] тоже подобрал:

Код: Выбрать все

   1   1   1   1   1   1
   1   1   2   2   3   3
   1   2   3   1   2   3
   1   2   1   3   3   2
   1   3   2   3   2   1
   1   3   3   2   1   2
   2   1   1   3   2   3
   2   1   3   1   3   2
   2   2   2   2   2   2
   2   2   3   3   1   1
   2   3   1   2   3   1
   2   3   2   1   1   3
   3   1   2   3   1   2
   3   1   3   2   2   1
   3   2   1   2   1   3
   3   2   2   1   3   1
   3   3   1   1   2   2
   3   3   3   3   3   3

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Минимум числа путей

Сообщение zykov » 02 дек 2021, 17:12

Этот метод (рекурсивный переход к следующему измерению) не сработал для [math].
Есть подозрение, что 27 недостижимо. Видимо включаются геометрически ограничения.
До этого были матрицы 4x4 (от 8 к 12) и 6x5 (от 12 к 18), а тут 9x6.
В 6x5 уже 6 было больше 5, но 9 больше 6 значительно.
Вобщем не знаю, что будет дальше и какая там асимптотика.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Минимум числа путей

Сообщение zykov » 04 дек 2021, 00:51

Тут такая ситуация.
Если две записи в каталоге не имеют общих элементов, то их гиперкубы размера 2 пересекаются ровно в 1 точке.
Вроде бы идеальный вариант. Но таких записей/вектров можно только 3 штуки подобрать. Первый - любой, второй - любой из [math], третий только один возможен. С учётом эквивлентности через симметрию получим только одну тройку векторов - все 1, все 2 и все 3.
Это работает для [math].
В первом случае два вектора покрывают [math].
Во втором случае три вектора покрывают [math].
Но уже при [math] оно сбоит. Покрытие от трёх будет [math], а надо 27. Такая тройка даёт минимальное количество непокрытых - 6. Но их форма плохая. Их не покрыть ни одним, ни двумя кубами размера 2. Нужно 3 куба.
Зато если взять только два из этой тройки и добавить ещё 3, то выйдет полное покрытие из 5 кубов. В приведенном примере вектор (2,2,2) не имеет общих элементов с другими 4 векторами. А эти 4 вектора попарно имеют ровно 1 общий элемент.
Поэтому кстати жданый алгоритм плохо работает. Он сразу добавляет эту тройку векторов, а непокрытый остаток имеет плохую форму.

Чем меньше общих элементов у записей, тем меньше их гиперкубы пересекаются, т.е. тем больше пара гиперкубов покрывает.
Нет общих элементов - пересекается в одной точке.
Ровно 1 общий элемент - пересекается в 2 точках.
Ровно 2 общих элемента - пересекается в 4 точках.
И т.д.

Дальше при [math] вектора имеют либо 0, либо 1, либо 2 общих элемента.
При [math] из 18 векторов каждый иимеет ровно 2 других вектора без общих элементов и 15 других с каждым ровно 2 общих элемента. (Тут картина наиболее симметрична, как например было при [math].)

Вот тут и проблема при переходе к [math]. Там уже не подобрать так чтобы было не более двух общих элементов в парах (доказать это?). А если будут пары с 3 или больше общими элементами, то у таких мар эффективность покрытия хуже и нужно будет больше векторов для полного покрытия.
Видимо с ростом [math] ситуация будет ухудшаться. (Потом и 3 общих не будет хватать, потом 4 и т.д.)
Отсюда вопрос, что будет асимптотически при больших [math]?
(Должно быть проще ответить, чем при конкретном конечном [math].)
Последний раз редактировалось zykov 04 дек 2021, 20:01, всего редактировалось 1 раз.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Минимум числа путей

Сообщение zykov » 04 дек 2021, 02:20

zykov писал(а):Source of the post При n=6 из 18 векторов каждый иимеет ровно 2 других вектора без общих элементов и 15 других с каждым ровно 2 общих элемента. (Тут картина наиболее симметрична, как например было при n=2.)

Вот эти 18 строк в симметричном виде.
6 групп по 3 строки. В каждой группе все 3 попарно не имееют общих элементов.
Между группами - любые две строки имеют ровно 2 общих элемента.

Код: Выбрать все

   1   1   1   1   1   1
   2   2   2   2   2   2
   3   3   3   3   3   3

   1   1   2   2   3   3
   2   2   3   3   1   1
   3   3   1   1   2   2

   1   3   2   3   2   1
   2   1   3   1   3   2
   3   2   1   2   1   3

   1   2   1   3   3   2
   2   3   2   1   1   3
   3   1   3   2   2   1

   1   2   3   1   2   3
   2   3   1   2   3   1
   3   1   2   3   1   2

   1   3   3   2   1   2
   2   1   1   3   2   3
   3   2   2   1   3   1

Отсюда и покрытие [math].

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Минимум числа путей

Сообщение zykov » 04 дек 2021, 21:47

zykov писал(а):Source of the post Отсюда вопрос, что будет асимптотически при больших n?

Попробовал прикинуть асимптотику. Правда сильно на пальцах - может где и не верно.

Вобщем, если взять два случайных вектора длины [math], то в среднем они будут иметь [math] общих элементов.
Вот например для [math] выходят в основном вектора с 2 общими элементами.
Тогда для количества векторов [math] и для больших [math] можно такое уравнение получить: [math].
Тогда будет [math].

В первом приближении это выходит те же [math].
Во втором приближении это выходит [math].
([math])

Относительная поправка экспоненциально мала (убывает в [math] раз примерно через [math]).
Абсолютная поправка равна [math]


Вернуться в «Математика»

Кто сейчас на форуме

Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 8 гостей