我正在應對這個挑戰：
機器人可以執行以下兩條指令中的任何一條：
- [F]向前：前進 1，速度加倍
- [B]ack：停止，改變方向并重置它的速度。
初始速度為 1。
給定一個距離，回傳一個滿足它的序列。該序列最多只能有 3 個“B”。如果 3 'B' 無法解決，則回傳空字串。
例如，
findSeq(2) -> FFBF (1 2-1) findSeq(3) -> FF (1 2) findSeq(4) -> FFFBFF (1 2 4 - (1 2))
這是我到目前為止所擁有的：
def findSeq(dist):
curr = 0
seq = ""
speed = 1
mul = 1
while (curr != dist):
seq = 'F'
curr = (speed*mul)
speed *= 2
if curr > dist and mul != -1:
seq = 'B'
mul = -1
speed = 1
elif curr < dist:
mul = 1
if curr == dist:
return seq
if seq.count('B') == 3 and curr != dist:
return ''
return seq
這適用findSeq(2)于findSeq(3)和findSeq(4)。然而，它開始打破findSeq(5)-> （它給出FFFBFFFBFF）
我不確定我錯過了什么。
uj5u.com熱心網友回復：
一些觀察結果：一系列 n F 個命令，使火車在當前方向上移動 2^n - 1。不失一般性，所有解的形式為 F^k1 BF^k2 BF^k3 BF^k4，其中 k1, k2, k3, k4 >= 0 因為如果我們不移動火車，我們可以簡單地設定一些 k 為 0。
這給出了問題的重述：給定 n，找到非負 k1、k2、k3、k4 使得 (2^k1 - 1) - (2^k2 - 1) (2^k3 - 1) - (2 ^k4 - 1) = n。
總和中的 1 取消，所以你需要找到 2^k1 2^k3 - 2^k2 - 2^k4 = n。
如果 n 有 N 位，那么不失一般性，四個數中的每一個最多可以是 N 1。
我確信有一個更聰明的方法，但只需搜索 (N 2)^4 可能性就會產生 O((log n)^4) 解決方案。
import itertools
def findSeq(n):
N = max(1, n.bit_length())
for k1, k2, k3, k4 in itertools.product(tuple(range(N 2)), repeat=4):
if (1<<k1) - (1<<k2) (1<<k3) - (1<<k4) == n:
return 'B'.join('F' * x for x in (k1, k2, k3, k4))
return ''
for i in range(100):
print(i, findSeq(i))
@MattTimmermans 建議進行 O((logn)^2) 改進：列舉 q = 2^k1 2^k3 形式的所有數字，然后查看 qn 是否具有相同的形式。
def findSeq2(n):
N = max(1, n.bit_length())
b2 = {(1<<k1) (1<<k2): (k1, k2) for k1, k2 in itertools.product(tuple(range(N 2)), repeat=2)}
for k1, k3 in b2.values():
r = (1 << k1) (1 << k3) - n
if r in b2:
k2, k4 = b2[r]
return 'B'.join('F' * x for x in (k1, k2, k3, k4))
return ''
uj5u.com熱心網友回復：
我建議使用一種演算法，無需搜索即可直接從給定數字中得出解決方案。
觀察
正如其他人也指出的那樣，這歸結為找到 (2 a - 1) - (2 b - 1) (2 c - 1) - (2 d - 1) 形式的項。
另外，請注意，當您有解決方案時，您始終可以在末尾附加一些“B”，這不會改變表示的距離。所以我們可以說恰好需要 3 個“B”字母，并且需要所有四個術語（如上所示）。這也意味著我們可以消除每個術語中的 -1，因為它們相互抵消。
當我們查看這些術語的二進制表示時，我們應該有這樣的東西：
0b1000000 - 0b100 0b10000 - 0b10
...其中這些數字中尾隨零的數量是可變的。
當使用這些術語時，很明顯不可能生成一個值 - 在其二進制表示中 - 具有 4 組相鄰的 1 位（或更多）。例如：0b1010101 不能用“F”和三個“B”指令編碼。
情況1：二進制表示有一組1位
當只有一組相鄰的 1 位時，這很容易。
例如 0b11100 可以用 FFFFFBFF 生成。第一組“F”只要有數字，第二組“F”只要有尾隨零。
情況2：二進制表示有兩組1位
當有兩組 1 位時，也很簡單：
例如 0b11001110 可以用 FFFFFFFFBFFFFFFFFFFFBF 生成。注意每組“F”比前一組短，表示從左側洗掉一組相同數字后剩余的二進制數字的數量。所以：
- 11001110 轉換為 8xF，
- 001110 至 6xF,
- 1110 至 4xF 和
- 0 到 1xF。
情況 3：二進制表示具有三組 1 位
有三組 1 位的情況是最復雜的情??況。通過更深入地分析這一點，事實證明，至少一個 0 分隔組（將兩組 1 分開）必須具有 1 的長度（即只有一個分隔 0）。因此，例如，對于 0b1001001 沒有解決方案，因為兩組 0 的大小都是 2。其次，與單個 0不相鄰的剩余 1 位組也必須是單個的。
所以：0b1010011 也沒有解，因為右側組（不與單個封閉的 0 相鄰）有兩個 1。但是 0b11011001 有一個解決方案，因為有一個孤立的 0（在 1 之間），而剩下的另一組 1 也是單個的（在右側）。
執行
有了這些規則，就有可能有一個快速的演算法，因為它并不真正搜索解決方案，而是從給定數字的二進制表示中推匯出它：
import re
def encode(position):
binary = bin(position)[2:]
# Split in sizes of same digits. First group will consist of 1s
sizes = list(map(len, re.findall(r"1 |0 ", binary)))
if len(sizes) > 6:
return "" # Not possible
# Create sequences of F, corresponding
# to the number of binary digits that follow
digits = ["F" * sizes[-1]]
for size in reversed(sizes[:-1]):
digits.append(digits[-1] "F" * size)
digits.reverse()
# Simple cases:
if len(sizes) <= 4:
return "B".join(digits)
# The case where there are 3 groups of 1s in the binary representation:
digits.append("") # Make sure that digits[5] is defined
if sizes[0] == 1 and sizes[3] == 1: # The isolated single zero is at group 3
return "B".join((digits[1], digits[4], digits[2], digits[5]))
if sizes[4] == 1 and sizes[1] == 1: # The isolated single zero is at group 1
return "B".join((digits[0], digits[2], digits[5], digits[3]))
return "" # Not possible.
一些驅動代碼：
# Helper function to verify a solution
def decode(code):
# Naive implementation according to rules
position = 0
direction = 1
speed = 1
for ch in code:
if ch == "B":
direction = -direction
speed = 1
else:
position = speed * direction
speed *= 2
return position
for i in range(1, 73):
code = encode(i)
decoded = decode(code)
print(i, code, decoded)
第一個無解的自然數是 73，其二進制表示為 0b1001001。
uj5u.com熱心網友回復：
您的代碼的問題是第二輪。請注意，當curr < dist您更改方向但不重置速度并將“B”添加到序列時。改變
elif curr < dist:
mul = 1
到
elif curr < dist and mul == -1:
seq = 'B'
mul = 1
speed = 1
應該能解決你的問題。另外，您說路徑最多可以有3個'B'，因此您需要更改
if seq.count('B') == 3 and curr != dist:
return ''
到
if seq.count('B') == 4 and curr != dist:
return ''
演算法分析
關于此功能可以達到的距離的一些見解（僅限于三圈）。當dist可以寫成2**n - 1任何大于 0 的整數時，此函式將dist無任何轉彎到達，路徑為'F' * n. 這是因為 的二進制表示是一個'1'2**n - 1的序列。n例子：
7 = 2**3-1 = 0b111-->findSeq(0b111) = 'FFF'15 = 2**4-1 = 0b1111-->findSeq(0b1111) = 'FFFF'31 = 2**5-1 = 0b11111-->findSeq(0b11111) = 'FFFFF'
等等
要達到 5，具有二進制表示0b101的函式將執行以下操作：
- 達到 7
- 轉身，回傳 4（即 2 的冪，4 = 0b100）
- 轉身，前進到5
print(findSeq(5)) # 'FFFBFFBF'
This means that the way your algorithm works is when starting from the Most Significant Bit (MSB) which is the leftmost-bit, for any change from 1 to 0, you will need to use 1 turn, and for another change from 0 to 1 you will need to use another turn. This happens because by the rules of the movement, a change from 1 to 0 in the binary representation, the function resets to the largest number which is smaller than dist and has a binary representation of s sequence of ones, followed by a sequence of zeros (e.g. 4 = 0b100 has 1 '1' followed by 2 '0').
This means that using your algorithm you can find a path to very large numbers, but for some small reachable numbers a path will not be found. Taking the very large number of 895, represented by 0b1101111111. You can see that there is only one change from '1' to '0' (bits 8 and 7 when the LSB is in location 0), the function will be able to find a path by:
- reaching 1023 (
0b1111111111) - return to 768 (
0b1100000000), has 2 '1' followed by 8 '0' - advance to 895 (
0b1101111111)
print(findSeq(0b1101111111)) # 'FFFFFFFFFFBFFFFFFFFBFFFFFFF'
print(findSeq(895)) # 'FFFFFFFFFFBFFFFFFFFBFFFFFFF'
Changing the dist to 892 will reults in an additional turn:
- return to 892 (
0b1101111100)
print(findSeq(0b1101111100)) # 'FFFFFFFFFFBFFFFFFFFBFFFFFFFBFF'
print(findSeq(892)) # 'FFFFFFFFFFBFFFFFFFFBFFFFFFFBFF'
But for relatively small numbers like 21 which is represented by 0b10101, the function will not find a path, although a valid path is given ('FFFFBFBFFF'):
- Advance 4 steps to 15
- Turn around, go back 1 step to 14
- Turn around again, take 3 steps to 14 7 = 21
Solution suggestion
This is a nice example of graph search problem. In a graph search problem you first need to define the states. The states in this problem are a tuples where each tuple consists of the sequence and the current location, i.e. (seq, current_loc). After defining the states, any graph search algorithm can solve your problem, where the two most prominent solutions will be the BFS and DFS. Since I wanted to get the path with the shortest amount of steps, I implemented BFS. Please find more information here.
The BFS solution is as follows:
import math
import collections
def findSeq(dist):
state_queue = collections.deque([]) # Pending states which have not been explored yet
upper_lim = 2**math.ceil(math.log2(dist))
state = ['', 0] # Starting state ; state is made out of the path at location [0], the 'B' count at location [1] and the distance at location [2]
found = True
while state[1] != dist:
# adding states to the queue according to conditions:
steps = len(state[0].split('B')[-1])
b_count = state[0].count('B')
if 0 <= state[1] < upper_lim: # advancing makes sense
state_1 = [state[0] 'F', state[1] ((-1)**b_count) * 2**steps]
state_queue.append(state_1)
if b_count < 3 and state[1] >= 0:
state_2 = [state[0] 'B', state[1]]
state_queue.append(state_2)
try:
state = state_queue.popleft()
except IndexError:
found = False
break
if found:
return state[0]
else:
return ''
Please note that this is not optimal since the states in the graph can be defined more efficiently, but this solves for all cases. In addition, the graph can be seen as a tree, meaning that you are not going back to the same state twice (in the current state definition) thus you do not need to keep a set of visited states.
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/446418.html
下一篇：A*實施