C/C++ - "Микрочип"

Drongo · Конфигурация компьютера

ArtTema, Есть хоть какое-то решение? Или вы предлагаете писать за вас?

ArtTema · Отправлено: **23:56, 07-04-2010** | #3

Нет, писать я не предлагаю вовсе

Мне нужна какая-нибудь рабочая идея, алгоритм, который можно было бы реально закодить

У меня есть некоторые соображения, но они достаточно обстрактны и конкретизировать у меня не получается, вот и обращаюсь за помощью

pva · Отправлено: **11:01, 08-04-2010** | #4

решите врукопашную такую расстановку:

Код:

+-----+
| ... |
| ... |
| ... |
|     |
+-----+

излагай идеи

delog · Конфигурация компьютера

А это точная формулировка задачи?

Цитата:

Микрочип...имеет форму плоского квадрата... На нижнюю грань выведены контакты

Квадрат - это двухмерная фигура, она не может быть ни плоской ни толстой.
Грань - это плоскость у объемной фигуры.

Значит формулировка должна начинаться:
На нижнюю грань микрочипа, имеющую форму квадрата, выведены...

И кроме того:

Цитата pva:

решите врукопашную такую расстановку:

Код:

+-----+
| ... |
| ... |
| ... |
|      |
+-----+

»

Если все дорожки должны быть параллельны сторонам чипа, не пересекаться и не изгибаться, то как при таких условиях можно провести дорожку из центра?

CyberDaemon · Отправлено: **13:05, 08-04-2010** | #6

Цитата delog:

Если все дорожки должны быть параллельны сторонам чипа, не пересекаться и не изгибаться, то как при таких условиях можно провести дорожку из центра? »

Никак, при таких начальных условиях задача не имеет решения.
Там же пример дан, если его нарисовать, то не будет там "заблокированных" контактов.

delog · Конфигурация компьютера

Точно, чужая иллюстрация меня немного сбила с мысли. Сходу могу предожить такой алгоритм:

1. посчитать "вес" каждой точки - если от нее можно провести дорожку во все стороны, то ее вес = 4, если в три стороны, то ее вес = 3 и т.д.

2. начать построение со свободной точки имеющей наименьший вес, строить в ту сторону, которая ближе всего - так, во-первых короче, а во-вторых будет заблокировано меньше всего других точек.

3. если еще есть свободные точки, то перейти к п.1, иначе п.4

4. конец

Но это сходу, врядли это идеальный вариант.

pva · Отправлено: **07:47, 09-04-2010** | #8

Цитата CyberDaemon:

Там же пример дан, если его нарисовать, то не будет там "заблокированных" контактов. »

Если требуется режить только заданный пример- это можно сделать и без компьютера. Если требуется разработать программу для решения произвольного примера - придётся рассмотреть все варианты (хотя бы в отладочных целях)

дополняем алгоритм delog:
для каждой точки посчитали списки пар {длина, направление}. Отсортировали списки по длине, количеству элементов. текущее решение будет определяться списком указателей на элементы таблицы для каждой точки.
Дальше либо перебором, либо вертится в голове идея, аналог симплекс-метода, как сформулирую - напишу

Вот ещё пример (отладить вариант delog)

Код:

+---------+
|         |
|         |
| ..      |
|   .     |
|   .     |
|         |
+---------+

lxa85 · Отправлено: **07:05, 11-04-2010** | #9

Можно попробовать подключить теорию графов. Критерий планарности/непланарности.
Я бы может предложит считать не вес точки, а "штрафы" т.е. расстояния до края по каждому направлению.
Можно попробовать построить дерево поиска с возвратом. Т
На начальном этапе отсечь тупиковые ветви. Например 2 точки на линии.
Далее рисовать граф, причем мы знает что с чем может быть соединено.
Можно не на каждом, можно для начала через 5/10/15 шагов производить оценку планарности. Т.к. это дорогостоящая операция. Затем конечно сократить кол-во шагов.

О!
Можно попробовать волновой алгоритм. С какой-нибудь его модификацией.
Можно попробовать решить обратную задачу. Т.е. найти минимальный остов.
http://ru.wikipedia.org/wiki/Минимал...стовное_дерево
Дерево Штайнера. http://book.itep.ru/3/stain_tree.htm
Также можно поискать задачи про укладку проводников.

pva · Отправлено: **08:43, 12-04-2010** | #10

Цитата lxa85:

Можно попробовать решить обратную задачу. Т.е. найти минимальный остов.
http://ru.wikipedia.org/wiki/Минимал...стовное_дерево
Дерево Штайнера. http://book.itep.ru/3/stain_tree.htm »

вот это мне кажется не подходит, потому что здесь процесс с блокировками. К примеру вот вроде бы оптимальное решение, но оно не допустимо

Код:

+---------+
|         |
|         |
|         |
|         |
+-..      |
+--+.     |
|  |.     |
|  ||     |
+--++-----+

а допустимо такое:

Код:

+--+------+
|  |      |
|  |      |
|  |      |
|  |      |
+-..      |
+---.     |
|   .     |
|   |     |
+---+-----+

применение штрафных функций слабо себя оправдывает, т.к. задача дискретная, гладкость решения от этого не повысится.

подумав-подумав допёрло как можно сделать. Нужно использовать принцип максимума понтрягина
. Пронумеруем контакты в любом порядке и начинаем поочереди их перебирать. За текущее состояние процесса принимаем направление обработанных дорожек + оставшиеся возможные направления необработанных (для каждого направления есть своя цена). Так как требуется найти интегральную цену (разделяемая на части сумма), этим принципом пользоваться можно.
Допустим мы уже сделали несколько ходов и у нас есть список возможных направлений для оставшихся дорожек. Тогда наши последовательные ходы должны быть такими, чтобы обеспечить наименьшее значение интеграла (суммарной цены). Мысленно доводим решение задачи до конца и начинаем раскручивать её обратно. На каждом шаге для контакта N (0<=N<=max(N)) и возможного направления I (0<=I<4) запоминаем рассчитываем наименьшую длину и запоминаем соответсвующую ей распайку контактов. Рассчёт ведётся из соображений, что сначала ни один контакт (из изначально не заблокированных) не заблокирован, потом что идеальный контакт заблокирован, потом что из оставшихся идеальный заблокирован и т.д.
На следующем шаге берём за основу полученные (максимум) 4 состояния, и рассчитываем схему с добавленным контактом. Итого потребуется вычислить (max(N)+1)*4 (возможно недоделанных) схем.