Собственно, родил такую задачу. Пусть есть стен, в каждой стене по двери, одна из дверей заминирована. Задача провести робота через все стены, чтобы он не взорвался. Это делается путем дачи роботу некоего листа с маршрутом из общего каталога, расположение мин нам известно.
Задача - найти минимальное число листов с маршрутом в каталоге, чтобы при любом расположении мин нашелся хотя бы один лист с безопасным маршрутом.
Для очевиден ответ листа (маршруты ), для надо листа (маршруты ), а что там с и т.д.? Желательно еще в пределе очень большого
Минимум числа путей
Минимум числа путей
Для [math] вышло 5.
[math]
[math]
Минимум числа путей
Посчитал для [math], вышло 8.
Вобщем есть подозрение, что [math] при [math].
A061419, A081226, A156623
Можно ещё так записать [math], где [math].
(Там в A081226 в формуле упоминается золотое сечение, но это не верно, хотя [math] и близко к [math].)
Код: Выбрать все
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 писал(а):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 писал(а):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 получилось.
Минимум числа путей
Хорошая задача. Что-то есть общее с viewtopic.php?f=4&t=529 например то, что в каждом сечении (стене) каталог должен быть распределен как можно более равномерно (число вхождений 1,2 и 3 на каждой стене не могут различаться более чем на 1) И действительно, если есть каталог, в котором гарантированно обходится любой набор мин, а число вхождений на 1м месте номера 1 на два больше чем номера 2, каталог можно хитро преобразовать, что их станет поровну и в новом каталоге также гарантированно обходится любой набор мин.Доказательство немного путаное, при нашей терминологии. Заменим в одном маршруте 1 на 2,тогда станет поровну маршрутов, начинающихся с 1 и 2, и в них поменяем местами хвосты-подкаталоги.Рассматриваем набор мин, якобы опровергающий новый (более равномерный) каталог. Если он начинается с мины 1, то набор, начинающийся с мины 2 -опровергает каталог, с которого мы начали, противоречие. Если он начинается с мин 2 или 3, то сам опровергает исходный каталог, тоже противоречие. Значит можно искать только каталоги, в которых числа используемых дверей на каждой стенке отличаются максимум на 1. И конечно формальная перенумерация дверей на каждой стенке переводит хороший каталог снова в хороший. Все это сокращает перебор
Минимум числа путей
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.
Минимум числа путей
Очевидная нижняя граница [math]. Но учитывая дискретность легко доказать более строгую нижнюю границу [math].
Интересно, что для [math] эта нижняя граница достижима. Будет ли дальше достижима?
Интересно, что для [math] эта нижняя граница достижима. Будет ли дальше достижима?
Минимум числа путей
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
Минимум числа путей
Этот метод (рекурсивный переход к следующему измерению) не сработал для [math].
Есть подозрение, что 27 недостижимо. Видимо включаются геометрически ограничения.
До этого были матрицы 4x4 (от 8 к 12) и 6x5 (от 12 к 18), а тут 9x6.
В 6x5 уже 6 было больше 5, но 9 больше 6 значительно.
Вобщем не знаю, что будет дальше и какая там асимптотика.
Есть подозрение, что 27 недостижимо. Видимо включаются геометрически ограничения.
До этого были матрицы 4x4 (от 8 к 12) и 6x5 (от 12 к 18), а тут 9x6.
В 6x5 уже 6 было больше 5, но 9 больше 6 значительно.
Вобщем не знаю, что будет дальше и какая там асимптотика.
Минимум числа путей
Тут такая ситуация.
Если две записи в каталоге не имеют общих элементов, то их гиперкубы размера 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].)
Если две записи в каталоге не имеют общих элементов, то их гиперкубы размера 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 писал(а):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 писал(а):Source of the post Отсюда вопрос, что будет асимптотически при больших n?
Попробовал прикинуть асимптотику. Правда сильно на пальцах - может где и не верно.
Вобщем, если взять два случайных вектора длины [math], то в среднем они будут иметь [math] общих элементов.
Вот например для [math] выходят в основном вектора с 2 общими элементами.
Тогда для количества векторов [math] и для больших [math] можно такое уравнение получить: [math].
Тогда будет [math].
В первом приближении это выходит те же [math].
Во втором приближении это выходит [math].
([math])
Относительная поправка экспоненциально мала (убывает в [math] раз примерно через [math]).
Абсолютная поправка равна [math]
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 5 гостей