Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 2 |
[ Сообщений: 15 ] | На страницу 1, 2 След. |
|
Автор | Сообщение | |
---|---|---|
Student Studentovich |
|
|
Интересная задача на расставление простых чисел по ребрам полного графа. Думаю никто меня не обвинит, если приведу оптимальный вариант для [math]n=4[/math] [math]\{11,3,7\},\{11,5,2\},\{3,5,13\},\{7,2,13\}.[/math] Энергия графа при этом [math]718.[/math] |
||
Вернуться к началу | ||
ivashenko |
|
|
А что делать-то надо? И как взаимосвязаны энергия графа и расставленные простые числа, в чем оптимальность?
|
||
Вернуться к началу | ||
Student Studentovich |
|
|
ivashenko
По ссылке вроде все ясно. Расставить простые числа в качестве весов для ребер полного графа (т.е. все ребра соединены с друг другом). При этом надо добиться минимума "энергии графа". Энергия графа вычисляется как сумма энергий узлов, а энергия узлов это произведение весов всех смежных с узлом ребер. Если у нас [math]n[/math] узлов, очевидно, что ребер [math]\frac{n(n-1)}{2}[/math] и надо расставить столько же первых простых чисел. В наборе указанном выше выписаны веса ребер смежных к четырем узлам [math]n=4[/math]. Вес в этом не оптимальном примере [math]2 \cdot 3\cdot 7+2\cdot 5\cdot 11+3\cdot 5\cdot 13+7\cdot 11\cdot 13=1348.[/math] |
||
Вернуться к началу | ||
За это сообщение пользователю Student Studentovich "Спасибо" сказали: ivashenko |
||
ivashenko |
|
|
Student Studentovich писал(а): По ссылке вроде все ясно. Я с english не особо лажу. |
||
Вернуться к началу | ||
ivashenko |
|
|
Ну так это задача на оптимизацию, которая похоже решается перебором или здесь есть закономерности?
|
||
Вернуться к началу | ||
Student Studentovich |
|
|
Перебором вы максимум решите только для [math]n=4;5;6[/math] ну черт с ним [math]7[/math]. А в задаче [math]n=4..25.[/math]
Если граф представить в виде матрицы смежности то перестановок будет [math]\frac12 n(n-1)![/math]. Это много. А закономерности искать надо. Хотя они не всегда будут приводить к оптимальному варианту. |
||
Вернуться к началу | ||
ivashenko |
|
|
Student Studentovich писал(а): А закономерности искать надо. А если их нет? |
||
Вернуться к началу | ||
Nataly-Mak |
|
|
Student Studentovich писал(а): Если граф представить в виде матрицы смежности то перестановок будет [math]\frac12 n(n-1)![/math]. Вот-вот, надо работать с матрицами и забыть вообще про графы Был уже подобный конкурс с графами у Al. Но быстро все поняли, что ни к чёрту графы не нужны в задаче, а всё сводится к линейкам. Я в том конкурсе участвовала. Там было интересно - вновинку была задача. Я там искала симметричные графы (по линейкам). Ко мне присоединился один конкурсант из США - по поиску симметричных решений. Мы с ним классно поработали. А в данной задаче всё сводится к матрицам. |
||
Вернуться к началу | ||
Nataly-Mak |
|
|
Вот он - тот конкурс с графами, о котором я сказала выше
http://azspcs.com/Contest/GracefulGraphs Посмотрите таблицу результатов в этом конкурсе http://azspcs.com/Contest/GracefulGraphs/Standings Больше половины таблицы - 25 баллов Быстренько нашли в Сети эти самые линейки - готовый алгоритм! Применили его и... задача полностью решена. Я там на 80-й позиции. После того, как задачу решила, начала заниматься поиском симметричных решений. Это было интересно! Может быть, и в теперешнем конкурсе есть нечто подобное. Во всяком случае, Ярослав Врублевский уже в первые дни конкурса набрал много баллов, первым был. Значит, алгоритм хороший есть! Тема на форуме dxdy.ru о текущем конкурсе http://dxdy.ru/topic121133.html В этой теме читаем: Цитата: На самом деле алгоритм решения данного конкурса чрезвычайно прост: я думаю, что к концу конкурса верх будет заполнен одними 25-ками. Если же этого не случится, то сразу по окончании конкурса я опубликую этот алгоритм, а точнее, мгновенно и в любом случае, чтобы мое утверждение не считали голословным (ответ заготовлю заранее). Правда, потом форумчанин написал, что погорячился. Но хороший алгоритм, как я уже написала выше, есть. И не исключено, что его раскопают и 25 баллов посыпятся |
||
Вернуться к началу | ||
За это сообщение пользователю Nataly-Mak "Спасибо" сказали: Student Studentovich |
||
Student Studentovich |
|
|
Nataly-Mak
Спасибо за ссылочки. |
||
Вернуться к началу | ||
На страницу 1, 2 След. | [ Сообщений: 15 ] |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 16 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |