Учебная практика, второй курс.
Требуется разработать визуальный редактор, позволяющий оптимально (с точки зрения суммарной длины проводов) размещать интегральные микросхемы на двумерной однослойной плате. Плата представляет собой двумерную сетку, разбитую на одинаковые квадраты. Каждая интегральная схема может занимать 1 квадрат и может быть связана с произвольным числом других интегральных схем. Таким образом, схема моделируется неориентированным графом, в котором вершинами являются схемы, а ребрами- соединения (между парой вершин может быть несколько ребер!). Соединения на плате между схемами идут строго параллельно и перпендикулярно (по клеточкам) (см. Манхеттенское расстояние). Для оптимальной разводки платы требуется чтобы провода в каждой клеточке не пересекались (крест-на крест) и суммарная длина проводов на всю плату должна быть минимальна.
Схема задаётся в виде XML-файла, в котором указан размер платы (прямоугольник — число клеток по веритикале и горизонтали). Для каждой интегральной схемы в файле указывается расположение на плате и список связей с другими интегральными схемами. Помимо этого в файле указывается Структуру XML-файла студент / группа разрабатывает самостоятельно. Описание структуры XML-файла должно быть приведено в отчёте по практике. Пользователю редактора должны быть доступны следующие функции:
- загрузка схемы;
- добавление в схему новых интегральных схем;
- возможность задания имени интегральной схемы и связей с другими интегральными схемами. Для каждой связи также должно задаваться имя;
- оптимизация размещения интегральных схем на плате по критерию минимальной суммарной длины проводов при отсутствии их пересечений.
- сохранение схемы в файл с возможностью его последующей загрузки в редактор.