@python_beginners
Viktor31.07.2016
22:27:37
22:27:37
Ленивый алгоритм ведь будет обязательно работать если нет нескольких вершин с одинаковым числом ребер?
GoogleViktor31.07.2016
22:28:12
22:28:12
¯\_(ツ)_/¯
Николай31.07.2016
22:28:40
22:28:40
Ленивый алгоритм ведь будет обязательно работать если нет нескольких вершин с одинаковым числом ребер?
Питон просто будет брать вершину наименьшую по старшинству кольца (между номером 2 и 9 выберет 2)Т.е. по номеру вершины
Viktor31.07.2016
22:29:34
22:29:34
а если "отрывать" от графа "подграфы" для которых обязательно сработает ленивый алгоритм, а перебор использоватьна оставшейся части?
Питон просто будет брать вершину наименьшую по старшинству кольца (между номером 2 и 9 выберет 2)
смотря как ты его написалалгоритм, не питон :)
вот мой набросок https://repl.it/CiBA
Николай31.07.2016
22:30:26
22:30:26
Хочешь скрестить жадный и ленивый алгоритм?
Viktor31.07.2016
22:30:30
22:30:30
ага
например, он точно работает для цепей
Denis31.07.2016
22:31:03
22:31:03
Против него есть тест
Николай31.07.2016
22:32:27
22:32:27
Но каким же образом ты определишь где какие подграфы создавать?
GoogleViktor31.07.2016
22:32:42
22:32:42
найти все вершины с одним ребром, идти от них к следующим пока число вершин равно двум и таким образом получить подграф
для цепей число разрывов всегда равно len(chain)//2
так можно избавится от... кхм, щупалец?
Николай31.07.2016
22:33:52
22:33:52
Т.е. удалять если есть вершину с 1 ребром? Точнее вторую вершину, которая соединена ребром с одиночной?
Denis31.07.2016
22:34:07
22:34:07
Где в твоем решении ответ?
Viktor31.07.2016
22:34:11
22:34:11
ну, длина должна быть равна минимум двум
Denis31.07.2016
22:34:50
22:34:50
Если нет вершин с одним ребром?
Viktor31.07.2016
22:35:03
22:35:03
тогда от него нет толку
это просто частный случай, для которого мы можем получить значительное ускорение довольно простым способом
Denis31.07.2016
22:36:08
22:36:08
Но там будет тест, где этот алгоритм ничего не ускорит
Поэтому он не поможет решить задачу в общем случае
Viktor31.07.2016
22:36:31
22:36:31
и будет тест где ускорит
Николай31.07.2016
22:36:42
22:36:42
Ну там большинство тестов где нет с 1 ребром вершин
Но мразу после 1 удаления они появляются
Denis31.07.2016
22:36:59
22:36:59
Но если будет решение общего случая, тот тест пройдет и без этой оптимизации
Viktor31.07.2016
22:37:14
22:37:14
ну да
Николай31.07.2016
22:38:16
22:38:16
ладно. Спасибо, парни. Думаю завтра разберусь с этим иродом
GoogleНиколай31.07.2016
22:38:22
22:38:22
Спокойной всем
Viktor31.07.2016
22:38:37
22:38:37
то есть идея в переборе решении?
Николай31.07.2016
22:38:56
22:38:56
Как самая оптимизированная, пока да
Viktor31.07.2016
22:39:07
22:39:07
удаляем сначала по одному кольцу, потом по два, потом по три и так далее?
Николай31.07.2016
22:39:18
22:39:18
Типа
Там в среднем не больше 6ти колец
Удалений
Ну мб есть штук 7, но там попроще будет, думаю
Viktor31.07.2016
22:40:18
22:40:18
хм, а ведь если будет хоть одна вершина с одним ребром, то от её удаления нет толку?
Николай31.07.2016
22:40:59
22:40:59
От удаления соседней с ней толк есть, просто пока плохо представляю работу алгоритмп с этим условием
Мб будет и быстрее, но будет проходить не все, а лишь определённые варианты
"Одни и те же"
Viktor31.07.2016
22:42:27
22:42:27
эт не баг?
Николай31.07.2016
22:42:48
22:42:48
Лол
Viktor31.07.2016
22:43:13
22:43:13
хм, а ведь если будет хоть одна вершина с одним ребром, то от её удаления нет толку?
нам нужно её удалять только если нужно "освободить" соседнюю
А это нужно делать только если у соседней осталось всего одно ребро: связывающее её с первой.
А в таком случае разницы нет какую удалять: первую или вторую.Николай31.07.2016
22:43:54
22:43:54
Согласен. Просто в этом случае некоторве ходы будут повторяться
Николай31.07.2016
22:45:59
22:45:59
Ну если при удалении определённой вершины остаётся 1 ребро - то теппрь будет алгоритм по отрыванию щупальца, а это, как правило, цепная реакция. И раз это цепная реакция, по 1 и тому же пути будут ходить удаляя некоторве вершины
Viktor31.07.2016
22:46:00
22:46:00
хотя вот в таком случае это не верно:
.-.-.
|
.
GoogleНиколай31.07.2016
22:46:23
22:46:23
Ну тот только 1 варик)
Viktor31.07.2016
22:46:55
22:46:55
хотя вот в таком случае это не верно:
.-.-.
|
.
тут по моей логике нужно убрать все крайние вершины и оставить только центральную, что не верноНиколай31.07.2016
22:47:15
22:47:15
А. Ну неплохо)
?
Спасибо в любом случае
Без вас хз скок бы с ней думал
4 часа на сон осталось)
AdminERROR: S client not available
Viktor31.07.2016
22:49:04
22:49:04
много
я хз правда или нет, но спать надо кратно полутора часам
s/надо/лучше
Фԉùཎыч⚠️31.07.2016
22:57:00
22:57:00
Хоп
Николай01.08.2016
04:26:15
04:26:15
удаляем сначала по одному кольцу, потом по два, потом по три и так далее?
Ребят, а что мне поможет сделать конструкцию, при которой можно увеличивать вложенность циклов т.о., чтобы все циклы были в одной области видимости.
Кроме global x для каждой итерации, вложенных функций (и то, пока не могу полностью понять конструкцию), модулей re и random, чтобы генерировать случайные буквы для каждого числа цикла.
Прикрепил к вопросу то, что я имею ввиду.Viktor01.08.2016
04:27:03
04:27:03
Николай01.08.2016
04:27:34
04:27:34
удаляем сначала по одному кольцу, потом по два, потом по три и так далее?
Ну помнишь мы вчера решили этоНиколай01.08.2016
04:28:10
04:28:10
Просто чтобы по кольцу прибавлять - нужно делать доп вложенный цикл
ZartGoogleНиколай01.08.2016
04:29:34
04:29:34
Оке. Посмотрю эту библиотеку. Не пользовался ещё
Viktor01.08.2016
04:29:45
04:29:45
Зачем строить велосипеды
Николай01.08.2016
04:29:48
04:29:48
Цикл то понятен
Viktor01.08.2016
04:30:27
04:30:27
Ну а в чем вопрос?
Николай01.08.2016
04:30:39
04:30:39
Ну если я раньше их не видел, то вполне вероятно что их и хотел строить)
Теперь не в чём
*ни в чём
Спасиб.
Viktor01.08.2016
04:31:20
04:31:20
:)
Николай01.08.2016
04:31:53
04:31:53
?
Николай01.08.2016
04:32:21
04:32:21
Ну так да. Но в тот момент я не знал про ленивый способ)
И не знал куда этот применять