|
Имеется набор стандартного домино: 28 костяшек с двумя значениями от 0 до 6. Из этого набора наугад выбирается N костяшек. Нужно рассчитать максимально возможное количество "концов" разложения этих N костяшек. То есть для примера если это костяшки (0-1), (1-2), (2-3), (3-4), то у этого набора только одно возможное разложение в линию, и, следовательно, два "конца". У набора (0-1), (0-2), (0-3), (0-4) разложение получается крестом, поэтому "концов" получается 4. Я пытался всё перевести в граф (ребра - это и есть костяшки) и на нём уже придумать алгоритм (убирать циклы в графе), но не особо получилось. Хотя остальные задания как-раз таки за счет этого получились легко: проверить, имеется ли полное разложение набора (граф связный), можно ли сложить в круг этот набор (все вершины имеют степень, равную 2 и граф связный), можно ли сложить в линию этот набор (все вершины имеют степень меньше 3 и граф связный)... задан 26 Мар '17 4:27 
chepiov
показано 5 из 9
показать еще 4
|
Здравствуйте
Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.
Присоединяйтесь!
отмечен:
задан
26 Мар '17 4:27
показан
1613 раз
обновлен
27 Мар '17 11:21
Связанные вопросы
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Наверное, надо начать с точной формулировки правила, которое набору костяшек ставит в соответствие "концы". Вот, например, возьмём все кости. Сколько будет "концов" при этом? У меня нет разумных трактовок.
@falcao Ой, забыл описать, извините. Как я понимаю: имеется ввиду из всех вариантов разложения всех костей выбрать тот вариант, при котором максимально количество тупиковых ветвей этого разложения. Костяшки можно складывать одинаковыми концами. Если костяшка симметрична, то на ней можно ветвиться в четыре стороны, прикладывая с каждой стороны другую костяшку стороной с тем же значением. Как-то так...Наверное это можно сделать брутфорсом, но возможно существует какая-то хитрость
@chepiov: как я понял, составляется дерево, вершины которого помечены числами от 0 до 6 (могут быть разные вершины с одинаковыми метками), а рёбра соответствуют взятым костям домино, и требуется определить, какое максимальное число висячих вершин (степени 1) у такого дерева может быть. Если так, то условие в общих чертах понятно, но надо оговорить, что делать, если дерево составить вообще нельзя (типа, взяты кости 0-1 и 2-3). Также не до конца ясна структура дерева с участием дублей.
@falcao дерево - это моя догадка, при помощи этого удалось решить другие задачи (и я делал, что вершины с одинаковыми метками - это одна вершина, так как в любом случае именно ребрами представлены костяшки). Да, именно число вершин со степенью 1 и нужно посчитать. Предполагается, что на вход алгоритму будет подаваться именно такой набор костяшек, который можно разложить таким образом, что будут участвовать все костяшки (граф связный). Дубли - это места, которые могут быть разветвлены в четыре стороны (если конечно есть соответсвующая дублю костяшка)
@falcao Я пытался убирать из дерева ребра, разрывая циклы, то есть просто не соединять костяшки, так как всё равно это считается корректным разложением. То есть например костяшки (1-2), (2-3), (3-1) можно соединить циклом, тогда вершин со степенью 1 нет, но если разорвать цикл, то все равно разложение корректное - костяшки расположены в линию, все костяшки задействованы. Тогда "концов" будет 2
@chepiov: прежде чем решать задачу, надо её точно поставить. Пока у на нет дерева, а есть только выбранные костяшки. И надо уточнить правила. В частности, с дублями пока ситуация не ясна.
@falcao "Дубли - это места, которые могут быть разветвлены в четыре стороны (если конечно есть соответсвующая дублю костяшка)" То есть, например, есть костяшка (2-2). И допустим есть костяшки (2-0), (2-3), (2-5), (2-6) и (3-1). Тогда к этой костяшке можно подставить со всех четырех сторон костяшки с 2-кой, но не можем подставить (3-1):
|1| |-| |3| | |3| |-| |2| | |5-2|-|2-2|-|2-6| | |2| |-| |0|Граф - это я так подумал, возможно как-то без него придумать алгоритм. http://i.imgur.com/tLmMCgI.jpg
@chepiov: на языке графов удобно выражать мысли. Поэтому их полезно привлекать.
Суть условия мне в принципе понятна (кроме того момента, когда дерево вообще образовать нельзя -- что делать в этом случае, Вы так и не пояснили). Есть ли здесь какой-то быстрый алгоритм, я пока не могу сказать. Наверное, надо начать с того, чтобы протестировать эту задачу на каких-то примерах -- не слишком простых, но и не слишком сложных. Из общих соображений понятно, что общая сумма степеней вершин нам известна, поэтому для увеличения числа висячих, надо создавать точки ветвления с как можно большей степенью.
@falcao, спасибо за помощь. "кроме того момента, когда дерево вообще образовать нельзя -- что делать в этом случае, Вы так и не пояснили" -- полагается, что на вход всегда подаются костяшки, которые можно разложить в дерево (всегда только одна компонента). Вроде понял: нужно при помощи обхода в глубину из любого дубля построить остовое дерево и отложить те ребра, которые не вошли в обход. Рёбра, не вошедшие в обход могут быть преобразованы в листья просто не соединяя их "вторым концом". Тогда количество "концов" - это количество листьев плюс незадействованные у дублей стороны.