分支限界法之布线问题 一、要求：



1、输入电路板区域n*m以及布线的起始位置和结束位置；



2、输出布线方案；



3、可以使用c或者vc实现



二、问题分析及实验原理：



在n*m的方格阵列中存在封锁区域（布线时必须绕开的区域），找到起始位置到目标位置的最短路径。从目标位置开始向起始位置回溯，逐步构造最优解。每次向标记距离比当前方格标记距离少1的相邻方格移动，直到到达起始方格为止。-Branch and bound method of a wiring problem, requirement: 1, enter the circuit board wiring region n* m and the start position and end position　2, output routing program　3, you can use c or vc achieve two, the analysis and experimental principle : n* m in the box in the array block area there (wiring must be bypassed in the region), the starting position to the target location to find the shortest path. Starting from the target location back to the starting position, and gradually construct the optimal solution. To mark each box marked distance from the current less than 1 in its adjacent cells move up until you reach the starting grid.