(distance_matrix, route0, i, j, old_distance = None)
| 897 | return seg_a, seg_b |
| 898 | |
| 899 | def _patch_two_fragments(distance_matrix, route0, i, j, old_distance = None): |
| 900 | n = route0.shape[0] |
| 901 | pieces = _segments_after_two_breaks(route0, i, j) |
| 902 | if pieces is None: |
| 903 | return route0, 0.0 |
| 904 | seg_a, seg_b = pieces |
| 905 | if old_distance is None: |
| 906 | old_distance = _tour_distance_zero(distance_matrix, route0) |
| 907 | |
| 908 | best_route = route0 |
| 909 | best_gain = 0.0 |
| 910 | orientations_a = [seg_a, seg_a[::-1].copy()] |
| 911 | orientations_b = [seg_b, seg_b[::-1].copy()] |
| 912 | |
| 913 | for a in orientations_a: |
| 914 | for b in orientations_b: |
| 915 | for cand in (np.concatenate((a, b)), np.concatenate((b, a))): |
| 916 | if cand.shape[0] != n or len(set(cand.tolist())) != n: |
| 917 | continue |
| 918 | new_distance = _tour_distance_zero(distance_matrix, cand) |
| 919 | gain = old_distance - new_distance |
| 920 | if gain > best_gain + 1e-12: |
| 921 | best_gain = gain |
| 922 | best_route = cand |
| 923 | return best_route, float(best_gain) |
| 924 | |
| 925 | def _patching_pass(distance_matrix, route0, cand_arr, max_trials_per_edge = 20): |
| 926 | n = route0.shape[0] |
no test coverage detected