摘要: By considering the quadratic assignment problem (QAP) as that of minimizing the product of a distance-graph with a flow-graph several special cases of the QAP are investigated. A polynomial-growth algorithm is described for the QA... 展开 By considering the quadratic assignment problem (QAP) as that of minimizing the product of a distance-graph with a flow-graph several special cases of the QAP are investigated. A polynomial-growth algorithm is described for the QAP when the distance and flow-graphs are isomorphic trees. In the case when the graphs are single stars the algorithm becomes the well known rule for multiplying two sequences of numbers. The case of a complete distance-graph and a tree flow-graph becomes the travelling salesman problem when the tree is a hamiltonian chain and the flows are all unity. A dynamic programming algorithm is presented for the case of the flow-graph being a general tree with arbitrary flows. The very special case of 'narrow' bipartite graphs is also considered. 收起