我们被困在两座山之间的河流中，我们的通信设备无法获得体面的信号，但不用担心
这很好！，如果我们只找到足够高的位置来发出信号
酷酷酷，毫无疑问，毫无疑问，毫无疑问，请保持乐观，不要惊慌！
目前对我们走的一件事是，我们从设备上有一个高度图，我们只需要到达Heighst Point并发送一个遇险信号
我们的地图看起来像这个
Sabqponm
abcryxxl
accszExk
acctuvwj
abdefghi
我们当前的位置标记为 s ，我们的目的地被标记为 e
我们还被告知每个位置的高度是每个字母的ASCII值
s = a 和 e = z
这闻起来像是图形问题...
解析
我们本可以按原样使用输入的结构，但我想使其更有意义，因此我们将其解析为点的矩阵！
首先，我们将创建一个新的Point struct
type Point struct {
i, j, v int
}
func (p *Point) id() string {
return fmt.Sprintf("(%d,%d)", p.i, p.j)
}
func newPoint(i, j, v int) *Point {
return &Point{i: i, j: j, v: v}
}
每个点位置都使用i和j保存，并且该值存储在v中。<br>
我们还创建了一个结构方法id，我们可能需要一段时间的时间
尽管我绝不是GO专家，但为结构提供新功能似乎是标准。可能是因为它的详细信息要少得多。
现在，让我们将输入矩阵更改为Points的矩阵
func createPoint(i, j int, r rune) *Point {
switch r {
case 'S':
return newPoint(i, j, 0)
case 'E':
return newPoint(i, j, int('z')-int('a'))
default:
return newPoint(i, j, int(r)-int('a'))
}
}
func parse(raw string) (matrix [][]*Point, start *Point, dest *Point) {
lines := strings.Split(string(raw), "\n")
matrix = make([][]*Point, len(lines))
for i := range matrix {
matrix[i] = make([]*Point, len(lines[0]))
rows := []*Point{}
for j, c := range lines[i] {
if c == 'S' {
start = createPoint(i, j, c)
}
if c == 'E' {
dest = createPoint(i, j, c)
}
rows = append(rows, createPoint(i, j, c))
}
matrix[i] = rows
}
return matrix, start, dest
}
我们要做的第一件事是在每个\n上分配我们的输入6
我们将分配每个“行”中的每一个以获取输入中的每个“单元”
对于每个单元格，我们将创建一个新点并将其推入当前行
最终，我们将获得点矩阵
第1部分
我们被要求从S到E，最少的步骤。
哦，为了确保我们在途中不会太累，我们只能从p1到p2，如果p2中的价值最多比p1中的值更高。
阅读第一行，“步骤最少”这是我们可以并且应该使用BFS
的死赠品由于我们需要一个Queue来轻松实现BF，并且没有任何内置的东西，因此我们需要先创建队列
创建一个名为well，queue的新软件包，并添加以下逻辑和struct
package queue
import "fmt"
type Queue[T comparable] struct {
items []T
}
// Enqueue - Adds an item T to the Q
func (q *Queue[T]) Enqueue(item T) {
q.items = append(q.items, item)
}
// Dequeue - Removes an element from the Q - FIFO
func (q *Queue[T]) Dequeue() T {
if q.IsEmpty() {
fmt.Println("Trying to Dequeue from an empty Queue")
}
firstItem := q.items[0]
q.items = q.items[1:]
return firstItem
}
func (q *Queue[T]) Peek() T {
return q.items[0]
}
func (q *Queue[T]) NumberOfItems() int {
return len(q.items)
}
func (q *Queue[T]) IsEmpty() bool {
return len(q.items) == 0
}
这里没有什么花哨的，只是您的常规Q ...
在我们的新队列中，我们可以开始实施BFS
BFS的要旨是
- 从节点x开始，然后将所有邻居推到“处理”队列
- 为了避免在该队列中重复，我们还将保持一组“可见”节点，因为我们将使用Abiaoqian的简单集
- 我们需要的最后一件事是跟踪我们如何到达每个节点，这意味着对于
p1，后者将其放入了当前处理的点的队列中。 让我们看一些代码
func BFS(graph [][]*Point, s *Point, destination *Point) int {
// Creating a Queue
Q := queue.Queue[*Point]{}
// Adding the start node to the Queue
Q.Enqueue(s)
// Keeping track of who got us into the Queue
backTrack := map[string]string{}
// Nodes we have seen
seen := set.NewSimpleSet[string]()
// Mark the starting node as seen to avoid pushing it into the Queue again
seen.Add(s.id())
// We keep going over the "graph" while there are nodes in the Queue
for !Q.IsEmpty() {
// The node we are currently processing
currentNode := Q.Dequeue()
if currentNode == destination {
// Yay we got to our destination, we can stop searching
break
}
// Get all valid neighbors from our current node
// we will go over the implementation of getting neighbors in a minute or two
neighbors := getNeighbors(graph, currentNode)
for _, v := range neighbors {
// For each neighbor, if we haven't seen it before, do the following
// 1. mark it as seen
// 2. mark the node that got to him i.e our currently processed node
// 3. push it to the Queue
if !seen.Has(v.id()) {
seen.Add(v.id())
backTrack[v.id()] = currentNode.id()
Q.Enqueue(v)
}
}
}
// go over the route to the destination node and count the number of steps it took us
return count(backTrack, destination.id())
}
// simple recursive function that uses the node id to jump from p1 to p2 where p2 is the node that got p1 into the Queue
func count(backTrack map[string]string, id string) int {
v, ok := backTrack[id]
if ok {
return 1 + count(backTrack, v)
}
return 0
}
func getNeighbors(graph [][]*Point, sink *Point) (neighbors []*Point) {
// moves represent our up, right, down, and left options
moves := [][]int{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}
for _, move := range moves {
// add the current move to the origin point
di, dj := move[0]+sink.i, move[1]+sink.j
// if the new indexes are inbound of our matrix/graph
if di >= 0 && di < len(graph) && dj >= 0 && dj < len(graph[0]) {
delta := graph[di][dj].v - sink.v
// We were also told in the question that we need to make sure we make moves of at most 1
if delta <= 1 {
neighbors = append(neighbors, graph[di][dj])
}
}
}
return neighbors
}
我尝试使一切都尽可能清楚，但是如果您正在努力挣扎，请在评论部分中打我
我们的最终解决方案看起来像这样
func Part1(raw string) int {
graph, start, dest := parse(raw)
steps := BFS(graph, start, dest)
return steps
}
第2部分
第2部分是事物变得有趣的地方，我们现在被要求找到通往我们目的地的最短路径，但是我们可以将地图中的每个a用作起始位置，而S7
我们可以在这里采取一种天真的方法，看看它是否有效，您问的天真方法是什么？
查找所有启动节点，从其中每个节点运行我们的BF，并跟踪最小值
这也意味着我们需要更改解析功能才能收集所有起点
// start is now an array of points
func parse2(raw string) (matrix [][]*Point, start []*Point, dest *Point) {
lines := strings.Split(string(raw), "\n")
matrix = make([][]*Point, len(lines))
for i := range matrix {
matrix[i] = make([]*Point, len(lines[0]))
rows := []*Point{}
for j, c := range lines[i] {
if c == 'S' || c == 'a' {
start = append(start, createPoint(i, j, c))
}
if c == 'E' {
dest = createPoint(i, j, c)
}
rows = append(rows, createPoint(i, j, c))
}
matrix[i] = rows
}
return matrix, start, dest
}
和我们第2部分的解决方案看起来像这样
func getMinValue(arr []int) (m int) {
for i, e := range arr {
if i == 0 || e < m && e != 0 {
m = e
}
}
return md
}
func Part2NaiveApproach(raw string) int {
graph, start, dest := parse2(raw)
steps := []int{}
for _, s := range start {
res := BFS(graph, s, dest)
if res > 0 {
steps = append(steps, res)
}
}
return getMinValue(steps)
}
这适用于问题输入，这使我感到惊讶，但要完成大约3秒钟，我们可以做得更好！
有一件事想到，为什么我们需要从每个节点中进行BF，我们不能将所有这些启动节点添加到我们的队列中，因为启动节点？
好吧，我们可以！它被称为multi-source BFS，
我碰巧从解决CSE的怪物问题give it a try中知道了这种方法。
在开始调整事物并尝试新方法之前，让我们写一些基准测试，以确保我们在做什么会产生影响。
func BenchmarkPart1(b *testing.B) {
input := util.ReadFile("./input.txt")
for n := 0; n < b.N; n++ {
Part1(input)
}
}
func BenchmarkPart2NaiveApproach(b *testing.B) {
input := util.ReadFile("./input.txt")
for n := 0; n < b.N; n++ {
Part2NaiveApproach(input)
}
}
运行go test bench=. -count 2
BenchmarkPart1-8 183 7225891 ns/op
BenchmarkPart1-8 182 7127653 ns/op
BenchmarkPart2NaiveApproach-8 1 1530454249 ns/op
BenchmarkPart2NaiveApproach-8 1 1476970916 ns/op
ophh ...我们的天真方法很慢。它只运行一个，然后拿走了大约1.53秒的1530454249ns
与我们的第1部分结果相比，这太糟糕了！
我们的多源BFS方法类似于我们的原始BFS，但前几行有变化
// s is now an array of starting points
func MultiSourceBFS(graph [][]*Point, s []*Point, destination *Point) int {
Q := queue.Queue[*Point]{}
seen := set.NewSimpleSet[string]()
// for each starting point push int into the Queue and mark it as seen
for _, v := range s {
Q.Enqueue(v)
seen.Add(v.id())
}
...
...
请参阅完整的代码here
让我们为我们的多源BFS方法写一个基准
func BenchmarkPart2MultiSourceBfs(b *testing.B) {
input := util.ReadFile("./input.txt")
// run the Fib function b.N times
for n := 0; n < b.N; n++ {
Part2MultiSourceBfs(input)
}
}
哇，有什么不同！我们的多源BFS运行〜205次，每次运行仅花了大约0.0058秒的~5841816ns！
大约快274倍！
BenchmarkPart1-8 184 7306437 ns/op
BenchmarkPart1-8 181 6429481 ns/op
BenchmarkPart2NaiveApproach-8 1 1475075477 ns/op
BenchmarkPart2NaiveApproach-8 1 1450753723 ns/op
BenchmarkPart2MultiSourceBfs-8 205 5841816 ns/op
BenchmarkPart2MultiSourceBfs-8 204 5818908 ns/op
所以我们有一个有趣的图形问题，我们已经看到了一些解决方法的方法，这真是一个有趣的一天！
希望您从这一天开始学到新的东西。
作为最后的音符，我会给大家一个问题，还有一种更好的方法来做我们刚刚做的事情吗？
我们可能可以更改逻辑并从其他节点开始，并以更有效的方式获得所需的答案？
如果您有任何想法，请在评论中告诉我：）
就是今天，明天见，
您可以找到完整的代码here
感谢您的阅读！