文件列表:

Branch_and_bound_for_TSP_tutorial.m (87489, 2012-01-22)
license.txt (1306, 2014-02-12)

Branch and Bound for solving traveling salesmen problems In this program, the various algorithms are shown to solve the traveling salesmen problem for symetric cost matrices: - Nearest Neighbour to find an upper bound - Hungarian method (Munkres Algorithm) to solve the assignment problem to find a lower bound - branch and bound - NOTE: This program was written for demonstration purposes and is not suitable to solve larger problems. See the readme file. To start the program, pick an example from the pop-up menu or enter an cost matrix in the text edit field, for example: [inf 4 3 4 4 6;4 inf 2 6 3 5;3 2 inf 4 1 3;4 6 4 inf 5 4;4 3 1 5 inf 2;6 5 3 4 2 inf]; GUI options: 1. Nearest Neighbour: If this checkbox is selected (default) the single steps of the algorithm are shown at the right text panel. Otherwise only the solution is shown. 2. Hungarian method: If the radio button is set to "always" the Munkres algorithm is shown in detail with explanations every time it is executed. Other options are "never" or "one time". Without details, only the assignment and the costs are shown. 3. Select branch: At the branch step, it is possible that several elements have the same minimum detour. If this option is selected, you can choose your element by clicking on it in the GUI. 4. Details short cycles If this checkbox is selected, the steps performed to look for short cycles in the sub sets are shown in detail. More notes: In the first iteration of the branch and bound algorithm, the mirrored element of the branching element is set to inf so this path is closed. The GUI requires a screen resolution of 1280x1024; if your computer has a lower resolution, there might be problems with the graphical representation The max matix size is limited to 9x9, but this might be already to large for the graphical representation of the tree. I only tested 6x6 matrices. This is an alpha version and will contain several bugs, for shure. The four examples provided are correctly solved but the program is only tested with these examples. So if you have any further examples with known solution and you find errors I would be grateful if you send me these examples to: martin.herold(at)hs-karlsruhe.de btw I know my english is not good and probably I use wrong expressions for optimization terminology, so any corrections are welcome.

近期下载者：

相关文件：

评论：[我要评论] [举报此文件]

收藏者：