Добрый день, уважаемые Коты!

На нетематическом форуме на днях возник вопрос. Есть квадрат 4х4 (16 комнат). Между комнатами двери (24 штуки), которые могут быть в открытом или закрытом состоянии (с вероятностью 50%). Найти: 1) Вероятность с которой можно попасть из любой (для определенности верхней левой) в любую другую комнату. Задача решалась аналитически и на компьютере. Было ли найдено аналитическое решение мне не известно, а вот компьютер дал вероятность 3,3%.
Затем задачу расширили. Нужно найти полное количество любых состояний дверей, при которых путь во всем комнаты будет открыт. Т.е. всего состояний дверей 2^24 = примерно 16 млн. Полным перебором программа нашла решение за 1,7 сек - 555195 перестановок (те же 3,3%).
Программу оптимизировали как могли и вышли на такую скорость. Но!
Дальше возникла задача найти количество решений для квадрата 5х5. Дверей в данном случае уже 40, т.е. это сложность возрастает в 2^16 раз. Плюс комнат больше в 1,56 раз, т.е. больше проверок в циклах. Примерная сложность решения будет в 100 тыс. раз больше. Ожидаемое время решения на одном ядре не самого свежего компьютера порядка 50 часов.

Теперь смотри в будущее. Каким образом решить эту задачу для квадрата 6х6? Дверей будет 60, это еще в 2^20 раз больше, комнат больше в 1,5. Ожидаемое время решения, мммм... 8 тыс. лет.

Что может предложить в данных условиях общественность?

По моим прикидкам, на каком-нибудь дорогущем Stratix IV перебор всех вариантов займет не меньше нескольких месяцев.

Общественность может предложить повторить на п.л.и.с. известный японский проект PROLOG-компьютера и на нём попытаться таки решить задачку не простым перебором.
( Можно сразу доработать проект до "FUZZYPARLOG" что sело упростит и ускорит на пару порядков. )

Остаётся только оценить затраты на оборудование и человеко-часы проектирования и программирования.

PCBWay - всего $5 за 10 печатных плат, первый заказ для новых клиентов БЕСПЛАТЕН

Сборка печатных плат от $30 + БЕСПЛАТНАЯ доставка по всему миру + трафарет

Онлайн просмотровщик Gerber-файлов от PCBWay + Услуги 3D печати