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

Представим плату, условно разбитую на 9 квадратов. Имея 6 микросхем мы имеем право расположить каждую из них в любом квадрате. Каждая микросхема имеет 4 выхода через которые соединена с выходами других микросхем.

Самое важное: Начальное расположение микросхем не имеет никаких ограничений, равно как и соединены они совершенно случайно (т.е. вероятность того, в начальный момент времени -- P(0) -- какая-то микросхема может быть соединена всеми четырьмя выходами с другой микросхемой равна вероятности того, что она же может быть соединена с четырьмя разными).

После того как мы случайным образом задали связи между микросхемами (нетрудно посчитать, что раз микросхем 6, на каждой по 4 выхода, то всего проводов их соединяющих -- 12, ну это так к слову ) нам необходимо наиболее оптимально расположить эти микросхемы на схеме, т.е. чтобы суммарная длинна расходуемого провода была минимальной.

Ваши версии (я пока не буду сбивать своими)?

Цитата(Royan @ 14.10.2004, 17:55)

нетрудно посчитать, что раз микросхем 6, на каждой по 4 выхода, то всего проводов их соединяющих -- 12

Вот это неочевидно.
Может еще такое условие есть: выход каждой микросхемы может быть соединен только с одним выходом другой микросхемы?

Цитата

чтобы суммарная длина расходуемого провода была минимальной

т.е. речь не о разводке платы, пересечения допустимы?

Цитата

Персечения допустимы

Да

Цитата

выход каждой микросхемы может быть соединен только с одним выходом другой микросхемы?

Точно так.

Никаких доп. условий свше тех, что я описал нет.

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

Нет это задача надуманная, и здесь нужен какой-то алгоритм, ответы перебором не принимаются

Royan
Задача решается только полным перебором. Упростить ее (вернее ускорить наступление события когда текущее решение равно оптимальному) можно только проведя предварительную сортировку микросхем по количеству связей - т.е. наиболее вероятно что та у коей больше связей, стоИт в центре квадрата или по центру стороны.

Цитата(Akina @ 19.10.2004, 14:14)

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

Цитата(Royan @ 14.10.2004, 18:19)

выход каждой микросхемы может быть соединен только с одним выходом другой микросхемы?

Т.е есть микросхемы у котрых 3 контакта из 4 задействованы???

RoyanВообщето, даже теоретическому проектированию печатных плат (разводке) на радио факультетах посвящается целый симестр. Тут надо знать и частотные фарактеристики, и энерго потребление, токи и напряжения питания и сигналов, тепловые характеристики элементов и т.д.
Так что чисто академически эта задача с наскока не решается.
А если говорить о практической части, то если пересечения проводников допускаются, то просто распологай корпуса по принципу заполнения плошади и все, необходимости оптимизации длины проводников я тут не вижу ну после оптимизации тебе понадобится не 100мм провода а 99мм

Это сообщение отредактировал(а) Mad - 19.10.2004, 14:28

Цитата(Royan @ 14.10.2004, 16:55)

Представим плату, условно разбитую на 9 квадратов. Имея 6 микросхем мы имеем право расположить каждую из них в любом квадрате

А микросхемы вращать можно?
А через границы квадратов связи организуюца.
Если нет, то можно сортить микросхемы по количеству связей. Т.е. Микросхема у которой четыре связи с четырьмя разными микросхемами должна стять в середине квадрата (между микросхемами с которыми связи организованны).
Соответственно если все выходы одной микрухи связаны с четырьмя выходами другой микрухи, то попарабану где их ставить, лиш бы поближе друг к другу были.

2Akina

Цитата

Задача решается только полным перебором

Никто не просит найти решение, необходимо улучшить начальное положение микросхем. А то что ты описал далее мне собственно и необходимо только в более конкретной форме


2Mad

Цитата

теоретическому проектированию печатных плат (разводке) на радио факультетах посвящается целый семестр

Это чисто теоретическая задача и вместо плат здесь можно было использовать что угодно, откуда и вытекает, что мне необходимо не ее реальное применение.
2~FoX~

Цитата

Т.е есть микросхемы у которых 3 контакта из 4 задействованы???

Все микросхемы соединены всеми имеющимися на них контактами с другими микросхемами, и все эти начальные соединения случайны.

Цитата

А микросхемы вращать можно? А через границы квадратов связи организуюца.

На оба вопроса да.

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

подтверди или откорректируй:
1) у каждой из 6 микросхем каждый из 4 ее выводов соединен с какой-либо другой микросхемой, незадействованных контактов или замкнутых на себя контактов ни у одной из микросхем нет.
2) любая пара микросхем может иметь между собой от 0 до 3 связей, любые 2 микросхемы соединены между собой напрямую или через другие микросхемы.
3) длина связи (провода) равна расстоянию между центрами соответствующих сторон квадратов, на которых расположены контакты микросхемы, связи идут по кратчайшему расстоянию между точками ака прямая.

Это сообщение отредактировал(а) Akina - 26.10.2004, 17:45

Цитата(Royan @ 26.10.2004, 16:39)

Цитата А микросхемы вращать можно? А через границы квадратов связи организуюца. На оба вопроса да.

Че та я тогда не понял на фига плату делить на 9 квадратов?

2Akina

Цитата

1) у каждой из 6 микросхем каждый из 4 ее выводов соединен с какой-либо другой микросхемой, незадействованных контактов или замкнутых на себя контактов ни у одной из микросхем нет.

Да все контакты задействованы. Еще раз повторю не стоит в этой задаче искать подвоха, ее условия элементарны.

Цитата

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

Нет каждая микросхема соединена всеми 4-мя контактами (см. вопрос №1) К примеру, есть две рядом стоящих микросхемы и они соединены контактом №1 (у первой) и контактом №4 (у второй), то длина провода в таком случае будет больше чем, еже ли бы они были соединены контактом №1 (у первой) и контактом №3 (у второй). Яное дело ежели они соединены контактом №1 (у первой) и контактом №1 (у второй) то это самый благоприятные вариант. На самом деле длину провода, при данных условиях можно высчитывать по Т. Пифагора, если представить, что каждый контакт будет находиться в своей клетке (тогда, каждая микросхема плата будет располагаться в 4 клетках) Соответственно высчитываются и случаи когда микросхемы не стоят непосредственно рядом.

Я думаю мой ответ на второй вопрос покрыл ответ на третий
2~FoX~

Цитата

А микросхемы вращать можно?

Тут я погорячился, микросхемы вращать нельзя.

Поскольку один раз увидеть лучше чем, известно, что, то вот тут мой скромный рисунок сделанный в Paint Brush, поэтому правильность форм немного нарушена. Т.О. примите что все контакты расположены вертикально.
Смотреть тут

Royan
Ты даже не читаешь что тебе пишут.
1а) Может быть так что контакт 1 микросхемы 1 соединен с контактом 2 микросхемы 1?
2а) может быть так что контакты 1...4 микросхемы 1 соединены с контактами 1...4 микросхемы 2?
3а) ни хрена не покрыл.

Цитата

вот тут мой скромный рисунок

Вот это уже ближе к телу... а почему их крутить-то нельзя? ну хотя бы на 180 градусов-то?