Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
 Алгоритм Магу и задачи: о нахождении клики, о расстановке ферзей, о минимальной раскраске  [new]
Мудроглюков
Member

Откуда:
Сообщений: 8314
..., и другие задачи.

Так алгоритм Магу "сделал" теоретическую сложность этих задач ниже экспоненциальной?

? Или-таки стали вникать в суть и пошло-поехало:
кроме P и NP
P — полиномиальное время (наиболее часто используется в вычислениях, поскольку задачи этого класса могут быть решены за реальное время)
NP — для задач этого класса неизвестны эффективные алгоритмы решения, поэтому рассматриваются алгоритмы проверки правильности решений (полный перебор вариантов)

обязательно надо уточнять (, чтобы всё не выглядело ерундой)

PSPACE — полиномиальные затраты памяти
EXP — экспоненциальная временная сложность
ESPACE — экспоненциальные затраты памяти
...

Ведь оптимальное раскрытие-сокращение длиннющих многопеременных булевых выражений требует огромной памяти. И т.д. и т.п.

__________________________
__________________________
PS Что есть "алгоритм Магу" -
http://sci.sernam.ru/book_comb.php?id=31
...
26 сен 18, 15:32    [21686900]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм Магу и задачи: о нахождении клики, о расстановке ферзей, о минимальной раскраске  [new]
Мудроглюков
Member

Откуда:
Сообщений: 8314
ведь наверно любой средний программист (и алгоритмист) легко
переведет экспоненциальный рост времени в экспоненциальный рост памяти, "сделав" при этом рост времени вообще линейным

а есть еще массивные параллельные вычисления, где дополнительные параллельные блоки могут подключаться
по мере надобности,
а есть еще аналоговые вычислительные подмодули,
а есть еще ...

и еще что-то обязательно появится
29 сен 18, 14:22    [21689868]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм Магу и задачи: о нахождении клики, о расстановке ферзей, о минимальной раскраске  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4489
Мудроглюков
ведь наверно любой средний программист (и алгоритмист) легко
переведет экспоненциальный рост времени в экспоненциальный рост памяти, "сделав" при этом рост времени вообще линейным

а есть еще массивные параллельные вычисления, где дополнительные параллельные блоки могут подключаться
по мере надобности,
а есть еще аналоговые вычислительные подмодули,
а есть еще ...

и еще что-то обязательно появится
заполнение экспоненциальной памяти само по себе провоцирует экспоненциальный рост времени на это дело, если конечно она не заполнена до этого
23 янв 19, 09:26    [21791781]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм Магу и задачи: о нахождении клики, о расстановке ферзей, о минимальной раскраске  [new]
mayton
Member

Откуда: loopback
Сообщений: 40521
Хм. Забавно. Новость от 2018 года. https://nplus1.ru/news/2018/04/10/chromatic-number

Уже 4 красок мало?
23 янв 19, 11:44    [21791945]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм Магу и задачи: о нахождении клики, о расстановке ферзей, о минимальной раскраске  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
mayton
Хм. Забавно. Новость от 2018 года. https://nplus1.ru/news/2018/04/10/chromatic-number

Уже 4 красок мало?
В данной работе работает шестиугольник, к которому пристыкован шестиугольник.
Во всех вершинах (кроме крайних ?) сходятся 3 грани.
6+6=12.

Есть ещё один вариант.
8+4=12.

Восьмиугольник и четырехугольник.
Во всех вершинах сходятся 3 грани.

Здесь появляется интересная задачка:
найти ещё картинки (или графы), повторяющиеся из одних и тех же сторон (или группы сторон) между гранями, где в вершине картинки только 3 грани.
23 янв 19, 12:57    [21792003]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм Магу и задачи: о нахождении клики, о расстановке ферзей, о минимальной раскраске  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
Например, ещё:

в сотах или в шестиугольниках, как в статье, вместо вершины будет треугольник.

Получаем 12-угольник и треугольник.

А далее, 24 и 3, 48 и 3 и т.д.
23 янв 19, 13:02    [21792016]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм Магу и задачи: о нахождении клики, о расстановке ферзей, о минимальной раскраске  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
Ошибся:

12, 6 и 3
24, 12, 6 и 3
48, 24, 12, 6 и 3
и т.д.
23 янв 19, 13:04    [21792018]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм Магу и задачи: о нахождении клики, о расстановке ферзей, о минимальной раскраске  [new]
mayton
Member

Откуда: loopback
Сообщений: 40521
Был в форумах такой Рэт-Крысопыт. Многим он запомнился хроническим депрессивным настроением
и жалобами на неудачи. Читатели ПТ вкурсе.

Но кроме этого он решал задачу изоморфизма графов на сях. И на тот момент лучше чем аналоги
и интернетах. Исходник он мне передавал но я к сожалению его прое.. не сохранил вобщем.
23 янв 19, 13:33    [21792059]     Ответить | Цитировать Сообщить модератору
Все форумы / Программирование Ответить