V🇺
обходить дфсом запоминая 3 последних родителя?
долго
Size: a a a
2016 November 16
AK
кого долго? хранить трёх родителей? за единицу спрашивать есть ли ребро?
V🇺
если имеется ввиду dfs по тройкам вершин
V🇺
если нет, то это не всегда работает
N
не програмные размышления решений можно писать? или тоже на пасту?
AK
если нет, то это не всегда работает
контрпример завезут?
AK
Это не задаче о шахматном коне, если что
AK
не надо её к нпполной сводить
AK
офк можно матрицу смежности в 4 степень возвести и там немного поколдовать, но это долго
V🇺
контрпример завезут?
расскажи более подробно, как ты решаешь - напишу контрпример)
N
взять вершину, если ребер 2 или больше, проверяем всех соседних на наличие еще одной общей вершины, т.е. хотя бы у двух одна общая, если нет, вычеркивать из графа текущую вершину .
?
?
V🇺
взять вершину, если ребер 2 или больше, проверяем всех соседних на наличие еще одной общей вершины, т.е. хотя бы у двух одна общая, если нет, вычеркивать из графа текущую вершину .
?
?
> проверяем всех соседних на наличие еще одной общей вершины
проверяем пары соседних, или что имеется ввиду под общей вершиной?
проверяем пары соседних, или что имеется ввиду под общей вершиной?
N
пусть текущая вершина - родитель, все соседниие - дети.
у всех детей найти одну или больше общих вершин
у всех детей найти одну или больше общих вершин
N
тогда цикл замкнется, только по стоимости хз как выйдет )
N
вроде как вложеный цикл n^2
V🇺
да, только в худшем случае все вершины побывают текущей, то есть в сумме n^3
N
тогда удалять из графа родителя, а его детей из итератора. если кто из них входит в ответ, то все равно попадет в проверку на другой вершине
V🇺
как используется итератор? в каком случае удаленные из него вершины не рассматриваются?
N
не, чет я сморозил, так можно всех выкинуть из проверки и не решить, даже при наличии решения
m
есть денить статья про составление расписаний с помощью генетического алгоритм?