街道小区服务设施的优化布局

摘  要

本文解决了1个带权值的网络最优化问题。结合图论相关知识对问题进行综合分析，分别采用1维数组和邻接矩阵来存储小区内居民数量和小区间的距离信息。通过对问题1的定量分析，把线路铺设方案的求解问题转化为构造连通网的最小代价生成树，运用普里姆算法对此问题进行求解；通过对问题2的定性分析，把服务设施点选址问题转化为求源点到其余各顶点的最短路径问题，选用迪杰斯特拉算法对其进行求解。
  根据普里姆算法和迪杰斯特拉算法，编写C++程序对该街道居民的路径选取过程进行模拟。所得结论显示问题解答结果与分析的结论相吻合，从而得出最佳线路铺设方案，并成功解决服务设施点选址问题。
关键词：邻接矩阵；普里姆算法；迪杰斯特拉算法；最短路径；最小生成树。

Abstract

This article has resolved a network optimization problem which has an weight. Uniting the knowledge in the diagram theory, we analyze the problem comprehensively, and adopt one dimension array and adjacency matrix to store the number of the residents resided in this section and the distance between two different sections. By quantitatively analyzing question one, we change the problem of the paving connection scheme into constructing the Minimum Cost Spanning Tree for connected network, and make Prim algorithm to answer the question; By quantitatively analyzing question two, we change the choosing address issue of service establishment into answering the shortest path for other verticals, we make Dijkstra algorithm to answer this question.
Based on Prim algorithm and Dijkstra algorithm, we simulate the choosing path process of this street by C++ program. The result shows that: the result of trouble shooting same to the analyzing result, and we succeed to answer the choosing address issue of service establishment.

Keywords: adjacency matrix; Prim algorithm; Dijkstra algorithm; The most short-circuit path; Minimal spanning tree. （科教范文网http://fw.ΝsΕΑc.com编辑）