Поиск алгоритма в графе Добрый день.
Я не программист, но так вышло, что должен решить нетривиальную абстрактную задачу. Чтобы её конкретизировать я попытался её представить в виде графа.
Итак:
Есть невзвешенный, связанный, неориентированный граф. Порядок графа = 2^N.
Размер графа = 2^N * (N+1). При этом каждая вершина имеет N ребер и ещё петлю. (в размере графа я посчитал петлю как одно ребро - поэтому (N+1), не знаю, правильно ли это). Рёбра графа соединяют вершины по заранее известному алгоритму.
Для формулировки задачи я должен теперь привести аналогию. Допустим, что есть N школьных классов. И есть большое общежитие, в котором 2^N комнат. Соответственно, каждая комната соединена с N другими комнатами. В каждой комнате можно разместить по одному школьнику. Каждый школьник является членом какого-либо одного класса. Но количество школьников в классе может быть разное. Я сам могу распределить школьников по классам.
А теперь задача - разместить школьников по комнатам надо так, чтобы я, попав в любую комнату, мог за один переход дойти до любой классной комнаты. А классная комната - это комната, где сидит школьник из этого класса. Т.е. мне говорят - класс № 16. Я вижу, что есть 10 комнат, в которых сидят школьники из класса №16, и хотя бы в одну такую комнату я могу попасть, сделав только один переход.
И ещё - я могу и просто остаться в комнате, если я уже в той самой комнате, которая мне нужна (для этого как раз петли).
Сформулировать эту задачу в терминах графов у меня не получается. Я графы помню из Университета просто как понятие, но, к сожалению, не прочувствовал их тогда. Сейчас пытаюсь разобраться, но понимаю, что без совета вряд ли смогу справиться.
Ещё раз скажу, что я не программист. Но очень хочется подступиться как-нибудь к этой задачке. Посоветуйте, пожалуйста, как быть.
Поиск алгоритма в графе Добрый день.
Я не программист, но так вышло, что должен решить нетривиальную абстрактную задачу. Чтобы её конкретизировать я попытался её представить в виде графа.
Итак:
Есть невзвешенный, связанный, неориентированный граф. Порядок графа = 2^N.
Размер графа = 2^N * (N+1). При этом каждая вершина имеет N ребер и ещё петлю. (в размере графа я посчитал петлю как одно ребро - поэтому (N+1), не знаю, правильно ли это). Рёбра графа соединяют вершины по заранее известному алгоритму.
Для формулировки задачи я должен теперь привести аналогию. Допустим, что есть N школьных классов. И есть большое общежитие, в котором 2^N комнат. Соответственно, каждая комната соединена с N другими комнатами. В каждой комнате можно разместить по одному школьнику. Каждый школьник является членом какого-либо одного класса. Но количество школьников в классе может быть разное. Я сам могу распределить школьников по классам.
А теперь задача - разместить школьников по комнатам надо так, чтобы я, попав в любую комнату, мог за один переход дойти до любой классной комнаты. А классная комната - это комната, где сидит школьник из этого класса. Т.е. мне говорят - класс № 16. Я вижу, что есть 10 комнат, в которых сидят школьники из класса №16, и хотя бы в одну такую комнату я могу попасть, сделав только один переход.
И ещё - я могу и просто остаться в комнате, если я уже в той самой комнате, которая мне нужна (для этого как раз петли).
Сформулировать эту задачу в терминах графов у меня не получается. Я графы помню из Университета просто как понятие, но, к сожалению, не прочувствовал их тогда. Сейчас пытаюсь разобраться, но понимаю, что без совета вряд ли смогу справиться.
Ещё раз скажу, что я не программист. Но очень хочется подступиться как-нибудь к этой задачке. Посоветуйте, пожалуйста, как быть.
Я не программист, но так вышло, что должен решить нетривиальную абстрактную задачу. Чтобы её конкретизировать я попытался её представить в виде графа.
Итак:
Есть невзвешенный, связанный, неориентированный граф. Порядок графа = 2^N.
Размер графа = 2^N * (N+1). При этом каждая вершина имеет N ребер и ещё петлю. (в размере графа я посчитал петлю как одно ребро - поэтому (N+1), не знаю, правильно ли это). Рёбра графа соединяют вершины по заранее известному алгоритму.
Для формулировки задачи я должен теперь привести аналогию. Допустим, что есть N школьных классов. И есть большое общежитие, в котором 2^N комнат. Соответственно, каждая комната соединена с N другими комнатами. В каждой комнате можно разместить по одному школьнику. Каждый школьник является членом какого-либо одного класса. Но количество школьников в классе может быть разное. Я сам могу распределить школьников по классам.
А теперь задача - разместить школьников по комнатам надо так, чтобы я, попав в любую комнату, мог за один переход дойти до любой классной комнаты. А классная комната - это комната, где сидит школьник из этого класса. Т.е. мне говорят - класс № 16. Я вижу, что есть 10 комнат, в которых сидят школьники из класса №16, и хотя бы в одну такую комнату я могу попасть, сделав только один переход.
И ещё - я могу и просто остаться в комнате, если я уже в той самой комнате, которая мне нужна (для этого как раз петли).
Сформулировать эту задачу в терминах графов у меня не получается. Я графы помню из Университета просто как понятие, но, к сожалению, не прочувствовал их тогда. Сейчас пытаюсь разобраться, но понимаю, что без совета вряд ли смогу справиться.
Ещё раз скажу, что я не программист. Но очень хочется подступиться как-нибудь к этой задачке. Посоветуйте, пожалуйста, как быть.
Похожие вопросы
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Отвечай на вопросы, зарабатывай баллы и трать их на призы.
Подробнее
Подробнее
Добрый день! Ваша задача звучит как задача о поиске хорошо связанного графа. Давайте попробуем сформулировать её в терминах графов.
У вас есть граф, вершины которого представляют собой комнаты, а рёбра соединяют комнаты, в которых находятся школьники из одного класса. Таким образом, в каждой вершине (комнате) есть N рёбер, ведущих к другим вершинам, где также находятся школьники из того же класса.
Задача заключается в том, чтобы расставить школьников таким образом, чтобы для любой школьной комнаты (вершины графа) существовал путь (по рёбрам), который позволяет дойти до любой другой школьной комнаты из этого же класса.
Для решения данной задачи можно воспользоваться алгоритмом поиска в ширину (BFS) или алгоритмом поиска в глубину (DFS) в графе. Необходимо запустить алгоритм поиска из каждой вершины и проверить, достижимы ли все остальные вершины из данной. Если для каждой вершины каждая другая вершина является достижимой, то граф удовлетворяет условию задачи.
Надеюсь, данное объяснение поможет вам в решении задачи. Если у вас возникнут дополнительные вопросы или потребуется дополнительная помощь, не стесняйтесь обращаться. Удачи в решении задачи!