Что нового

[Все] Нахождение наиболее оптимальной конфигурации графа.

C2H5OH

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


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

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

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

Код:
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 - белый

f5404245ddbb.jpg


Задание

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

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

C2H5OH

AutoIT Гуру
Сообщения
1,473
Репутация
333
У меня собственное решение есть давно, с того времени как возникла необходимость построения максимально эффективной конфигурации.
А помериться со мной ... скриптами так никто и не решился.
По сей день не прислано ни одного решения.
:(
 

DarWiM

Продвинутый
Сообщения
527
Репутация
90
C2H5OH
Лично я условие не понял :smile:
 
Автор
C2H5OH

C2H5OH

AutoIT Гуру
Сообщения
1,473
Репутация
333
Так что, вот так прямо название игрушки сказать?


Добавлено:
Сообщение автоматически объединено:

Spore. Этап "Космос".
Получить в городе максимальную производительность без штрафа в морали.
 
Автор
C2H5OH

C2H5OH

AutoIT Гуру
Сообщения
1,473
Репутация
333
Вот так это выглядит в игре.
Нужно расставить заводы(A), дома(B) и центры развлечений(C) так, чтобы получить максимальную производительность (синий цвет) и чтобы не было штрафа в морали (красный цвет).
Красный цвет компенсируется зелёным.
В центре всегда стоит ратуша (тип здания - дом).
Нумеруем площадки в городе, начиная из центра и получаем для вот этого города массив рёбер графа
Код:
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
 
Верх