目錄
1. 問題描述
2. 解題分析
3. 代碼及測驗
1. 問題描述
問題：求把10個數字全部顯示出來時，亮燈/滅燈的切換次數最少的顯示順序，以及這個切換次數，
注：原題從答案來看是不包括第一個數字顯示時從全黑到顯示該數字所需要的亮滅切換次數的，不過這個不影響解題，但是可能會影響答案，
2. 解題分析
從暴力搜索（原書中使用“全量搜索”這個詞很貼切）著手，
10個數字的不同排列順序共有10!=factorial(10)=3628800種，針對每一種排列順序進行切換次數的統計即可，
本題解中用numpy array存盤各數字顯示所需要的燈亮滅表示矩陣，每行表示一個數字，表示使用7段碼對應的二進制表示，
切換次數的計算可以理解為兩個二進制序列之間的漢明距離(hamming distance)，即兩個二進制序列之間的不同的數的個數，漢明距離可以用異或操作實作，
此外，各數字的二進制表示之間的漢明距離總共只有10*10=100個（連自己與自己之間的距離也算上，雖然不用，考慮到查找實作的便利，(k,j)和(j,k)也分開來算，雖然它們是相等的）可以預先計算好，這樣可以避免在遍歷搜索時的大量的重復計算，
3. 代碼及測驗
# -*- coding: utf-8 -*-
"""
Created on Wed Sep 22 07:37:19 2021
@author: chenxy
"""
import sys
import time
import datetime
import math
import random
from typing import List
# from queue import Queue
from collections import deque
import itertools as it
from math import sqrt, floor, ceil
import numpy as np
class Solution:
segs = np.array([[1,1,1,1,1,1,0],
[0,1,1,0,0,0,0],
[1,1,0,1,1,0,1],
[1,1,1,1,0,0,1],
[0,1,1,0,0,1,1],
[1,0,1,1,0,1,1],
[1,0,1,1,1,1,1],
[1,1,1,0,0,0,0],
[1,1,1,1,1,1,1],
[1,1,1,1,0,1,1]])
distArray = dict()
minDistSum = np.sum(segs)
minOrder = None
def initDistArray(self):
for i in range(len(self.segs)):
for j in range(len(self.segs)):
self.distArray[tuple([i,j])] = np.sum(self.segs[i] ^ self.segs[j])
def printDistArray(self):
print(self.distArray)
def minToggle(self):
for order in it.permutations(list(range(10))):
# print(order)
distSum = 0 #np.sum(self.segs[0])
for k in range(9):
distSum += self.distArray[(order[k],order[k+1])]
if self.minDistSum > distSum:
self.minDistSum = distSum
self.minOrder = order
return self.minDistSum, self.minOrder
if __name__ == '__main__':
sln = Solution()
sln.initDistArray()
# sln.printDistArray()
t1 = time.perf_counter()
minDistSum, minOrder = sln.minToggle()
tCost = time.perf_counter() - t1
print('Number of toggles = {0}, order = {1}, tCost = {2}'.format(minDistSum, minOrder,tCost))
運行結果：
Number of toggles = 13, order = (0, 8, 6, 5, 9, 4, 1, 7, 3, 2), tCost = 8.640sec
4. 后記
運行時間有點長，需要考慮進一步優化，
這個問題其實可以看作是，具有10個節點的全連接無向圖，每條邊的權重值代表兩個節點所代表的數字的7段碼顯示的二進制表示之間的漢明距離，因此本題就轉化為就該圖中任意一條最長無重復路徑的權重總和，這其實就是著名（惡名昭彰）的旅行商問題，這是一個NP問題，但是只有10個節點還可以對付，接下來考慮用遞回+Memoization的方法來試一試會不會變得更快一些，
上一篇：Q36: 翻轉骰子
下一篇：
本系列總目錄參見：程式員的演算法趣題：詳細分析和Python全解
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/302185.html
標籤：其他