Автор Тема: [Все] Нахождение наиболее оптимальной конфигурации графа.  (Прочитано 8767 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн C2H5OH [?]

  • Знаю я тут одно место с офигенными циркулями...
  • AutoIt Гуру
  • *****
  • Сообщений: 1473
  • Репутация: 329
  • Пол: Мужской
    • Награды
  • Версия AutoIt: 3.3.12.0
Регламент конкурса.
В конкурсе участвуют все желающие.
Принимаются решения в виде скриптов AutoIt без использования вызовов сторонних библиотек и программ (.dll, .exe).
Решения присылайте мне как личное сообщение. Решения опубликованные на форуме так же принимаются. (Не рекомендуется заранее выкладывать свои решения на форуме. Вы опубликуете свой скрипт и поедете в фанзону на всю ночь, а бухгалтер Вася посмотрит Ваш алгоритм, исправит Ваши ошибки, перепишет код и пришлёт свой скрипт. Необъективные результаты конкурса будут.)
Если несколько скриптов проходят все тесты, лучшим считается тот, который выполняет поиск результата за меньшее время.
Из двух скриптов, у которых время поиска результата отличается на 10%, лучшим считается тот, который прислан раннее.
Временем поступления скрипта на конкурс считается время получения последнего скрипта.
Вопросы по конкурсу задавайте только в данной теме.


КОНКУРСНОЕ ЗАДАНИЕ

Есть плоский граф.

Граф задаётся в виде матрицы рёбер.

Код: AutoIt [Выделить]
Const $N = 12
Dim $GrafLink[$N][$N] = [ _
[0,1,0,0,0,1,0,0,0,0,0,1], _
[1,0,1,0,0,0,0,0,0,0,0,0], _
[0,1,0,1,0,0,0,0,0,0,0,0], _
[0,0,1,0,1,0,0,0,0,0,0,0], _
[0,0,0,1,0,1,0,0,0,0,0,0], _
[1,0,0,0,1,0,1,0,0,0,0,0], _
[0,0,0,0,0,1,0,1,0,0,0,0], _
[0,0,0,0,0,0,1,0,1,0,0,1], _
[0,0,0,0,0,0,0,1,0,0,0,0], _
[0,0,0,0,0,0,0,0,0,0,1,1], _
[0,0,0,0,0,0,0,0,0,1,0,1], _
[1,0,0,0,0,0,0,1,0,1,1,0]]

То есть нулевую вершину рёбра графа соединяют с 1-ой, 5-ой и 11-ой.
Первую вершину с нулевой и 2-ой.
...
(Нулевая вершина находится в центре. Нумерация идёт от нулевой вершины по часовой стрелке.)

В данных гарантированно присутствует константа $N указывающая количество узлов графа.
Максимальное количество узлов 12.
Для группы пользователей [Новичек] количество узлов равно 12.


В узлах графа могут быть расположены элементы трёх видов - A, B и C.
Причем в центральном узле (в матрице позиция 0) ВСЕГДА расположен элемент вида B.

Элементы имеют цвет:
A - красный
B - белый
C - зелёный

В зависимости от типа вершин, которые они соединяют, рёбра графа окрашиваются в цвет:
A-B - синий
A-C - красный
B-C - зелёный
X-X - белый



Задание

Требуется расположить в узлах графа элементы A, B и C таким образом чтобы количество синих рёбер было максимальным.
Обязательное условие: суммарное количество красных узлов и рёбер не может быть больше чем суммарное количество зелёных узлов и рёбер.

Решением является строка символов A, B и C, где позиция символа означает номер вершины (нумерация позиций начинается с 0) или массив символов соответсвующий такой строке.
Например, для описанного выше графа решением является строка "BABABABABCCB" или массив [B,A,B,A,B,A,B,A,B,C,C,B]. Именно при такой расстановке вершин количество синих рёбер максимально.
Все возможные решения выводить не требуется. Если решений несколько всё равно достаточно одного.
Дополнительную информацию выводить не требуется.
« Последнее редактирование: Июль 14, 2012, 08:39:52 от C2H5OH »
Рано или поздно все станет понятно, все станет на свои места и выстроится в единую красивую схему, как кружева. Станет понятно, зачем все было нужно, потому что все будет правильно.

Русское сообщество AutoIt


Оффлайн DarWiM [?]

  • Продвинутый
  • ***
  • Сообщений: 527
  • Репутация: 89
  • Пол: Мужской
    • Награды
  • Версия AutoIt: 3.3.8.1
C2H5OH
А результат есть?

Оффлайн C2H5OH [?]

  • Знаю я тут одно место с офигенными циркулями...
  • AutoIt Гуру
  • *****
  • Сообщений: 1473

  • Автор темы
  • Репутация: 329
  • Пол: Мужской
    • Награды
  • Версия AutoIt: 3.3.12.0
У меня собственное решение есть давно, с того времени как возникла необходимость построения максимально эффективной конфигурации.
А помериться со мной ... скриптами так никто и не решился.
По сей день не прислано ни одного решения.
:(

Оффлайн DarWiM [?]

  • Продвинутый
  • ***
  • Сообщений: 527
  • Репутация: 89
  • Пол: Мужской
    • Награды
  • Версия AutoIt: 3.3.8.1
C2H5OH
Лично я условие не понял :)

Русское сообщество AutoIt

Re: [Все] Нахождение наиболее оптимальной конфигурации графа.
« Ответ #3 Отправлен: Октябрь 15, 2012, 16:18:21 »

Оффлайн C2H5OH [?]

  • Знаю я тут одно место с офигенными циркулями...
  • AutoIt Гуру
  • *****
  • Сообщений: 1473

  • Автор темы
  • Репутация: 329
  • Пол: Мужской
    • Награды
  • Версия AutoIt: 3.3.12.0
Так что, вот так прямо название игрушки сказать?


Добавлено: Октябрь 15, 2012, 18:25:18
Spore. Этап "Космос".
Получить в городе максимальную производительность без штрафа в морали.
« Последнее редактирование: Октябрь 15, 2012, 18:25:18 от C2H5OH, Причина: Объединение сообщений »

Оффлайн C2H5OH [?]

  • Знаю я тут одно место с офигенными циркулями...
  • AutoIt Гуру
  • *****
  • Сообщений: 1473

  • Автор темы
  • Репутация: 329
  • Пол: Мужской
    • Награды
  • Версия AutoIt: 3.3.12.0
Вот так это выглядит в игре.
(нажмите для показа/скрытия)
Нужно расставить заводы(A), дома(B) и центры развлечений(C) так, чтобы получить максимальную производительность (синий цвет) и чтобы не было штрафа в морали (красный цвет).
Красный цвет компенсируется зелёным.
В центре всегда стоит ратуша (тип здания - дом).
Нумеруем площадки в городе, начиная из центра и получаем для вот этого города массив рёбер графа
Код: AutoIt [Выделить]
Const $N = 12
Dim $GrafLink[$N][$N] = [ _
[0,0,1,0,1,0,0,0,1,1,0,1], _
[0,0,1,0,0,0,0,0,0,0,0,1], _
[1,1,0,1,0,0,0,0,0,0,0,0], _
[0,0,1,0,1,1,0,0,0,0,0,0], _
[1,0,0,1,0,1,0,0,0,0,0,0], _
[0,0,0,1,1,0,1,0,0,0,0,0], _
[0,0,0,0,0,1,0,1,1,0,0,0], _
[0,0,0,0,0,0,1,0,1,1,0,0], _
[1,0,0,0,0,0,1,1,0,0,0,0], _
[1,0,0,0,0,0,0,1,0,0,0,1], _
[0,0,0,0,0,0,0,0,0,0,0,1], _
[1,1,0,0,0,0,0,0,0,1,1,0]]


Изображенная на рисунке города расстановка зданий описывается как BBABCBABABBA.
Для данного города такая расстановка даёт максимально возможный результат.
Есть и другие расстановки с таким же результатом, но лучше нет.
 ;D

Оффлайн MissEnlila [?]

  • MissEnlilaLJ
  • Сообщений: 8
  • Репутация: -1
  • Пол: Мужской
    • Награды
  • Версия AutoIt: 3.3.14.0
а если у меня есть вышивание и вязание, в какой раздел это можно разместить?

Русское сообщество AutoIt

Все Нахождение наиболее оптимальной конфигурации графа
« Ответ #6 Отправлен: Декабрь 01, 2016, 18:25:01 »

 

Похожие темы

  Тема / Автор Ответов Последний ответ
38 Ответов
13339 Просмотров
Последний ответ Октябрь 21, 2012, 00:47:42
от beve
3 Ответов
3976 Просмотров
Последний ответ Июнь 07, 2010, 17:10:41
от Kaster
1 Ответов
2791 Просмотров
Последний ответ Октябрь 14, 2010, 22:03:34
от Yashied
7 Ответов
3907 Просмотров
Последний ответ Январь 05, 2011, 17:48:29
от Suppir
6 Ответов
5941 Просмотров
Последний ответ Февраль 02, 2011, 01:40:11
от WSWR
0 Ответов
2352 Просмотров
Последний ответ Декабрь 25, 2010, 01:46:50
от Yashied
0 Ответов
4829 Просмотров
Последний ответ Январь 25, 2011, 19:05:34
от PopovN
1 Ответов
470 Просмотров
Последний ответ Ноябрь 28, 2015, 20:51:19
от Yashied
4 Ответов
838 Просмотров
Последний ответ Январь 15, 2016, 13:12:48
от photozoom
5 Ответов
2174 Просмотров
Последний ответ Июнь 14, 2016, 18:15:30
от Dk