论文部分内容阅读
二十世纪中后期，随着计算机的出现和发展，图论的研究得到广泛重视，最短路径问题和旅行售货员问题已经是图论中的典型问题，本文通过两个实际例子说明最短路问题在山区修建公路和旅行售货员问题灾区巡视路线中的应用。在山区修路中采用将地形图转化为网络图的方法对网络的边的公路、隧道、桥梁分别赋予不同的值，最后求最小成本路线问题就转化为求网络中最短路径的问题。在灾区巡视路线的数学模型属于旅行售货员问题，应用多推销员回路等近似解法制订了三种行驶路线。在本文中根据实际问题的需要选择恰当的算法合理的解决实际需要。