一、问题描述
二、问题分析
一开始，我使用了贪心的方式（也在C/C++实现中，是错的），认为短视能够获得好的结果，运行结果确实是13步最少，但是路径却不是数组路径，debug发现在0开始的贪心路径中，得到的最好结果是14，而书中0开始的最好结果为13，也就是说贪心算法至少在求局部最优时达不到效果；于是想到DP（也在C/C++实现中），但是对于DP来说，中间的计算结果不易保存，那么递归实现必然有大量的重复计算，而且DP的最终效果依旧是遍历所有排列，故最终还是选择了对所有排列的遍历（Python实现）。
三、代码实现
1.C/C++实现
#include <iostream>using namespace std;// 状态码
const int codes[10] = {0b1111110, // 00b0110000, // 10b1101101, // 20b1111001, // 30b0110011, // 40b1011011, // 50b1011111, // 60b1110000, // 70b1111111, // 80b1111011 // 9
};
// 最大步数，用于初始化
const int MAX_STEPS_INIT = 7 * 10;// 记录状态之间的距离
int distances[10][10];// 记录已使用的标志，和顺序
int used[10];
int order[10][1 << 10];// 计算两个状态之间的变化距离
void calc_distances() {for (int i = 0; i < 10; i++) {for (int j = i; j < 10; j++) {distances[i][j] = 0;if (i != j) {int tmp = (codes[i] ^ codes[j]);while (tmp) {distances[i][j] += (tmp % 2);tmp /= 2;}distances[j][i] = distances[i][j];}}}
}// 由 cur 开始进行贪心的变换数量
int greedy(int cur) {int total = 0;for (int i = 1; i < 11; i++) {used[cur] = i;// 找下一个int next = -1, steps = 14;for (int j = 0; j < 10; j++) {if (used[j] == 0) {if (distances[cur][j] < steps) {steps = distances[cur][j];next = j;}}}if (next >= 0) {cur = next;total += steps;}}return total;
}// 由 cur 开始进行dp的变换数量
int dp(int cur, int left) {if (left == (1 << 10) - 1) {return 0;}int min_steps = MAX_STEPS_INIT;for (int i = 0; i < 10; i++) {if ((left & (1 << i)) == 0) {int tmp = distances[cur][i] + dp(i, left | (1 << i));if (tmp < min_steps) {min_steps = tmp;order[cur][left] = i;}}}return min_steps;
}int main() {calc_distances();int min_op = MAX_STEPS_INIT;int min_route[10] = { 0 };// 使用贪心法 (×)for (int i = 0; i < 10; i++) {memset(used, 0, sizeof(used));int tmp = greedy(i);if (tmp < min_op) {min_op = tmp;for (int j = 0; j < 10; j++) {min_route[used[j] - 1] = j;}}}cout << min_op << endl;for (int i = 0; i < 10; i++) {cout << min_route[i] << '\t';}cout << endl;// 使用 DPmin_op = MAX_STEPS_INIT;int min_index = 0;for (int i = 0; i < 10; i++) {int tmp = dp(i, 1 << i);if (tmp < min_op) {min_op = tmp;min_index = i;}}cout << min_op << endl;cout << min_index << '\t';int cur = min_index, left = 1 << cur;for (int i = 0; i < 9; i++) {cout << order[cur][left] << '\t';cur = order[cur][left];left |= 1 << cur;}return 0;
}2.Python实现
# coding = utf-8from itertools import permutationsMAX_STEPS = 7 * 10CODES = [0b1111110, # 00b0110000, # 10b1101101, # 20b1111001, # 30b0110011, # 40b1011011, # 50b1011111, # 60b1110000, # 70b1111111, # 80b1111011] # 9distances = []def calc_distances():for i in range(10):tmp = [0] * 10for j in range(10):if i != j:tmp[j] = str(bin(CODES[i] ^ CODES[j])).count('1')distances.append(tmp)passdef calc_for_route(route):steps = 0for i in range(len(route) - 1):steps += distances[route[i]][route[i + 1]]return stepsdef get_min():calc_distances()min_steps = MAX_STEPSmin_route = ()for item in permutations(range(10)):tmp = calc_for_route(item)if min_steps > tmp:min_steps = tmpmin_route = itemreturn min_steps, min_routeif __name__ == '__main__':steps, route = get_min()print(steps, route)pass
