|
Алгоритм Магу и задачи: о нахождении клики, о расстановке ферзей, о минимальной раскраске
|
|||
---|---|---|---|
#18+
..., и другие задачи. Так алгоритм Магу "сделал" теоретическую сложность этих задач ниже экспоненциальной? ? Или-таки стали вникать в суть и пошло-поехало: кроме P и NP P — полиномиальное время (наиболее часто используется в вычислениях, поскольку задачи этого класса могут быть решены за реальное время) NP — для задач этого класса неизвестны эффективные алгоритмы решения, поэтому рассматриваются алгоритмы проверки правильности решений (полный перебор вариантов) обязательно надо уточнять (, чтобы всё не выглядело ерундой) PSPACE — полиномиальные затраты памяти EXP — экспоненциальная временная сложность ESPACE — экспоненциальные затраты памяти ... Ведь оптимальное раскрытие-сокращение длиннющих многопеременных булевых выражений требует огромной памяти. И т.д. и т.п. __________________________ __________________________ PS Что есть "алгоритм Магу" - http://sci.sernam.ru/book_comb.php?id=31 ... ... |
|||
:
Нравится:
Не нравится:
|
|||
26.09.2018, 15:32 |
|
Алгоритм Магу и задачи: о нахождении клики, о расстановке ферзей, о минимальной раскраске
|
|||
---|---|---|---|
#18+
ведь наверно любой средний программист (и алгоритмист) легко переведет экспоненциальный рост времени в экспоненциальный рост памяти, "сделав" при этом рост времени вообще линейным а есть еще массивные параллельные вычисления, где дополнительные параллельные блоки могут подключаться по мере надобности, а есть еще аналоговые вычислительные подмодули, а есть еще ... и еще что-то обязательно появится ... |
|||
:
Нравится:
Не нравится:
|
|||
29.09.2018, 14:22 |
|
Алгоритм Магу и задачи: о нахождении клики, о расстановке ферзей, о минимальной раскраске
|
|||
---|---|---|---|
#18+
Мудроглюковведь наверно любой средний программист (и алгоритмист) легко переведет экспоненциальный рост времени в экспоненциальный рост памяти, "сделав" при этом рост времени вообще линейным а есть еще массивные параллельные вычисления, где дополнительные параллельные блоки могут подключаться по мере надобности, а есть еще аналоговые вычислительные подмодули, а есть еще ... и еще что-то обязательно появитсязаполнение экспоненциальной памяти само по себе провоцирует экспоненциальный рост времени на это дело, если конечно она не заполнена до этого ... |
|||
:
Нравится:
Не нравится:
|
|||
23.01.2019, 09:26 |
|
Алгоритм Магу и задачи: о нахождении клики, о расстановке ферзей, о минимальной раскраске
|
|||
---|---|---|---|
#18+
Хм. Забавно. Новость от 2018 года. https://nplus1.ru/news/2018/04/10/chromatic-number Уже 4 красок мало? ... |
|||
:
Нравится:
Не нравится:
|
|||
23.01.2019, 11:44 |
|
Алгоритм Магу и задачи: о нахождении клики, о расстановке ферзей, о минимальной раскраске
|
|||
---|---|---|---|
#18+
maytonХм. Забавно. Новость от 2018 года. https://nplus1.ru/news/2018/04/10/chromatic-number Уже 4 красок мало?В данной работе работает шестиугольник, к которому пристыкован шестиугольник. Во всех вершинах (кроме крайних ?) сходятся 3 грани. 6+6=12. Есть ещё один вариант. 8+4=12. Восьмиугольник и четырехугольник. Во всех вершинах сходятся 3 грани. Здесь появляется интересная задачка: найти ещё картинки (или графы), повторяющиеся из одних и тех же сторон (или группы сторон) между гранями, где в вершине картинки только 3 грани. ... |
|||
:
Нравится:
Не нравится:
|
|||
23.01.2019, 12:57 |
|
Алгоритм Магу и задачи: о нахождении клики, о расстановке ферзей, о минимальной раскраске
|
|||
---|---|---|---|
#18+
Например, ещё: в сотах или в шестиугольниках, как в статье, вместо вершины будет треугольник. Получаем 12-угольник и треугольник. А далее, 24 и 3, 48 и 3 и т.д. ... |
|||
:
Нравится:
Не нравится:
|
|||
23.01.2019, 13:02 |
|
Алгоритм Магу и задачи: о нахождении клики, о расстановке ферзей, о минимальной раскраске
|
|||
---|---|---|---|
#18+
Ошибся: 12, 6 и 3 24, 12, 6 и 3 48, 24, 12, 6 и 3 и т.д. ... |
|||
:
Нравится:
Не нравится:
|
|||
23.01.2019, 13:04 |
|
Алгоритм Магу и задачи: о нахождении клики, о расстановке ферзей, о минимальной раскраске
|
|||
---|---|---|---|
#18+
Был в форумах такой Рэт-Крысопыт. Многим он запомнился хроническим депрессивным настроением и жалобами на неудачи. Читатели ПТ вкурсе. Но кроме этого он решал задачу изоморфизма графов на сях. И на тот момент лучше чем аналоги и интернетах. Исходник он мне передавал но я к сожалению его прое.. не сохранил вобщем. ... |
|||
:
Нравится:
Не нравится:
|
|||
23.01.2019, 13:33 |
|
|
start [/forum/topic.php?fid=16&fpage=11&tid=1340004]: |
0ms |
get settings: |
11ms |
get forum list: |
14ms |
check forum access: |
5ms |
check topic access: |
5ms |
track hit: |
71ms |
get topic data: |
13ms |
get forum data: |
2ms |
get page messages: |
47ms |
get tp. blocked users: |
2ms |
others: | 14ms |
total: | 184ms |
0 / 0 |