Как реализовать программу для "разводки печатной платы"?
Совершенно не понимаю как это реализовать помогите пожалуйста
Дана карта печатной платы (файл, структура которого имеет примерно следующий вид): (В одной строке 17 символов не считая прбелов)
0 0 5 0 0 0 0 0 0 0 0 2 0 0 0 0 0
0 0 1 0 0 0 0 3 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0
0 0 5 0 0 0 0 0 0 0 0 0 4 0 0 4 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Здесь обозначены: 0 – проходимые области 1…1, 2…2 и т.д. – пары точек, которые нужно соединить Написать программу, которая строит схему дорожек печатной платы. По возможности стараться найти кратчайшие маршруты.
Ответы (1 шт):
В качестве наивного подхода, могу предложить построение путей А* между парами точек.
Пути строить по очереди, 1-1, 2-2, и т.д. Затем построить пути в другом порядке, например, 2-2, 1-1 и т.д. Если очередной путь не удается построить, то перейти к следующему порядку построения.
В итоге, у вас будет, для данного примера, 5*4*3*2*1 вариантов пострения, часть неудачных, а среди удачный вы выберите тот, в котором сумма длинн путей - минимальна.